Cryptanalysis of RSA with small prime difference (Q1598120)

The author proves that choosing an RSA modulus with a small difference between its prime factors yields improvements on the small private exponent attacks of Wiener and Boneh-Durfee. The following theorem is the main result of this paper. Theorem. Let \(p,q\) be large primes of about the same size, \(n=pq\) and \(\Delta=|p-q|\). Let \(e,d\) be integers \(>1\) and \(<\varphi (n)\), satisfying \(ed\equiv 1\pmod{\varphi (n)}\). Put \(\Delta=n^{\beta}\) and \(d=n^{\delta}\). Given only \(n\) and \(e\), the factors \(p,q\) of \(n\) and the number \(d\) can be recovered efficiently whenever \(2-4\beta<\delta<1-\sqrt{2\beta -\frac 12}\) or \(\delta<\frac 16(4\beta +5)-\frac 13\sqrt{(4\beta +5)(4\beta -1)}\).