6
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

|improve this answer|||||
$\endgroup$
  • $\begingroup$ There are no conditions I'm aware of on the $k$ in $p = kq + 1$ other than that it be large enough for index calculus to be infeasible in $\mathbb Z/p\mathbb Z$, as long as you work with a standard generator of order $q$. Some folks call a group of this form a Schnorr group. $\endgroup$ – Squeamish Ossifrage Nov 19 '19 at 2:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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