Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
A Timing-Resistant Elliptic Curve Backdoor in RSA
verfasst von : Adam L. Young, Moti Yung
Erschienen in: Information Security and Cryptology
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 present a fast algorithm for finding pairs of backdoor RSA primes (
p
,
q
) given a security parameter. Such pairs posses an
asymmetric backdoor
that gives the designer the exclusive ability to factor
n
=
pq
, even when the key generation algorithm is public. Our algorithm uses a pair of twisted curves over GF(2
257
) and we present the first incremental search method to generate such primes. The search causes the
$\frac{1}{2}$
log(
n
)+O(log(log(
n
))) least significant bits of
n
to be modified during key generation after
p
is selected and before
q
is determined. However, we show that this is tolerable by using point compression and ECDH. We also present the first rigorous experimental benchmarks of an RSA asymmetric backdoor and show that our OpenSSL-based implementation outperforms OpenSSL RSA key generation. Our application is highly efficient key recovery. Of independent interest, we motivate the need to find large binary twists. We present the twist we generated and how we found it.