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?

  • $\begingroup$ You work in a subgroup of order $q$, so your values $x$, $e$ and $c$ need to come from $\mathbb{Z}_q$. $\endgroup$
    – DrLecter
    Apr 27, 2014 at 13:03
  • $\begingroup$ @DrLecter You're right; this is actually what I'm doing. I've edited the question. $\endgroup$
    – Anthony
    Apr 27, 2014 at 13:07
  • 2
    $\begingroup$ 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. $\endgroup$
    – DrLecter
    Apr 27, 2014 at 13:24
  • $\begingroup$ @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. $\endgroup$
    – Anthony
    Apr 28, 2014 at 6:00
  • $\begingroup$ 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. $\endgroup$
    – DrLecter
    Apr 28, 2014 at 12:26

1 Answer 1


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 implementing such protocols you can take the following "rule of the thumb":

  • 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$).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.