I understand that given solutions for solving a discrete logarithm problem are on the order of 𝑂(2𝑛/2), ergo, 256bit private keys based on 25519 or secp256k1 have an effective bit strength of 128bits.

I was wondering if anyone could explain how one can know the largest size private key supported by a curve. Is it to do with the curves prime field? I'm just trying to learn a bit more about ECC.

As people slowly look at RSA 3072+ as archaic and not strong enough, I wonder how long before 128bit strength ECC goes the same way.

Do we have any non NIST (NSA backdoored :) ) curves which support 512 bit private keys (yielding 256bit security?).

Thanks, John

  • 1
    $\begingroup$ First, the NIST curves themselves are most likely not backdoored (we have a question about this on this site), so P-521 should do. Second, have a look at Curve448 ("Goldilocks"). $\endgroup$ – SEJPM May 10 '19 at 12:37
  • $\begingroup$ @SEJPM thanks! I was being a little facetious regarding the NSA. Can I ask you how I can tell the largest key supported by a curve? What's the property of a curve that dictates this? $\endgroup$ – Woodstock May 10 '19 at 13:06
  • 2
    $\begingroup$ The curve order (which is closely related to the size of the underlying field / prime) $\endgroup$ – SEJPM May 10 '19 at 13:07
  • $\begingroup$ @SEJPM thank you $\endgroup$ – Woodstock May 10 '19 at 13:11
  • 3
    $\begingroup$ That said: there is no particular reason to doubt a 128-bit security level today; the main predictable threats beyond unpredictable breakthroughs in cryptanalysis are the possibility of large quantum computers, which would devastate elliptic curve cryptography and RSA, and operational or implementation errors like not doing cryptography at all because it's too inconvenient or costly. You are probably better off just using X25519/Ed25519 for key agreement/signature, or secp256k1, because there are widely available high-quality low-cost implementations. $\endgroup$ – Squeamish Ossifrage May 10 '19 at 14:40

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.