40
$\begingroup$

Wikipedia says in reference to the elliptic curves officially recommended by NIST in FIPS 186-3:

Five prime fields for certain primes p of sizes 192, 224, 256, 384, and 521 bits. For each of the prime fields, one elliptic curve is recommended.

The first four bit sizes are immediately familiar from other cryptographic algorithms, but 521 seems to be the odd man out. Wikipedia even includes a footnote assuring readers that it is not a typo:

The sequence may seem suggestive of a typographic error. Nevertheless, the last value is 521 and not 512 bits.

Is there a cryptographically-sound reason for 521 bits instead of a more conventional power-of-two? If so, what is it — or if not, why and how was 521 chosen?

Improve this question
$\endgroup$
3
  • 13
    $\begingroup$ I guess $2^{521}-1$ being prime was too nice to pass up. $\endgroup$
    – CodesInChaos
    Commented Feb 3, 2013 at 23:05
  • $\begingroup$ I do know that it's not fun to work with keys not on a byte boundary though. Brainpool curves have been designed to have all their parameters nicely on byte boundaries, including the highest curve being defined for 512 bit key sizes. $\endgroup$
    – Maarten Bodewes ♦
    Commented Sep 22, 2014 at 0:32
  • 4
    $\begingroup$ Primes of this form $2^n-1$ are known as Mersenne primes. $\endgroup$
    – CodesInChaos
    Commented Oct 21, 2014 at 12:01

1 Answer 1

Reset to default
33
$\begingroup$

I very much suspect it's to related to the fact that $2^{521}-1$ is prime. The previous similar prime is $2^{127}-1$ and the next such is $2^{607}-1$ so they're quite rare. Elliptic curve operations on such a field can be implemented somewhat faster than over another prime field with similar size but without this special form.

I very much doubt that serious thought went into this decision at all. If there are no breakthroughs in elliptic curve logarithm finding then 521-bit coordinate components are complete overkill. If there were a suitable breakthrough then there's no guarantee that 521 bits would be enough. Elliptic curves tend to be used when the size becomes a factor in the design of a system. It's hard to imagine what sort of constraints would have to operate to make a 521 bit curve order make sense.

Improve this answer
$\endgroup$
3
  • $\begingroup$ That seems, to me, like saying AES 256-bit is overkill compared to AES 128. ECIES on a 521 bit curve can be used for public key encrypted systems, for example. Pretty reasonable constraint, IMO. $\endgroup$
    – Erik Aronesty
    Commented Nov 21, 2018 at 20:51
  • 5
    $\begingroup$ In contrast to, say, edwards448, E-521 is overkill, which is why the CFRG adopted edwards448 and not E-521 for RFC 7748: edwards448 obtains a much higher security level than edwards25519—so much higher than an already high 128-bit security level for edwards25519 that it would take a cryptanalytic breakthrough for the difference to have any meaning whatsoever—and much higher performance than E-521. But AES-256 actually attains the standard 128-bit security level, while AES-128 does not. $\endgroup$
    – Squeamish Ossifrage
    Commented Apr 27, 2019 at 13:51
  • $\begingroup$ Does the eliptic curve algo rely or use primes still? I assume it's closer to Pi. Or is this bit-depth more of a subtle in-joke the point of using 2^521−1? I heard the solutions are always integers whereas the false outcomes are floating points. That sounds pretty sick security! $\endgroup$
    – Tomachi
    Commented Dec 10 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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