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?

  • 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$ – corpsfini Jul 12 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$ – JohnGalt Jul 12 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$ – SEJPM Jul 12 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$ – corpsfini Jul 12 at 22:14
  • 2
    $\begingroup$ This paper (PDF) might be of interest to this question. $\endgroup$ – SEJPM yesterday

Your Answer

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

Browse other questions tagged or ask your own question.