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\). Ben 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 use Shamir's Secret Share (SSS) and where we share the ECDSA signature with \(n\) hosts, and where we need \(k\) hosts to recover the signature.
ECDSA Signing with Secret Shares |
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.
The following is an outline of the code:
import sys import random import hashlib import libnum import tss from tss import share_secret, Hash import base64 from secp256k1 import curve,scalar_mult,point_add msg="Hello" thres=3 n_shares=6 if (len(sys.argv)>1): msg=(sys.argv[1]) if (len(sys.argv)>2): thres=int(sys.argv[2]) if (len(sys.argv)>3): shares=int(sys.argv[3]) # 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!") ## The signature is (r,s). For shares - we only do for r here secret=r shares = tss.share_secret(thres, n_shares, secret, 'my-id', Hash.NONE) print ("Using t shares") reconstructed_secret = tss.reconstruct_secret(shares[0:thres]) print ("Secret:\t",secret) print ("===Shares (showing a few - and first 80 chars)===") for x in range (0,thres): print (base64.b64encode(shares[x])[:80]) print ("\nReconstructed:\t",reconstructed_secret.decode()) print ("\nNow sharing s") secret=s shares = tss.share_secret(thres, n_shares, secret, 'my-id', Hash.NONE) reconstructed_secret = tss.reconstruct_secret(shares[0:thres]) print ("Secret:\t",secret) print ("===Shares (showing a few - and first 80 chars)===") for x in range (0,thres): print (base64.b64encode(shares[x])[:80]) print ("\nReconstructed:\t",reconstructed_secret.decode())
And a sample run:
Msg: Hello Alice's private key=38384043304725281613780123878815242377931520211045394797991561882067402490908 Alice's public key=(43178831897470460595973877304239671785472952822380553016715299503147342643404, 106712441329013076595649553283608671128133986074474669508228197275022478425027) k= 9745783230872244706041587530885545208594534789477545477353642567669070352969 r=105185324626571473303296183506689072765133071973696325484845674613221176963005 s=95474866890307418299520003270644785286573079260464920699034962983524611552596 Result r=105185324626571473303296183506689072765133071973696325484845674613221176963005 Signature matches! Using t shares Secret: 105185324626571473303296183506689072765133071973696325484845674613221176963005 ===Shares (showing a few - and first 80 chars)=== b'bXktaWQAAAAAAAAAAAAAAAADAE8BbPLWmUsLg46yExdPQllCj9t5wH6g5qHZS+3JTzAY1KwxeC8Q0ok+' b'bXktaWQAAAAAAAAAAAAAAAADAE8Ckck3YxHhreI1W+JPtlSk4s8erKdLh7ObxIF0OrDQDEStFAkIiBUj' b'bXktaWQAAAAAAAAAAAAAAAADAE8DzAvUy2LfHV6zfsc2wTrXWSNUX+nYUyt0vlSOQLD+7tClXBEqbaoo' Reconstructed: 105185324626571473303296183506689072765133071973696325484845674613221176963005 Now sharing s Secret: 95474866890307418299520003270644785286573079260464920699034962983524611552596 ===Shares (showing a few - and first 80 chars)=== b'bXktaWQAAAAAAAAAAAAAAAADAE4B21wIMPbC7swYZxUmFe/wqv3g8+GlPqJtXbBQ5ttrq2vqR16FYLDm' b'bXktaWQAAAAAAAAAAAAAAAADAE4C6tiVTuK/zxig8eFNyflQhNWKeKQUnAzHCx8xllASpQGjLQzrDk4Y' b'bXktaWQAAAAAAAAAAAAAAAADAE4DCLGpSSBFF+KAr8RY7CGUHxBYsnyEkJ6aZpxTR7tPOl5+UmdcVsjL' Reconstructed: 95474866890307418299520003270644785286573079260464920699034962983524611552596