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$
2
  • $\begingroup$ This may help. $\endgroup$
    – mikeazo
    Dec 19, 2015 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, 2015 at 4:31

1 Answer 1

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$
2
  • $\begingroup$ (In particular, if the server itself is malicious, then the whole TLS is pointless.) ​ ​ $\endgroup$
    – user991
    Dec 19, 2015 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, 2015 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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