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

=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 sysimport randomimport libnump=11q=13m=0if (len(sys.argv)>1):        m=int(sys.argv)if (len(sys.argv)>2):        p=int(sys.argv)if (len(sys.argv)>3):        q=int(sys.argv)N=p*qr=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=",xprint "y=",yprint "N=",Nprint "\nr=",rif (m==0):	z=r % Nelse:	z=x*r % Nres = z**2 % Nprint "\nz=",zprint "z^2 (mod N)=",resprint "s (mod N)=",s%Nprint "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= 53q= 59m= 0We create a random secret (y)y= 311x= 1243N= 3127r= 367z= 367z^2 (mod N)= 228s (mod N)= 228ys (mod N)= 2114Proof: 0`

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

`p= 53q= 59m= 1We create a random secret (y)y= 626x= 761N= 3127r= 223z= 845z^2 (mod N)= 1069s (mod N)= 2824ys (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.

Written by

## 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