A Cryptographic Attack: Finding the Discrete Logarithm on Elliptic Curves of Trace One

The crux of elliptic curve cryptography, a popular mechanism for securing data, is an asymmetric problem. The elliptic curve discrete logarithm problem, as it is called, is hoped to be generally hard in one direction but not the other, and it is this asymmetry that makes it secure. This paper describes the mathematics (and some of the computer science) necessary to understand and compute an attack on the elliptic curve discrete logarithm problem that works in a special case. The algorithm, proposed by Nigel Smart, renders the elliptic curve discrete logarithm problem easy in both directions for elliptic curves of so-called "trace one." The implication is that these curves can never be used securely for cryptographic purposes. In addition, it calls for further investigation into whether or not the problem is hard in general.