EXHIBIT 07● REAL BIGINT ARITHMETIC · 2048-BIT
Beyond Schnorr: representations and RSA roots
Two Sigma protocols, one extraction mechanism: answer two challenges for the same commitment and the witness comes out.
✓ Completeness ✓ Special soundness ✓ Special HVZK

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.

Cryptographic honesty: Okamoto and GQ use exact BigInt equations at 2048 bits, with SHA-256 deriving h from the seed shown below. The p = 47 witness-independence census is explicitly a complete toy model. This is inspectable teaching code, not a constant-time production library.
ACT A

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.

REAL-SIZE PARAMETERS · RFC 3526 GROUP 14
Prime p
deriving…
Order q = (p − 1)/2
deriving…
Generator g
4
Sizes
p: — · q: —
Published nothing-up-my-sleeve seed
crypto-lab-zk-proof-lab/okamoto-h/v1

The 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.

Derived h
deriving…

Deriving h and checking subgroup membership…

TRANSCRIPT · gαzhβz = utuc
ValueComputed output
statement u—
commitment ut—
challenge c—
response αz—
response βz—
left side—
right side—
Run the proof to compute the verifier equation.
BREAK IT YOURSELF · REWIND THE SAME COMMITMENT

The rewind keeps ut fixed and changes only c. Dividing the two accepting equations cancels the commitment.

ValueSecond answer / extracted value
second challenge c′—
second response α′z—
second response β′z—
extracted α̂—
extracted β̂—
gα̂hβ̂—
A second challenge will expose the witness.
WITNESS INDEPENDENCE · COMPLETE TOY CENSUS

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.

Toy group
p=47 · q=23 · g=4 · h=9
Registered witness
(5, 7)
Second witness
(9, 8)
Same statement u
—
WitnessNonce pairsChallenges per pairTranscript count
registered (5, 7)———
second (9, 8)———
Enumerate the two transcript multisets to compare every entry.
Fact 10.3 readout: the two representations reveal 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.

ACT B

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.

Changing e retires every result below.
No GQ result yet. Run an honest proof to generate a fresh WebCrypto modulus.
REAL 2048-BIT RSA MODULUS · ONLY N ENTERS THE PROTOCOL

Waiting for WebCrypto key generation.

N
—
ValueComputed output
public y = xe—
commitment yt—
challenge c—
response xz—
left side xze—
right side ytyc—
Run the proof to compute the verifier equation.
BREAK IT YOURSELF · SHAMIR’S TRICK

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.

ValueComputed output
second challenge c′—
Δc—
s—
t—
extracted root—
roote mod N—
A second challenge will expose the RSA root.
BREAK IT YOURSELF · SMALL-e CHEATER

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.

Attempts
—
Acceptances
—
Guessed c*
—
Verifier c
—
ValueComputed output
forged yt—
chosen xz—
left side—
right side—

Verifier equation: not run · group membership: not run.

Run an honest proof first, then try the public-data-only cheater.

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.