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

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 ?

-
You also probably want to mention something about the field over which you're working in your security check? – figlesquidge Apr 11 '14 at 15:58
For what it's worth, I would conjecture the answer is 'no', because if nothing else we don't really know what makes a generic curve secure or not. We know some curves that seem secure, and we know curves that are not, but there are lots of curves where we don't really know. After all, even the secure ones may yet turn out to be insecure if progress is made on the EC-DLP. – figlesquidge Apr 11 '14 at 17:01

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

-