How the NSA (may have) put a backdoor in RSA’s cryptography: A technical primer

Author Nick Sullivan worked for six years at Apple on many of its most important cryptography efforts before recently joining CloudFlare, where he is a systems engineer. He has a degree in mathematics from the University of Waterloo and a Masters in computer science with a concentration in cryptography from the University of Calgary. This post was originally written for the CloudFlare blog and has been lightly edited to appear on Ars.

There has been a lot of news lately about nefarious-sounding backdoors being inserted into cryptographic standards and toolkits. One algorithm, a pseudo-random bit generator, Dual_EC_DRBG, was ratified by the National Institute of Standards and Technology (NIST) in 2007 and is attracting a lot of attention for having a potential backdoor. This is the algorithm that the NSA reportedly paid RSA $10 million in exchange for making it the default way for its BSAFE crypto toolkit to generated random numbers.

So how is that possible? This is a technical primer that explains what a backdoor is, how easy it can be to create your own, and the dangerous consequences of using a random number generator that was designed to have a backdoor. This is necessarily a long technical discussion, but hopefully by the end it should be clear why Dual_EC_DRBG has such a bad reputation.