Elliptic curve parameter generation

Question

I am curious of the details of how one would go about generating elliptic curve parameters. (I know standardized parameters exist, but I'm trying to understand both how they were generated and the general case.)

Let's also assume we want to work in a prime-order subgroup of size $O(2^n)$. For simplicity, let's work over a prime-order field $F_p$.

As I understand it, the basic idea is (1) generate a random elliptic curve $E$ over $F_p$; (2) use a point-counting algorithm to count the number of points $N = |E(F_p)|$; finally, (3) check that $N$ is divisible by an $n$-bit prime

I am confused about the 3rd step: how is it implemented efficiently without using a general-purpose factoring algorithm? Also, how many iterations are required (in expectation) before finding a curve $E$ whose order $N$ is divisible by an $n$-bit prime? Finally, given $n$, how should we best choose $p$? (This is related to the question of what co-factor one should be looking for.)

Answer 1

First of all, for elliptic curves based on a prime field $F_p$, we always work with a prime $p$ that is the same size as our target subgroup.

The reason is quite simple: we could work in a proper subgroup based on a larger curve, but what would that buy us? It becomes more costly (as all our internal computations are modulo $p$, and if $p$ is larger, those operations are more expensive), and it doesn't make it any more secure; the best attack still involves $O(2^{n/2})$ operations.

A side effect of this decision is to make step 3 quite simple.

$N$ will always be in the "Hasse interval"; $p - 2 \sqrt{p} + 1 \le N \le p + 2 \sqrt{p} + 1$, or in other words $N \approx p$. Since $p$ is an n-bit number, that means that if $N$ were to have an n-bit factor, well, $N$ would have to be that n-bit factor (there is a possibility is that $p = 2^{n} - \epsilon$, where $\epsilon < 2 \sqrt{p}$; in that case $N \ge 2^n$ is possible; I'll ignore that corner case)

So, step 3 is effectively "test $N$ for primality"; that can be implemented quite efficiently.

As for your other questions:

• The number of curves you'd expect to go through: if the probability of a curve order being prime is approximately the probability of a random number in the Hasse interval being prime, then we'd have an expected $\log{p}$ iterations. However, I'm not certain about true that assumption is; I expect it is close.

• What size of $p$ do we want? As above, we pick a cofactor of 1, with $p$ being an $n$-bit prime; again, we could use a larger prime, but there doesn't appear to be any benefit from doing so.

Answer 2

As a follow up to your question on the distribution of elliptic curve orders. The distribution is roughly semi-circular (to be precise its the class number of the quadratic field where the curve is the reduction of a curve with complex multiplication over that quadratic field). In practice this is only a second order effect is searching for prime order elliptic curve group and one should still expect to find these after $n\log 2$ or so attempts.

An alternative approach is to decide to use a curve with complex multiplication with small discriminant. This gives a parameterisation of possible characteristics and corresponding group orders. One can test the candidates until both are prime and then construct the appropriate curve. This is the method typically used in pairing-friendly cryptography where there are very stringent conditions on the relationship between curve order and characteristic.