Cryptanalysis of multi-prime RSA with small prime difference

Abstract

We show that the attack of de Weger on RSA using continued fractions extends to Multi-Prime RSA. Let (n,e) be a Multi-Prime RSA public-key with private key d, where n = p 1 p 2⋯p r is a product of r distinct balanced (roughly of the same bit size) primes, and p 1 < p 2 <⋯< p r. We show that if p r - p 1 = n α, 0 < α ≤ 1/r, r ≥ 3 and 2d 2 + 1 < n 2/r-α/6r, then Multi-Prime RSA is insecure. © 2012 Springer-Verlag.