The Schnorr identification scheme was defined in 1991 [1] and supports a zero knowledge proof method. It uses discrete logarithms. The prover (Peggy) has a proving public key of \((g,X)\) where \(g\) is a generator, and \(X= g^x \pmod N \). \(x\) is the secret value that the prover (Peggy) must prove. After Peggy generates her public proving key, she will then be challenged by Victor to produce the correct result. In the following we define a secret value (\(x\)), a generator (\(g\)) and a modulus value (\(N\)). We can determine the possible values of g from [here]:
Schnorr identification scheme |
Method
With Schnorr identification, Peggy (the prover) has a proving public key of \((N,g,X)\) and a proving secret key of \((N,x)\). \(N\) is a prime number for the modulus operation, and \(x\) is the secret, and where:
\(X \leftarrow g^x \pmod N \)
On the registration of the secret, Peggy generates a random value (\(y\)), and then computes \(Y\):
\(Y \leftarrow g^y \pmod N\)
This value is sent to Victor (who is the verifier). Victor then generates a random value \((c)\) and sends this to Peggy. This is a challenge to Peggy to produce the correct result. Peggy then computes:
\(z \leftarrow (y+ xc) \pmod N\)
He then sends this to Victor in order to prove that he knows \(x\). Victor then computes two values:
\(val_1 = Y X^c \pmod N\)
\(val_2 =g^z \pmod N\)
If the values are the same (\(val_1 \equiv val_2\)), Peggy has proven that she knows \(x\).
This works because:
\(Y X^c = g^y {g^x}^c = g^{y+cx}\)
\(g^z = g^{y+cx}\)
In a formal definition (taken from this paper) [2], the method is:
Coding
import random import sys N=89 g=3 x = random.randint(1,97) X = pow(g,x) % N y = random.randint(1,97) Y = pow(g,y) % N print("Peggy (the Prover) generates these values:") print("x(secret)=\t",x) print("N=\t\t",N) print("X=\t\t",X) print("\nPeggy generates a random value (y):") print("y=",y) print("\nPeggy computes Y = g^y (mod N) and passes to Victor:") print("Y=",Y) print("\nVictor generates a random value (c) and passes to Peggy:") c = random.randint(1,97) print("c=",c) print("\nPeggy calculates z = y.x^c (mod N) and send to Victor (the Verifier):") z = (y + c * x) print("z=",z) print("\nVictor now computes val=g^z (mod N) and (Y X^c (mod N)) and determines if they are the same\n") val1= pow(g,z) % N val2= (Y * (X**c)) % N print("val1=\t",val1, end=' ') print(" val2=\t",val2) if (val1==val2): print("Peggy has proven that he knows x") else: print("Failure to prove")
References
[1] . C. P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161–174, 1991. [paper]
[2] Bellare, M., & Palacio, A. (2002, August). GQ and Schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks. In Annual International Cryptology Conference (pp. 162-177). Springer, Berlin, Heidelberg. [paper]