When Peggy Met Victor

Zero Knowledge Proof (ZKP) with probabilistic encryption

Prof Bill Buchanan OBE
Oct 19 · 3 min read

In this method we have Peggy (the Prover) and Victor (the Verifier), and where Peggy will prove to Victor that she still knows a secret. In this case, Victor will challenge Peggy to prove her identity by showing that she knows a given secret. Initially Peggy will select two large prime numbers (p and q), and then publish their product at N:

N=pq

Now Peggy has a secret y, and then finds a value of y which satisfies this:

x²=y (mod N)

For example, if y=3 and p=11,q=13, then N=143. Now we need to find the value of x for:

x²=3 (mod 143)

The solution for this is x=126:

126²=3 (mod 143)

Now each time Peggy wants to prove that she knows y, she performs the following:

1. Peggy create a random number (r) and computes:

s=r² (mod N)

2. Next Victor either sends Peggy a value of 0 or 1 (m∈{0,1}) as a challenge.

3. Peggy now calculates a value of z on sends it to Victor:

z=r (mod N), if m=0

z=xr (mod N), if m=1.

Then Victor calculates z² (mod N ) and does a check based on m:

=s (mod N), if m=0,

=ys (mod N), if m=1.

and where y is the secret that Peggy has registered.

The coding is here [sample]:

import sys
import random
import libnum
p=11
q=13
m=0if (len(sys.argv)>1):
m=int(sys.argv[1])
if (len(sys.argv)>2):
p=int(sys.argv[2])
if (len(sys.argv)>3):
q=int(sys.argv[3])
N=p*q
r=random.randint(5,1000) % N
s=r**2 % N# Find solution to x^2 = y(mod N)
while (True):
y=random.randint(5,1000) % N
if (libnum.has_sqrtmod(y,{p: 1,q:1})):
x=libnum.sqrtmod(y,{p: 1,q:1}).next()
break
print "x=",x
print "y=",y
print "N=",N
print "\nr=",rif (m==0):
z=r % N
else:
z=x*r % N
res = z**2 % Nprint "\nz=",z
print "z^2 (mod N)=",res
print "s (mod N)=",s%N
print "ys (mod N)=",y*s%N
if (res == (s%N)):
print "\nProof: 0"
elif (res==y*s%N):
print "\nProof: 1"

In this case we find the solution to the square root modulus with:

# Find solution to x^2 = y (mod N)
while (True):
y=random.randint(5,1000) % N
if (libnum.has_sqrtmod(y,{p: 1,q:1})):
x=libnum.sqrtmod(y,{p: 1,q:1}).next()
break

A sample run for m=0 [sample]:

p= 53
q= 59
m= 0
We create a random secret (y)
y= 311
x= 1243
N= 3127
r= 367z= 367
z^2 (mod N)= 228
s (mod N)= 228
ys (mod N)= 2114
Proof: 0

And for a proof for m=1 [sample]:

p= 53
q= 59
m= 1
We create a random secret (y)
y= 626
x= 761
N= 3127
r= 223z= 845
z^2 (mod N)= 1069
s (mod N)= 2824
ys (mod N)= 1069
Proof: 1

In this case, Victor can prompt Peggy a number of times, and each time she proves she knows the secret, the more trust Victor will have in her. For n challenges, the chances of Peggy not being Peggy is 1 over 2^n. With three challenges, if Peggy produces the right proof, there is a 1 in 8 chance that she has guessed them by random.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade