Paper 2008/296
Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits
Hung-Min Sun, Mu-En Wu, Ron Steinfeld, Jian Guo, and Huaxiong Wang
Abstract
LSBS-RSA denotes an RSA system with modulus primes, p and q, sharing a large number of least significant bits. In ISC 2007, Zhao and Qi analyzed the security of short exponent LSBS-RSA. They claimed that short exponent LSBS-RSA is much more vulnerable to the lattice attack than the standard RSA. In this paper, we point out that there exist some errors in the calculation of Zhao & Qi's attack. After re-calculating, the result shows that their attack is unable for attacking RSA with primes sharing bits. Consequently, we give a revised version to make their attack feasible. We also propose a new method to further extend the security boundary, compared with the revised version. The proposed attack also supports the result of analogue Fermat factoring on LSBS-RSA, which claims that p and q cannot share more than (n/4) least significant bits, where n is the bit-length of pq. In conclusion, it is a trade-off between the number of sharing bits and the security level in LSBS-RSA. One should be more careful when using LSBS-RSA with short exponents.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- cryptanalysis
- Contact author(s)
- mn @ is cs nthu edu tw
- History
- 2008-07-23: revised
- 2008-07-04: received
- See all versions
- Short URL
- https://ia.cr/2008/296
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2008/296,
author = {Hung-Min Sun and Mu-En Wu and Ron Steinfeld and Jian Guo and Huaxiong Wang},
title = {Cryptanalysis of Short Exponent {RSA} with Primes Sharing Least Significant Bits},
howpublished = {Cryptology {ePrint} Archive, Paper 2008/296},
year = {2008},
url = {https://eprint.iacr.org/2008/296}
}
