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 import sys from libnum import ecc mytype="BN(2,254)" M="hello" if (len(sys.argv)>1): M=str(sys.argv[1]) if (len(sys.argv)>2): mytype=(sys.argv[2]) if (mytype=="secp256k1"): print ("secp256k1") a=0 b=7 G=(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424) p=115792089237316195423570985008687907853269984665640564039457584007908834671663 n=115792089237316195423570985008687907852837564279074904382605163141518161494337 elif (mytype=="Curve25519"): print ("Curve 25519 - Weierstrass") a=19298681539552699237261830834781317975544997444273427339909597334573241639236 b=55751746669818908907645289078257140818241103727901012315294400837956729358436 G=(19298681539552699237261830834781317975544997444273427339909597334652188435546, 14781619447589544791020593568409986887264606134616475288964881837755586237401) p=pow(2,255)-19 n=7237005577332262213973186563042994240857116359379907606001950938285454250989 elif (mytype=="P192"): print ("P192") a=-3 b=18958286285566608000408668544493926415504680968679321075787234672564 G=(19277929113566293071110308034699488026831934219452440156649784352033, 19926808758034470970197974370888749184205991990603949537637343198772) p=26959946667150639794667015087019630673557916260026308143510066298881 n=6277101735386680763835789423176059013767194773182842284081 elif (mytype=="P512"): print ("P512") a=-3 b=1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984 G=(2661740802050217063228768716723360960729859168756973147706671368418802944996427808491545080627771902352094241225065558662157113545570916814161637315895999846, 3757180025770020463545507224491183603594455134769762486694567779615544477440556316691234405012945539562144444537289428522585666729196580810124344277578376784) p=6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151 n=0x000001fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409 elif (mytype=="P256"): print ("P256") a=-3 b=41058363725152142129326129780047268409114441015993725554835256314039467401291 G=(48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109) p=115792089210356248762697446949407573530086143415290314195533631308867097853951 n=115792089210356248762697446949407573529996955224135760342422259061068512044369 elif (mytype=="P224"): print ("P224") a=-3 b=18958286285566608000408668544493926415504680968679321075787234672564 G=(19277929113566293071110308034699488026831934219452440156649784352033, 19926808758034470970197974370888749184205991990603949537637343198772) p=26959946667150639794667015087019630673557916260026308143510066298881 n=26959946667150639794667015087019625940457807714424391721682722368061 elif (mytype=="P384"): print ("P384") a=-3 b=27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575 G=(26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087, 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871) p=39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319 n=0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973 elif (mytype=="secp160r2"): print ("secp160r2") a=1461501637330902918203684832716283019651637554288 b=1032640608390511495214075079957864673410201913530 G=(0x52dcb034293a117e1f4ff11b30f7199d3144ce6d , 0xfeaffef2e331f296e071fa0df9982cfea7d43f2e) p=1461501637330902918203684832716283019651637554291 n=1461501637330902918203685083571792140653176136043 elif (mytype=="brainpoolP160r1"): print ("brainpoolP160r1") a=0x340E7BE2A280EB74E2BE61BADA745D97E8F7C300 b=0x1E589A8595423412134FAA2DBDEC95C8D8675E58 G=(0xBED5AF16EA3F6A4F62938C4631EB5AF7BDBCDBC3, 0x1667CB477A1A8EC338F94741669C976316DA6321) p=0xE95E4A5F737059DC60DFC7AD95B3D8139515620F n=0xE95E4A5F737059DC60DF5991D45029409E60FC09 elif (mytype=="brainpoolP192r1"): print ("brainpoolP192r1") a=0x6A91174076B1E0E19C39C031FE8685C1CAE040E5C69A28EF b=0x469A28EF7C28CCA3DC721D044F4496BCCA7EF4146FBF25C9 G=(0xC0A0647EAAB6A48753B033C56CB0F0900A2F5C4853375FD6, 0x14B690866ABD5BB88B5F4828C1490002E6773FA2FA299B8F) p=0xC302F41D932A36CDA7A3463093D18DB78FCE476DE1A86297 n=0xC302F41D932A36CDA7A3462F9E9E916B5BE8F1029AC4ACC1 elif (mytype=="brainpoolP224r1"): print ("brainpoolP224r1") a=0x68A5E62CA9CE6C1C299803A6C1530B514E182AD8B0042A59CAD29F43 b=0x2580F63CCFE44138870713B1A92369E33E2135D266DBB372386C400B G=(0x0D9029AD2C7E5CF4340823B2A87DC68C9E4CE3174C1E6EFDEE12C07D,0x58AA56F772C0726F24C6B89E4ECDAC24354B9E99CAA3F6D3761402CD) p=0xD7C134AA264366862A18302575D1D787B09F075797DA89F57EC8C0FF n=0xD7C134AA264366862A18302575D0FB98D116BC4B6DDEBCA3A5A7939F elif (mytype=="brainpoolP256r1"): print ("brainpoolP256r1") a=0x7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9 b=0x26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6 G=(0x8BD2AEB9CB7E57CB2C4B482FFC81B7AFB9DE27E1E3BD23C23A4453BD9ACE3262,0x547EF835C3DAC4FD97F8461A14611DC9C27745132DED8E545C1D54C72F046997) p=0xA9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377 n=0xA9FB57DBA1EEA9BC3E660A909D838D718C397AA3B561A6F7901E0E82974856A7 elif (mytype=="BN(2,254)"): print ("BN(2,254)") a=0 b=2 G=(1,2) p=0xfffffffffffcf0cd46e5f25eee71a49f0cdc65fb12980a82d3292ddbaed33013 n=0xfffffffffffcf0cd46e5f25eee71a49e0cdc65fb1299921af62d536cd10b500d else: print("Not supported") curve = ecc.Curve(a,b,p,G,order=n) # Alice's secret key s = random.randint(0,curve.order-1) # Alice random value for signature y = random.randint(0, curve.order-1) Y = curve.power(curve.g,y) S = curve.power(curve.g,s) M=M.encode() Y_x,Y_y = Y S_x,S_y = S e=hashlib.sha256(Y_x.to_bytes(sys.getsizeof(Y_x),'big')+Y_y.to_bytes(sys.getsizeof(Y_y),'big')+M) digest = e.hexdigest() e = int(digest, 16) z=(y-s*e) %(curve.order) 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 = curve.power(curve.g,z) S_ = curve.power(S,e) Res=curve.add(Z,S_) Res_x,Res_y = Res Res_=int(hashlib.sha256(Res_x.to_bytes(sys.getsizeof(Res_x),'big')+Res_y.to_bytes(sys.getsizeof(Res_y),'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:
P512 Message: hello Alice secret key (s)=2873744109982369750289135346377686461452582104508802522501056036484566009481099839462133612313835240975763965908044284485528676372431410605828079405319735722 Alice public key (S)=(1675992303564605276781585091770914199119039168434754972042430132520982762610841153817194249147934629998061518722824466084925438333756358285304264463914865188, 6211204141696545803109858356411088552780670865041806642775036219240288621420431295430368688378610635091535477096787206382608421768803496956446629938940230688) Alice random (y)=4567918117560171109508270598612534076396468032850463946126838764320350265420673516442048805075782386446681195250038260532893534349934733967250779466386901012 Signature: e=67642790023658789187795899300025912549355155141052838046904179456856175007580 z=1703864315791864215811307956393133471169547166842871165525455180026430878225781125755080687954256579979120234217763616051419286272222886959694063801579448445 == To check, Bob uses z, e and S == Result=67642790023658789187795899300025912549355155141052838046904179456856175007580 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].