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.)

  • $\begingroup$ Usually the cofactor is small, so you can find it either by trial division or by Lenstra's elliptic curve factorization algorithm (normally trial division is sufficient), and then test the quotient for primeness. $\endgroup$ – j.p. Jun 27 '13 at 7:01
  • 2
    $\begingroup$ Typical co-factors are 1, 2, 4 and 8 i.e. very small. $\endgroup$ – CodesInChaos Jun 27 '13 at 12:01

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.

  • 1
    $\begingroup$ OK...this helps. However, it doesn't rigorously answer the question about how many curves you need to go through. Is the distribution of curve orders uniform in the Hasse interval? $\endgroup$ – user432944 Jun 28 '13 at 0:36

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.