1
$\begingroup$

I'm looking at the FIPS-186 standard. On page 88, it gives a table recommending the size of the base field for the elliptic curve versus the order $n$ of a point on the curve. The numbers don't seem to make sense. For example it says if the bit length of $n$ is between $161$ and $223$, then the bit length of the ambient finite field should be $192$. But if you go off these numbers, there's a good chance that $n$ will be bigger than the size of the elliptic curve group itself. For example, say $p \approx 2^{192}$ and the bit length of $n$ equals $223$. Then by Hasse's theorem, the number of points on the elliptic curve will be less than $2^{192} + 1 + 2^{96}$, which is much smaller than $n$.

Can someone explain to me what the table in the standard means?

$\endgroup$

1 Answer 1

2
$\begingroup$

SP 800-57, Table 2 (on page 54) defines five levels of security. For each of these levels of security, this table provides recommended ranges for the size of $n$, the order of the elliptic curve group used.

Table D-1 in FIPS 186 suggests appropriate base field sizes to meet each of the ranges.

For example, SP 800-57 suggests that curve orders of $160$-$223$ bits should only be used when less than $80$-bit security is required. FIPS 186 then suggests using $192$-bit $p$ in this case.

You are correct that a base field with order $p$ of bitlength $192$ would never give rise to an elliptic curve group with $223$-bit order. This is the reverse of how the table should be interpreted.

$\endgroup$
5
  • $\begingroup$ so should the table be read like: "if I want a security level of less than 80 bits, I should work over a subgroup of order 161-223 generated by a point on the elliptic curve. To find such a point quickly, my curve should be over $\mathbb F_p$ where $p$ is $192$ bits long" $\endgroup$ Apr 15, 2022 at 2:23
  • $\begingroup$ Also I'm not sure if I should make another question for this, but I also don't see why the parameters given in the FIPS table would generate curves resistant to the MOV attack and the Frey Ruck attack. Would you be able to clarify on that? Thanks! $\endgroup$ Apr 15, 2022 at 2:27
  • $\begingroup$ @cryptolearner : My quite limited understanding is that the Frey-Rück attack applies to pairings, rather than to standard Elliptic Curves groups. The later is the only kind of Elliptic Curve in FIPS 186-4, and IIRC SP 800-57. $\endgroup$
    – fgrieu
    Apr 15, 2022 at 13:41
  • $\begingroup$ > "To find such a point quickly, my curve should be over Fp where p is 192 bits long." - this doesn't have any relationship with choosing the generator point. It's just a recommendation for the field size so that the curve order is in the correct range. $\endgroup$ Apr 15, 2022 at 21:07
  • $\begingroup$ > "would generate curves resistant to the MOV attack and the Frey Ruck attack." - this depends on the curve, not $p$. The same document suggests specific curves that are considered secure by all known attacks. $\endgroup$ Apr 15, 2022 at 21:11

Your Answer

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

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