Secret Sharing of ECDSA

Secret Sharing of ECDSA

The ECDSA signature method is used to sign a message with a private key. So rather than sharing the signature, could we give a share of the signature to a number of nodes, and who must come together to share the signature. We will only be able to recover it if enough hosts come together to share their shares. In this case, we will use Shamir Secret Shares (SSS) for which we have n shares, and where we can recover the share using t nodes:

For ECDSA, Alice signs the message with the following:

1. Create a hash of the message e=HASH(m).
2. Let h be the Ln be the leftmost bits of e, Ln has a bit length of the group order N.
3. Create a random number k which is between 1 and N−1.
4. Calculate a point on the curve as (x_1,y_1)=k×G
5. Calculate r=x_1(modN)
6. If r=0, go back to Step 3.
7. Calculate s=k^{−1}(h+rdA)(modN).
8. If s=0, go back to Step 3.
9. The signature is the pair (r,s)

Bob will check with:

1. Create a hash of the message e=HASH(m).
2. Let h be the Ln leftmost bits of e.
3. Calculate c=s^{−1}(modN)
4. Calculate u1=h⋅c(modN) and u2=r⋅c(modN).
5. Calculate the curve point (x1,y1)=u1×G+u2×QA
6. If (x1,y1)=0 then the signature is invalid.
7. The signature is valid if r≡x1(modn) , invalid otherwise.

The following is an outline of the code [here]:

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===")
for x in range (0,thres):   
    print (base64.b64encode(shares[x]))

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)===")
for x in range (0,thres):   
    print (base64.b64encode(shares[x]))

print ("\nReconstructed:\t",reconstructed_secret.decode())

And a sample run [here]:

Msg: Hello

Alice's private key=24717110312959500398894080358434843509578578934054314213246494970478133031767
Alice's public key=(87531740538625017975357079156707681014534748755964202251330009337208067796042, 38148151312816124635784137975068946355154271184135375253990123903870980798553)
k= 67679870494495400649203854546733381935582201499769568232654302572052878179396

r=76175175749926314353139927368125446231633516634661818556116920398835217992524
s=46725313239594522980520655465965498046518288553336671629019598746369932257443

Result r=76175175749926314353139927368125446231633516634661818556116920398835217992524
Signature matches!
Using t shares
Secret:	 76175175749926314353139927368125446231633516634661818556116920398835217992524
===Shares===
b'bXktaWQAAAAAAAAAAAAAAAAEAE4BVSwdX3EMTA6I8KFFdd3EUriKEgYNVeOrWTkARvfVxBJ8R6idLd1N5ZEIDGvBsYdLJNbYE9FA5AOrvOz2DhQS6rssZkHDpbUgcCI+Epk='
b'bXktaWQAAAAAAAAAAAAAAAAEAE4C6EBufzWPi11wwRDsFUsolGM8GubYne4Dj3wELfPm7smOqiq36mwOv5pSuH6kyhKJFnPA+edd5psN/nfxtobPry/hozUnr5GbelMyad8='
b'bXktaWQAAAAAAAAAAAAAAAAEAE4DkAEXLPYL7vVAAgEOkF7v7sOZNdcZIjUmZWe5YAnO+3w7Ds7V/lkZltHIdvLPqnOt21JB1ASGPji6wmxqfhulv5J1zTPu2aWVjg1+jAg='
b'bXktaWQAAAAAAAAAAAAAAAAEAE4ELXn7gKHc5BQTKjlRX5Z9GJcFVBgakWM2Hvk0yD/9LrVjRvBzq7NiZBS7kZXLaOXEaD6KcE1bj4tXtqzh2CX1BwuWkQrIk8knMUBkNXU='

Reconstructed:	 76175175749926314353139927368125446231633516634661818556116920398835217992524

Now sharing s
Secret:	 46725313239594522980520655465965498046518288553336671629019598746369932257443
===Shares (showing a few)===
b'bXktaWQAAAAAAAAAAAAAAAAEAE4BGv+HC/FCsk7v/nloTwCoxc+7G4VzHlgUMTaetUl0DWL43ECmDQxtw4JObiKGV3E6VN7qTvNX1JQ/tZWk44P0hVtyqh9eg/ZXKsqlOVc='
b'bXktaWQAAAAAAAAAAAAAAAAEAE4CS+Gjz4YOcEemlhJSxCvtRfGNVT8MHd6yzDTlop4JUF7fZU/ENCbofsbqc1GkqmkvLr4BdyXGDl9amd6KPODub8quj8/RC8MBwanEWNI='
b'bXktaWQAAAAAAAAAAAAAAAAEAE4Du/ST0MGxmd6JcahoWITgcIr9lRUXFWxVDFg5I6e3tE9vJ0MpAU+JVL5EEMZrD7hhO/4NkGWMEndNf7owciLBH7CrU3zi0slSOp3ywU4='
b'bXktaWQAAAAAAAAAAAAAAAAEAE4EXNJ7FxpZkaqJzAkPO+TiU7GMXbRtTUXV/CYhPxyPtNUotzbkF41iOxzzto/7klso2tL8JMUvN8PUSXNUSF9Kh3pJduEWIRkIvNryypo='

Reconstructed:	 46725313239594522980520655465965498046518288553336671629019598746369932257443

And the code: