# Hide a weakness in ECC by choosing the prime or one of the curve coefficients

Suppose you are given a value $c$. Can you find a prime $p$ and an integer $b$ such that the elliptic curve

$$E: y^2 \equiv x^3 -3x + b \pmod p$$

is cryptographically weak? You need to choose $p,b$ so that all of the following restrictions also hold:

1. $p$ has some desired size (say, 256 bits)

2. $1 < b < p$ and $1 < c < p$

3. $b^2 c \equiv -27 \pmod p$

4. the order $n$ of the curve is a prime number

By cryptographically weak, I mean that the discrete log problem is easy on the curve (or that some other standard cryptographic assumption is false).

Is there any known way to do this? Is there a procedure to find $p,b$ (as a function of $c$) satisfying all these conditions, where the procedure succeeds with non-negligible probability (say, probability $\ge 1/10^{12}$)? Or, is there a proof or heuristic argument that doing so is likely to be impossible?

Basically, this amounts to asking whether there's any way to ensure that the resulting elliptic curve has a non-trivial probability of being cryptographically weak, given ability to choose some (but not all) of the curve parameters.

(For instance, maybe you could choose $b$ however you like, factor $b^2c+27$, select an appropriate divisor as $p$, and hope that the resulting curve is vulnerable to some particular attack; or who knows what. Your choice of strategy.)

Motivation: If this problem has a solution, then it means that the NSA could have hidden a backdoor in the NIST-recommended elliptic curves (specifically, the P-xxx curves). Thus, it has implications for how much trust we can put in the those standard curves.

Some small classes are known, (as Neves says) the curves with small embedding degree and the anomalous curves (order $n$ equals the prime $p$), but all of these were known back then (though not all of them by everyone in 1985, the MOV attack was a real attack, and the anomalous curves were an attempt to block the MOV attack, I think). So these classes are hard to hit at random, and are easily detected anyway.