Diffie-Hellman: *assumed* largest prime factor of order of $g$? I've read in several places:


some of my confusions about DDH assumption - comment by Thomas Pornin on his own post
Is there a key length definition for DH or DHE? - the answer by Tom Leek


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