Schnorr proves you know one secret exponent. The same three-move pattern proves you know a pair of exponents, or an RSA root — and if you can answer twice for one commitment, you hand the secret over.
Everything below runs on the values printed here. The first act uses a published 2048-bit group; the second asks WebCrypto for a fresh 2048-bit RSA modulus.
Okamoto · know a representation
The public statement is u = gαhβ. A prover knows a pair (α, β), commits with a fresh pair, then answers the verifier’s challenge without identifying which valid representation it holds.
deriving…deriving…4The page expands seed || I2OSP(counter, 4) with SHA-256 to 2,112 bits, reduces modulo p, and squares. That places h in the order-q subgroup without computing or storing logg h.
deriving…Deriving h and checking subgroup membership…
| Value | Computed output |
|---|---|
| statement u | — |
| commitment ut | — |
| challenge c | — |
| response αz | — |
| response βz | — |
| left side | — |
| right side | — |
The rewind keeps ut fixed and changes only c. Dividing the two accepting equations cancels the commitment.
| Value | Second answer / extracted value |
|---|---|
| second challenge c′ | — |
| second response α′z | — |
| second response β′z | — |
| extracted α̂ | — |
| extracted β̂ | — |
| gα̂hβ̂ | — |
Okamoto’s protocol proves knowledge of a representation of u, not of the registered one.
Only at p = 47 and q = 23 can this page brute-force logg h, construct a second representation, and enumerate the whole transcript space. The real-size panel never does that.
p=47 · q=23 · g=4 · h=9(5, 7)(9, 8)—| Witness | Nonce pairs | Challenges per pair | Transcript count |
|---|---|---|---|
| registered (5, 7) | — | — | — |
| second (9, 8) | — | — | — |
log49 = —; the independent check prints 4log mod 47 = —. The second witness’s verifier equation prints — = —.
At real size, two distinct representations compute logg h. That hardness, a large challenge space, and witness independence are what Boneh–Shoup Theorem 19.23 uses for Okamoto identification against active attacks.
Guillou–Quisquater · know an RSA root
The public statement is y = xe mod N. The verifier checks xze = ytyc mod N; two answers for one commitment expose x through the extended Euclidean algorithm.
Waiting for WebCrypto key generation.
—| Value | Computed output |
|---|---|
| public y = xe | — |
| commitment yt | — |
| challenge c | — |
| response xz | — |
| left side xze | — |
| right side ytyc | — |
For Δx = xz/x′z and Δc = c − c′, extended Euclid finds s·e + t·Δc = 1. Then root = ysΔxt; negative powers use modular inverses.
| Value | Computed output |
|---|---|
| second challenge c′ | — |
| Δc | — |
| s | — |
| t | — |
| extracted root | — |
| roote mod N | — |
With a small exponent e, an accepted GQ proof does not show the prover knows an e-th root: a cheater who holds only y passes about one time in e.
The cheater guesses c*, chooses xz, and backs out yt = xze/yc*. It receives only public y, e, N—never x. The verifier samples c after that commitment exists.
————| Value | Computed output |
|---|---|
| forged yt | — |
| chosen xz | — |
| left side | — |
| right side | — |
Verifier equation: not run · group membership: not run.
Sources and next seams
The equations and theorem labels follow Boneh–Shoup v0.6: Fig. 19.6 and Theorem 19.9 (Okamoto), Fig. 19.10 and Theorem 19.13 (GQ), Theorem 19.21 (witness independence), Theorem 19.23 (active security), Fact 10.3, and Theorem 10.6 (Shamir’s trick). RFC 3526 §3 publishes p and generator 2; this exhibit squares it to g = 4 for the order-q subgroup. The RFC does not claim q is prime, so the unit suite independently tests both p and q.
The original papers are Tatsuaki Okamoto, “Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes,” CRYPTO ’92, pp. 31–53, and Louis C. Guillou & Jean-Jacques Quisquater, “A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory,” EUROCRYPT ’88, pp. 123–128. The latter is distinct from the CRYPTO ’89 cave-story citation in Exhibit 01.
Related demos: Schnorr Forge shows same-commitment nonce reuse as key recovery; Threshold Decrypt shows Chaum–Pedersen partial-decryption proofs; Credential Veil implements a Chaum–Pedersen OR proof; and RSA Forge explores RSA failures.
Extension seams: enlarge GQ’s challenge space as in Exercise 19.6; make both protocols non-interactive with Exhibit 05’s Fiat–Shamir transform; or build an AND composition proving both statements together.