Elliptic Curve Digital Signature Algorithm (ECDSA) supports the signing of data with Elliptic Curve methods. Basically we take a message (\(m\)) and create a hash (\(h\)). Alice will have a key pair of \( (d_A,Q_A)\), and where \(Q_A = d_A G\), and \(d_A\) is her private key. To sign a message, Alice generates a random value (\(k\)) and then calculates \(r=k \cdot G\) and where \(G\) is the base point on the secp256k1 curve (and where \(r\) is the x-point of the result. She will then compute \(s=k^{-1}(h+r \cdot d_A) \pmod N\), and where \(N\) is the order of the curve. Alice sends the value of \((r,s)\) as the signature. Bob then checks by taking a hash of the mesasge (\(h\)) and \(c=s^{-1} \pmod N\), and then \(u_1=h \cdot c \pmod N\) and \(u_2=r \cdot c \pmod N\). He will then do a point add to determine \(P=u_1 \cdot G + u_2 \cdot Q_A\). Bob then takes the x-co-ordinate of \(P\) \(\pmod N\) and compares this against \(r\). If they match, the signature is correct.
ECDSA Signing in 12 lines of Python |
Theory
The following is an outline of ECDSA. With this, Bob signs a hash of a message with his private key, and then then Alice proves with his public key. Bob also uses a random nonce value for the signature (\(k\)):
With ECDSA, Alice will sign a message with her private key, and then Bob will use her public key to verify that she signed the message (and that the message has now changed):
Alice signs the message with the following:
- Create a hash of the message \(e=\textrm{HASH}(m)\).
- Let \(h\) be the \(L_{n}\) be the leftmost bits of \(e\), \(L_{n}\) has a bit length of the group order \(N\).
- Create a random number \(k\) which is between 1 and \(N-1\).
- Calculate a point on the curve as \((x_{1},y_{1})=k\times G\).
- Calculate \( r=x_{1} \pmod N \). If \(r=0\), go back to Step 3.
- Calculate \(s=k^{-1}(h+rd_{A}) \pmod N\). If \(s=0\), go back to Step 3.
- The signature is the pair \((r,s)\).
Bob will check with:
- Create a hash of the message \(e=\textrm{HASH}(m)\).
- Let \(h\) be the \(L_{n}\) leftmost bits of \(e\).
- Calculate \(c=s^{-1} \pmod N\)
- Calculate \(u_{1}=h \cdot c \pmod N\) and \(u_{2}=r \cdot c \pmod N\).
- Calculate the curve point (\(x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}\). If \((x_{1},y_{1})=O\) then the signature is invalid.
- The signature is valid if \(r\equiv x_{1}{\pmod {n}}\), invalid otherwise.
The following is an outline of the code:
import sys import random import hashlib import libnum from secp256k1 import curve,scalar_mult,point_add msg="Hello" if (len(sys.argv)>1): msg=(sys.argv[1]) # Alice's key pair (dA,QA) dA = random.randint(0, curve.n-1) QA = scalar_mult(dA,curve.g) h=int(hashlib.sha256(msg.encode()).hexdigest(),16) k = random.randint(0, curve.n-1) rpoint = scalar_mult(k,curve.g) r = rpoint[0] % curve.n # Bob takes m and (r,s) and checks inv_k = libnum.invmod(k,curve.n) s = (inv_k*(h+r*dA)) % curve.n print (f"Msg: {msg}\n\nAlice's private key={dA}\nAlice's public key={QA}\nk= {k}\n\nr={r}\ns={s}") # To check signature inv_s = libnum.invmod(s,curve.n) c = inv_s u1=(h*c) % curve.n u2=(r*c) % curve.n P = point_add(scalar_mult(u1,curve.g), scalar_mult(u2,QA)) res = P[0] % curve.n print (f"\nResult r={res}") if (res==r): print("Signature matches!")
And a sample run:
Msg: Hello123 Alice's private key=59415685509516291732623466804953470944903908623780094388038002011461202208070 Alice's public key=(24554141300969450064163263426844888628802498988426591124072119496449289448505, 114359388960404339679375420973260643085090792950846610450698101016317921839644) k= 626370194392365919645426225410460629018059338503019940991523460332833854777 r=49777266633806946836633548434487737353728205925599644723795061274162419287834 s=79380768682391122524878065479189865213298432507682482439352705536832774411973 Result r=49777266633806946836633548434487737353728205925599644723795061274162419287834 Signature matches!