This is an automated email from the ASF dual-hosted git repository. sandreoli pushed a commit to branch update-model-no-replay in repository https://gitbox.apache.org/repos/asf/incubator-milagro-MPC.git
commit e2bf31f302afdb3aa0abf87872ece3439487fa3f Author: Samuele Andreoli <[email protected]> AuthorDate: Thu May 14 00:54:25 2020 +0100 Make nizkp non replayable in model --- model/examples/run_factorization_zk.py | 14 +++-- model/examples/run_schnorr.py | 35 ++++++++----- model/sec256k1/factorization_zk.py | 16 ++++-- model/sec256k1/schnorr.py | 12 ++++- model/vectors/factorization_zk/genZKFACT.py | 45 +++++++++++----- model/vectors/schnorr/genDSCHNORR.py | 12 +++-- model/vectors/schnorr/genSCHNORR.py | 24 ++++++--- model/vectors/schnorr/genVector.py | 79 +++++++++++++++++++---------- 8 files changed, 161 insertions(+), 76 deletions(-) diff --git a/model/examples/run_factorization_zk.py b/model/examples/run_factorization_zk.py index ed60126..fe4b3aa 100755 --- a/model/examples/run_factorization_zk.py +++ b/model/examples/run_factorization_zk.py @@ -10,6 +10,8 @@ from Crypto.Util import number DETERMINISTIC = False if __name__ == "__main__": + ID = "proverID".encode('utf-8') + AD = "something".encode('utf-8') # Generate P,Q,N if DETERMINISTIC: @@ -22,9 +24,11 @@ if __name__ == "__main__": N = p * q print("ZK proof of knowledge of factoring") - print("\tP = {}".format(hex(p)[2:].zfill(fact.nlen))) - print("\tQ = {}".format(hex(q)[2:].zfill(fact.nlen))) - print("\tN = {}".format(hex(N)[2:].zfill(fact.nlen * 2))) + print("\tP = {}".format(hex(p)[2:].zfill(fact.nlen))) + print("\tQ = {}".format(hex(q)[2:].zfill(fact.nlen))) + print("\tN = {}".format(hex(N)[2:].zfill(fact.nlen * 2))) + print("\tID = {}".format(ID.decode('utf-8'))) + print("\tAD = {}\n".format(AD.decode('utf-8'))) print("") # ZK proof setup (once for each n, can be reused) @@ -43,7 +47,7 @@ if __name__ == "__main__": if DETERMINISTIC: r = 0x279775a316e9e86c9e89116e80c6cc9843930f6a8c083ad0244b3c516ed224e2150ac3542ff525f7422bc4c5f64a52d2e925a9685391d1948dd4eb0fe2a517a5fcb4dec60979346d8475bceb1aa905f5540f0d01472fde3d5c1c3189c5f7e1fd5ac42ac7c5e5eb463c15b8a26ce66720dc0d51d60d70f671634b4e685ee7a9f173924954fd6e10bd885fc958a4f54c84e33ddb2d86bbe9dffa1d77a71fdb7dc3e40177b68fb9c36f3a8f82e943a14320c78b16c55e7f1e26dba64b6e7af4f96d81580bf3c12eb5fc4f171f4d6b6e568584c220254a271a9a3949aa8231ef96c52db2d4cf54aab52f73ea203de9addd [...] - e,y = fact.nizk_prove(N,p,q,Zi,r=r) + e,y = fact.nizk_prove(N,p,q,Zi,ID,AD=AD,r=r) print("\tE = {}".format(hex(e)[2:].zfill(fact.B//4))) print("\tY = {}".format(hex(y)[2:].zfill(fact.nlen * 2))) @@ -52,7 +56,7 @@ if __name__ == "__main__": # ZK verifiction print("[Bob] Verification") - if fact.nizk_verify(Zi,N,e,y): + if fact.nizk_verify(Zi,N,e,y,ID,AD=AD): print("\tSuccess!") else: print("\tFail!") diff --git a/model/examples/run_schnorr.py b/model/examples/run_schnorr.py index 7f929b9..f15f7ab 100755 --- a/model/examples/run_schnorr.py +++ b/model/examples/run_schnorr.py @@ -11,6 +11,9 @@ import sec256k1.schnorr as schnorr DETERMINISTIC = True if __name__ == "__main__": + ID = "proverID".encode('utf-8') + AD = "something".encode('utf-8') + # Single DLOG knowledge proof # Generate DLOG @@ -22,8 +25,10 @@ if __name__ == "__main__": V = x * ecp.generator() print("Single DLOG knowledge ZK proof") - print("x {}".format(hex(x).zfill(64))) - print("V {}\n".format(V)) + print("\tx = {}".format(hex(x).zfill(64))) + print("\tV = {}".format(V)) + print("\tID = {}".format(ID.decode('utf-8'))) + print("\tAD = {}\n".format(AD.decode('utf-8'))) # ZK proof print("Begin ZK proof\n") @@ -36,10 +41,10 @@ if __name__ == "__main__": # C is the commitment, r is kept secret r, C = schnorr.commit(r) - print("Commit\n\tr {}\n\tC {}\n".format(hex(r)[2:].zfill(64), C)) + print("Commit\n\tr = {}\n\tC = {}\n".format(hex(r)[2:].zfill(64), C)) # Challenge - c = schnorr.challenge(V,C) + c = schnorr.challenge(V,C,ID,AD=AD) print("Challenge {}\n".format(hex(c)[2:].zfill(64))) @@ -76,11 +81,13 @@ if __name__ == "__main__": V = ecp.ECp.mul(R, s, ecp.generator(), l) print("\nDouble DLOG knowledge ZK proof") - print("r {}".format(hex(r)[2:].zfill(64))) - print("s {}".format(hex(s)[2:].zfill(64))) - print("l {}".format(hex(l)[2:].zfill(64))) - print("R = r.G {}".format(R)) - print("V {}\n".format(V)) + print("\tr = {}".format(hex(r)[2:].zfill(64))) + print("\ts = {}".format(hex(s)[2:].zfill(64))) + print("\tl = {}".format(hex(l)[2:].zfill(64))) + print("\tR = r.G = {}".format(R)) + print("\tV = {}".format(V)) + print("\tID = {}".format(ID.decode('utf-8'))) + print("\tAD = {}\n".format(AD.decode('utf-8'))) # ZK proof @@ -95,19 +102,19 @@ if __name__ == "__main__": a, b, C = schnorr.d_commit(R, a, b) print("Commit") - print("\ta {}".format(hex(a)[2:].zfill(64))) - print("\tb {}".format(hex(b)[2:].zfill(64))) - print("\tC {}\n".format(C)) + print("\ta = {}".format(hex(a)[2:].zfill(64))) + print("\tb = {}".format(hex(b)[2:].zfill(64))) + print("\tC = {}\n".format(C)) # Challenge - c = schnorr.d_challenge(R, V, C) + c = schnorr.d_challenge(R, V, C, ID, AD=AD) print("Challenge {}\n".format(hex(c)[2:].zfill(64))) # Proof t, u = schnorr.d_prove(a, b, c, s, l) - print("Prove\n\tt {}\n\tu {}\n".format( + print("Proof\n\tt = {}\n\tu = {}\n".format( hex(t)[2:].zfill(64), hex(u)[2:].zfill(64))) # Verification diff --git a/model/sec256k1/factorization_zk.py b/model/sec256k1/factorization_zk.py index d70c05b..f5327ac 100644 --- a/model/sec256k1/factorization_zk.py +++ b/model/sec256k1/factorization_zk.py @@ -93,7 +93,7 @@ def nizk_setup(N): return Zi -def nizk_prove(N, P, Q, Zi, r = None): +def nizk_prove(N, P, Q, Zi, ID, AD=None, r = None): """ Compute ZK proof of knowledge of factorization of N Args:: @@ -131,7 +131,7 @@ def nizk_prove(N, P, Q, Zi, r = None): if DEBUG: print("X = {}".format(X.hex())) - # Compute public challenge e = H'(N,z1,...,zK,X) + # Compute public challenge e = H'(N,z1,...,zK,X,ID,AD) Hprime = hashlib.new(Hprime_param) Hprime.update(N.to_bytes(nlen, byteorder='big')) @@ -140,6 +140,10 @@ def nizk_prove(N, P, Q, Zi, r = None): Hprime.update(Z.to_bytes(nlen, byteorder='big')) Hprime.update(X) + Hprime.update(ID) + + if AD: + Hprime.update(AD) e = big.from_bytes(Hprime.digest()[:B//8]) @@ -148,7 +152,7 @@ def nizk_prove(N, P, Q, Zi, r = None): return e,y -def nizk_verify(Zi, N, e, y): +def nizk_verify(Zi, N, e, y, ID, AD=None): """ Verify ZK proof of knowledge of factorization of N Args:: @@ -181,7 +185,7 @@ def nizk_verify(Zi, N, e, y): X = H.digest() - # Compute e_verifier = H'(N,z1,...,zK,X) + # Compute e_verifier = H'(N,z1,...,zK,X,ID,AD) Hprime = hashlib.new(Hprime_param) Hprime.update(N.to_bytes(nlen, byteorder='big')) @@ -190,6 +194,10 @@ def nizk_verify(Zi, N, e, y): Hprime.update(Z.to_bytes(nlen, byteorder='big')) Hprime.update(X) + Hprime.update(ID) + + if AD: + Hprime.update(AD) e_verifier = big.from_bytes(Hprime.digest()[:B//8]) diff --git a/model/sec256k1/schnorr.py b/model/sec256k1/schnorr.py index 6cc54be..f1f854d 100644 --- a/model/sec256k1/schnorr.py +++ b/model/sec256k1/schnorr.py @@ -25,13 +25,17 @@ def d_commit(R, a=None, b=None): return a, b, C -def d_challenge(R, V, C): +def d_challenge(R, V, C, ID, AD=None): H = hashlib.new("sha256") H.update(ecp.generator().toBytes(True)) H.update(R.toBytes(True)) H.update(C.toBytes(True)) H.update(V.toBytes(True)) + H.update(ID) + + if AD: + H.update(AD) e_bytes = H.digest() e = big.from_bytes(e_bytes) @@ -81,12 +85,16 @@ def commit(r=None): return r, C -def challenge(V, C): +def challenge(V, C, ID, AD): H = hashlib.new("sha256") H.update(ecp.generator().toBytes(True)) H.update(C.toBytes(True)) H.update(V.toBytes(True)) + H.update(ID) + + if AD: + H.update(AD) e_bytes = H.digest() e = big.from_bytes(e_bytes) diff --git a/model/vectors/factorization_zk/genZKFACT.py b/model/vectors/factorization_zk/genZKFACT.py index 81795d4..cc60c37 100755 --- a/model/vectors/factorization_zk/genZKFACT.py +++ b/model/vectors/factorization_zk/genZKFACT.py @@ -11,21 +11,24 @@ sys.path.append("../../") import json import argparse +import random from Crypto.Util import number from sec256k1 import big from sec256k1 import factorization_zk as fact vector_fields = { - "prove": ["TEST", "N", "P", "Q", "R", "E", "Y"], - "verify": ["TEST", "N", "E", "Y"] + "prove": ["TEST", "N", "P", "Q", "ID", "AD", "R", "E", "Y"], + "verify": ["TEST", "N", "E", "Y", "ID", "AD"] } -def genVector(test_no, tv_type): +def genVector(test_no, ID = None, AD = None): """Generate a single test vector Args:: test_no: Test vector identifier + ID: prover identifier + AD: additional data for challenge Returns:: @@ -35,6 +38,15 @@ def genVector(test_no, tv_type): Exception """ + + # Generate ID and AD + if ID is None: + ID = random.SystemRandom().getrandbits(128).to_bytes(16, byteorder='big') + + if AD is None: + AD = random.SystemRandom().getrandbits(128).to_bytes(16, byteorder='big') + + P = number.getStrongPrime(fact.nlen * 4) Q = number.getStrongPrime(fact.nlen * 4) N = P * Q @@ -42,15 +54,17 @@ def genVector(test_no, tv_type): Zi = fact.nizk_setup(N) R = big.rand(fact.A) - E, Y = fact.nizk_prove(N, P, Q, Zi, r=R) + E, Y = fact.nizk_prove(N, P, Q, Zi, ID, AD=AD, r=R) - assert fact.nizk_verify(Zi, N, E, Y) + assert fact.nizk_verify(Zi, N, E, Y, ID, AD=AD) return { "TEST": test_no, "N": hex(N)[2:].zfill(fact.nlen * 2), "P": hex(P)[2:].zfill(fact.nlen), "Q": hex(Q)[2:].zfill(fact.nlen), + "ID": ID.hex(), + "AD": AD.hex(), "R": hex(R)[2:].zfill(fact.nlen * 2), "E": hex(E)[2:].zfill(fact.B//4), "Y": hex(Y)[2:].zfill(fact.nlen * 2) @@ -66,20 +80,27 @@ if __name__ == '__main__': args = parser.parse_args() - print("Generate {} vector(s). Type '{}'".format(args.nVec, args.type)) + n = args.nVec + v_type = args.type + + print("Generate {} vector(s). Type '{}'".format(n, v_type)) vectors = [] - for i in range(args.nVec): - vector = genVector(i, args.type) + for i in range(n): + AD = None + if i < (n//2): + AD = b'' + + vector = genVector(i, AD=AD) - vector = {k: vector[k] for k in vector_fields[args.type]} + vector = {k: vector[k] for k in vector_fields[v_type]} vectors.append(vector) - json.dump(vectors, open("{}.json".format(args.type), "w"), indent=2) + json.dump(vectors, open("{}.json".format(v_type), "w"), indent=2) - with open("{}.txt".format(args.type), "w") as f: + with open("{}.txt".format(v_type), "w") as f: for vector in vectors: - for field in vector_fields[args.type]: + for field in vector_fields[v_type]: f.write("{} = {},\n".format(field, vector[field])) f.write("\n") diff --git a/model/vectors/schnorr/genDSCHNORR.py b/model/vectors/schnorr/genDSCHNORR.py index da1931c..c795bb4 100755 --- a/model/vectors/schnorr/genDSCHNORR.py +++ b/model/vectors/schnorr/genDSCHNORR.py @@ -17,7 +17,7 @@ from Crypto.Util import number vector_fields = { "commit": ["TEST", "R", "A", "B", "C"], - "challenge": ["TEST", "R", "V", "C", "E"], + "challenge": ["TEST", "R", "V", "C", "E", "ID", "AD"], "prove": ["TEST", "A", "B", "E", "S", "L", "T", "U"], "verify": ["TEST", "R", "V", "C", "E", "T", "U"], } @@ -31,13 +31,19 @@ if __name__ == '__main__': help='number of test vectors to generate') args = parser.parse_args() + + n = args.n vecType = args.type keys = vector_fields[vecType] vectors = [] - for i in range(args.n): - vector = genDoubleSchnorrVector(i) + for i in range(n): + AD = None + if i < (n//2): + AD = b'' + + vector = genDoubleSchnorrVector(i, AD = AD) vector = {k: vector[k] for k in keys} vectors.append(vector) diff --git a/model/vectors/schnorr/genSCHNORR.py b/model/vectors/schnorr/genSCHNORR.py index 51ad252..50cae70 100755 --- a/model/vectors/schnorr/genSCHNORR.py +++ b/model/vectors/schnorr/genSCHNORR.py @@ -15,7 +15,7 @@ from genVector import genSchnorrVector vector_fields = { "commit": ["TEST", "R", "C"], - "challenge": ["TEST", "V", "C", "E"], + "challenge": ["TEST", "V", "C", "E", "ID", "AD"], "prove": ["TEST", "R", "E", "X", "P"], "verify": ["TEST", "V", "C", "E", "P"], } @@ -28,20 +28,28 @@ if __name__ == '__main__': args = parser.parse_args() - print("Generate {} vector(s). Type '{}'".format(args.nVec, args.type)) + n = args.nVec + v_type = args.type + + print("Generate {} vector(s). Type '{}'".format(n, v_type)) vectors = [] - for i in range(args.nVec): - vector = genSchnorrVector(i) + for i in range(n): + AD = None + if i < (n//2): + AD = b'' + + vector = genSchnorrVector(i, AD = AD) + + vector = {k: vector[k] for k in vector_fields[v_type]} - vector = {k: vector[k] for k in vector_fields[args.type]} vectors.append(vector) - json.dump(vectors, open("{}.json".format(args.type), "w"), indent=2) + json.dump(vectors, open("{}.json".format(v_type), "w"), indent=2) - with open("{}.txt".format(args.type), "w") as f: + with open("{}.txt".format(v_type), "w") as f: for vector in vectors: - for field in vector_fields[args.type]: + for field in vector_fields[v_type]: f.write("{} = {},\n".format(field, vector[field])) f.write("\n") diff --git a/model/vectors/schnorr/genVector.py b/model/vectors/schnorr/genVector.py index 432313b..acf53a8 100644 --- a/model/vectors/schnorr/genVector.py +++ b/model/vectors/schnorr/genVector.py @@ -6,7 +6,7 @@ import sec256k1.curve as curve import sec256k1.schnorr as schnorr -def genSchnorrVector(test_no, x=None, r=None): +def genSchnorrVector(test_no, x=None, r=None, ID=None, AD=None): """Generate a single test vector Use parameters to generate a single test vector @@ -14,8 +14,10 @@ def genSchnorrVector(test_no, x=None, r=None): Args:: test_no: Test vector identifier - x: exponent for the DLOG - r: random number for the commitment + x: exponent for the DLOG + r: random number for the commitment + ID: prover identifier + AD: additional data for challenge. left empty if None Returns:: @@ -26,6 +28,13 @@ def genSchnorrVector(test_no, x=None, r=None): Exception """ + # Generate ID and AD + if ID is None: + ID = random.SystemRandom().getrandbits(128).to_bytes(16, byteorder='big') + + if AD is None: + AD = random.SystemRandom().getrandbits(128).to_bytes(16, byteorder='big') + # Generate DLOG if x is None: x = big.rand(curve.r) @@ -35,7 +44,7 @@ def genSchnorrVector(test_no, x=None, r=None): # ZK proof r, C = schnorr.commit(r) - e = schnorr.challenge(V, C) + e = schnorr.challenge(V, C, ID, AD) p = schnorr.prove(r, e, x) @@ -43,18 +52,20 @@ def genSchnorrVector(test_no, x=None, r=None): vector = { "TEST": test_no, - "X": hex(x)[2:].zfill(64), - "V": "{}".format(V.toBytes(True).hex()), - "R": hex(r)[2:].zfill(64), - "C": "{}".format(C.toBytes(True).hex()), - "E": hex(e)[2:].zfill(64), - "P": hex(p)[2:].zfill(64), + "X": hex(x)[2:].zfill(64), + "V": "{}".format(V.toBytes(True).hex()), + "ID": ID.hex(), + "AD": AD.hex(), + "R": hex(r)[2:].zfill(64), + "C": "{}".format(C.toBytes(True).hex()), + "E": hex(e)[2:].zfill(64), + "P": hex(p)[2:].zfill(64), } return vector -def genDoubleSchnorrVector(test_no, R=None, s=None, l=None, a=None, b=None): +def genDoubleSchnorrVector(test_no, R=None, s=None, l=None, a=None, b=None, ID=None, AD=None): """Generate a single test vector Use parameters to generate a single test vector @@ -62,12 +73,14 @@ def genDoubleSchnorrVector(test_no, R=None, s=None, l=None, a=None, b=None): Args:: test_no: Test vector identifier - R: point on the curve - s: exponent for the DLOG with R - l: exponent for the DLOG with G - a: random number for the commitment - b: random number for the commitment - c: challenge + R: point on the curve + s: exponent for the DLOG with R + l: exponent for the DLOG with G + a: random number for the commitment + b: random number for the commitment + c: challenge + ID: prover identifier + AD: additional data for challenge Returns:: @@ -78,6 +91,14 @@ def genDoubleSchnorrVector(test_no, R=None, s=None, l=None, a=None, b=None): Exception """ + # Generate ID and AD + if ID is None: + ID = random.SystemRandom().getrandbits(128).to_bytes(16, byteorder='big') + + if AD is None: + AD = random.SystemRandom().getrandbits(128).to_bytes(16, byteorder='big') + + # Generate r for subgroup generator if R is None: R = big.rand(curve.r) * ecp.generator() @@ -93,7 +114,7 @@ def genDoubleSchnorrVector(test_no, R=None, s=None, l=None, a=None, b=None): # ZK proof a, b, C = schnorr.d_commit(R, a, b) - c = schnorr.d_challenge(R, V, C) + c = schnorr.d_challenge(R, V, C, ID, AD) t, u = schnorr.d_prove(a, b, c, s, l) @@ -101,16 +122,18 @@ def genDoubleSchnorrVector(test_no, R=None, s=None, l=None, a=None, b=None): vector = { "TEST": test_no, - "R": "{}".format(R.toBytes(True).hex()), - "S": hex(s)[2:].zfill(64), - "L": hex(l)[2:].zfill(64), - "V": "{}".format(V.toBytes(True).hex()), - "A": hex(a)[2:].zfill(64), - "B": hex(b)[2:].zfill(64), - "C": "{}".format(C.toBytes(True).hex()), - "E": hex(c)[2:].zfill(64), - "T": hex(t)[2:].zfill(64), - "U": hex(u)[2:].zfill(64), + "R": "{}".format(R.toBytes(True).hex()), + "S": hex(s)[2:].zfill(64), + "L": hex(l)[2:].zfill(64), + "V": "{}".format(V.toBytes(True).hex()), + "ID": ID.hex(), + "AD": AD.hex(), + "A": hex(a)[2:].zfill(64), + "B": hex(b)[2:].zfill(64), + "C": "{}".format(C.toBytes(True).hex()), + "E": hex(c)[2:].zfill(64), + "T": hex(t)[2:].zfill(64), + "U": hex(u)[2:].zfill(64), } return vector
