Abstract
This paper reports record-setting performance for the elliptic-curve method of integer factorization: for example, 926.11 curves/second for ECM stage 1 with B 1 = 8192 for 280-bit integers on a single PC. The state-of-the-art GMP-ECM software handles 124.71 curves/second for ECM stage 1 with B 1 = 8192 for 280-bit integers using all four cores of a 2.4 GHz Core 2 Quad Q6600.
The extra speed takes advantage of extra hardware, specifically two NVIDIA GTX 295 graphics cards, using a new ECM implementation introduced in this paper. Our implementation uses Edwards curves, relies on new parallel addition formulas, and is carefully tuned for the highly parallel GPU architecture. On a single GTX 295 the implementation performs 41.88 million modular multiplications per second for a general 280-bit modulus. GMP-ECM, using all four cores of a Q6600, performs 13.03 million modular multiplications per second.
This paper also reports speeds on other graphics processors: for example, 2414 280-bit elliptic-curve scalar multiplications per second on an older NVIDIA 8800 GTS (G80), again for a general 280-bit modulus. For comparison, the CHES 2008 paper “Exploiting the Power of GPUs for Asymmetric Cryptography” reported 1412 elliptic-curve scalar multiplications per second on the same graphics processor despite having fewer bits in the scalar (224 instead of 280), fewer bits in the modulus (224 instead of 280), and a special modulus (2224 − 296 + 1).
Permanent ID of this document: 6904068c52463d70486c9c68ba045839. Date of this document: 2009.01.26. This work was sponsored in part by the National Science Foundation under grant ITR–0716498, in part by Taiwan’s National Science Council (grants NSC-96-2221-E-001-031-MY3 and -96-2218-E-001-001, also through the Taiwan Information Security Center NSC-97-2219-E-001-001, -96-2219-E-011-008), and in part by the European Commission through the ICT Programme under Contract ICT–2007–216676 ECRYPT II. Part of this work was carried out while Bernstein and Lange visited NTU.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-642-01001-9_35
Chapter PDF
Similar content being viewed by others
Keywords
References
13th IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM 2005), Napa, CA, USA, April 17–20, 2005. IEEE Computer Society, Los Alamitos (2005); ISBN 0-7695-2445-1. See [44]
Aoki, K., Franke, J., Kleinjung, T., Lenstra, A.K., Osvik, D.A.: A Kilobit Special Number Field Sieve Factorization. In: ASIACRYPT 2007 [31], pp. 1–12 (2007) (Cited in §1, §1)
Atkin, A.O.L., Morain, F.: Finding suitable curves for the elliptic curve method of factorization. Mathematics of Computation 60, 399–405 (1993); ISSN 0025-5718, MR 93k:11115, http://www.lix.polytechnique.fr/~morain/Articles/articles.english.html (Cited in §2.2)
Bahr, F., Boehm, M., Franke, J., Kleinjung, T.: Subject: rsa200 (2005), http://www.crypto-world.com/announcements/rsa200.txt (Cited in §1)
Bahr, F., Franke, J., Kleinjung, T.: Discrete logarithms in GF(p) - 160 digits (2007), http://www.nabble.com/ (Cited in §1)
Bernstein, D.J.: How to build the 2009.01.23 standard workstation, http://cr.yp.to/hardware/build-20090123.html (Cited in §6)
Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted Edwards Curves. In: AFRICACRYPT [47], pp. 389–405 (2008), http://eprint.iacr.org/2008/013 (Cited in §2.2)
Bernstein, D.J., Birkner, P., Lange, T., Peters, C.: ECM using Edwards curves (2008), http://eprint.iacr.org/2008/016 (Cited in §2, §2.2, §2.2, §2.2)
Bernstein, D.J., Lange, T.: Explicit-formulas database (2008), http://hyperelliptic.org/EFD (Cited in §2.2, §5)
Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: ASIACRYPT 2007 [31], pp. 29–50 (2007), http://cr.yp.to/papers.html#newelliptic (Cited in §2.2, §2.2)
Boneh, D. (ed.): CRYPTO 2003. LNCS, vol. 2729. Springer, Heidelberg (2003); ISBN 3-540-40674- 3. See [43]
Cavallar, S., Dodson, B., Lenstra, A.K., Leyland, P.C., Lioen, W.M., Montgomery, P.L., Murphy, B., te Riele, H., Zimmermann, P.: Factorization of RSA-140 Using the Number Field Sieve. In: ASIACRYPT 1999 [33], pp. 195–207 (1999) (Cited in §1)
Cavallar, S., Dodson, B., Lenstra, A.K., Lioen, W.M., Montgomery, P.L., Murphy, B., te Riele, H., Aardal, K., Gilchrist, J., Guillerm, G., Leyland, P.C., Marchand, J., Morain, F., Muffett, A., Putnam, C., Putnam, C., Zimmermann, P.: Factorization of a 512-Bit RSA Modulus. In: EUROCRYPT 2000 [41], pp. 1–18 (2000) (Cited in §1, §1)
Cook, D.L., Ioannidis, J., Keromytis, A.D., Luck, J.: CryptoGraphics: Secret Key Cryptography Using Graphics Cards. In: CT-RSA 2005 [36], pp. 334–350 (2005) (Cited in §3)
Cook, D.L., Keromytis, A.D.: CryptoGraphics: Exploiting Graphics Cards For Security. In: Advances in Information Security, vol. 20. Springer, Heidelberg (2006); ISBN 978-0- 387-29015-7 (Cited in §3)
Cowie, J., Dodson, B., Elkenbracht-Huizing, R.M., Lenstra, A.K., Montgomery, P.L., Zayer, J.: A World Wide Number Field Sieve Factoring Record: On to 512 Bits. In: ASIACRYPT 1996 [28], pp. 382–394 (1996) (Cited in §1)
Dwork, C. (ed.): CRYPTO 2006. LNCS, vol. 4117. Springer, Heidelberg (2006); ISBN 3-540- 37432-9. See [27]
Edwards, H.M.: A normal form for elliptic curves. Bulletin of the American Mathematical Society 44, 393–422 (2007), http://www.ams.org/bull/2007-44-03/S0273-0979-07-01153-6/home.html (Cited in §2.2)
Franke, J., Kleinjung, T., Paar, C., Pelzl, J., Priplata, C., Stahlke, C.: SHARK: A Realizable Special Hardware Sieving Device for Factoring 1024-Bit Integers. In: CHES 2005 [42], pp. 119–130 (2005) (Cited in §1, §1)
Gaj, K., Kwon, S., Baier, P., Kohlbrenner, P., Le, H., Khaleeluddin, M., Bachimanchi, R.: Implementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware. In: CHES 2006 [23], pp. 119–133 (2006) (Cited in §1)
Galbraith, S.D. (ed.): Cryptography and Coding 2007. LNCS, vol. 4887. Springer, Heidelberg (2007); ISBN 978-3-540-77271-2. See [38]
Geiselmann, W., Shamir, A., Steinwandt, R., Tromer, E.: Scalable Hardware for Sparse Systems of Linear Equations, with Applications to Integer Factorization. In: CHES 2005 [42], pp. 131–146 (2005) (Cited in §1)
Goubin, L., Matsui, M. (eds.): CHES 2006. LNCS, vol. 4249. Springer, Heidelberg (2006); ISBN 3- 540-46559-6. See [20]
Hess, F., Pauli, S., Pohst, M.E. (eds.): ANTS 2006. LNCS, vol. 4076. Springer, Heidelberg (2006); ISBN 3- 540-36075-1. See [48]
Hisil, H., Wong, K., Carter, G., Dawson, E.: Faster group operations on elliptic curves (2007), http://eprint.iacr.org/2007/441 (Cited in §2.2)
Joux, A., Lercier, R.: Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method, Mathematics of Computation 72, 953–967 (2003) (Cited in §1)
Joux, A., Lercier, R., Smart, N.P., Vercauteren, F.: The Number Field Sieve in the Medium Prime Case. In: CRYPTO 2006 [17], pp. 326–344 (2006) (Cited in §1)
Kim, K., Matsumoto, T. (eds.): ASIACRYPT 1996. LNCS, vol. 1163. Springer, Heidelberg (1996); ISBN 3-540-61872-4. See [16]
Kleinjung, T.: Cofactorisation strategies for the number field sieve and an estimate for the sieving step for factoring 1024-bit integers. In: Proceedings of SHARCS 2006 (2006), http://www.math.uni-bonn.de/people/thor/cof.ps (Cited in §1, §1)
Koblitz, N., Menezes, A.: Pairing-Based Cryptography at High Security Levels. In: Coding and Cryptography [45], pp. 13–36 (2005) (Cited in §1)
Kurosawa, K. (ed.): ASIACRYPT 2007. LNCS, vol. 4833. Springer, Heidelberg (2007); See [2], [10]
Laih, C.-S. (ed.): ASIACRYPT 2003. LNCS, vol. 2894. Springer, Heidelberg (2003); ISBN 3-540-20592-6. See [35]
Lam, K.-Y., Okamoto, E., Xing, C. (eds.): ASIACRYPT 1999. LNCS, vol. 1716. Springer, Heidelberg (1999); ISBN 3-540-66666-4. See [12]
Lenstra Jr., H.W.: Factoring integers with elliptic curves. Annals of Mathematics 126, 649–673 (1987); ISSN 0003-486X, MR 89g:11125, http://links.jstor.org/sici?sici=0003-486X1987112:126:3649:FIWEC2.0.CO;2-V (Cited §1)
Lenstra, A.K., Tromer, E., Shamir, A., Kortsmit, W., Dodson, B., Hughes, J., Leyland, P.C.: Factoring Estimates for a 1024-Bit RSA Modulus. In: ASIACRYPT 2003 [32], pp. 55–74 (2003) (Cited in §1)
Menezes, A.J. (ed.): CT-RSA 2005. LNCS, vol. 3376. Springer, Heidelberg (2005); ISBN 3- 540-24399-2. See [14]
Montgomery, P.L.: Modular multiplication without trial division. Mathematics of Computation 44, 519–521 (1985), http://www.jstor.org/pss/2007970 (Cited in §4.1)
Moss, A., Page, D., Smart, N.P.: Toward Acceleration of RSA Using 3D Graphics Hardware. In: Cryptography and Coding 2007 [21], pp. 364–383 (2007) (Cited in §3)
Oswald, E., Rohatgi, P. (eds.): CHES 2008. LNCS, vol. 5154. Springer, Heidelberg (2008); ISBN 978-3-540-85052-6. See [46]
Pelzl, J., Šimka, M., Kleinjung, T., Franke, J., Priplata, C., Stahlke, C., Drutarovský, M., Fischer, V., Paar, C.: Area-time efficient hardware architecture for factoring integers with the elliptic curve method. IEE Proceedings on Information Security 152, 67–78 (2005) (Cited in §1)
Preneel, B. (ed.): EUROCRYPT 2000. LNCS, vol. 1807. Springer, Heidelberg (2000); ISBN 3-540-67517-5. See [13]
Rao, J.R., Sunar, B. (eds.): CHES 2005. LNCS, vol. 3659. Springer, Heidelberg (2005); ISBN 3-540-28474-5. See [19], [22]
Shamir, A., Tromer, E.: Factoring Large Numbers with the TWIRL Device. In: CRYPTO 2003 [11], pp. 1–26 (2003) (Cited in §1)
Šimka, M., Pelzl, J., Kleinjung, T., Franke, J., Priplata, C., Stahlke, C., Drutarovský, M., Fischer, V.: Hardware Factorization Based on Elliptic Curve Method. In: FCCM 2005 [1], pp. 107–116 (2005) (Cited in §1)
Smart, N.P. (ed.): Cryptography and Coding 2005. LNCS, vol. 3796. Springer, Heidelberg (2005); See [30]
Szerwinski, R., Güneysu, T.: Exploiting the Power of GPUs for Asymmetric Cryptography. In: CHES 2008 [39], pp. 79–99 (2008) (Cited in §3.1, §6, §2)
Vaudenay, S. (ed.): AFRICACRYPT 2008. LNCS, vol. 5023. Springer, Heidelberg (2008); ISBN 978-3- 540-68159-5. See [7]
Zimmermann, P., Dodson, B.: 20 Years of ECM. In: ANTS 2006 [24], pp. 525–542 (2006) (Cited in §2)
Zimmermann, P.: 50 largest factors found by ECM, http://www.loria.fr/~zimmerma/records/top50.html (Cited in §1)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bernstein, D.J., Chen, TR., Cheng, CM., Lange, T., Yang, BY. (2009). ECM on Graphics Cards. In: Joux, A. (eds) Advances in Cryptology - EUROCRYPT 2009. EUROCRYPT 2009. Lecture Notes in Computer Science, vol 5479. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01001-9_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-01001-9_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01000-2
Online ISBN: 978-3-642-01001-9
eBook Packages: Computer ScienceComputer Science (R0)