Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint
verfasst von : Alexander May, Maike Ritzenhofen
Erschienen in: Public Key Cryptography – PKC 2009
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
We address the problem of polynomial time factoring RSA moduli
N
1
=
p
1
q
1
with the help of an oracle. As opposed to other approaches that require an oracle that
explicitly
outputs bits of
p
1
, we use an oracle that gives only
implicit
information about
p
1
. Namely, our oracle outputs a different
N
2
=
p
2
q
2
such that
p
1
and
p
2
share the
t
least significant bits. Surprisingly, this implicit information is already sufficient to efficiently factor
N
1
,
N
2
provided that
t
is large enough. We then generalize this approach to more than one oracle query.