Elliptic Curve Digital Signature Algorithm (ECDSA) supports the signing of data with Elliptic Curve methods using P256. In this case we will perform the core operations in the signing and verification. With this we calculate the hash of the message (\(h\)) and have a public key (\(Q_A\)) and a private key (\(d_A\)). We then generate a signature of (\(r,s\)) using a random value of \(k\). The public key (\(Q_A\)) and (\(r,s\)) is then used to check the signature.
Elliptic Curve Digital Signature Algorithm (ECDSA) using P256 |
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 c G + r c 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 sys import random import hashlib import libnum from p256 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 the ECC code is:
import collections EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h') p1=2**256 - 2**224 + 2**192 + 2**96 - 1 curve = EllipticCurve( 'P-256', # Field characteristic. p=p1, # Curve coefficients. a=-3, b=41058363725152142129326129780047268409114441015993725554835256314039467401291, # Base point. g=(48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109), # Subgroup order. n=0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551, # 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
A sample run is:
Msg: Hello Alice's private key=22468753113466412389710863294612970851209228875218569670766961707508540858284 Alice's public key=(85422671189782301797434271396355494291179242211206497433802334721389971017367, 105995302353017086107493930567745454722682777051303532097732095982586303560835) k= 29395472882301882870549721348596199883652078683057352874239805297954535507874 r=74752318095367749748269803644750676659622275439402632454862292269623634486476 s=2326953324292898993111312867614334167074890030238022438244433061804356758152 Result r=74752318095367749748269803644750676659622275439402632454862292269623634486476 Signature matches!