Sage and ECDSA (secp256k1)
[ECDSA Home][Home]
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 secp256k1 curve (as used in Bitcoin and Ethereum).
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 sepc256k1 curve has the following parameters: \(p=2^{256}-2^{32}-2^{9} -2^{8} - 2^{7} - 2^{6} - 2^{4} - 1\) \(y=x^3+ 7 \pmod p \) \(n\) = 115792089237316195423570985008687907852837564279074904382605163141518161494337 \(G\)=(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) This is defined in Sage as: F = FiniteField(2**256-2**32-2**9 -2**8 - 2**7 - 2**6 - 2**4 - 1) a = 0 b = 7 E = EllipticCurve(F, [a, b]) G = E((55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)) n = 115792089237316195423570985008687907852837564279074904382605163141518161494337 h = 1 Fn = FiniteField(n) CodingThe following is the full Sage code: import hashlib F = FiniteField(2**256-2**32-2**9 -2**8 - 2**7 - 2**6 - 2**4 - 1) a = 0 b = 7 E = EllipticCurve(F, [a, b]) G = E((55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)) n = 115792089237316195423570985008687907852837564279074904382605163141518161494337 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: (56394942779607862671902771113493053889227027642429164839406567845097686294481, 10123591665485484354034593781289403370308696324767861261144856806186141135600) Private Key: 67186271637299976575892668135860412181299192243436928290686792367299723384748 === Signature === r = 52677608421642022653770692275361644896652519132647104503890511174101025685364 s = 106673964228295695493432918336277688668714483155543972841422517456598771482480 Verification: True and for another key pair and nonce: Message: My Message Public Key: (63315908534464214093482829201001909114501322225919677835861463521103763995319, 114620250423107263475204455149629217158038299771125949280273781975249928745094) Private Key: 91855495417553426403221784468898796362475884350911047240707014515565909159148 === Signature === r = 115271757414703320900728767899749804584436498657762482320183134659131051396998 s = 46837512581088998810617997252946743846223020591641575465933911624539451803417 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]. |