2
$\begingroup$

There are some very large safe primes listed here: https://en.wikipedia.org/wiki/Safe_and_Sophie_Germain_primes

Would using any of them result in a secure DH construction? Generator is 2. The exponent would be of the same magnitude as the prime.

Performance impact of using such large numbers is irrelevant to the question.

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you want to use such large primes? Did you consider the cost? Are you afraid of Quantum Computers, then see NIST post quantum CRYSTALS-KYBER. The generator is not important. $\endgroup$
    – kelalaka
    Commented Dec 12, 2023 at 7:48
  • $\begingroup$ I find the idea of using very large moduli as a mitigation against the early (hypothetical) CRQC interesting. The reasoning is that the larger the modulus, the more coherent quantum gates are required (and I think that's rather more than proportional). The same idea would work with Schnorr groups, with less time and size penalty, especially for signature. $\endgroup$
    – fgrieu ♦
    Commented Dec 12, 2023 at 10:19
  • $\begingroup$ Kyber & McEliece are both used in our scheme. But given that performance impact is of no concern for our application the use of enormous field size DH was also suggested as a hedge. $\endgroup$
    – user113099
    Commented Dec 12, 2023 at 19:38
  • $\begingroup$ You may actually want to use RSA-KEM instead of DH for such large numbers. It's much faster than DH. 16384-bit DH takes ~1 second vs. 5ms encrypt and 200ms decrypt with RSA-16384. RSA key generation is much slower than DH key generation however. $\endgroup$
    – LightTunnelEnd
    Commented Dec 13, 2023 at 21:54

3 Answers 3

Reset to default
2
$\begingroup$

In terms of the computational complexity of solving the discrete logarithm on classical computational resources, any safe prime of 4096-bits or greater should be safe from this attack for the foreseeable future. This size should preclude not only general number field sieve attacks, but also special number field sieve attacks (note that SNFS attacks exist for all of the primes that you link to). However, this does not include:-

  • attacks by a quantum-capable adversary
  • attacks due to insufficient randomness in the choice of one or more private keys
  • sidechannel cryptanalysis
  • cryptovirologic attacks such as SETUP
  • attacks on insecure key management
  • software vulnerabilities leading to memory disclosure or overwrite
  • man-in-the-middle attacks due to weak authentication of the exchange
  • etc.

A secure Diffie-Hellman implementation is dependent on more than the choice of parameters (though weak choice of parameters are likely impossible to render secure).

Improve this answer
$\endgroup$
3
  • $\begingroup$ About why SNFS is the algorithm of choice for all of the primes linked to: if you have a rule of thumb for limits of $a$, $r$, $e$, $b$ such that SNFS is the algorithm of choice for modulus $a\,r^e±b$ (or same for that $a\,r^e±b\,s^f$ form I just learn about from wikipedia), please add this or a link! $\endgroup$
    – fgrieu ♦
    Commented Dec 12, 2023 at 10:12
  • 1
    $\begingroup$ Are there known large 100,000+ bit safe primes that are not vulnerable to SNFS? $\endgroup$
    – user113099
    Commented Dec 12, 2023 at 19:35
  • $\begingroup$ @James Arlington: the safe primes you consider are not really "vulnerable", because they are so large. They are only less invulnerable than random ones of the same size. You can ask a question about generating large random safe primes. If we used brute force search for $b=100,000$ bit, that would require testing about $(b\,\ln2)^2\approx5,000,000,000$ candidates, which would be hard. But here are ways to cut on that enormously, including generating something convincingly noting-up-my-sleeves, e.g. by restricting to $p$ with a remainder modulo small primes compatible with being a safe prime. $\endgroup$
    – fgrieu ♦
    Commented Dec 14, 2023 at 10:28
1
$\begingroup$

What you are trying to do is hedge against a quantum computer with large numbers. You will most certainly gain years over everyone else in doing so.

However using DH for this purpose is inefficient.

You should instead use MP-RSA (multi prime RSA). This is in fact the basis of pqRSA which contends to be immune to practical quantum computers entirely by having up to 1TB keys.

If you just go as far as having ~10 ~4,000-bit RSA primes you will almost certainly be the highest hanging fruit on the tree.

If you choose to go this route you might as well hybridize with Kyber and Mceliece - and you indicated you are doing that.

Improve this answer
$\endgroup$
-4
$\begingroup$

If I know the safe primes or where you got them from then I can get them from the same source and your security is broken.

Any primes “listed somewhere” should never be used.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Knowing the prime used for a Diffie-Hellman scheme does not affect the security. For this reason there are many well-known safe primes that are used as standard DH moduli (see e.g. appendix E of RFC 2412) $\endgroup$
    – Daniel S
    Commented Dec 12, 2023 at 12:49
  • $\begingroup$ @DanielS Please always link to the official RFC editor variant of the standard (just add "editor" to the Google search engine, as it manages to muck up the references to RFC's again). I'd rather have pointed out the more generic RFC 5114 (Additional Diffie-Hellman Groups) or RFC 3526 (same for IKE) for larger key sizes than these insecure ones. $\endgroup$
    – Maarten Bodewes ♦
    Commented Dec 12, 2023 at 13:14

Your Answer

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