# Why is the NIST recommendation for the private key exponent so much smaller than the modulus?

NIST recommends a 256-bit private key exponent for DLP with a 3072-bit modulus. This question answered how the modulus was chosen/calculated, however, why isn't the private key size closer to the modulus size? It would seem that if one achieves order equal to $$2^{256}$$, this would be a sufficient number of random private key exponent possibilities to make a brute force attack computationally infeasible? So why the disparity between $$2^{256}$$ private key and $$2^{3072}$$ modulus?

• For $128$-bit security the smallest exponent size is $256$ bits (due to generic DLP algorithms). The corresponding modulus size is $3072$ bits (due to subexponential algorithm in this group). But a $256$-bit exponent is definitely cheaper for computation than a $3072$-bit one. – corpsfini Jul 12 '19 at 15:01
• @corpsfini when you say "due to subexponential algorithm in this group" are you referring to the existence of some algorithm that undermines the unique powers generated by the cyclic group if the modulus isn't much greater than the key size? – JohnGalt Jul 12 '19 at 15:23
• I think the basic intution here is that we don't know any algorithms that recover a DLP private key $x$ in time much less than $\sqrt x$ while we do know how to recover any private key in fields in subexponential time in the size of the field. (Though I don't have any good references for this right now so no proper answer from me) – SEJPM Jul 12 '19 at 17:36
• In the multiplicative group of a finite field, the Index Calculus method (based on the number field sieve for factoring, or its variant) has a subexponential complexity in the size of the modulus, hence the big modulus. – corpsfini Jul 12 '19 at 22:14
• This paper (PDF) might be of interest to this question. – SEJPM Jul 14 '19 at 20:50

Generic algorithms for solving the DLP, like Shanks baby step-giant step or pollard rho are of complexity of order $$\mathcal{O}(|G|^{0.5})$$. That is, for $$|G|=2^{256}$$ you get a complexity of $$\mathcal{O}(2^{128})$$. However, for the index calculus method, that is operated on the modulus, for complexity of $$\mathcal{O}(2^{128})$$ you would need a modulus of size 3072 bits. You may use larger exponent, but this will result in more complex calculations, while the security remains $$\mathcal{O}(2^{128})$$