The use of elliptic curves in cryptography

Abstract

The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor Miller in 1985. Being a relatively new field, there is still a lot of ongoing research on the subject, but elliptic curve cryptography, or ECC for short, has already been implemented in real-life applications. Its strength was proved in 2003 when the U.S. National Security Agency adopted ECC for protecting information classified as mission-critical by the U.S. government. The security of public-key cryptographic systems that can be considered secure, efficient, and commercially viable is directly tied to the relative hardness of their underlying mathematical problems. In the case of ECC, this mathematical problem is to solve the discrete logarithm problem over elliptic curves, or ECDLP for short. Because the best-known way to solve ECDLP is fully exponential, we can use substantially smaller key sizes to obtain equivalent strengths compared to other systems. Hence, ECC provides the most security per bit of any public-key scheme known. In this thesis we have focused on presenting the known attacks on the ECDLP. We started by introducing some basic facts from the theory of elliptic curves. In the rest of the thesis we have described, analyzed and presented running time estimates of attacks on the ECDLP. This included a presentation of attacks which are specially designed to exploit weaknesses in the structure of some classes of elliptic curves. We have also presented attacks which can be used to solve the ECDLP over general elliptic curves. This included Pollard’s rho and lambda algorithms, where the former was used for solving the ECDLP challenges set by the Certicom company.