NIST B-283 Elliptic Curve

asked 2012-02-23 22:28:29 +0100

MichaelJ
1 ●1 ●2 ●1

updated 2015-01-13 21:35:04 +0100

FrédéricC

5206 ●3 ●43 ●114

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.

edit retag flag offensive close merge delete

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 ( 2012-02-23 23:16:01 +0100 )edit

add a comment

0

answered 2012-04-26 10:21:22 +0100

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?

edit flag offensive delete 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 ( 2017-07-27 13:12:13 +0100 )edit

add a comment

0

answered 2012-02-24 16:27:09 +0100

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.

edit flag offensive delete 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 ( 2012-02-24 21:38:43 +0100 )edit

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

MichaelJ ( 2012-02-27 21:35:12 +0100 )edit

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 ( 2012-02-27 21:45:10 +0100 )edit

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 ( 2017-07-27 13:19:06 +0100 )edit

add a comment

0

answered 2012-05-03 07:41:06 +0100

twoforone
31 ●2 ●3 ●6

updated 2012-05-03 07:43:10 +0100

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

edit flag offensive delete link

add a comment

0

answered 2012-04-26 15:59:18 +0100

achrzesz
2768 ●5 ●25 ●60

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

edit flag offensive delete link

Comments

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

achrzesz ( 2012-04-27 02:31:19 +0100 )edit

add a comment

0

answered 2012-04-26 17:58:32 +0100

achrzesz
2768 ●5 ●25 ●60

    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

edit flag offensive delete link

Comments

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

achrzesz ( 2012-04-26 19:49:46 +0100 )edit

add a comment

NIST B-283 Elliptic Curve

Comments

5 Answers

Comments

Comments

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

NIST B-283 Elliptic Curve edit

Comments

5 Answers

Comments

Comments

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

NIST B-283 Elliptic Curve