International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Yansong Feng , Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, School of Mathematical Sciences, University of Chinese Academy of Sciences
Abderrahmane Nitaj , Normandie University
Yanbin Pan , Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, School of Mathematical Sciences, University of Chinese Academy of Sciences
Download:
DOI: 10.62056/ahjbhey6b
URL: https://cic.iacr.org//p/1/3/29
Search ePrint
Search Google
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.

BibTeX
@article{cic-2024-34840,
  title={Small Public Exponent Brings More: Improved Partial Key Exposure Attacks against RSA},
  journal={cic},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 3},
  url={https://cic.iacr.org//p/1/3/29},
  doi={10.62056/ahjbhey6b},
  author={Yansong Feng and Abderrahmane Nitaj and Yanbin Pan},
  year=2024
}