# Schnorr Identification protocol sometimes wrong?

I'm implementing the Schnorr Identification protocol as part of a larger protocol. In a large percentage of cases, around 20%, my test fails. I don't think it's a code problem, although possible, but I think it's a problem with my understanding of the protocol.

Here's how I currently perform Schnorr Identification:

• Using OpenSSL, I find a safe prime $p$ and subsequent prime $q = (p - 1) / 2$
• I find a generator $g$ for the cyclic group $\mathbb{G}_q$ of order $q$.
• This is the part I'm the most suspicious of. I've read that it's believed taking random $h \in \mathbb{Z}^{*}_{p}$ and setting $g = h^{(p-1)/q} \mod q$ will result in $g$ being a likely generator for $\mathbb{G}_q$ as long as $g \neq 1$, although it's not proven. I don't fully understand this, and it seems a probable place for my implementation to fall down.
• I generate a random private key $x \in \mathbb{Z}_q$ and set $y = g^x \mod p$

With the ElGamal key now set up, I want to prove knowledge of $x$ to a verifier who knows the public key $(p, q, g, y)$.

• I pick a random $e \in \mathbb{Z}_q$ and send $w = g^e \mod p$ as my commitment.
• As verifier, send random $c \in \mathbb{Z}_q$ to prover.
• As prover, send $s = cx + e \mod q$ to verifier.
• As verifier, check that $wy^c \mod p = g^s \mod p$.

The final step is where it will sometimes fail; the equality doesn't hold. Because each test run generates new random numbers, it's hard to see what's causing the failure.

I don't think it's a code problem; I believe I have coded everything to do exactly what the above steps outline. I think one or more of the steps themselves might be wrong. Note that I have included the modulus for each calculation that I'm doing, because some papers tend to leave them as implicit.

Is my understanding of the Schnorr Identification protocol correct, and have I correctly reproduced the formulas? If so, can I do it better?

• You work in a subgroup of order $q$, so your values $x$, $e$ and $c$ need to come from $\mathbb{Z}_q$. Apr 27, 2014 at 13:03
• @DrLecter You're right; this is actually what I'm doing. I've edited the question. Apr 27, 2014 at 13:07
• If you have a safe-prime $p=2q+1$ then the order of $Z_p^*$ is $p-1=2q$ and the order of all elements divide the group order. if $g=h^{(p-1)/q}\neq 1$, then is is not of order 2 and hence must be of order $q$ and thus a genertor of the order $q$ subgroup. Apr 27, 2014 at 13:24
• @DrLecter OK, I think I understand now. It could be a particular random number that sometimes does not have the properties I think it does. I will break the steps up, possibly by reusing known good random values to see which one(s) cause the errors. I will edit/post an answer when I have some results. Apr 28, 2014 at 6:00
• I just want to point out two other bugs in your description: you have to compute $g=h^{(p-1)/q} \bmod p$ and you compute $w$ as $w=g^e \bmod p$. Not sure if these are just typos, but just in case they are not. Apr 28, 2014 at 12:26

Good that we have resolved the issue (the bug is to compute $g=h^{(p-1)/q} \bmod p$ instead of $g=h^{(p-1)/q} \bmod q$).
• When working with group elements of the multiplicative group $\mathbb{Z}_p^*$, i.e., performing group operations, then you always do your computations modulo $p$, e.g., you compute $z=y w \bmod p$.
• When working "in the exponent" and your "base element" ($g$ in that case) generates a subgroup of order $q$, then you perform the computations on these integers modulo $q$, i.e., you compute $s=cx+e \bmod q$ (Note that when you then take your group element $g$ to the power of $s$, then you do another group operation, i.e., compute $g^s \bmod p$).