NIST B-283 Elliptic Curve

0

asked 13 years ago

MichaelJ
1 ●1 ●2 ●1

updated 10 years ago

FrédéricC

5426 ●4 ●44 ●121

I'm new to Sage so forgive me if this is simple. I am trying to define the NIST B-283 elliptic curve as follows:

def B283_test():
  order = 2**283
  a = 1
  b = 0x027B680AC8B8596DA5A4AF8A19A0303FCA97FD7645309FA2A581485AF6263E313B79A2F5
  K.<x>= GF(2)[]
  K.<a> = GF(order=order, name='a', modulus=x^283 + x^12 + x^7 + x^5 + 1 )
  B283_curve = EllipticCurve(K, [1,a,0,0,b])

I get a fairly long traceback after the last line followed by:

OverflowError: long int too large to convert to int

Any help is appreciated.

Comments

Hmm. Looks like something is wrong with GF at large order. Does using `FF = sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari; `K. = FF(order, 'a', modulus=x^283 + x^12 + x^7 + x^5 + 1 )[]` help any? [This changes the backend.]

DSM ( 13 years ago )

add a comment

0

answered 12 years ago

twoforone
31 ●2 ●3 ●6

I want to know the order of the curve that have been built above i.e K283_curve.order(). Is there a way to know the order of that curve and in that how could I generate a random point which is element of that curve? this works fine FF = sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari;K. = FF(order, 'a', modulus=x^283 + x^12 + x^7 + x^5 + 1 )[]

How could I get its order? In that, how could I find a random point of that curve?

link

Comments

The following code constructs the Koblitz curve of MichaelJs answer. There is no relation to the posted B283.

R.<x>= GF(2)[]
K.<a> = GF( 2**283, modulus = x^283 + x^12 + x^7 + x^5 + 1 )
K283 = EllipticCurve( K, [1,0,0,0,1] )

The order is known: $2^k+1-(w^k+\bar w^k)\ , \ w=\frac 12(-1+\sqrt{-7})\ ,\ k=283\ .$ We compute it:

KK.<u> = QuadraticField( -7 )
ord = ZZ( 2^k + 1 - ( w^k + w.conjugate()^k ) ) 
print "The order of the Koblitz curve K283 is theoretically (hex):\n%s" % hex(ord)
print "It factorizes as:\n%s" % ZZ(ord).factor()

and get

The order of the Koblitz curve K283 is theoretically (hex):
7ffffffffffffffffffffffffffffffffffa6b8bb41d5dc9977fdfe511478187858f184

Then one repeats:

P = K283.random_point(); ord*P; ZZ(ord/2)*P

dan_fulea ( 7 years ago )

add a comment

0

answered 13 years ago

MichaelJ
1 ●1 ●2 ●1

Thanks DSM. I no longer get the overflow. For what it's worth the K283 curve seems to work and the only real differences are the a and b invariants:

def K283_test():
  order = 2**283
  a = 0
  b = 1
  K.<x>= GF(2)[]
  K.<a> = GF(order=order, name='a', modulus=x^283 + x^12 + x^7 + x^5 + 1  )
  K283_curve = EllipticCurve(K, [1,a,0,0,b])

no overflow... I think it's related to the b parameter.

link

Comments

It's related to b as a number, but not to anything EllipticCurve-related. Simply try `GF(2**283,'a')(2**64)`, which fails too.

DSM ( 13 years ago )

When I use sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari

MichaelJ ( 13 years ago )

When I use sage.rings.finite_rings.finite_field_ext_pari.FiniteField_ext_pari, I get different methods in the Class EllipticCurve and some I would like aren't there (like random_point). Any recommendations on how to handle this other than (attempting to) write these myself?

MichaelJ ( 13 years ago )

This is one of the two Koblitz curves, already defined over $\mathbb F_2$ , considered then over the bigger field. It has predicted order, and the given curve in the post has nothing to do with the Koblitz curve. There are a plenty of realizable orders of elliptic curves in the Hasse interval around $q+1$ , $q=2^{283}$ , and the post wants information about a specific one...

dan_fulea ( 7 years ago )

add a comment

0

answered 12 years ago

twoforone
31 ●2 ●3 ●6

updated 12 years ago

Please, help to compute order of the above elliptic curve E using SAGE and libraries in sage?

link

add a comment

0

answered 12 years ago

achrzesz
2803 ●5 ●25 ●61

b =  0x027B680AC8B8596DA5A4AF8A19A0303FCA97FD7645309FA2A581485AF6263E313B79A2F5
Z.<x>=GF(2)[]
K.<a>=GF(2^283,'a',modulus=x^283 + x^12 + x^7 + x^5 + 1)
bb=Z(b.digits(2))
E=EllipticCurve(K,[1,1,0,0,bb]) 
P=E.random_element()
print P[0]
print P[1]
print E.is_on_curve(P[0],P[1])  # OK

# I was not able  to compute the order
# print E.order()   exhausts memory and exits

link

Comments

hex representation of P[0]: w=P[0] v=w.polynomial('a') print hex(v.change_ring(ZZ)(2))

achrzesz ( 12 years ago )

add a comment

0

answered 12 years ago

achrzesz
2803 ●5 ●25 ●61

    b =  0x027B680AC8B8596DA5A4AF8A19A0303FCA97FD7645309FA2A581485AF6263E313B79A2F5
    Z.<x>=GF(2)[]
    K.<a>=GF(2^283,'a',modulus=x^283 + x^12 + x^7 + x^5 + 1)
    bb=Z(b.digits(2))
    E=EllipticCurve(K,[1,1,0,0,bb]) 
    x=0x5f939258db7dd90e1934f8c70b0dfec2eed25b8557eac9c80e2e198f8cdbecd86b12053
    y=0x3676854fe24141cb98fe6d4b20d02b4516ff702350eddb0826779c813f0df45be8112f4
n=7770675568902916283677847627294075626569625924376904889109196526770044277787378692871
    xx=Z(x.digits(2))
    yy=Z(y.digits(2))
    PP=E(xx,yy)
    print E.is_on_curve(PP[0],PP[1])
    print n*PP
    #True
    #(0 : 1 : 0)     -->   n is equal to the order of PP

link

Comments

n can be computed for example using schoof2 program from Miracl library The curve order is 2n

achrzesz ( 12 years ago )

add a comment

Comments

5 Answers

Comments

Comments

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

NIST B-283 Elliptic Curve savecancel

Comments

5 Answers

Comments

Comments

Comments

Comments