Is there an algorithm to check if an elliptic curve is secure?

Question

As I understand it elliptic curves are of the form $y^2 = x^3 + ax + b$ Where $a$ and $b$ are the curve parameters. However not all parameters will give a curve suitable for crypto purposes. Is there a known algorithm that can evaluate a pair of numbers $(a,b)$ and return YES if they are valid ECC parameters. Is this algorithm deterministic or probabilistic ?

Answer 1

Let's suppose that you work in field $\mathbb{F}_p$ for a prime $p$; i.e. the $x$, $y$, $a$ and $b$ values are integers modulo $p$. The curve order $n$ is the number of points on the curve. By Hasse's theorem we know that $n$ is relatively close to $p$; namely, the theorem states that: $$|n-(p+1)| \leq 2\sqrt{p}$$ So you get a range of possible values for $n$. The exact value depends on $a$ and $b$.

For cryptography, you normally need $n$ to be the multiple of a big enough prime. "Big enough" means $2b$ bits if you are after a "security level" of $b$ bits (i.e. resistance to attacks for a work factor of at least $2^b$). In practice, to make things simpler, you will want $n$ (the complete curve order) to be prime. So the algorithm you seek is roughly:

1. Compute the curve order. This uses Schoof's algorithm or a variant thereof. This yields $n$.
2. Check that $n$ is prime. If not, try again with new values for $a$ and/or $b$.
3. Do some extra checks.

The "extra checks" are about the MOV and FR attacks, which use pairings. This is a complex matter; to make the story short, there is a value called the embedding degree which is the smallest integer $k \geq 1$ such that $n$ divides $p^k-1$. Your curve will be safe if $k$ is high enough; it suffices that $k\geq 100$ (and that's with a wide error margin). In practice, with random $a$ and $b$, $k$ will be very high with overwhelming probability; however, testing all values $k$ from $1$ to $100$ is easy enough, so testing it is not a big issue. ANSI X9.62 recommends that test.

Schoof's algorithm (step 1) is deterministic. There are deterministic algorithms for primality, but usually we use Miller-Rabin, which is probabilistic but much more efficient. In any case, difference between deterministic and probabilistic has little practical relevance, because there is no computer which is really 100.0% reliable; a stray cosmic ray can still flip a transistor at the right time (or the wrong time, depending on your point of view). If you use Miller-Rabin with 50 iterations, you will get as much certainty of primality as you could ever get in the Physical World.

---

All of the above assumes that $a$ and $b$ are chosen randomly. Actually, $a$ can be fixed to some value (many standard curves use $a = p-3$, which yields a slight computational advantage in some implementations of point addition). If $a$ and $b$ are not chosen randomly, but with specific features, then you could obtain a weak(er) curve. Or you could loop forever; for instance, if you choose $a$ and $b$ such that the curve is a Montgomery curve, then $n$ is always a multiple of $4$, hence never a prime.

(See the Handbook of Elliptic and Hyperelliptic Curve Cryptography for details. The Guide to Elliptic Curve Cryptography is also a nice book; less complete but still full of information, and possibly clearer in its practical aspects.)