Annals of Computer Science and Information Systems, Volume 15

DOI: http://dx.doi.org/10.15439/2018F197

Citation: Proceedings of the 2018 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 15, pages 363–368 (2018)

Full text

Abstract. Elliptic Curve Method (ECM) is a well-known method for factoring integers, which is usually used in the Number Field Sieve algorithm as a subroutine for factoring smaller integers than the targeted one. ECM is called many times and can be executed in parallel for different inputs. This method mainly consist of simple operations on elliptic curves. Thus, ECM is suitable for hardware implementations that can efficiently reduce computational time. This work describes a new, improved FPGA-based hardware accelerator for ECM, designed for large scale computations. Our accelerator can operate with an on board ARM processor or with an external host computer. This design can factor several numbers at once and can be easily ported to various FPGA boards. Different methods for improving results (e.g. the use of DSP blocks, cache-rgisters, reorganizing instruction order) are described and their performance is analyzed. As a result, one of the fastest hardware ECM units is achieved.

References

1. H. W. Lenstra, “Factoring Integers with Elliptic Curves” Annals of Mathematics, vol. 126, no.2, pp. 694–673, 1985.
2. A. K. Lenstra and H. W. Lenstra, “The Development of the Number Field Sieve” Lecture Notes in Math, Volume 1554, 1993.
3. R. P. Brent, “Some integer factorization algorithms using elliptic curves,” Australian Computer Science Communications, vol. 8, pp. 148-163, 1986.
4. P. L. Montgomery, “Speeding the Pollard and elliptic curve methods of factorization,” Mathematics of Computation, vol. 48, pp. 243-264, 1987.
5. P. L. Montgomery, “Modular Multiplication Without Trial Division,” Mathematics of Computation,, vol. 44, pp. 519-519, 1985.
6. K. Gaj et al., “Area-time efficient implementation of the elliptic curve method of factoring in reconfigurable hardware for application in the number field sieve,” IEEE Transactions on Computers, vol. 59, pp. 1264-1280, 2010/9
7. K. Gaj, M. Huang, S. Kwon, T. A. El-Ghazawi, “An Optimized Hardware Architecture for the Montgomery Multiplication Algorithm,” Public Key Cryptography, , 2008
8. M. Andrzejczak, “Koprocesor kryptograficzny wspierajacy faktoryzacje liczb metoda krzywych eliptycznych,” [Konferencja mlodych naukowcow wiwat 2017, Falenty, Polska, 2017], in press.
9. K. Itoh, M. Takenaka, N. Torii, S. Temma, Y. Kurihara “Fast Implementation of Public-Key Cryptography on a DSP”, [Cryptographic Hardware and Embedded System], 2002.
10. G. de Meulenaer, F. Gosset, G. de Dormale, J. Quisquater, “Integer Factorization Based on Elliptic Curve Method: Towards Better Exploitation of Reconfigurable Hardware”, [15th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM 2007)], Napa, CA, 2007, pp. 197-206.
11. R. Zimmermann, “Optimized Implementation of the Elliptic Curve Factorization Method on a Highly Parallelized Hardware Cluster”, Master Thesis, TU Braunschweig, 2009 r.