Paper 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.

Note: We remove the latex from the abstract on the web to make it easy to read.