Elliptic Curve Digital Signature Algorithm (ECDSA) supports the signing of data with Elliptic Curve methods. In this case we will perform the core operations in the signing and verification.
Elliptic Curve Digital Signature Algorithm (ECDSA) |
Theory
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.
(\(x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A} = h \cdot c \cdot G + r \cdot c \cdot Q_A = c (hG + rQ_A) = \frac{hG + rQ_A} {k^{-1}(h+rd_A) } = \frac{hG + rd_A G} {k^{-1}(h+rd_A) } = \frac{(h + rd_A) G} {k^{-1}(h+rd_A) } = kG \).
The following is an outline of the code:
import base64 import sys import random import hashlib import collections msg="Hello" 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 # Keypair generation and ECDSA ################################################ def make_keypair(): """Generates a random private-public key pair.""" private_key = random.randrange(1, curve.n) public_key = scalar_mult(private_key, curve.g) return private_key, public_key def sign(hash, random_k,secret): G = curve.g n = curve.n k = random_k % n p1 = scalar_mult(k, G) r = p1[0] if r == 0: raise RuntimeError("r is zero. Please repeat") s = (inverse_mod(k, n) * (hash + (secret * r) % n)) % n if s == 0: raise RuntimeError("r is zero. Please repeat") return r, s def verifies(hash, r,s,pub): G = curve.g n = curve.n if r < 1 or r > n - 1: return False if s < 1 or s > n - 1: return False c = inverse_mod(s, n) u1 = (hash * c) % n u2 = (r * c) % n xy = point_add(scalar_mult(u1,G) , scalar_mult(u2, pub)) v = xy[0] % n print("V=",v) return v == r def string_to_int(s): result = 0 for c in s: if not isinstance(c, int): c = ord(c) result = 256 * result + c return result n = curve.n hash= hashlib.sha256(msg.encode()).hexdigest() print("Message:\t",msg) print("N:\t",curve.n) print("G:\t",curve.g) print("Hash:\t",hash) privkey,pubkey = make_keypair() print("=====================") print("Private key:\t",privkey) print("Public key:\t",pubkey) hash = string_to_int(hash) print("=====================") signature = sign( hash, random.randrange( 1, n ),privkey ) print("R=",signature[0]) print("S=",signature[1]) ver=verifies( hash, signature[0],signature[1],pubkey) print("Verified:\t",ver)