Top

Published in:

2020 | OriginalPaper | Chapter

Revisiting ECM on GPUs

Authors : Jonas Wloka, Jan Richter-Brockmann, Colin Stahlke, Thorsten Kleinjung, Christine Priplata, Tim Güneysu

Published in: Cryptology and Network Security

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Modern public-key cryptography is a crucial part of our contemporary life where a secure communication channel with another party is needed. With the advance of more powerful computing architectures – especially Graphics Processing Units (GPUs) – traditional approaches like RSA and Diffie-Hellman schemes are more and more in danger of being broken.

We present a highly optimized implementation of Lenstra’s ECM algorithm customized for GPUs. Our implementation uses state-of-the-art elliptic curve arithmetic and optimized integer arithmetic while providing the possibility of arbitrarily scaling ECM’s parameters allowing an application even for larger discrete logarithm problems. Furthermore, the proposed software is not limited to any specific GPU generation and is to the best of our knowledge the first implementation supporting multiple device computation. To this end, for a bound of \(B_1 = {8 192}\) and a modulus size of 192 bit, we achieve a throughput of 214 thousand ECM trials per second on a modern RTX 2080 Ti GPU considering only the first stage of ECM. To solve the Discrete Logarithm Problem for larger bit sizes, our software can easily support larger parameter sets such that a throughput of 2 781 ECM trials per second is achieved using \(B_1={50\, 000}\), \(B_2 = {5\, 000\, 000}\), and a modulus size of 448 bit.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Curves with Fast Computations in the First Pairing Group

next chapter Arcula: A Secure Hierarchical Deterministic Wallet for Multi-asset Blockchains

Available at http://ecm.gforge.inria.fr/.

Antao, S., Bajard, J.C., Sousa, L.: RNS-based elliptic curve point multiplication for massive parallel architectures. Comput. J. 55(5), 629–647 (2012)CrossRef

Antao, S., Bajard, J.C., Sousa, L.: Elliptic curve point multiplication on GPUs. In: ASAP 2010–21st IEEE International Conference on Application-specific Systems, Architectures and Processors. IEEE, July 2010

Barker, E.B., Dang, Q.H.: Recommendation for Key Management Part 3: Application-Specific Key Management Guidance. Technical Report NIST SP 800–57Pt3r1, National Institute of Standards and Technology, January 2015

Bernstein, D.J., et al.: The billion-mulmod-per-second PC. In: SHARCS 2009 Workshop Record (Proceedings 4th Workshop on Special-purpose Hardware for Attacking Cryptograhic Systems, Lausanne, Switserland, September 9–10, 2009) (2009)

Bernstein, D., Birkner, P., Lange, T., Peters, C.: ECM using edwards curves. Math. Comput. 82(282), 1139–1179 (2013)MathSciNetCrossRefMATH

Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted edwards curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389–405. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68164-9_26CrossRef

Bernstein, D.J., Birkner, P., Lange, T.: Starfish on strike. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol. 6212, pp. 61–80. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14712-8_4CrossRef

Bernstein, D.J., Chen, T.-R., Cheng, C.-M., Lange, T., Yang, B.-Y.: ECM on graphics cards. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 483–501. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_28CrossRef

Bernstein, D.J., Chuengsatiansup, C., Lange, T.: Double-base scalar multiplication revisited. Cryptology ePrint Archive, Report 2017/037 (2017). https://eprint.iacr.org/2017/037

10.

Bernstein, D.J., Lange, T.: Explicit-Formulas Database. https://hyperelliptic.org/EFD/index.html

11.

Bos, J.W.: Low-latency elliptic curve scalar multiplication. Int. J. Parallel Prog. 40(5), 532–550 (2012)CrossRef

12.

Bos, J.W., Kleinjung, T.: ECM at work. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 467–484. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_29CrossRef

13.

Boudot, F., Gaudry, P., Guillevic, A., Heninger, N., Thomé, E., Zimmermann, P.: Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment. Cryptology ePrint Archive, Report 2020/697 (2020). https://eprint.iacr.org/2020/697

14.

Bouvier, C., Imbert, L.: Faster cofactorization with ECM using mixed representations. Cryptology ePrint Archive, Report 2018/669 (2018). https://eprint.iacr.org/2018/669

15.

Dixon, B., Lenstra, A.K.: Massively parallel elliptic curve factoring. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 183–193. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-47555-9_16CrossRef

16.

Emmart, N., Luitjens, J., Weems, C., Woolley, C.: Optimizing Modular Multiplication for NVIDIA’s Maxwell GPUs. In: 2016 IEEE 23nd Symposium on Computer Arithmetic (ARITH), pp. 47–54. IEEE, Silicon Valley, CA, USA, July 2016

17.

Gélin, A., Kleinjung, T., Lenstra, A.K.: Parametrizations for families of ecm-friendly curves. In: Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2017, Kaiserslautern, Germany, July 25–28, 2017, pp. 165–171 (2017)

18.

Großschädl, J., Kamendje, G.-A.: Optimized RISC architecture for multiple-precision modular arithmetic. In: Hutter, D., Müller, G., Stephan, W., Ullmann, M. (eds.) Security in Pervasive Computing. LNCS, vol. 2802, pp. 253–270. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-39881-3_22CrossRef

19.

Hisil, H., Wong, K.K.-H., Carter, G., Dawson, E.: Twisted edwards curves revisited. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 326–343. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89255-7_20CrossRef

20.

Kaya Koc, C., Acar, T., Kaliski, B.: Analyzing and comparing Montgomery multiplication algorithms. IEEE Micro 16(3), 26–33 (1996)CrossRef

21.

Kleinjung, T., et al.: Factorization of a 768-Bit RSA modulus. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 333–350. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_18CrossRef

22.

Kleinjung, T., et al.: A heterogeneous computing environment to solve the 768-bit RSA challenge. Cluster Comput. 15(1), 53–68 (2012)CrossRef

23.

Kleinjung, T., Diem, C., Lenstra, A.K., Priplata, C., Stahlke, C.: Computation of a 768-Bit prime field discrete logarithm. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 185–201. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_7CrossRef

24.

Kruppa, A.: A Software Implementation of ECM for NFS. Research Report RR-7041, INRIA (2009). https://hal.inria.fr/inria-00419094

25.

Leboeuf, K., Muscedere, R., Ahmadi, M.: A GPU implementation of the Montgomery multiplication algorithm for elliptic curve cryptography. In: 2013 IEEE International Symposium on Circuits and Systems (ISCAS2013), pp. 2593–2596, May 2013

26.

Lenstra, A.K.: Integer factoring. Des. Codes Crypt. 19(2–3), 101–128 (2000). https://doi.org/10.1023/A:1008397921377MathSciNetCrossRefMATH

27.

Lenstra, A.K.: General purpose integer factoring. Cryptology ePrint Archive, Report 2017/1087 (2017). https://eprint.iacr.org/2017/1087

28.

Lenstra, H.W.: Factoring integers with elliptic curves. Ann. Math. 126(3), 649–673 (1987). https://doi.org/10.2307/1971363MathSciNetCrossRefMATH

29.

Mahé, E.M., Chauvet, J.M.: Fast GPGPU-based elliptic curve scalar multiplication. Cryptology ePrint Archive, Report 2014/198 (2014). https://eprint.iacr.org/2014/198

30.

Miele, A.: On the analysis of public-key cryptologic algorithms (2015). https://infoscience.epfl.ch/record/207710

31.

Miele, A., Bos, J.W., Kleinjung, T., Lenstra, A.K.: Cofactorization on graphics processing units. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 335–352. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44709-3_19CrossRef

32.

Neves, S., Araujo, F.: On the performance of GPU public-key cryptography. In: ASAP 2011–22nd IEEE International Conference on Application-specific Systems, Architectures and Processors, pp. 133–140. September 2011

33.

Savas, E., Koc, C.K.: Montgomery inversion. J. Cryptographic Eng. 8(3), 201–210 (2018)CrossRef

34.

Szerwinski, R., Güneysu, T.: Exploiting the power of GPUs for asymmetric cryptography. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 79–99. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85053-3_6CrossRef

35.

Valenta, L., Cohney, S., Liao, A., Fried, J., Bodduluri, S., Heninger, N.: Factoring as a service. In: Grossklags, J., Preneel, B. (eds.) FC 2016. LNCS, vol. 9603, pp. 321–338. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54970-4_19CrossRef

36.

Yu, W., Musa, S.A., Li, B.: Double-base chains for scalar multiplications on elliptic curves. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 538–565. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_18CrossRef

37.

Zimmermann, P., Dodson, B.: 20 years of ECM. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 525–542. Springer, Heidelberg (2006). https://doi.org/10.1007/11792086_37CrossRef

Title: Revisiting ECM on GPUs
Authors: Jonas Wloka
Jan Richter-Brockmann
Colin Stahlke
Thorsten Kleinjung
Christine Priplata
Tim Güneysu
Publisher: Springer International Publishing
Book: Cryptology and Network Security
Print ISBN: 978-3-030-65410-8

Electronic ISBN: 978-3-030-65411-5

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-65411-5_15

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"