Score:1

Order of point on elliptic curve vs order of base field

hr flag

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?

Score:2
gb flag

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.

hr flag
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"
hr flag
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!
fgrieu avatar
ng flag
@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.
meshcollider avatar
gb flag
> "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.
meshcollider avatar
gb flag
> "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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.