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 ]