You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@milagro.apache.org by sa...@apache.org on 2020/05/14 22:47:43 UTC
[incubator-milagro-MPC] 27/27: Make nizkp non replayable in model
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 <sa...@yahoo.it>
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