In Chapter 21.3 of Schneier, Applied Cryptography I read the following about the Schnorr Authentication Protocol:
To generate a key pair, first choose two primes, $p$ and $q$, such that $q$ is a prime factor of $p - 1$. Then, choose an $a$ not equal to $1$, such that $a^q \equiv 1 \pmod{p}$. Then choose a random number less than $q$. This is the private key $s$. Then calculate $v = a^{-s} \mod p$. This is the public key.
Authentication Protocol
(1) Peggy picks a random number, $r$, less than $q$, and computes $x = a^r \mod p$.
(2) Peggy sends $x$ to Victor.
(3) Victor sends Peggy a random number, $e$, between $0$ and $2^t - 1$. (I’ll discuss $t$ in a moment.)
(4) Peggy computes $y = (r + se) \mod q$ and sends $y$ to Victor.
(5) Victor verifies that $x = a^yv^e \mod p$.
The security is based on the parameter $t$. The difficulty of breaking the algorithm is about $2t$. Schnorr recommended that $p$ be about $512$ bits, $q$ be about $140$ bits, and $t$ be $72$.
I have two questions regarding this:
- Why can $r$ not also be $q$? This would make the commitment $x=1$, but what would be the problem with that?
- Why is the challenge $t$ not allowed to be as large as $q$? It would not break anything, would it? I even found this lecture on Youtube where the lecturer lets the challenge (there denomiated $c$) be $c \in \mathbb{Z}_q$. Does limiting the size of $t$ make the procedure more efficient? If so, how?