• DocumentCode
    3300577
  • Title

    A new RSA vulnerability using continued fractions

  • Author

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

  • Author_Institution
    Ain Shams Univ., Cairo
  • fYear
    2008
  • fDate
    March 31 2008-April 4 2008
  • Firstpage
    694
  • Lastpage
    701
  • Abstract
    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 po ges 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.
  • Keywords
    approximation theory; computational complexity; matrix decomposition; public key cryptography; Coppersmith method; RSA public key; RSA vulnerability; approximation theory; continued fractions; deterministic polynomial time; factorization; Computer science; Data privacy; Equations; Lattices; Mathematics; Polynomials; Public key; Public key cryptography; Smart cards; Coppersmith’s method; Lattice basis reduction; RSA; Wiener’s attack; continued fractions; low exponent RSA;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computer Systems and Applications, 2008. AICCSA 2008. IEEE/ACS International Conference on
  • Conference_Location
    Doha
  • Print_ISBN
    978-1-4244-1967-8
  • Electronic_ISBN
    978-1-4244-1968-5
  • Type

    conf

  • DOI
    10.1109/AICCSA.2008.4493604
  • Filename
    4493604