Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
One note: you can take (5) off the list; it is known that, on a curve of prime order, no member (other than the PoI, of course) is particularly weak; if we can solve the DLOG or cDH problem with one generator, we can solve them with any generator. If there is a weakness, it must reside in the combination of $p$ and $b$. –  poncho Sep 11 '13 at 0:30
    
Thanks, @poncho! Revised accordingly. I appreciate it. –  D.W. Sep 11 '13 at 2:38

1 Answer 1

Bernstein and Lange says that there has been no progress for prime-field elliptic curves since about 1999, when the NIST curves were chosen. No large class of weak curves were known then, and no large class is known now.

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.

The problem of embedding trapdoors in elliptic curves has been studied by Edlyn Teske, but she uses curves over extension fields, not prime fields. (Her techniques rely on it being hard to find isogenies between curves, but it is possible to find curves with isogenies. You choose one curve over an extension field that is secure, another that is not secure, and an isogeny between them. The isogeny is the trapdoor and allows you to move the DLOG instance from one curve to the other. The extension field attacks this relies on do not apply to NIST's extension field curves, as far as I know.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.