ECDSA is a signing algorithm in cryptography. You might have seen it in use in SSH (ssh-keygen -t ecdsa). Also, most cryptocurrencies use ECDSA as the signing algorithm to prove that you own the coins in an address.
An elliptic curve is basically described by an equation like $$$y^2 = x^3 + 7$$$, or more accurately, in a finite field mod a power of 2 or a prime, like $$$y^2 \equiv x^3 + 7 \pmod{p}$$$, where $$$p$$$ is large, like $$$2^{256}$$$ large.
In short, the algorithm works by generating a private key $$$d$$$, which is a random number less than the order of the curve ( DO NOT pick $$$d=4$$$ like someone did ), and there's a public point $$$G$$$ called the generator point. The public key is the (x, y)-coordinates of $$$d \cdot G$$$, where $$$\cdot$$$ is multiplication.
Adding and multiplying points is a little convoluted and is described here. It's a little different in finite fields, and you can find an example implementation on my GitHub.
In short, ECDSA works because "division" (technically discrete logarithm problem) on an elliptic curve is supposed to be really hard, while multiplication is easy. If I give you $$$xG$$$ and $$$yG$$$, you can trivially add those two points together to get $$$(x+y)G$$$, but finding what number $$$x$$$ was multiplied with $$$G$$$ to give $$$xG$$$ is really hard.
For instance, find what $$$x$$$ generated this point $$$xG$$$: (101143937713719082963090668683011527973146442333401502687785111310791413372479, 38862116509156141457510692564259449296113038651200971193676748814312797774871) on the curve secp256k1.
The ECDSA algorithm itself leverages this property with a few other things to generate cryptographically secure digital signatures. You can find the algorithm here on Wikipedia, though it is quite hard to understand. It took me a while to prove that it works.
The controversy
So, compare these two curves:
secp256k1 (used in bitcoin)
- Equation: $$$y^2 = x^3 + 7$$$
- Mod: $$$2^{256} - 2^{32} - 977$$$
NIST P-256 (the "standard" one)
- Equation: $$$y^2 = x^3 - 3x + 41058363725152142129326129780047268409114441015993725554835256314039467401291$$$
- Mod: $$$2^{256} - 2^{224} + 2^{192} + 2^{96} - 1$$$
"What the hell is $$$41058363725152142129326129780047268409114441015993725554835256314039467401291$$$?", you probably just said into your computer screen. Well, the NSA says they generated it "verifiably at random" by hashing the following seed: 0xc49d360886e704936a6678e1139d26b7819f7e90.
Yeah, doesn't look very "verifiably at random" to me. There were many concerns from experts that, if there are weak curves that appear occasionally (such as if 1 in $$$10^{15}$$$ curves have some weird mathematical property that breaks security), then the NSA can brute force to find one of those seeds and then backdoor this cryptosystem. Especially given NSA's reputation for trying to introduce backdoors into crypto at the time.
The argument against the backdoor was that the NSA uses its own curves to secure US government information, so they probably wouldn't intentionally build a weakness into their own curves that could be discovered by anyone. And decades of research by skilled mathematicians have turned up nothing.
Still, there was a lot of suspicion among the curves, which allegedly led Bitcoin to pick secp256k1 instead, and alternative standards (like Edwards Curve) being developed.
Claude proceeds to find the origin of the seeds
Seed searching effort over the last 25 years yielded nothing until now.
They were generated from a 1990s era LCG random number generator (which is famously weak btw). It was seeded with the time: August 16th, 1997.
This adds a lot more credibility to the argument that the seed was not backdoored, although technically it's still possible if, say, 1 in $$$10^7$$$ curves were backdoored and they just cycled through miscellaneous "nothing-up-my-sleeve numbers" before they found one. It also makes me scared for my job.
