Cryptology ePrint Archive: Report 2015/1137
A New Factoring Attack on Multi-Prime RSA with Small Prime Difference
Mengce Zheng and Honggang Hu
Abstract: In this paper, we study the security of multi-prime RSA whose modulus is N=p_1p_2...p_r for r>=3 with small prime difference of size N^\gamma. In ACISP 2013, Zhang and Takagi showed a Fermat-like factoring attack, which can directly factor N for \gamma<1/r^2. We improve this bound to theoretically achieve \gamma<2/(r(r+2)) by a new factoring attack. Furthermore, we also analyse specific MPRSA with imbalanced prime factors. Experimental results are provided to show the efficiency of our attack.
Category / Keywords: public-key cryptography / Factoring attack, multi-prime RSA, small prime difference, cryptanalysis, lattice
Date: received 24 Nov 2015, last revised 26 Nov 2015
Contact author: mczheng at mail ustc edu cn
Available format(s): PDF | BibTeX Citation
Note: We remove the latex from the abstract on the web to make it easy to read.
Version: 20151127:051213 (All versions of this report)
Short URL: ia.cr/2015/1137
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]