Sage and ECDSA (P256)ECDSA [1] is used in Bitcoin and Ethereum, and creates a signature (\(r,s\)) for a message (\(m\)). This involves creating a key pair. The private key is \(d\) and the public key is \(Q=d.G\), and where \(G\) is the base point on the curve. The private key is used to sign the message, and the public key will prove that the private key signed it. In this case we will use the NIST defined P256 curve. Creating key pairWith our curve, we have a generator point of \(G\) and an order \(n\). We start by generating a private key (\(d\)) and then generate the public key of: \(Q=d.G\) The public key is a point on the curve, and where it is derived from adding the point \G\), \(d\) times. Signing the messageWith a message (\(m\)), we aim to apply the private key, and then create a signature (\(r,s\)). First we create a random nonce value (\(k\)) and then determine the point: \(P=k.G\) Next we compute the x-axis point of this point: \(r=P_x \pmod n \) This gives us the \(r\) value of the signature. Next, we take the hash value of the message: \(e=H(m)\) And then compute the \(s\) value as: \(s=k^{-1}.(e + d.r) \pmod n\) The signature is (\(r,s\)). This can be coded with: def ecdsa_sign(d, m): r = 0 s = 0 while s == 0: k = 1 while r == 0: k = randint(1, n - 1) Q = k * G (x1, y1) = Q.xy() r = Fn(x1) e = hashit(m) s = Fn(k) ^ (-1) * (e + d * r) return [r, s] Verifying the signatureWe can verify by taking the message (\(m\), the signature (\(r,s\)) and the public key (\(Q\)): \(e=H(m)\) Next we compute: \(w =s^{-1} \pmod n\) \(u_1 = e.w\) \(u_2 = r.w\) We then compute the point: \(X = u_1.G + u_2.Q \) And then take the x-co-ordinate of \(X\): \(x = X_x \pmod n\) If \(x\) is equal to \(r\), the signature has been verified. In Sage, this can be implemented as: def ecdsa_verify(Q, m, r, s): e = hashit(m) w = s ^ (-1) u1 = (e * w) u2 = (r * w) P1 = Integer(u1) * G P2 = Integer(u2) * Q X = P1 + P2 (x, y) = X.xy() v = Fn(x) return v == r P256 curveThe NIST P256 curve has the following parameters: \(p=2^{256}-2^{224}+2^{192}+2^{96}-1\) \(y=x^3-3x+ 41058363725152142129326129780047268409114441015993725554835256314039467401291 \pmod p \) \(n\) = 115792089210356248762697446949407573529996955224135760342422259061068512044369 \(G\)=(48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109) This is defined in Sage as: F = FiniteField(2**256-2**224+2**192+2**96-1) a = -3 b = 41058363725152142129326129780047268409114441015993725554835256314039467401291 E = EllipticCurve(F, [a, b]) G = E((48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109)) n = 115792089210356248762697446949407573529996955224135760342422259061068512044369L h = 1 Fn = FiniteField(n) CodingThe following is the full Sage code: import hashlib F = FiniteField(2**256-2**224+2**192+2**96-1) a = -3 b = 41058363725152142129326129780047268409114441015993725554835256314039467401291 E = EllipticCurve(F, [a, b]) G = E((48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109)) n = 115792089210356248762697446949407573529996955224135760342422259061068512044369L h = 1 Fn = FiniteField(n) def hashit(msg): return Integer('0x' + hashlib.sha256(msg.encode()).hexdigest()) def keygen(): d = randint(1, n - 1) Q = d * G return (Q, d) def ecdsa_sign(d, m): r = 0 s = 0 while s == 0: k = 1 while r == 0: k = randint(1, n - 1) Q = k * G (x1, y1) = Q.xy() r = Fn(x1) e = hashit(m) s = Fn(k) ^ (-1) * (e + d * r) return [r, s] def ecdsa_verify(Q, m, r, s): e = hashit(m) w = s ^ (-1) u1 = (e * w) u2 = (r * w) P1 = Integer(u1) * G P2 = Integer(u2) * Q X = P1 + P2 (x, y) = X.xy() v = Fn(x) return v == r (Q, d) = keygen() m = 'My Message' [r, s] = ecdsa_sign(d, m) result = ecdsa_verify(Q, m, r, s) print (f"Message: {m}") print (f"Public Key: {Q.xy()}") print (f"Private Key: {d}") print ("=== Signature ===") print (f" r = {r}") print (f" s = {s}") print (f"Verification: {result}") A sample run shows the verification: Message: My Message Public Key: (40005503892534932482199246625575925713741123460980122908032941096322558301572, 17942555816247406046761294810756717289964959818026620401700982523997926577296) Private Key: 28719108332361337064869555726249980772469823436921824837929439156718876305649 === Signature === r = 54996503181899996898543967404284217445995044815819121691785498803699354157480 s = 36878016288479143284818725426650120369180133193163060702010837351814638940549 Verification: True and for another key pair and nonce: Message: My Message Public Key: (105515299804995824881494484568224519711483350031395010021856487287751088522361, 15535487501550379145598692266765826008594388436049461921657681152631554031470) Private Key: 41502546889623149599894237915572731636210952669622773866405864537319376178842 === Signature === r = 87945218934224689456649252667135603931839948809402338187787503213159245897299 s = 84724878870878312214159613324322590351606811105567182620170101219725344765396 Verification: True References[1] Johnson, D., Menezes, A., & Vanstone, S. (2001). The elliptic curve digital signature algorithm (ECDSA). International journal of information security, 1(1), 36–63 [here]. |