3
$\begingroup$

Looking at the following NIST recommendations for a discrete logarithm, for 2016-2030 and beyond they list 3072-bit number for the group and 256-bit for the key.

If using Diffie-Hellman, does group equal the recommended size of the prime modulus and key equal the recommended size of the private key exponent?

$\endgroup$
3
$\begingroup$

Yes, when using cryptosystems based on the difficulty of the Discrete Logarithm in $\Bbb Z_p^*$ or a subgroup thereof, a key size recommendation of a 3072-bit group means that the modulus $p$ is 3072-bit, and a 256-bit key implies that a private exponent (a key) is 256-bit.

In some (as far as I know: all) NIST contexts, a 256-bit key additionally implies that the order of the public generator $g$ is a 256-bit prime $q$, and (thus) that $p-1$ has that 256-bit prime factor $q$, and public keys belong to a subgroup of $\Bbb Z_p^*$ having order $q$. The generation of $p$ and $q$ is described in FIPS 186-4 appendix A (Dave Thompson's comment explains that's for various sizes including 3072/256).

In all contexts, a private exponent should be at least twice as wide as the security level in bits, which guards against Baby-step giant-step and Pollard's rho. It is good and customary that $p-1$ has a large prime factor $q$, and that the order of the generator $g$ is a multiple of that $q$. That $q$ should be at least twice as wide as the security level in bits, which guards against Pohlig-Hellman.

The width of $p$ is dictated by resistance to a Discrete-Log extension of GNFS, which is why recommendations for this parameters match those for RSA public moduli.

In Diffie-Hellman, it can (but need not) be chosen $p$ such that $q=(p-1)/2$ is prime, and thus $g$ of order $(p-1)/2$ or $p-1$, even when the key is narrower.

$\endgroup$
  • $\begingroup$ The 'backward compatibility' verification in 186-4 A.1.1.1, for parameters generated per now-obsoleted 186-2, is only 1024/160, but the current procedures in A.1.1.2-3 and A.1.2.1-2 use the sizes defined in 4.2 (referenced by A.1) which are 1024/160 2048/224 2048/256 3072/256 constrained by SP800-57 whose rev3 in 2012 prohibited signing with 1024/160 (80-strength) after 2013, and the next two (112-strength) after 2030. Cf crypto.stackexchange.com/questions/19005/… $\endgroup$ – dave_thompson_085 Feb 12 at 2:00

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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