Skip to main content
Search
Search
Quick Search anywhere
Quick Search anywhere
Quick Search anywhere
Quick Search anywhere
Quick Search anywhere
Quick Search anywhere
Advanced Search
Skip main navigation
No Access

Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction

Published Online:February 28, 2012pp 212-228https://doi.org/10.1504/IJACT.2012.045590

Abstract

We describe a cell processor implementation of Pollard’s rho method to solve discrete logarithms in groups of elliptic curves over prime fields. The implementation was used on a cluster of PlayStation 3 game consoles to set a new record. We present in detail the underlying single instruction multiple data modular arithmetic.

Keywords

elliptic curve discrete logarithm, Pollard’s rho method, cell processor, single instruction multiple data, SIMD, negation map

References

  • 1. Anderson, D.P. (2004). ‘Boinc: a system for public-resource computing and storage’. in GRID ’04: Proceedings of the 5th IEEE/ACM International Workshop on Grid Computing. IEEE Computer Society, 4-10 Google Scholar
  • 2. Bailey, D.V. , Batina, L. , Bernstein, D.J. , Birkner, P. , Bos, J.W. , Chen, H-C. , Cheng, C-M. , van Damme, G. , de Meulenaer, G. , Perez, L.J.D. , Fan, J. , Guneysu, T. , Gurkaynak, F. , Kleinjung, T. , Lange, T. , Mentens, N. , Niederhagen, R. , Paar, C. , Regazzoni, F. , Schwabe, P. , Uhsadel, L. , Herrewege, A.V. , Yang, B-Y. (2009). ‘Breaking ECC2K-130’. Report 2009/541, Cryptology ePrint Archive, available at http://eprint.iacr.org/2009/541 Google Scholar
  • 3. Bajard, J-C. , Meloni, N. , Plantard, T. (2005). ‘Efficient RNS basesfor cryptography’. in IMACS’05: World Congress: Scientific Computation Applied Mathematics and Simulation Google Scholar
  • 4. Bender, A. , Castagnoli, G. (1990). ‘On the implementation of elliptic curve cryptosystems’. 435, in Crypto 1989, Lecture Notes in Computer Science, Springer, 186-192 Google Scholar
  • 5. Bernstein, D.J. (2006). ‘Curve25519: new Diffie-Hellman speed records’. 3958, in Public Key Cryptography – PKC 2006, Lecture Notes in Computer Science, Springer, 207-228 Google Scholar
  • 6. Bernstein, D.J. , Chen, H-C. , Chen, M-S. , Cheng, C-M. , Hsiao, C-H. , Lange, T. , Lin, Z-C. , Yang, B-Y. (2009). ‘The billion-mulmod-per-second PC’. in Workshop record of SHARCS’09, 131-144, available at http://www.hyperelliptic.org/tanja/SHARCS/record2.pdf Google Scholar
  • 7. Bernstein, D.J. , Lange, T. (2007). ‘Faster addition and doubling on elliptic curves’. 4833, in Asiacrypt 2007, Lecture Notes in Computer Science, Springer, 29-50 Google Scholar
  • 8. Bernstein, D.J. , Lange, T. , Schwabe, P. (2011). ‘On the correct use of the negation map in the Pollard rho method’. 6571, in Public Key Cryptography – PKC 2011, Lecture Notes in Computer Science, Springer, 128-146 Google Scholar
  • 9. Bos, J.W. (2010). ‘High-performance modular multiplication on the cell processor’. 6087, in International Workshop on the Arithmetic of Finite Fields – WAIFI 2010, Lecture Notes in Computer Science, Springer, 7-24 Google Scholar
  • 10. Bos, J.W. , Kaihara, M.E. (2010). ‘Montgomery multiplication on the cell’. 6067, in Parallel Processing and Applied Mathematics 2009, Lecture Notes in Computer Science, Springer, 477-485 Google Scholar
  • 11. Bos, J.W. , Kaihara, M.E. , Montgomery, P.L. (2009). ‘Pollard rho on the PlayStation 3’. in Workshop Record of SHARCS’09, 35-50, available at http://www.hyperelliptic.org/tanja/SHARCS/record2.pdf Google Scholar
  • 12. Bos, J.W. , Kleinjung, T. , Lenstra, A.K. (2010a). ‘On the use of the negation map in the Pollard rho method’. 6197, in Ninth Algorithmic Number Theory Symposium – ANTS-IX, Lecture Notes in Computer Science, Springer, 67-83 Google Scholar
  • 13. Bos, J.W. , Kleinjung, T. , Niederhagen, R. , Schwabe, P. (2010b). ‘ECC2K-130 on cell CPUs’. 6055, in Africacrypt 2010, Lecture Notes in Computer Science, Springer, 225-242 Google Scholar
  • 14. Bos, J.W. , Kleinjung, T. , Lenstra, A.K. , Montgomery, P.L. (2011). ‘Efficient SIMD arithmetic modulo a Mersenne number’. in IEEE Symposium on Computer Arithmetic – Arith-20, IEEE Computer Society, 213-221 Google Scholar
  • 15. Brent, R.P. , Pollard, J.M. (1981). ‘Factorization of the eighth Fermat number’. Mathematics of Computation. 36, 154, 627-630 Google Scholar
  • 16. Certicom (2002). ‘Press release: Certicom announces elliptic curve cryptosystem (ECC) challenge winner’. available at http://www.certicom.com/index.php/2002-press-releases/382002-press-releases/340-notre-dame-mathematician-solveseccp109-encryption-key-problem-issued-in-1997 Google Scholar
  • 17. Certicom Research (2000). ‘Standards for efficient cryptography 2: recommended elliptic curve domain parameters’. Certicom, Standard SEC2 Google Scholar
  • 18. Cheon, J.H. , Hong, J. , Kim, M. (2008). ‘Speeding up the Pollard rho method on prime fields’. 5350, in Asiacrypt 2008, Lecture Notes in Computer Science, Springer, 471-488 Google Scholar
  • 19. Costigan, N. , Schwabe, P. (2009). ‘Fast elliptic-curve cryptography on the cell broadband engine’. 5580, in Africacrypt 2009, Lecture Notes in Computer Science, Springer, 368-385 Google Scholar
  • 20. Costigan, N. , Scott, M. (2007). ‘Accelerating SSL using the vector processors in IBM’s cell broadband engine for Sony’s Playstation 3’. Report 2007/061, Cryptology ePrint Archive, available at http://eprint.iacr.org/2007/061 Google Scholar
  • 21. Crandall, R.E. ‘Method and apparatus for public key exchange in a cryptographic system’. US patent. 5,159,632, 1992, 10 Google Scholar
  • 22. Duursma, I.M. , Gaudry, P. , Morain, F. (1999). ‘Speeding up the discrete log computation on curves with automorphisms’. 1716, in Asiacrypt 1999, Lecture Notes in Computer Science, Springer, 103-121 Google Scholar
  • 23. Edwards, H.M. ‘A normal form for elliptic curves’. Bulletin of the American Mathematical Society. 2007, 07, 44, 393-422 Google Scholar
  • 24. Galbraith, S. (2010). ‘Mathematics of public key cryptography (version 0.6)’. (accessed on 2011 November), available at http://www.isg.rhul.ac.uk/sdg/crypto-book/cryptobook.html Google Scholar
  • 25. Gallant, R.P. , Lambert, R.J. , Vanstone, S.A. (2000). ‘Improving the parallelized Pollard lambda search on anomalous binary curves’. Mathematics of Computation. 69, 232, 1699-1705 Google Scholar
  • 26. Hofstee, H.P. (2005). ‘Power efficient processor architecture and the cell processor’. in HPCA 2005, 258-262 Google Scholar
  • 27. Hotz, G. (2010). ‘Here’s your silver plate’. (accessed on January 2010), available at http://www.theregister.co.uk/2010/01/25/playstation_cracked_wide_open/ Google Scholar
  • 28. IBM (2010). ‘Multi-precision math library’. (accessed on March 2010), Example Library API Reference, available at https://www.ibm.com/developerworks/power/cell/documents.html Google Scholar
  • 29. Kaihara, M.E. , Takagi, N. (2005). ‘A hardware algorithm for modular multiplication/division’. IEEE Trans. Computers. 54, 1, 12-21 Google Scholar
  • 30. Kaliski, B.S. (1995). ‘The Montgomery inverse and its applications’. IEEE Transactions on Computers. 44, 8, 1064-1065 Google Scholar
  • 31. Kim, J.H. , Montenegro, R. , Peres, Y. , Tetali, P. (2010). ‘A birthday paradox for Markov chains, with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm’. The Annals of Applied Probability. 20, 2, 495-521 Google Scholar
  • 32. Kleinjung, T. , Aoki, K. , Franke, J. , Lenstra, A. , Thom´e, E. , Bos, J. , Gaudry, P. , Kruppa, A. , Montgomery, P. , Osvik, D.A. , Riele, H.t. , Timofeev, A. , Zimmermann, P. (2010). ‘Factorization of a 768-bitRSAmodulus’. 6223, in Crypto 2010, Lecture Notes in Computer Science, Springer, 333-350 Google Scholar
  • 33. Knuth, D.E. (1997). Seminumerical Algorithms. The Art of Computer Programming. 3rd ed., Reading, Massachusetts, USA:Addison-Wesley Google Scholar
  • 34. Knuth, D.E. (1998). Sorting and Searching. The Art of Computer Programming. 2nd ed., Reading, Massachusetts, USA:Addison-Wesley Google Scholar
  • 35. Koblitz, N. (1987). ‘Elliptic curve cryptosystems’. Mathematics of Computation. 48, 117, 203-209 Google Scholar
  • 36. Koblitz, N. (1992). ‘CM-curves with good cryptographic properties’. 576, in Crypto 1991, Lecture Notes in Computer Science, Springer, 279-287 Google Scholar
  • 37. Lenstra, A.K. , Lenstra, H.W., Jr. (1993). ‘The development of the number field sieve’. Lecture Notes in Mathematics. 1554, Springer Google Scholar
  • 38. Lenstra, H.W., Jr. (1987). ‘Factoring integers with elliptic curves’. Annals of Mathematics. 126, 3, 649-673 Google Scholar
  • 39. Miller, V.S. (1986). ‘Use of elliptic curves in cryptography’. 218, in Crypto 1985, Lecture Notes in Computer Science, Springer, 417-426 Google Scholar
  • 40. Montgomery, P.L. ‘Modular multiplication without trial division’. Mathematics of Computation. 1985, 04, 44, 170, 519-521 Google Scholar
  • 41. Montgomery, P.L. (1987). ‘Speeding the Pollard and elliptic curve methods of factorization’. Mathematics of Computation. 48, 117, 243-264 Google Scholar
  • 42. Nivasch, G. (2004). ‘Cycle detection using a stack’. Information Processing Letters. 90, 3, 135-140 Google Scholar
  • 43. Pollard, J.M. (1978). ‘Monte Carlo methods for index computation (mod p)’. Mathematics of Computation. 32, 143, 918-924 Google Scholar
  • 44. RSA the Security Division of EMC (2010). ‘The RSA challenge numbers’. available at formerly on http://www.rsa.com/rsalabs/node.asp?id=2093, now on http://en.wikipedia.org/wiki/RSA_numbers Google Scholar
  • 45. Schulte-Geers, E. (2000). ‘Collision search in a random mapping: some asymptotic results’. Talk at ECC 2000, The Fourth Workshop on Elliptic Curve Cryptography, Essen, Germany, available at http://www.cacr.math.uwaterloo.ca/conferences/2000/ecc2000/slides.html Google Scholar
  • 46. Solinas, J.A. (1999). ‘Generalized Mersenne numbers’. Centre for Applied Cryptographic Research, University of Waterloo, Technical Report CORR 99-39 Google Scholar
  • 47. Solinas, J.A. ‘Cryptographic identification and digital signature method using efficient elliptic curve’. US patent. 6,898,284, 2005, 05 Google Scholar
  • 48. Stevens, M. , Sotirov, A. , Appelbaum, J. , Lenstra, A.K. , Molnar, D. , Osvik, D.A. , de Weger, B. (2009). ‘Short chosen prefix collisions for MD5 and the creation of a rogue CA certificate’. 5677, in Crypto 2009, Lecture Notes in Computer Science, Springer, 55-69 Google Scholar
  • 49. Teske, E. (2001). ‘On random walks for Pollard’s rho method’. Mathematics of Computation. 70, 234, 809-825 Google Scholar
  • 50. van Oorschot, P.C. , Wiener, M.J. (1999). ‘Parallel collision search with cryptanalytic applications’. Journal of Cryptology. 12, 1, 1-28 Google Scholar
  • 51. Wedeniwski, S. (2010). ‘Piologie – an exact arithmetic library in C++’. (accessed on March 2010), available at http://www.zetagrid.net/zeta/sourcecode.html, iPhone application: http://itunes.apple.com/app/piologie/id387334278?mt=8 Google Scholar
  • 52. Wiener, M.J. , Zuccherato, R.J. (1998). ‘Faster attacks on elliptic curve cryptosystems’. in Selected Areas in Cryptography, Lecture Notes in Computer Science. 1556, Springer, 190-200 Google Scholar
Previous article
Next article