Area–time efficient hardware architecture for factoring integers with the elliptic curve method

Abstract : Since the introduction of public key cryptography, the problem of factoring large composites has been of increased interest. The security of the most popular asymmetric cryptographic scheme RSA depends on the hardness of factoring large numbers. The best known method for factoring large integers is the general number field sieve (GNFS). One important step within the GNFS is the factorisation of mid-size numbers for smoothness testing, an efficient algorithm for which is the elliptic curve method (ECM). Since smoothness testing is also suitable for parallelisation, the implementation of ECM in hardware is promising. We show that massive parallel and cost-efficient ECM hardware engines can improve the area–time product of the RSA moduli factorisation via the GNFS considerably. The computation of ECM is a classic example of an algorithm that can be significantly accelerated through special-purpose hardware. The authors thoroughly analyse the prerequisites for an area–time efficient hardware architecture for ECM. The authors present an implementation of ECM to factor numbers up to 200 bits, which is also scalable to other bit lengths. ECM is realised as a software–hardware co-design on a field-programmable gate array (FPGA) and an embedded microcontroller (system-on-chip). Furthermore, the authors provide estimates for state-of-the-art CMOS implementation of the design and for the application of massive parallel ECM engines to the GNFS. This appears to be the first publication of a realised hardware implementation of ECM, and the first description of GNFS acceleration through hardware-based ECM.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal-ujm.archives-ouvertes.fr/ujm-00289036
Contributor : Viktor Fischer <>
Submitted on : Thursday, June 19, 2008 - 3:54:26 PM
Last modification on : Thursday, February 7, 2019 - 2:22:19 PM
Long-term archiving on : Friday, May 28, 2010 - 10:39:45 PM

File

iee-ecm.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ujm-00289036, version 1

Collections

Citation

Jan Pelzl, Martin Simka, Thorsten Kleinjung, Milos Drutarovsky, Viktor Fischer, et al.. Area–time efficient hardware architecture for factoring integers with the elliptic curve method. Information Security, IEE Proceedings, 2005, 152 (1), pp.67-78. ⟨ujm-00289036⟩

Share

Metrics

Record views

249

Files downloads

320