RSA Laboratories

3.5.2 Are elliptic curve cryptosystems secure?

In general, the best attacks on the elliptic curve discrete logarithm problems have been general brute-force methods. The current lack of more specific attacks means that shorter key sizes for elliptic cryptosystems appear to give similar security as much larger keys that might be used in cryptosystems based on the discrete logarithm problem and integer factorization. For certain choices of elliptic curves there do exist more efficient attacks. Menezes, Okamoto, and Vanstone [MOV90] have been able to reduce the elliptic curve discrete logarithm problem to the traditional discrete logarithm problem for certain curves, thereby necessitating the same size keys as is used in more traditional public-key systems. However these cases are readily classified and easily avoided

In 1997, elliptic curve cryptography began to receive a lot more attention; by the end of 1999, there were no major developments as to the security of these cryptosystems. The longer this situation continues, the more confidence will grow that they really do offer as much security as currently appears. However, a sizeable group of very respected researchers have some doubts as to whether this situation will remain unchanged for many years. In particular, there is some evidence that the use of special elliptic curves, sometimes known as Koblitz curves, which provide very fast implementations, might allow new specialized attacks. As a starting point, the basic brute-force attacks can be improved when attacking these curves [Wie98]. While RSA Laboratories believes that continued research into elliptic curve cryptosystems might eventually create the same level of wide-spread trust as is enjoyed by other public-key techniques (provided there are no upsets), the use of special purpose curves will most likely always be viewed with extreme skepticism.

Top of the page