Cryptographic Protocols - Codes: The Guide to Secrecy from Ancient to Modern Times - page 206

Example 5.1 ( With artificially small parameters for illustration only. ) We
dispense with the issue of the certificate and assume it has been handled properly.
We proceed with the rest of the protocol. Suppose that we have p = 8699 , q =
4389 and t =10 . We know that α =4 has order 4389 in F p , since 2 is a

2 ( p − 1) /q (mod p ) . If Alice's private exponent primitive root modulo p and α ≡

α − e 4 − 11

is e =11 , she computes v 4111(mod 8699) . This completes

the interaction of Trent and Alice. Now if Alice selects k = 110 , she computes
γ

≡ ≡ ≡

α k 4 110

4572(mod 8699) . If Bob chooses r = 233 and sends it to
Alice, she computes y

≡ ≡ ≡

≡ k + er ≡ 110 + 11 · 233 ≡ 2673(mod 4389) , which she

sends to Bob who computes

α y v r 4 2673 4111 233

δ ≡ ≡ · ≡ 4572 ≡ γ (mod 4937) ,

so Bob accepts Alice's identity as valid.

Analysis
Security : We first demonstrate that the protocol has the soundness prop-
ertydiscussed on page 203. Suppose that Malloryhas knowledge of γ , and
that he has a nonnegligible probabilityof successfullyimpersonating Alice. We
now show this means that Mallorycan actuallycompute e , which will demon-
strate soundness. Mallorycan compute a response y that will be accepted by
Bob's verification in step 4 of the protocol, so Mallorycan compute integers
y 1 ,y 2 ,r 1 ,r 2 such that both

α y 1 v r 1 α y 2 v r 2 (mod p ) .

y 1 ≡ y 2 (mod p ) and γ ≡ ≡

Hence,

α y 1 − y 2 v r 2 − r 2 (mod p ) . ≡

α − e (mod p ), then Since v ≡

y 1 − y 2 ≡ e ( r 1 − r 2 )(mod q ) .

Since

< 2 t and q> 2 t is prime, 0 < | r 2 − r 1 |

then gcd( r 2 − r 1 ,q ) = 1. Hence, ( r 2 −

r 1 ) has a multiplicative inverse modulo

q . It follows that Mallorycan compute

r 2 ) − 1 (mod q ) . e =( y 1 − y 2 )( r 1 −

What we have shown is that if Malloryhas a reasonable (nonnegligible) prob-
abilityof successfullyexecuting Schnorr's protocol, then he must (essentiall)
“know” Alice's private exponent e . This is soundness.
Once Alice proves her identityin the fashion prescribed in the protocol, Bob
accepts her proof in step 4, so the protocol has the completeness property, also
discussed on the aforementioned page. However, soundness and completeness
are insuKcient to guarantee security. For example, Alice could just reveal her