# When Peggy Met Victor

## Zero Knowledge Proof (ZKP) with probabilistic encryption

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*:

*z²*=*s *(mod *N*), if *m*=0,

*z²*=*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) % Ns=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()

breakprint "x=",x

print "y=",y

print "N=",Nprint "\nr=",rif (m==0):

z=r % N

else:

z=x*r % Nres = z**2 % Nprint "\nz=",z

print "z^2 (mod N)=",res

print "s (mod N)=",s%N

print "ys (mod N)=",y*s%Nif (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= 0We create a random secret (y)

y= 311

x= 1243

N= 3127r= 367z= 367

z^2 (mod N)= 228

s (mod N)= 228

ys (mod N)= 2114Proof: 0

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

p= 53

q= 59

m= 1We create a random secret (y)

y= 626

x= 761

N= 3127r= 223z= 845

z^2 (mod N)= 1069

s (mod N)= 2824

ys (mod N)= 1069Proof: 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.