Small Public Exponent Brings More: Improved Partial Key Exposure Attacks against RSA
Authors
Yansong Feng, Abderrahmane Nitaj, Yanbin Pan
Yansong Feng
Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China
fengyansong at amss dot ac dot cn
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China
fengyansong at amss dot ac dot cn
Abderrahmane Nitaj
Normandie University, Caen, France
abderrahmane dot nitaj at unicaen dot fr
abderrahmane dot nitaj at unicaen dot fr
Yanbin Pan
Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China
panyanbin at amss dot ac dot cn
School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China
panyanbin at amss dot ac dot cn
Abstract
Let (N,e) be a public key of the RSA cryptosystem, and d be the corresponding private key. In practice, we usually choose a small e for quick encryption. In this paper, we improve partial private key exposure attacks against RSA with a small public exponent e. The key idea is that under such a setting we can usually obtain more information about the prime factor of N and then by solving a univariate modular polynomial with Coppersmith's method, N can be factored in polynomial time. Compared to previous results, we reduce the number of d's leaked bits needed to mount the attack by log_2 (e) bits. Furthermore, our experiments show that for 1024-bit N, our attack can achieve the theoretical bound on a personal computer, which verified our attack.
References
[Ajt98]
Miklós Ajtai. The Shortest Vector Problem in L\({}_{\mbox{2}}\) is NP-hard for Randomized Reductions (Extended Abstract). In Jeffrey Scott Vitter, editor, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 10–19. 1998. ACM. DOI: 10.1145/276698.276705
[Aon09]
Yoshinori Aono. A New Lattice Construction for Partial Key Exposure Attack for RSA. In Stanislaw Jarecki and Gene Tsudik, editors, Public Key Cryptography - PKC 2009, 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, CA, USA, March 18-20, 2009. Proceedings, volume 5443 of Lecture Notes in Computer Science, pages 34–53. 2009. Springer. DOI: 10.1007/978-3-642-00468-1_3
[BD99]
Dan Boneh and Glenn Durfee. Cryptanalysis of RSA with Private Key Less than ${N}^{0.292}$. In EUROCRYPT '99, volume 1592 of Lecture Notes in Computer Science, pages 1–11. 1999. Springer. DOI: 10.1007/3-540-48910-X_1
[BDF98a]
Dan Boneh, Glenn Durfee, and Yair Frankel. An Attack on RSA Given a Small Fraction of the Private Key Bits. In Kazuo Ohta and Dingyi Pei, editors, Advances in Cryptology - ASIACRYPT '98, International Conference on the Theory and Applications of Cryptology and Information Security, Beijing, China, October 18-22, 1998, Proceedings, volume 1514 of Lecture Notes in Computer Science, pages 25–34. 1998. Springer. DOI: 10.1007/3-540-49649-1_3
[BDF98b]
Dan Boneh, Glenn Durfee, and Yair Frankel. Exposing an RSA Private Key Given a Small Fraction of its Bits. Full version of the work from Asiacrypt'98, available at http://crypto.stanford.edu/ dabo/abstracts/bits_of_d.html. 1998.
[BGG+20]
Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé, and Paul Zimmermann. Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment. In Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II 40, pages 62–91. 2020. Springer. DOI: 10.1007/978-3-030-56880-1_3
[Ble98]
Daniel Bleichenbacher. Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS# 1. In Advances in Cryptology—CRYPTO'98: 18th Annual International Cryptology Conference Santa Barbara, California, USA August 23–27, 1998 Proceedings 18, pages 1–12. 1998. Springer. DOI: 10.1007/BFB0055716
[BM03]
Johannes Blömer and Alexander May. New Partial Key Exposure Attacks on RSA. In Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings, volume 2729 of Lecture Notes in Computer Science, pages 27–43. 2003. Springer. DOI: 10.1007/978-3-540-45146-4_2
[CM07]
Jean-Sébastien Coron and Alexander May. Deterministic Polynomial-Time Equivalence of Computing the RSA Secret Key and Factoring. J. Cryptol., 20(1):39–50, 2007. DOI: 10.1007/S00145-006-0433-6
[Cop96]
Don Coppersmith. Finding a Small Root of a Univariate Modular Equation. In Ueli M. Maurer, editor, Advances in Cryptology - EUROCRYPT '96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding, volume 1070 of Lecture Notes in Computer Science, pages 155–165. 1996. Springer. DOI: 10.1007/3-540-68339-9_14
[Cop97]
Don Coppersmith. Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities. J. Cryptol., 10(4):233–260, 1997. DOI: 10.1007/S001459900030
[dW02]
Benne de Weger. Cryptanalysis of RSA with Small Prime Difference. Appl. Algebra Eng. Commun. Comput., 13(1):17–28, 2002. DOI: 10.1007/S002000100088
[EJMdW05]
Matthias Ernst, Ellen Jochemsz, Alexander May, and Benne de Weger. Partial Key Exposure Attacks on RSA up to Full Size Exponents. In Ronald Cramer, editor, Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings, volume 3494 of Lecture Notes in Computer Science, pages 371–386. 2005. Springer. DOI: 10.1007/11426639_22
[HM09]
Mathias Herrmann and Alexander May. Attacking Power Generators Using Unravelled Linearization: When Do We Output Too Much?. In Mitsuru Matsui, editor, Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings, volume 5912 of Lecture Notes in Computer Science, pages 487–504. 2009. Springer. DOI: 10.1007/978-3-642-10366-7_29
[HM10]
Mathias Herrmann and Alexander May. Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA. In Phong Q. Nguyen and David Pointcheval, editors, Public Key Cryptography - PKC 2010, 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, May 26-28, 2010. Proceedings, volume 6056 of Lecture Notes in Computer Science, pages 53–69. 2010. Springer. DOI: 10.1007/978-3-642-13013-7_4
[How97]
Nick Howgrave-Graham. Finding Small Roots of Univariate Modular Equations Revisited. In Michael Darnell, editor, Cryptography and Coding, 6th IMA International Conference, Cirencester, UK, December 17-19, 1997, Proceedings, volume 1355 of Lecture Notes in Computer Science, pages 131–142. 1997. Springer. DOI: 10.1007/BFB0024458
[KSI11]
Noboru Kunihiro, Naoyuki Shinohara, and Tetsuya Izu. A Unified Framework for Small Secret Exponent Attack on RSA. In Ali Miri and Serge Vaudenay, editors, Selected Areas in Cryptography - 18th International Workshop, SAC 2011, Toronto, ON, Canada, August 11-12, 2011, Revised Selected Papers, volume 7118 of Lecture Notes in Computer Science, pages 260–277. 2011. Springer. DOI: 10.1007/978-3-642-28496-0_16
[LLL82]
Arjen K Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring Polynomials with Rational Coefficients. Mathematische Annalen, 261:515–534, 1982. DOI: 10.1007/BF01457454
[LZPL15]
Yao Lu, Rui Zhang, Liqiang Peng, and Dongdai Lin. Solving linear equations modulo unknown divisors: revisited. In International Conference on the Theory and Application of Cryptology and Information Security, pages 189–213. 2015. Springer. DOI: 10.1007/978-3-662-48797-6_9
[Mac13]
Edmond K Machie. Network security traceback attack and react in the United States Department of Defense network. Trafford Publishing 2013.
[May03]
Alexander May. New RSA Vulnerabilities Using Lattice Reduction Methods. PhD thesis, University of Paderborn, 2003.
[May04]
Alexander May. Computing the RSA Secret Key Is Deterministic Polynomial Time Equivalent to Factoring. In Matthew K. Franklin, editor, Advances in Cryptology - CRYPTO 2004, 24th Annual International CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings, volume 3152 of Lecture Notes in Computer Science, pages 213–219. 2004. Springer. DOI: 10.1007/978-3-540-28628-8_13
[MH24]
Gabrielle De Micheli and Nadia Heninger. Survey: Recovering cryptographic keys from partial information, by example. IACR Communications in Cryptology, 1(1), 2024. DOI: 10.62056/ahjbksdja
[Mil75]
Gary L. Miller. Riemann's Hypothesis and Tests for Primality. In William C. Rounds, Nancy Martin, Jack W. Carlyle, and Michael A. Harrison, editors, Proceedings of the 7th Annual ACM Symposium on Theory of Computing, May 5-7, 1975, Albuquerque, New Mexico, USA, pages 234–239. 1975. ACM. DOI: 10.1145/800116.803773
[MN23]
Jonas Meers and Julian Nowakowski. Solving the Hidden Number Problem for CSIDH and CSURF via Automated Coppersmith. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part IV, volume 14441 of Lecture Notes in Computer Science, pages 39–71. 2023. Springer. DOI: 10.1007/978-981-99-8730-6_2
[MNS21]
Alexander May, Julian Nowakowski, and Santanu Sarkar. Partial key exposure attack on short secret exponent CRT-RSA. In International Conference on the Theory and Application of Cryptology and Information Security, pages 99–129. 2021. Springer. DOI: 10.1007/978-3-030-92062-3_4
[MNS22]
Alexander May, Julian Nowakowski, and Santanu Sarkar. Approximate divisor multiples–factoring with only a third of the secret CRT-exponents. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 147–167. 2022. Springer. DOI: 10.1007/978-3-031-07082-2_6
[MR09]
Alexander May and Maike Ritzenhofen. Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint. In PKC 2009, volume 5443 of Lecture Notes in Computer Science, pages 1–14. 2009. Springer. DOI: 10.1007/978-3-642-00468-1_1
[RH23]
Keegan Ryan and Nadia Heninger. Fast Practical Lattice Reduction Through Iterated Compression. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part III, volume 14083 of Lecture Notes in Computer Science, pages 3–36. 2023. Springer. DOI: 10.1007/978-3-031-38548-3_1
[RSA78]
Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM, 21(2):120–126, 1978. DOI: 10.1145/359340.359342
[STK20]
Kaichi Suzuki, Atsushi Takayasu, and Noboru Kunihiro. Extended partial key exposure attacks on RSA: Improvement up to full size decryption exponents. Theor. Comput. Sci., 841:62–83, 2020. DOI: 10.1016/J.TCS.2020.07.004
[TK16]
Atsushi Takayasu and Noboru Kunihiro. How to Generalize RSA Cryptanalyses. In Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, and Bo-Yin Yang, editors, Public-Key Cryptography - PKC 2016 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part II, volume 9615 of Lecture Notes in Computer Science, pages 67–97. Springer 2016. DOI: 10.1007/978-3-662-49387-8_4
[TK19]
Atsushi Takayasu and Noboru Kunihiro. Partial key exposure attacks on RSA: Achieving the Boneh-Durfee bound. Theor. Comput. Sci., 761:51–77, 2019. DOI: 10.1016/J.TCS.2018.08.021
[Wie90]
Michael J. Wiener. Cryptanalysis of short RSA secret exponents. IEEE Trans. Inf. Theory, 36(3):553–558, 1990. DOI: 10.1109/18.54902
[ZvdPYS22]
Yuanyuan Zhou, Joop van de Pol, Yu Yu, and François-Xavier Standaert. A Third is All You Need: Extended Partial Key Exposure Attack on CRT-RSA with Additive Exponent Blinding. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part IV, volume 13794 of Lecture Notes in Computer Science, pages 508–536. 2022. Springer. DOI: 10.1007/978-3-031-22972-5_18
PDF
History
Submitted: 2024-07-08
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Yansong Feng, Abderrahmane Nitaj, and Yanbin Pan, Small Public Exponent Brings More: Improved Partial Key Exposure Attacks against RSA. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ahjbhey6b.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.