Ding-ding. It’s secp256k1 and Curve 25519 in Red Corner and NIST in the Blue Corner

Ding-ding. It’s secp256k1 and Curve 25519 in Red Corner and NIST in the Blue Corner

It’s a battle for the protection of the Internet (and its users)

The world of security has its foundation in the usage of encryption, and Cybercrime thrives because we have build such an untrusted digital world. We secure data with encryption, prove its integrity using encryption, and also prove identities with encryption.

In our modern world, encryption should provide the foundation layer of the Internet, in the same way that we never consider living in a house without a lock on the door. And at the core of this security is the magic of elliptic curve cryptography (ECC) and prime numbers.

With symmetric key methods, such as AES and DES, we define the security strength by the number of bits in the key. For most purposes a 128-bit key is strong enough, as it would take all of the energy on the planet to crack just a single key. For public key encryption, such as with ECC and RSA, the strength is often defined by the length of the prime number used. For RSA, we have very long prime numbers, such as with 2,048 bits, but with ECC, we have relatively small primes, such as with 256 bits. A 256-bit ECC key, for example, is as strong as a 3,072-bit RSA key.

So should we use a defined standard, such as defined by NIST? Well, the standard form of ECC is:

y²=x³+ax +b (mod p)

and where p is the prime number used. The NIST standards include [here]:

P-192:
p = 2¹⁹²−2⁶⁴−1
a=−3 b=2455155546008943817740293915197451784769108058161191238065

P-244:
p = 2²²⁴−2⁹⁶+1
a=−3
b=18958286285566608000408668544493926415504680968679321075787234672564

P-256:
p = 2²⁵⁶−2²²⁴+2¹⁹²+2⁹⁶−1
a=−3
b=41058363725152142129326129780047268409114441015993725554835256314039467401291

But few people trust the NIST curves because of Snowden. Bruce Schneier wrote:

I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry.

and that:

I looked at the random seed values for the P-xxxr curves. For example, P-256r’s seed is c49d360886e704936a6678e1139d26b7819f7e90. No justification is given for that value.

and:

I now personally consider this to be smoking evidence that the parameters are cooked.

And so, Bitcoin, Tor and so many applications avoid the NIST derived curves, and instead focus on secp256k1 and Curve 25519. Bitcoin uses secp256k1 which has a prime of 2²⁵⁶-2³²−977, and Tor uses Curve 25519 which has prime of 2²⁵⁵-19.

And so when you generate your Bitcoin wallet you use secp256k1 to do this:

In this case the private key is a 256-bit random value (priv) and the public key is (priv x G), and where we add a generator point priv times. We see the public key is 512 bits (64 bytes or 128 hex characters), as it is an (x,y) point on the curve (the 0x04 at the start is just an identified for the point).

If you are interested in ECC, there’s lots of examples here:

And so, NIST lost this boxing match, when it came to random number generators, there was a bit more trouble when Microsoft discovered a possible backdoor function: