Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
3  
I guess $2^{521}-1$ being prime was too nice to pass up. –  CodesInChaos Feb 3 '13 at 23:05
add comment

1 Answer

up vote 9 down vote accepted

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 doubt that very much 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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