## Which curves? What order?

My academic advisor #3 asked those questions yesterday. And I got the answers from “Software Implementation of Elliptic Curve Cryptography over Binary Fields”, Darrel Hankerson, Julio Lopez Hernandez, and Alfred Menezes:

Which curves?

FIPS 186-2 has 10 recommended finite fields: 5 prime fields, and the binary fields $F_{2^{163}}$, $F_{2^{233}}$, $F_{2^{283}}$, $F_{2^{409}}$ and $F_{2^{571}}$. For each of the prime fields, one randomly selected eliptic curve was recommended, while for each of the binary fields one randomly selected elliptic curve and one Koblitz curve was selected.

The order

The fields were selected so that the bitlengths of their orders are at least twice the key lengths of common symmetric-key block ciphers – this is because exhaustive key search of a $k$-bit block sipher is expected to take roughly the same time as the solution of an instance of the elliptic curve discrete logarithm problem using Pollard’s rho algorithm for an appropriately-selected elliptic curve over a finite fied whose order has bitlength $2k$.