Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

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

1 Answer 1

up vote 2 down vote accepted

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$).
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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