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?
$\begingroup$
$\endgroup$
10
-
2$\begingroup$ 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. $\endgroup$– user69015Commented Jul 12, 2019 at 15:01
-
1$\begingroup$ @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? $\endgroup$– JohnGaltCommented Jul 12, 2019 at 15:23
-
2$\begingroup$ 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) $\endgroup$– SEJPMCommented Jul 12, 2019 at 17:36
-
2$\begingroup$ 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. $\endgroup$– user69015Commented Jul 12, 2019 at 22:14
-
2$\begingroup$ This paper (PDF) might be of interest to this question. $\endgroup$– SEJPMCommented Jul 14, 2019 at 20:50
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
3
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})$
-
1$\begingroup$ Just thought you might like to know: You can use mathjax to format your posts, it makes the parts that contain notation look much nicer and easier to read. $\endgroup$ Commented Jul 18, 2019 at 20:36
-
$\begingroup$ I do not quite get "that is operated on the modulus". If "that" refers to "complexity", is is meant something beyond: complexity of index calculus is a function of the modulus (size)? $\endgroup$– fgrieu ♦Commented Jul 18, 2019 at 21:43
-
$\begingroup$ Should be "The complexity of the index calculus method is a function of the modulus" $\endgroup$ Commented Jul 19, 2019 at 5:32