An alternative cryptosystem, relying upon the difficulty of solving the "discrete logarithm problem" rather than factoring, was the topic of my seminar during Spring 1996. I'm interested in a particular case using "elliptic curves" (currently used in some cell phones), as well as a future case using number fields. Elliptic curves are also applied to factoring, and recent results using Lehigh's blaze cluster were reported in the Algorithmic Number Theory Symposium (ANTS VII), Berlin 2006. Readers at sites with access may view the paper at Springer online. Earlier results obtained using the old fire cluster are described at [ecmnet2004fin]. Further information may be obtained by following the ECMNET link.
For information on the Number Field Sieve "GNFS" algorithm, try browsing the links from the Lehigh webpage for the RSA130 factoring challenge. This algorithm was used in an extensive data collection effort ("sieving"), which produced a gigantic sparse matrix with 3,500,000 columns. The matrix equation was solved on a Cray C90, using 62 hours of CPUtime, breaking a 430-bit RSA key (130 decimal digits) into two 65-digit primes. While the RSA cryptosytem, used to provide security for web browsers and computer operating systems, currently relies upon 768-bit or 1024-bit keys; our computation [gave] the largest key broken in public, and [was] described at AsiaCrypt'96, a cryptography conference. An update on the above may be found at RSA Factoring Challege, for information on my part in breaking RSA-140 and RSA-155 (a 512-bit RSA-key) in 1999; or see the published paper Factorization of a 512-bit RSA Modulus . (For the RSA link, click "About RSA", then "RSA Laboratories", then "Historical", then "Cryptographic Challenges" and finally "The RSA Factoring Challenge". The 512-bit key is RSA-155, with 155-decimal digits.) The current record is RSA-768 (with 233-decimal digits), which used a parallel version of the matrix solving software. A publically available version currently runs on Lehigh's Corona cluster, using MPI. For sieving results obtained using Lehigh's SGI Origin computer cf. [snfs2004].
To go to Lehigh's home page, click here.
BRUCE A. DODSON