Hardware Factorization Based Elliptic Curve Method

M. Simka, Jan Pelzl, T. Kleinjung, J. Franke, C. Priplata, C. Stahlke, M. Drutarovsky, V. Fischer, Chris­tof Paar

IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2005, Napa, CA, USA, April 17-20, 2005.


The security of the most popular asymmetric cryptographic scheme RSA depends on the hardness of factoring large numbers. The best known method for factorization large integers is the General Number Field Sieve (GNFS). Recently, architectures for special purpose hardware for the GNFS have been proposed [5, 12]. One important step within the GNFS is the factorization of mid-size numbers for smoothness testing, an ef?cient algorithm for which is the Elliptic Curve Method (ECM). Since the smoothness testing is also suitable for parallelization, it is promising to improve ECM via special-purpose hardware. We show that massive parallel and cost ef?cient ECM hardware engines can improve the cost-time product of the RSA moduli factorization via the GNFS considerably