Abstract
Bos, Kaihara, Kleinjung, Lenstra, and Montgomery recently showed that ECDLPs on the 112-bit secp112r1 curve can be solved in an expected time of 65 years on a PlayStation 3. This paper shows how to solve the same ECDLPs at almost twice the speed on the same hardware. The improvement comes primarily from a new variant of Pollard’s rho method that fully exploits the negation map without branching, and secondarily from improved techniques for modular arithmetic.
Chapter PDF
Similar content being viewed by others
References
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., Dominguez Perez, L.J., Fan, J., Güneysu, T., Gürkaynak, F., Kleinjung, T., Lange, T., Mentens, N., Niederhagen, R., Paar, C., Regazzoni, F., Schwabe, P., Uhsadel, L., Van Herrewege, A., Yang, B.-Y.: Breaking ECC2K-130 (2010), http://eprint.iacr.org/2009/541/ , Citations in this document: §2, §2
Bernstein, D.J.: Curve25519: new Diffie-Hellman speed records. In: PKC 2006 [24], pp. 207–228 (2006), http://cr.yp.to/papers.html#curve25519 , Citations in this document: §4
Bos, J.W., Kaihara, M.E., Kleinjung, T., Lenstra, A.K., Montgomery, P.L.: PlayStation 3 computing breaks 260 barrier; 112-bit prime ECDLP solved (2009), http://lacal.epfl.ch/112bit_prime , Citations in this document: §1, §1, §4, §4, §5, §6, §6, §6
Bos, J.W., Kaihara, M.E., Kleinjung, T., Lenstra, A.K., Montgomery, P.L.: On the security of 1024-bit RSA and 160-bit elliptic curve cryptography: version 2.1 (2009), http://eprint.iacr.org/2009/389/ , Citations in this document: §1, §4, §5, §5, §5, §5, §5, §5, §6
Bos, J.W., Kaihara, M.E., Montgomery, P.L.: Pollard rho on the PlayStation 3. In: Workshop record of SHARCS 2009, pp. 35–50 (2009), http://www.hyperelliptic.org/tanja/SHARCS/record2.pdf , Citations in this document: §1, §1, §4, §5, §5, §5, §5, §6, §6, §6
Bos, J.W., Kleinjung, T., Lenstra, A.K.: On the use of the negation map in the Pollard rho method. In: ANTS 2010 [11], pp. 66–82 (2010), Citations in this document: §1,§1, §2, §2, §6
Certicom Research, SEC 2: Recommended elliptic curve domain parameters (2000), http://www.secg.org/collateral/sec2_final.pdf , Citations in this document: §4
Costigan, N., Schwabe, P.: Fast elliptic-curve cryptography on the Cell Broadband Engine. In: AFRICACRYPT 2009 [18], pp. 368–385 (2009), http://cryptojedi.org/users/peter/#celldh , Citations in this document: §4
Duursma, I.M., Gaudry, P., Morain, F.: Speeding up the discrete log computation on curves with automorphisms. In: ASIACRYPT 1999 [14], pp. 103–121 (1999), Citations in this document: §2, §2
Gallant, R.P., Lambert, R.J., Vanstone, S.A.: Improving the parallelized Pollard lambda search on anomalous binary curves. Mathematics of Computation 69, 1699–1705 (2000), Citations in this document: §2
Hanrot, G., Morain, F., Thomé, E. (eds.): Proceedings of Algorithmic Number Theory, 9th International Symposium, ANTS-IX, Nancy, France, July 19-23. LNCS, vol. 6197. Springer, Heidelberg (2010), See [6]
Harley, R.J.: Solution to Certicom’s ECC2K-95 problem (email message) (1998), http://cristal.inria.fr/~harley/ecdl5/ECC2K-95.submission.text , Citations in this document: §2
IBM DeveloperWorks, Cell Broadband Engine Programming Handbook, Including the PowerXCell 8i Processor (version 1.11) (2008), http://www-01.ibm.com/chips/techlib/techlib.nsf/techdocs/1741C509C5F64B3300257460006FD68D , Citations in this document: §5
Lam, K.-Y., Okamoto, E., Xing, C. (eds.): Proceedings of Advances in Cryptology – ASIACRYPT 1999, International Conference on the Theory and Applications of Cryptology and Information Security, Singapore, November 14-18. LNCS, vol. 1716. Springer, Heidelberg (1999), See [9]
Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation 48, 243–264 (1987), http://links.jstor.org/sici?sici=0025-5718(198701)48:177<243:STPAEC>2.0.CO;2-3, ISSN 0025–5718, MR 88e:11130, Citations in this document: §3
van Oorschot, P.C., Wiener, M.: Parallel collision search with cryptanalytic applications. Journal of Cryptology 12, 1–28 (1999), http://members.rogers.com/paulv/papers/pubs.html , ISSN 0933–2790, Citations in this document: §2
Pollard, J.M.: Monte Carlo methods for index computation mod p. Mathematics of Computation 32, 918–924 (1978) ISSN 0025–5718, MR 58:10684, Citations in this document: §2
Preneel, B. (ed.): Proceedings of Progress in Cryptology – AFRICACRYPT 2009, Second International Conference on Cryptology in Africa, Gammarth, Tunisia, June 21-25. LNCS, vol. 5580. Springer, Heidelberg (2009), See [8]
Sony Corporation, Cell Broadband Engine architecture, Version 1.01 (2006), http://cell.scei.co.jp/pdf/CBE_Architecture_v101.pdf , Citations in this document: §5
Tavares, S., Meijer, H. (eds.): Selected areas of cryptography 1998. LNCS, vol. 1556. Springer, Heidelberg (1999), See [23]
Teske, E.: On random walks for Pollard’s rho method. Mathematics of Computation 70, 809–825 (2001), Citations in this document: §2
Wiener, M.J., Zuccherato, R.J.: Faster attacks on elliptic curve cryptosystems (1998); see also newer version [23], http://grouper.ieee.org/groups/1363/Research/contributions/attackEC.ps
Wiener, M.J., Zuccherato, R.J.: Faster attacks on elliptic curve cryptosystems. In: SAC 1998 [20], pp. 190–200 (1998); see also older version [22], Citations in this document: §2
Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.): Proceedings of Public Key Cryptography – 9th International Conference on Theory and Practice in Public-Key Cryptography, New York, NY, USA, April 24-26. LNCS, vol. 3958. Springer, Heidelberg (2006), See [2]
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 International Association for Cryptologic Research
About this paper
Cite this paper
Bernstein, D.J., Lange, T., Schwabe, P. (2011). On the Correct Use of the Negation Map in the Pollard rho Method. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds) Public Key Cryptography – PKC 2011. PKC 2011. Lecture Notes in Computer Science, vol 6571. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19379-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-19379-8_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19378-1
Online ISBN: 978-3-642-19379-8
eBook Packages: Computer ScienceComputer Science (R0)