Chapter 10: An Elliptic Curve Asymmetric Backdoor in OpenSSL RSA Key Generation
Adam L. Young, Moti M. Yung · 2006
In this chapter we present an experimental implementation of an asymmetric backdoor in RSA key generation. The implementation is written in ANSI C. We codified what it means for an asymmetric backdoor to be secure (for the designer) in our definition of a secretly embedded trapdoor with universal protection (SETUP). The main properties of a SETUP are: (1) the complete code for the backdoor does not enable anyone except the designer to use the backdoor, and (2) the key pairs that are output by the backdoor RSA key generator appear to all probabilistic polynomial time algorithms like normal (no backdoor) RSA key pairs. We introduced the notion of a SETUP at Crypto ’96 [15] and there has been significant advances in the area since then. This chapter and the corresponding appendix constitutes Fundamental Research in cryptovirology and expands on our elliptic curve backdoor in RSA key generation that we presented at the Selected Areas in Cryptography conference in 2005. In particular, the design employs several algorithmic improvements that enable the key generator to run faster. This chapter provides a walk-through of the experimental implementation. The backdoor is based on OpenSSL and the code for it appears in the appendix that is associated with this chapter. For over 10 years we have advocated that the industry change the way RSA keys are generated. We devised and presented heuristic methods that completely foil this entire class of backdoors in RSA key generation [15, 12]. The approach in [12] is reminiscent of the NIST FIPS 186-2 DSA parameter generation method. ∗ If this file was obtained from a publicly accessible website other than the website www.cryptovirology.com then (1) the entity or entities that made it available are in violation of our copyright and (2) the contents of this file should therefore not be trusted. Please obtain the latest version directly from the official Cryptovirology Labs website at: