Sage and Elliptic Curves ( NIST P-256 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: NIST P256In this case, we have the NIST P-256 curve, and which has the form of: \(y^2 = x^3 -3x + 41058363725152142129326129780047268409114441015993725554835256314039467401291 \pmod p\) and which is the mod of a prime number (\(p\)): \(p=2^{256}-2^{224}+2^{192}+2^{96}-1\) We also have a base point of (\(G\)) of: 48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109 In Sage, we can define the base point (\(G_x, G_y\)) 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 = 2^256-2^224+2^192+2^96-1 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 n = 115792089210356248762697446949407573529996955224135760342422259061068512044369L 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) secp256k1An important curve that we use in Bitcoin, Ethereum and Tor is the secp256k1 curve. For this, we have new parameters, and where: \(y^2 = x^3 + 7 \pmod p\) \(p = 2^{256}-2^{32}-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 walletObviously 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). |