Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Deterministic Polynomial Time Equivalence Between Factoring and Key-Recovery Attack on Takagi’s RSA
verfasst von : Noboru Kunihiro, Kaoru Kurosawa
Erschienen in: Public Key Cryptography – PKC 2007
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
For RSA, May showed a deterministic polynomial time equivalence of computing
d
to factoring
N
( =
pq
). On the other hand, Takagi showed a variant of RSA such that the decryption algorithm is faster than the standard RSA, where
N
=
p
r
q
while
$ed=1 \bmod (p-1)(q-1)$
. In this paper, we show that a deterministic polynomial time equivalence also holds in this variant. The coefficient matrix
T
to which LLL algorithm is applied is no longer lower triangular, and hence we develop a new technique to overcome this problem.