## Small Public Exponent Brings More: Improved Partial Key Exposure Attacks against RSA

### Authors

### 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

*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

*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

*EUROCRYPT '99*, volume 1592 of

*Lecture Notes in Computer Science*, pages 1–11. 1999. Springer. DOI: 10.1007/3-540-48910-X_1

*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

^{+}20]

*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

*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

*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

*J. Cryptol.*, 20(1):39–50, 2007. DOI: 10.1007/S00145-006-0433-6

*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

*J. Cryptol.*, 10(4):233–260, 1997. DOI: 10.1007/S001459900030

*Appl. Algebra Eng. Commun. Comput.*, 13(1):17–28, 2002. DOI: 10.1007/S002000100088

*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

*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

*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

*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

*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

*Mathematische Annalen*, 261:515–534, 1982. DOI: 10.1007/BF01457454

*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

*Network security traceback attack and react in the United States Department of Defense network*. Trafford Publishing 2013.

*New RSA Vulnerabilities Using Lattice Reduction Methods*. PhD thesis, University of Paderborn, 2003.

*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

*IACR Communications in Cryptology*, 1(1), 2024. DOI: 10.62056/ahjbksdja

*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

*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

*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

*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

*PKC 2009*, volume 5443 of

*Lecture Notes in Computer Science*, pages 1–14. 2009. Springer. DOI: 10.1007/978-3-642-00468-1_1

*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

*Commun. ACM*, 21(2):120–126, 1978. DOI: 10.1145/359340.359342

*Theor. Comput. Sci.*, 841:62–83, 2020. DOI: 10.1016/J.TCS.2020.07.004

*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

*Theor. Comput. Sci.*, 761:51–77, 2019. DOI: 10.1016/J.TCS.2018.08.021

*IEEE Trans. Inf. Theory*, 36(3):553–558, 1990. DOI: 10.1109/18.54902

*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

##### 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.