How is the recommended NIST modulus for DLP chosen/calculated?

Question

NIST recommends a 256-bit private key exponent for DLP with a 3072-bit modulus. From this answer it appears that the range of private key numbers is derived by calculating a prime modulus via $2⋅p$ where $p$ is a 256-bit prime and then adding $1$ to the result (e.g. $2p+1$). If the result $n$ is a prime number and $a$ in $a^2 \pmod{n} \ne 1$, then we can use $n$ as the modulus.

I believe the difference in the recommended size between the private key (256-bit) and the modulus (3072-bit) has to do with the General Number Field Sieve Attack which has to do with the size of the modulus and not the size of the private key exponent. So the modulus needs to be much larger than the private key exponent.

My question is how the 3072 modulus derived? Not to implement my own of course, but to understand how it works. For example, does one simply choose a 3071-bit prime, multiply it by $2$ and add $1$, testing for whether the result is prime? If it is prime then check whether $a^2 \pmod{n} \ne 1$, and if it's not, then we can choose $2$ for the base a random private key exponent that's at least 256-bits and know that the best attacks will still require $\sqrt{2^{256}}$ brute force exponentiations to determine the private key exponent?

Answer 1

How is the 3072-bit modulus derived?

Find the smallest $c$ such that $$p = 2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi\rfloor + c)$$ and $q = (p - 1)/2$ are prime, and $p \equiv 7 \pmod 8$. In this case, $n = 3072$ and so $c = 1690314$.

Use $g = 2$ as the generator.

(Here $\pi = \int_{-1}^1 dx/\sqrt{1 - x^2} = 4/[1 + \mathrm K_{i=1}^\infty i^2/(2i - 1)]$ as is customary.)

---

Why this shape?

This follows the procedure of RFC 2412, Appendix E, and matches Group 15 of RFC 3526:

1. We choose $p$ to be a safe prime—that is, choose $p$ so that $q = (p - 1)/2$ is also prime—so that the only subgroup orders are $\{1, 2, q, 2q\}$, which limits Lim–Lee active small-subgroup attacks.

2. We choose $p \equiv 7 \pmod 8$ so that, by the law of quadratic reciprocity, $g = 2$ has prime order $q$, since $g = 2$ is a convenient base, and a composite-order subgroup would leak some of the secret exponent.

   (If your key is $h \equiv g^x \pmod p$ and $g$ generates the whole group or a composite-order subgroup rather than a prime-order subgroup other than $\{-1,1\}$, then it is easy to tell whether $x$ is even or odd by testing whether $h^{(p - 1)/2} \equiv 1 \pmod p$ or not; the same idea generalizes to composite $q$.)

3. We choose a shape with no particularly nice pattern to prevent SNFS attacks.

4. We choose specifically the semi-rigid RFC 3526 groups from the RFC 2412 process with the particular nothing-up-my-sleeves constant $\pi$—rather than $e$ or $\sqrt 2$ or $\cos 1$ or, worse, randomly chosen bits—to give slightly more confidence that there is no back door in the prime choice.

Actually, even better, we just use the elliptic-curve-based X25519 which is faster, safer, and free of magic constants like $\pi$!