A Timing-Resistant Elliptic Curve Backdoor in RSA

A Timing-Resistant Elliptic Curve Backdoor in RSA,10.1007/978-3-540-79499-8_33,Adam L. Young,Moti Yung

A Timing-Resistant Elliptic Curve Backdoor in RSA   (Citations: 1)
BibTex | RIS | RefWorks Download
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(2257) and we present the first incremental search method to generate such primes. The search causes the \frac12\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.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: