A new RSA vulnerability using continued fractions
Dieaa I. Nassr, Hatem M. Bahig, Ashraf Bhery, Sameh S. Daoud · 2008
Let (n = pq, e) be an RSA public key with private exponent d = ndelta, where p and q are large primes of the same bit size. Suppose that poges radicn be an approximation of p with |p - po| les 1/8nalpha, alpha les 1/2. Using continued fractions, we show that the system is insecure if delta < 1-alpha/2. Our result is deterministic polynomial time and an extension of Coppersmith's result on a factorization.