Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
A New Related Message Attack on RSA
verfasst von : Oded Yacobi, Yacov Yacobi
Erschienen in: Theoretical Computer Science
Verlag: Springer Berlin Heidelberg
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
Coppersmith, Franklin, Patarin, and Reiter show that given two RSA cryptograms
x
e
mod
N
and (
ax
+
b
)
e
mod
N
for known constants
a
,
b
∈ ℤ
N
, one can usually compute
x
in
O
(
e
log
2
e
) ℤ
N
-operations (there are
O
(
e
2
) messages for which the method fails).
We show that given
e
cryptograms
c
i
≡ (
a
i
x
+
b
i
)
e
mod
N
,
i
=0,1,...
e
–1, for any known constants
a
i
,
b
i
∈ ℤ
N
, one can deterministically compute
x
in
O
(
e
) ℤ
N
-operations that depend on the cryptograms, after a pre-processing that depends only on the constants. The complexity of the pre-processing is
O
(
e
log
2
e
) ℤ
N
-operations, and can be amortized over many instances. We also consider a special case where the overall cost of the attack is
O
(
e
) ℤ
N
-operations. Our tools are borrowed from numerical-analysis and adapted to handle formal polynomials over finite-rings. To the best of our knowledge their use in cryptanalysis is novel.