Computes the public value \( y \):
Computes the value \( a \):
Receives the challenge \( b \):
Computes the response \( z \):
Before Peggy and Victor can begin the Fiat-Shamir zero-knowledge proof, Peggy needs two prime numbers \( p \) and \( q \), which are known only to her:
Use the Left and Right arrow keys to navigate.
Peggy receives the two prime numbers \( p \) and \( q \), and sends their product \( n = p \cdot q \) to Victor.
Peggy wants to convince Victor that \( y \) is a square modulo \( n \) without revealing the secret value \( x \) to him.
Peggy first chooses the secret value \( x \), then computes the public value \( y \), which she sends to Victor.
Peggy computes the value \( a \) using a randomly chosen integer \( r \).
Victor randomly chooses a challenge \( b \) and sends it to Peggy, where \( b = 0 \) or \( b = 1 \).
In response to the challenge, Peggy computes the value \( z \) and sends it 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 holds does he send a new challenge to Peggy (as in step 4), which she must respond to.
If Peggy can successfully respond to all \( k \) challenges sent by Victor, he is convinced that \( y \) is a square modulo \( n \), i.e., that she knows the secret value \( x \).
Receives the public values.
Receives the value \( a \).
Chooses a random challenge \( b \):
Receives the response \( z \).
Verifies Peggy's knowledge of the secret value \( x \):