One of the necessary components to the Schnorr Digital Signature scheme is a pair of prime numbers p and q such that q divides p-1. However, there is never a modular inverse taken of q so why is there an extra constraint on q? Couldn't q be a number that divides p-1 but not prime?
Tell me more
×
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.
|
|
|
First of all, while Schnorr Signatures are usually described that way, the two primes are not necessary for it to work. In principle, Schnorr works in any cyclic group. However, to achieve security we need that the discrete logarithm problem in that group is hard. So the reason for the choice of $q$ (which is the group order) is that DL is believed to be hard in subgroups of prime order $q$ of $\mathbb{Z}_p^*$, where p is a safe prime, i.e. $p=2q+1$. (And also for other values than $2$, but I'm currently not sure what the conditions are.) |
|||
|
|
