We can convert the Fiat-Shamir method for zero-knowledge proofs into a method for signing a message. This page uses the method defined in [1], and uses elliptic curve methods. In this case Alice takes the message (\(M\)), random value (\(y\)), and her private key (\(s\)), and computes \((e,z)\). Bob checks this signature using Alice's public key (\(S\)).
Factoring Based Signature with Fiat-Shamir (Elliptic Curve) |
Outline
We will implement the method defined in [1], but use elliptic curve methods:
For elliptic curve methods, Alice generates a random private key (\(s\)), and then computes her public key:
\(S=sG\)
and where \(G\) is the base point on the curve. For each signature, Alice generates a random value (\(y\)) and computes:
\(Y=yG\)
Now Alice takes the message (\(M\)) and computes:
\(e=Hash(Y || M)\)
and where "||" is a concatenation operation. Next she computes:
\(z= y-se \pmod{n}\)
The signature for the message is then (\(z,e\)), and where \(n\) is the order of the curve. Bob then wants to check the signature, he computes:
\(Z=zG\)
\(eS = (e)S\)
\(e'=Hash( (Z + eS) || M)\)
if \(e'\) is the same as \(e\), the signature is valid.
This works because:
\(e'=Hash( (Z + eS) || M) = Hash( ( zG + (e)sG) || M) = Hash( (y-se)G + (e)sG) || M) = Hash( yG || M) = Hash( Y || M) \)
The following is the code using the secp256k1 curve:
import random import hashlib from secp256k1 import curve,scalar_mult,point_add import sys # Alice's secret key s = random.randint(0, curve.n-1) # Alice random value for signature y = random.randint(0, curve.n-1) G= curve.g Y = scalar_mult(y,G) S = scalar_mult(s,G) M="hello" if (len(sys.argv)>1): M=str(sys.argv[1]) M=M.encode() Y_x,Y_y = Y S_x,S_y = S e=hashlib.sha256(Y_x.to_bytes(32,'big')+Y_y.to_bytes(32,'big')+M) digest = e.hexdigest() e = int(digest, 16) z=(y-s*e) % curve.n print (f"Message: {M.decode()}") print (f"Alice secret key (s)={s}") print (f"Alice public key (S)={S}\n") print (f"Alice random (y)={y}\n\n") Z = scalar_mult(z,G) S_ = scalar_mult(e,S) Res=point_add(Z,S_) Res_x,Res_y = Res Res_=int(hashlib.sha256(Res_x.to_bytes(32,'big')+Res_y.to_bytes(32,'big')+M).hexdigest(),16) print (f"\nSignature:\ne={e}\nz={z}") print ("\n== To check, Bob uses z, e and S ==") print (f"\nResult={Res_}") if (e==Res_): print("They match!!!")
A sample run gives the proof:
Message: hello Alice secret key (s)=79372360234784491245802153557901650538712864544231990695104256261465725042050 Alice public key (S)=(60289430997947944525018523511685181848106621025118324003397786578563820448554, 53656803965313566209050975602646185993844184973675069576770742185561736825970) Alice random (y)=43367599150729727169188786487222261280236438204793945195805121335812876009495 Signature: e=58006645943275619189249399530845873697163578902032125665999993987578678122821 z=98076753675682586563161462099149764381360471242026070999961932942775127739388 == To check, Bob uses z, e and S == Result=58006645943275619189249399530845873697163578902032125665999993987578678122821 They match!!!
Presentation
Reference
[1] Lyubashevsky, V. (2009, December). Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 598–616). Springer, Berlin, Heidelberg [paper].