Paper 2015/1137
Improved Factoring Attacks on Multi-Prime RSA with Small Prime Difference
Mengce Zheng, Noboru Kunihiro, and Honggang Hu
Abstract
In this paper, we study the security of multi-prime RSA with small prime difference and propose two improved factoring attacks. The modulus involved in this variant is the product of r distinct prime factors of the same bit-size. Zhang and Takagi (ACISP 2013) showed a Fermat-like factoring attack on multi-prime RSA. In order to improve the previous result, we gather more information about the prime factors to derive r simultaneous modular equations. The first attack is to combine all the equations and solve one multivariate equation by generic lattice approaches. Since the equation form is similar to multi-prime Phi-hiding problem, we propose the second attack by applying the optimal linearization technique. We also show that our attacks can achieve better bounds in the experiments.
Note: We remove the latex from the abstract on the web to make it easy to read.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. ACISP 2017
- Keywords
- CryptanalysisMulti-prime RSASmall prime differenceFactoring attackLattice-based linearization technique
- Contact author(s)
- mengce zheng @ gmail com
- History
- 2018-03-18: last of 2 revisions
- 2015-11-26: received
- See all versions
- Short URL
- https://ia.cr/2015/1137
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2015/1137,
author = {Mengce Zheng and Noboru Kunihiro and Honggang Hu},
title = {Improved Factoring Attacks on Multi-Prime {RSA} with Small Prime Difference},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/1137},
year = {2015},
url = {https://eprint.iacr.org/2015/1137}
}
