Sage and Elliptic Curves: P256 and secp256k1

Sage and Elliptic Curves: P256 and secp256k1

Our world of trust on the Internet is built on a foundation of elliptic curves. Two of the most important of these are NIST P-256 and secp256k1 (as used in Bitcoin, Ethereum and Tor). For this, we can use Sage to model our curves:

In this case, we have the NIST P-256 curve, and which has the form of:

and which is the mod of a prime number (p):

p=2²⁵⁶-2²²⁴+2¹⁹²+2⁹⁶-1

We also have a base point of (G) of:

48439561293906451759052585252797914202762949526041747995844080717082404635286,36134250956749795798585127919587881956611106672985015071877198253568414405109

In Sage, we can define the base point (gx, gy) and the order of the curve (n) with:

gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286L
gy = 36134250956749795798585127919587881956611106672985015071877198253568414405109L
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369L

Next we can define the curve (EC) and the base point (G) with:

p256 = 115792089210356248762697446949407573530086143415290314195533631308867097853951L

a256 = p256 - 3

b256 = 41058363725152142129326129780047268409114441015993725554835256314039467401291L

FF = GF(p256)
EC = EllipticCurve([FF(a256), FF(b256)])
EC.set_order(n)

# Base point 
G = EC(FF(gx), FF(gy))

and now we have the curve all set. If we have a private key of a, and a public key of A, we compute with:

A = a.G

and where a multiplies the base point (G) — and is basically G+G+..+G (a times). Let’s try for a=1, a=2 and a=3:

a=1
A=a*G
print (A)
(48439561293906451759052585252797914202762949526041747995844080717082404635286 : 36134250956749795798585127919587881956611106672985015071877198253568414405109 : 1)

a=2
A=a*G
print (A)
(56515219790691171413109057904011688695424810155802929973526481321309856242040 : 3377031843712258259223711451491452598088675519751548567112458094635497583569 : 1)

a=3
A=a*G
print (A)
(42877656971275811310262564894490210024759287182177196162425349131675946712428 : 61154801112014214504178281461992570017247172004704277041681093927569603776562 : 1)

This confirms with a bare-bones approach here. The full Sage code is now:

###### NIST P-256
p256 = 2^256-2^224+2^192+2^96-1
a256 = p256 - 3
b256 = 41058363725152142129326129780047268409114441015993725554835256314039467401291L

## Base point
gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286L
gy = 36134250956749795798585127919587881956611106672985015071877198253568414405109L

## Curve order
qq = 115792089210356248762697446949407573529996955224135760342422259061068512044369L
FF = GF(p256)
EC = EllipticCurve([FF(a256), FF(b256)])
EC.set_order(qq)

# Base point
G = EC(FF(gx), FF(gy))

## Alice's private key
a = 1
## Alice's public key
A = a*G
print (A)

secp256k1

An important curve that we use in Bitcoin, Ethereum and Tor is the secp256k1 curve. For this, we have new parameters, and where:

y² = x³ + 7 (mod p)

p = 2²⁵⁶-2³²-997

and the base point is (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424). This can be coded in Sage as:

###### secp256k1
p256 = 2^256-2^32-977
a256 = 0
b256 = 7

## Base point
gx= 55066263022277343669578718895168534326250603453777594175500187360389116729240L
gy= 32670510020758816978083085130507043184471273380659243275938904335757337482424L

## Curve order
n = 115792089237316195423570985008687907852837564279074904382605163141518161494337L

FF = GF(p256)
EC = EllipticCurve([FF(a256), FF(b256)])
EC.set_order(n)

# Base point
G = EC(FF(gx), FF(gy))

## Alice's private key
a = 1
## Alice's public key
A = a*G
print (A)

If we run, we get the values for 1G (just the base point), 2G and 3G:

a=1
A=a*G
print (A)
(55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)

a=2
A=a*G
print (A)
(89565891926547004231252920425935692360644145829622209833684329913297188986597 : 12158399299693830322967808612713398636155367887041628176798871954788371653930 : 1)

a=3
A=a*G
sage: print (A)
(112711660439710606056748659173929673102114977341539408544630613555209775888121 : 25583027980570883691656905877401976406448868254816295069919888960541586679410 : 1)

These points correspond to the points we get here.

Creating Alice’s wallet

Obviously Alice would not use a private key (a) of 1, 2 or 3, and will select a random number.

set_random_seed()
a=initial_seed()
A=a*G
print (f"Private key: {a}")
print (f"Public key: {A}")

This gives a run of:

Private key: 217257450721080989305651684948856497923
Public key: (50583223393827439972415863678913594639347143297941530817347167896458128718978 : 55659009629153860575299312057954698196529450916484391285648355389962854410941 : 1)

In this case, Alice’s private key is 217257450721080989305651684948856497923, and her public key is (50583223393827439972415863678913594639347143297941530817347167896458128718978, 55659009629153860575299312057954698196529450916484391285648355389962854410941).

Conclusions

Sage is such a cool system and allows us to layout out finite fields and do our elliptic curve calculations. If you want to install Sage, try here:

and the Sage coding is defined here:

https://asecuritysite.com/sage/sage02