Paper 2024/1329

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

Yansong Feng, Academy of Mathematics and Systems Science
Abderrahmane Nitaj, Normandie University
Yanbin Pan, Academy of Mathematics and Systems Science
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 MSBs of d and small e. The key idea is that under such a setting we can usually obtain more information about the prime factors of N and then, by solving a univariate modular polynomial equation using Coppersmith's method, N can be factored in polynomial time. Compared to previous results, we reduce the number of the leaked bits in that are needed to mount the attack by bits. For , previous work required an additional enumeration of 17 bits to achieve our new bound, resulting in a (or 1,024) x increase in time consumption. Furthermore, our experiments show that for a -bit modulus , our attack can achieve the theoretical bound on a simple personal computer, which verifies the new method.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in CIC 2024
DOI
10.62056/ahjbhey6b
Keywords
RSAFactorizationCoppersmith's methodPartial key attack
Contact author(s)
fengyansong @ amss ac cn
abderrahmane nitaj @ unicaen fr
panyanbin @ amss ac cn
History
2024-10-07: last of 2 revisions
2024-08-25: received
See all versions
Short URL
https://ia.cr/2024/1329
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1329,
      author = {Yansong Feng and Abderrahmane Nitaj and Yanbin Pan},
      title = {Small Public Exponent Brings More: Improved Partial Key Exposure Attacks against {RSA}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1329},
      year = {2024},
      doi = {10.62056/ahjbhey6b},
      url = {https://eprint.iacr.org/2024/1329}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.