Cloud of suspicion lifted from NIST curves

NIST published a set of elliptic curves for cryptography in 2000. The seeds for the curves were supplied by the NSA, and cryptographers suspected the agency may have installed backdoors in the curves. And not without reason: the NSA did insert a backdoor in the Dual_EC_DRBG random number generator. Two days ago researchers at Anthropic [1] showed that the NIST curves were not seeded with a backdoor. The rest of this post will give the background necessary to appreciate this result. The security of elliptic curve cryptography depends on the difficult of solving the discrete logarithm problem. In the context of elliptic curve arithmetic, the analog of exponentiation is easy but the analog of taking logarithms is hard. In general it’s not practical to compute discrete logarithms over large elliptic curves. But it could be easy for someone with inside information to compute discrete logarithms if something about the curve was not “general.” Specifically, the NIST curves have the form y² =…