A Unified Method for Private Exponent Attacks on RSA using Lattices - Normandie Université Accéder directement au contenu
Article Dans Une Revue International Journal of Foundations of Computer Science Année : 2019

A Unified Method for Private Exponent Attacks on RSA using Lattices

Hatem M Bahig
  • Fonction : Auteur
  • PersonId : 1056334

Résumé

Let (n = pq, e = n^β) be an RSA public key with private exponent d = n^δ , where p and q are large primes of the same bit size. At Eurocrypt 96, Coppersmith presented a polynomial-time algorithm for finding small roots of univariate modular equations based on lattice reduction and then succussed to factorize the RSA modulus. Since then, a series of attacks on the key equation ed − kφ(n) = 1 of RSA have been presented. In this paper, we show that many of such attacks can be unified in a single attack using a new notion called Coppersmith's interval. We determine a Coppersmith's interval for a given RSA public key (n, e). The interval is valid for any variant of RSA, such as Multi-Prime RSA, that uses the key equation. Then we show that RSA is insecure if δ < β + 1/3 α − 1/3 √ (12αβ + 4α^2) provided that we have approximation p0 ≥ √ n of p with |p − p0| ≤ 1/2 n^α , α ≤ 1/2. The attack is an extension of Coppersmith's result.
Fichier principal
Vignette du fichier
GeneralCoppersmith.pdf (484.42 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02320914 , version 1 (19-10-2019)

Identifiants

  • HAL Id : hal-02320914 , version 1

Citer

Hatem M Bahig, Dieaa I Nassr, Ashraf Bhery, Abderrahmane Nitaj. A Unified Method for Private Exponent Attacks on RSA using Lattices. International Journal of Foundations of Computer Science, In press. ⟨hal-02320914⟩
83 Consultations
736 Téléchargements

Partager

Gmail Facebook X LinkedIn More