Computes the public value \( y \):
Computes the value \( a \):
Receives the challenge \( b \)
Computes the response \( z \):
Before Peggy and Victor can start the Fiat-Shamir zero-knowledge proof Peggy needs two prime numbers \( p \) and \( q \) which are only known by Peggy:
Use the left and right arrow keys to navigate.
Peggy receives the two prime numbers \( p \) and \( q \) and sends the product \( n = p \cdot q \) to Victor.
Peggy wants to convince Victor about that \( y \) is a square modulo \( n \) without revealing the secret value \( x \) to Victor.
Peggy first chooses the secret value \( x \) and then computes the public value \( y \) which she sends to Victor.
Peggy computes the value \( a \) using the random integer \( r \).
Victor chooses randomly a challenge \( b \) and sends it to Peggy where \( b = 0 \) or \( b = 1 \).
In response to the challenge Peggy computes the value \( z \) which she sends to Victor.
Victor verifies the received response \( z \) from Peggy by checking that \( z^{2} \: mod \: n = y^{b} \cdot a \: mod \: n \). Only if this is the case he sends a new challenge to Peggy (as in step 4) which she have to respond to.
If Peggy can successfully respond on all \( k \) challenges sent by Victor, he is convinced that \( y \) is a square modulo \( n \), i.e. she know the secret value \( x \).
Receives the public values
Receives the value \( a \)
Chooses the random challenge \( b \):
Receives the response \( z \)
Verifies Peggy's knowledge about the secret value \( x \):