Ask Your Question
0

computing order of elliptic curves over binary field

asked 2012-04-24 04:15:06 -0600

twoforone gravatar image

updated 2015-01-18 04:26:06 -0600

FrédéricC gravatar image

Do you have any information on how to compute order of elliptic curves over binary field in SAGE mathematics software? Example: I have the following domain parameters which are taken from

p = 0800000000000000000000000000000000000000C9
a = 07B6882CAAEFA84F9554FF8428BD88E246D2782AE2
b = 0713612DCDDCB40AAB946BDA29CA91F73AF958AFD9       
x = 0369979697AB43897789566789567F787A7876A654     
y = 00435EDB42EFAFB2989D51FEFCE3C80988F41FF883

The problem I am facing is to to know the order of this elliptic curve? I ahve got on the net that it is possible to compute using this library sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari and it takes these parameters properly with out any error. But there is error while requesting the order of that parameter.

This was what I deed in sage:

FF = sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari;
order = 2**163;
c = 07B6882CAAEFA84F9554FF8428BD88E246D2782AE2;
b = 0713612DCDDCB40AAB946BDA29CA91F73AF958AFD9
K.<x>= GF(2)[];
K.<k> = FF(order, 'a', modulus = x^163 + x^7 + x^6 + x^3 + 1)[];
K163_curve = EllipticCurve(K,[1,c,0,0,b]);K163_curve
edit retag flag offensive close merge delete

Comments

Our free book http://software.intel.com/en-us/articles/ipp-crypto-guide/ pages 264,265 contains some computations in C/C++ with "your" curve, including the order. We were not able to compute the order in Sage

achrzesz gravatar imageachrzesz ( 2012-04-25 19:14:26 -0600 )edit

1 answer

Sort by » oldest newest most voted
1

answered 2017-03-25 13:06:33 -0600

dan_fulea gravatar image

updated 2017-03-25 13:13:00 -0600

The order of the curve is: $$ 2\cdot 5846006549323611672814738465098798981304420411291\ . $$ (The second factor is a prime.) Source:

Intel(R) Integrated Performance Primitives, Cryptography Guide, IPP 7.1, Andrzej Chrzeszczyk, Jakub Chrzeszczyk, September, 2012, page 214.

https://software.intel.com/sites/default/files/article/181895/intelcrypt710.pdf

(One has to read between the lines.)

The above source / link in the comments is no longer available.

Sage could in my hands with the present libraries not proceed with the search. (It was even hard to kill the sage process, no chance to access mouse and keyboard after some minutes. It took all resources on the machine.)

Here is the code that only verifies the order.

P  = 0x0800000000000000000000000000000000000000C9
c  = 0x07B6882CAAEFA84F9554FF8428BD88E246D2782AE2
b  = 0x0713612DCDDCB40AAB946BDA29CA91F73AF958AFD9       
x0 = 0x0369979697AB43897789566789567F787A7876A654     
y0 = 0x00435EDB42EFAFB2989D51FEFCE3C80988F41FF883

R.<X> = PolynomialRing( GF(2) )
modulus = R( P.digits(2) )

q = 2 ** 163
F = GF( q, modulus=modulus, name='x' )
E = EllipticCurve( F, [ 1, F(c.digits(2)), 0, 0, F(b.digits(2)) ] )

POINT = E.point( ( F(x0.digits(2)), F(y0.digits(2)) ) )
PRIME = 5846006549323611672814738465098798981304420411291

print "Is   PRIME * POINT == 0? %s" % ( (   PRIME * POINT ).is_zero() )
print "Is 2*PRIME * POINT == 0? %s" % ( ( 2*PRIME * POINT ).is_zero() )


print "The value 2*PRIME is in hex between the Hasse bounds as follows:" 
print "%s :: hex of ceil  of q + 1 - 2 sqrt(q)" % hex(  ceil( q + 1 - 2*sqrt(q) ) )
print "%s :: hex of 2*PRIME = order of ( E( GF(q) ), + )" % hex( 2*PRIME )
print "%s :: hex of floor of q + 1 + 2 sqrt(q)" % hex( floor( q + 1 + 2*sqrt(q) ) )

And we get:

Is   PRIME * POINT == 0? True
Is 2*PRIME * POINT == 0? True
The value 2*PRIME is in hex between the Hasse bounds as follows:
7fffffffffffffffffffa57d86660310cdbdd3415 :: hex of ceil  of q + 1 - 2 sqrt(q)
7fffffffffffffffffffe91556d1385394e204f36 :: hex of 2*PRIME = order of ( E( GF(q) ), + )
800000000000000000005a827999fcef32422cbed :: hex of floor of q + 1 + 2 sqrt(q)
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2012-04-24 04:15:06 -0600

Seen: 864 times

Last updated: Mar 25