4
$\begingroup$

I've read in several places:

that somehow the largest prime factor $q$ of $|g|$ (order of $g$) is assumed to be large enough without actually knowing $q$. How do they do that?

The only method I'm aware of is to start with a large enough prime $q$ and search for prime $p=nq+1$, then compute $g=a^{(p-1)/q}\pmod{p}$ for some random $a$. So the order of $g$ is $q$ if $g\neq 1$.

$\endgroup$
  • $\begingroup$ This may help. $\endgroup$ – mikeazo Dec 19 '15 at 3:53
  • $\begingroup$ Basically, smooth integers are rare (this is one reason why factoring is so hard, since sieve-type factoring algorithms require a lot of smooth numbers), so if $p$ is randomly chosen, it is highly unlikely that $p-1$ will be smooth. $\endgroup$ – fkraiem Dec 19 '15 at 4:31
2
$\begingroup$

I've read in several places that somehow the largest prime factor $q$ of $|g|$ (order of $g$) is assumed to be large enough without actually knowing $q$. How do they do that?

Actually, both references talk about the behavior of the TLS client when negotiating a DHE-based ciphersuite. The server proposes $p$ and $g$ as a part of the exchange, and hence the client doesn't know $q$. This doesn't mean that $q$ is unknown, only that the client must trust that the server generated the group properly (which isn't totally unreasonable, as the client needs to trust the server to do other things properly as well). Now, it would have been reasonable for the server to include the value $q$ as well (so a paranoid client could check it); they didn't include that in the protocol.

The only method I'm aware of is to start with a large enough prime $q$ and search for prime $p=nq+1$...

That is certainly one method which is used in practice. An alternative method would be to search for a Sophie-Germaine prime, that is, two values $p$ and $q = (p-1)/2$ which are prime simultaneously; in this case, any quadratic residue (other than 1, of course) would work as a generator. This takes a bit of more work than the method you listed; however if you're generating a group once, this is irrelevant.

$\endgroup$
  • $\begingroup$ (In particular, if the server itself is malicious, then the whole TLS is pointless.) ​ ​ $\endgroup$ – user991 Dec 19 '15 at 6:14
  • 1
    $\begingroup$ @RickyDemer: this is true; however it's possible that the server is well meaning but clueless... $\endgroup$ – poncho Dec 19 '15 at 14:38

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.