A new RSA vulnerability using continued fractions

Dieaa I. Nassr, Hatem M. Bahig, Ashraf Bhery, Sameh S. Daoud

2008 · 16 citations · 13 references

Concepts

Abstract

Let (n = pq, e) be an RSA public key with private exponent d = n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">delta</sup> , where p and q are large primes of the same bit size. Suppose that p <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o</sub> ges radicn be an approximation of p with |p - po| les 1/8n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">alpha</sup> , 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.

References

13