22
$\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?

$\endgroup$
  • 5
    $\begingroup$ I guess $2^{521}-1$ being prime was too nice to pass up. $\endgroup$ – CodesInChaos Feb 3 '13 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 Sep 22 '14 at 0:32
  • 2
    $\begingroup$ Primes of this form $2^n-1$ are known as Mersenne primes. $\endgroup$ – CodesInChaos Oct 21 '14 at 12:01
18
$\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.

$\endgroup$
  • $\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 Nov 21 '18 at 20:51
  • $\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 Apr 27 at 13:51

Your Answer

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

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