Recovering a public key from an ECDSA signature in Python[ECDSA Home][Home]
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. In this case, we will recover Alice's public key from the signature (\(r,s\)).
|
Theory
In ECDSA, Bob creates a random private key (\(x\)), and then a public key from:
\(pub= x.G\)
Next, in order to create a signature for a message of \(M\), he creates a random number (\(k\)) and generates the signature of:
\(R = k.G\)
\(s = k^{-1} (h+ r.x)\)
and where \(x\) is the private key and \(h=H(M)\) The signature is then \((R,s)\) and where \(r\) is the x-co-ordinate of the point \(kG\). \(h\) is the SHA-256 hash of the message (\(M\)), and converted into an integer value.
Now, we need to recover the public key from (\(R,s\)). For this we take:
\(R=k.G\)
and transform to give:
\(k=R.G^{-1}\)
Now, we take:
\(s = k^{-1}.(h+ r.x)\)
and substitute \(k\) to give:
\(s = R^{-1}.G. (h+ r.x)\)
\(s.R = G.(h+ r.x)\)
\(s.r.G = h.G + r.x.G\)
\(r.s.G = h.G+ r.x.G\)
And thus:
\(r.x.G = r.s.G - h.G\)
\(x.G = r^{-1}.(r.s.G - h.G)\)
And so we have found the public key:
\(pub = r^{-1}.(r.s.G - h.G)\)
As we can get two \(y\) co-ordinate points, we also get:
\(pub = r^{-1}.(h.G-r.s.G)\)
Both these points will have the same x-co-ordinate point, and which is equivalent of having \((x,y)\) and \((x,-y)\).
Coding
The coding becomes the operations of point addition, scalar multiplication, and in creating the negative of a point:
pub = scalar_mult(libnum.invmod(r,curve.n),(point_add(scalar_mult(s,rpoint),point_neg(scalar_mult(h,curve.g)))))
and which is translated to:
\(pub = r^{-1}.(r.s.G - h.G)\)
and which is:
\(pub = r^{-1}.(s.R - h.G)\)
With this, \(R\) is the value of \(r\) converted to a point (\(r.G\)). In this case \(G\) is the base point on the curve. We can code this with:
import sys import random import hashlib import libnum from secp256k1 import curve,scalar_mult,point_add,point_neg 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!") print("\n=== Now recovering Alice's public key ===") pub1 = scalar_mult(libnum.invmod(r,curve.n),(point_add(scalar_mult(s,rpoint),point_neg(scalar_mult(h,curve.g))))) pub2 = scalar_mult(libnum.invmod(r,curve.n),(point_add(point_neg(scalar_mult(s,rpoint)),scalar_mult(h,curve.g)))) print(f"\nAlice's public key is one of the these:\n{pub1}\n{pub2}") if (pub1[0]==QA[0]): print("Key recovered")
And a sample run:
Msg: Hello Alice's private key=51807341738254329389736646254693242327142174011095991939024161233563883052655 Alice's public key=(29536825323447158318398958334778222234623534948898819523892551224271187751503, 100617733002231258870267900359120638387481820412279399098395797030288659404861) k= 78239816292540973623348822290723524828665027578289616038455379559013972694565 r=91457593152987843762518269128415380901655617003136377539774416188614535938789 s=94829889541214320331845482826979126529774337950845442366439736640766059212081 Result r=91457593152987843762518269128415380901655617003136377539774416188614535938789 Signature matches! === Now recovering Alice's public key === Alice's public key is one of the these: (29536825323447158318398958334778222234623534948898819523892551224271187751503, 100617733002231258870267900359120638387481820412279399098395797030288659404861) (29536825323447158318398958334778222234623534948898819523892551224271187751503, 15174356235084936553303084649567269465788164253361164941061786977620175266802) Key recovered
Presentation
Reference
The code used for secp256k1.py is:
# Code from: https://github.com/andreacorbellini/ecc/blob/master/scripts/ecdhe.py import collections EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h') curve = EllipticCurve( 'secp256k1', # Field characteristic. p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f, # Curve coefficients. a=0, b=7, # Base point. g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8), # Subgroup order. n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141, # Subgroup cofactor. h=1, ) # Modular arithmetic ########################################################## def inverse_mod(k, p): """Returns the inverse of k modulo p. This function returns the only integer x such that (x * k) % p == 1. k must be non-zero and p must be a prime. """ if k == 0: raise ZeroDivisionError('division by zero') if k < 0: # k ** -1 = p - (-k) ** -1 (mod p) return p - inverse_mod(-k, p) # Extended Euclidean algorithm. s, old_s = 0, 1 t, old_t = 1, 0 r, old_r = p, k while r != 0: quotient = old_r // r old_r, r = r, old_r - quotient * r old_s, s = s, old_s - quotient * s old_t, t = t, old_t - quotient * t gcd, x, y = old_r, old_s, old_t assert gcd == 1 assert (k * x) % p == 1 return x % p # Functions that work on curve points ######################################### def is_on_curve(point): """Returns True if the given point lies on the elliptic curve.""" if point is None: # None represents the point at infinity. return True x, y = point return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0 def point_add(point1, point2): """Returns the result of point1 + point2 according to the group law.""" assert is_on_curve(point1) assert is_on_curve(point2) if point1 is None: # 0 + point2 = point2 return point2 if point2 is None: # point1 + 0 = point1 return point1 x1, y1 = point1 x2, y2 = point2 if x1 == x2 and y1 != y2: # point1 + (-point1) = 0 return None if x1 == x2: # This is the case point1 == point2. m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p) else: # This is the case point1 != point2. m = (y1 - y2) * inverse_mod(x1 - x2, curve.p) x3 = m * m - x1 - x2 y3 = y1 + m * (x3 - x1) result = (x3 % curve.p, -y3 % curve.p) assert is_on_curve(result) return result def scalar_mult(k, point): """Returns k * point computed using the double and point_add algorithm.""" assert is_on_curve(point) if k % curve.n == 0 or point is None: return None if k < 0: # k * point = -k * (-point) return scalar_mult(-k, point_neg(point)) result = None addend = point while k: if k & 1: # Add. result = point_add(result, addend) # Double. addend = point_add(addend, addend) k >>= 1 assert is_on_curve(result) return result def point_neg(point): """Returns -point.""" assert is_on_curve(point) if point is None: # -0 = 0 return None x, y = point result = (x, -y % curve.p) assert is_on_curve(result) return result