Consider the DSA key generation:

  1. A large prime $p$ is chosen;
  2. A smaller modulus $q$ is chosen such that $p - 1$ is a multiple of $q$;
  3. A generator $g$ s.t. $\operatorname{ord}_p(g) = q$ is chosen.

My question is -- why do we require that $p - 1$ be a multiple of $q$? Is there any underlying mathematics I'm missing? Thanks.

  • 3
    $\begingroup$ Lagrange's theorem. $\endgroup$ – SEJPM Dec 12 '15 at 22:19
  • 3
    $\begingroup$ That is, if $q$ isn't a divisor of $p-1$, then there won't be a subgroup of size $q$ $\endgroup$ – poncho Dec 12 '15 at 22:20
  • $\begingroup$ Thanks guys. I almost thought of it myself. Feel free to write an answer so that I can accept it. $\endgroup$ – d125q Dec 12 '15 at 22:21
  • $\begingroup$ It's actually done the other direction: find prime q of the desired size (e.g. 256 bits) then find prime p = kq+1 of the desired size (e.g. 2048 bits). 'find' can either be 'choose a random candidate and test (Miller-Rabin plus optional Lucas)' or 'construct from half-size primes, recursively (Shawe-Taylor) and tweak'. See A.1 C.3 C.6 of FIPS186, on the NIST CSRC website on days the President isn't having a temper tantrum. $\endgroup$ – dave_thompson_085 Jan 17 at 5:50

As was noted in the comments the reason for $q$ having to divide $p-1$ is Lagrange's theorem:

Lagrange's theorem [...], states that for any finite group $G$, the order (number of elements) of every subgroup $H$ of $G$ divides the order of $G$.

In the case of DSA we are working in subgroups of $\mathbb F_p$ (which has order $p-1$). By Lagrange's theorem every subgroup has to have an order $q$ such that $q$ divides $p-1$.


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.