Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Cryptanalysis of RSA with Multiple Small Secret Exponents
verfasst von : Atsushi Takayasu, Noboru Kunihiro
Erschienen in: Information Security and Privacy
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we study the security of RSA when there are multiple public/secret exponents (
e
1
,
d
1
), …, (
e
n
,
d
n
) with the same public modulus
N
. We assume that all secret exponents are smaller than
N
β
. When
n
= 1, Boneh and Durfee proposed a polynomial time algorithm to factor the public modulus
N
. The algorithm works provided that
$ \beta<1-1/\sqrt{2}$
. So far, several generalizations of the attacks for arbitrary
n
have been proposed. However, these attacks do not achieve Boneh and Durfee’s bound for
n
= 1. In this paper, we propose an algorithm which is the exact generalization of Boneh and Durfee’s algorithm. Our algorithm works when
$ \beta<1-\sqrt{2/(3n+1)}$
. Our bound is better than all previous results for all
n
≥ 2. We construct the lattices by collecting as many helpful polynomials as possible. The collections reduce the volume of the lattices and enable us to improve the bound.