1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I'm trying to understand where (mod 8) is coming from? It appears that 3 is your starting prime that after multiplying by 2 and adding 1 you get 7. I would think 7 is the modulus? Where does 8 fit in the process? $\endgroup$ – JohnGalt Jun 18 at 14:34
  • 1
    $\begingroup$ 2 is a quadratic residue modulo $p$—and in this case consequently has order $q$—if and only if $p \equiv 7 \pmod 8$ or $p \equiv 1 \pmod 8$, by the law of quadratic reciprocity, and the only safe prime congruent to 1 modulo 4 is 5 so $p \not\equiv 1 \pmod 8$. $\endgroup$ – Squeamish Ossifrage Jun 18 at 17:48
  • $\begingroup$ Can you also speak to the advantages of using the formula for $p$ versus choosing random primes that are 3072-bits in length? And why 𝜋 is necessary generally in the generation of $p$? $\endgroup$ – JohnGalt Jun 18 at 22:58
  • 1
    $\begingroup$ @JohnGalt See point (4). $\endgroup$ – Squeamish Ossifrage Jun 18 at 23:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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