4
$\begingroup$

Why there are abnormal field size like 521, 571, 233, 283 bits in prime and binary fields that are defined by NIST?

$\endgroup$
  • 2
    $\begingroup$ Reference: Recommended Elliptic Curves for Federal Government use (NIST, 1999). Indeed, that has a striking lack of justification of why $p=521$ rather than $p=512$ at the 256-bit level; why (exclusively past the 80-bit level) $m$ is significantly larger than the prime immediately above twice the security level; and how the corresponding fudge factors have been chosen. $\endgroup$ – fgrieu Jan 19 '17 at 7:50
  • 5
    $\begingroup$ @fgrieu wasn't 521 picked because $2^{521}-1$ (the modulus for the underlying field) is a Mersenne Prime (and thus offers speed advantages)? As for the other curves, the bear has already given the explanation. $\endgroup$ – SEJPM Jan 19 '17 at 8:27
  • $\begingroup$ The bear's explanation is adamant, but in this case the question is pretty different from the one linked to by SEJPM. I'm not sure if we should close the question. I guess we can at least answer for the 521 bit prime curve. $\endgroup$ – Maarten Bodewes Jan 19 '17 at 13:38
  • 1
    $\begingroup$ Bear has 'Restrict yourself to prime values of m to avoid possible weaknesses by plunging into sub-fields'; I'm pretty sure selecting m as a multiple of 8 (which it would need to be "byte-aligned") would imply that it's not prime... $\endgroup$ – poncho Jan 19 '17 at 16:30
1
$\begingroup$

There are some good answers in the comments, let me summarize and add a comment at the end.

Binary fields

For fields of the form $\mathbb{F}_{2^m}$, so field with $2^m$ elements, there are attacks which use the fact that $m$ is a composite number. So in practice you would want $m$ to be prime, and in particular not a multiple of 8. Therefore in this case you're out of luck, you can't have a "byte-aligned" field. This is what poncho mentions.

Prime fields

For fields of the form $\mathbb{F}_p$, you would want to choose a prime such that you can efficiently do field arithmetic. In other words, you want to give the prime some structure such that the modular reduction becomes easy. Examples are:

  • Mersenne primes, i.e. primes of the form $2^n-1$. This makes the modular reduction extremely fast. Unfortunately there don't exist many, and the smallest one which achieves a $256$-bit security level is $2^{521}-1$. This is what SEJPM remarks.
  • Since there are not many Mersenne prime, you want to choose something a little different. In the NIST documents, they use so-called Solinas primes. An example is the prime for P-256, which is $p=2^{256}-2^{224}+2^{192}+2^{96}-1$.
  • Any other structure. A commonly used one is $2^{255}-19$.

What is important, is that being "byte-aligned" is not necessarily useful. In fact, there are many implementation tricks which use the fact that it is not. Take for example $p=2^{127}-1$. Any integer mod $p$ fits in four 32-bit registers, but only needs 127 bits. There is one extra bit which is "free", and there are circumstances where you can use this bit to speed things up. This is usually what is referred to as using a "redundant representation".

A note: this is kind of an ongoing discussion, but there are arguments why primes with any kind of structure are less preferred. The reason is that the structure of the prime will in some sense be carried over the elliptic curve group. This can have downsides, for example it makes "additive scalar blinding" harder, which results in a slow-down. I'm not saying one way or the other is better, but be aware that there are different opinions on this.

$\endgroup$

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.