secp256k1

[DeathAndTaxes]

How many hundreds of transactions per second is your smartcard going to process? 

[1714897509]

1714897509

[1714897509]

1714897509

[1714897509]

1714897509

[Mike Hearn]

Hal posted some example code for it, a while ago. I don't remember if it was implemented.

[kjj]

Hal posted some example code for it, a while ago. I don't remember if it was implemented.

Found it!

here

[Dusty]

I also discussed with satoshi, and he said that his employers at the NSA wanted him to create the first P2P currency with a back door in it. That back door happens to be in this specific elliptic curve. Government supercomputers searched for a random elliptic curve that contained a back door.

Just joking, but that's my conspiracy theory. Actually if there is no particular reason for this elliptic curve to be chosen, that is actually suspicious...

If I'm not mistaken, while at the time this was just a conspiracy theory, nowadays we know that something exactly of that kind happened and NSA pushed a cryptography standard exclusively because they had some kind of backdoor for it (some random and incomplete references: 1, 2, 3, 4, 5).

We also know that good cryptographic conventions requires to explain how arbitrary constants get chosen, expressly to rule out the possibility of using some particular algebraic field with known (to NSA or others) properties that can lead to advantages when implementing algorithms to break it.

So, each time an arbitrary constant is chosen without explaining how and why, a good cryptographer has reason to believe that something fishy is going on.

Someone says that Satoshi is the nickname of an NSA working group and I really don't care if this is true or not because the code is open source and everyone can verify whether the code and the protocol are sound.

But I'm really not at ease knowing that every signature in a Bitcoin transaction is implemented using a very particular and unusual elliptic curve that has been selected for an unknown reason that his chooser is unwilling to elaborate on.

[gmaxwell]

But I'm really not at ease knowing that every signature in a Bitcoin transaction is implemented using a very particular and unusual elliptic curve that has been selected for an unknown reason that his chooser is unwilling to elaborate on.

You mean you are uneasy that he chose the _only_ standardized curve at the time without unexplained parameters?

[Dusty]

You mean you are uneasy that he chose the _only_ standardized curve at the time without unexplained parameters?

Can you please elaborate a bit more on the subject?
I'm sincerely interested, thanks.

[Dusty]

You mean you are uneasy that he chose the _only_ standardized curve at the time without unexplained parameters?

Can you please elaborate a bit more on the subject?

I reply to myself, found reading this other thread:
http://crypto.stackexchange.com/questions/10263/should-we-trust-the-nist-recommended-ecc-parameters/10273#10273

[bluemeanie1]

 The advantage to Koblitz curves is faster arithmetic.  I would imagine they are thought to be appropriate for bitcoin because of the number of ECDSA operations that are required.  When you use Koblitz curves, part of the equation can be dropped(the ax part as a=0 in secp256k1).

 -bm

 

Bitcoin uses elliptic curve cryptography for its keys and signatures, but the specific curve used is pretty unusual. It is called secp256k1, from a standard called SEC2, published by a group called SECG, http://www.secg.org/index.php?action=secg,docs_secg.

Taking the name secp256k1 apart, sec comes from the standard, p means that the curve coordinates are a prime field, 256 means the prime is 256 bits long, k means it is a variant on a so-called Koblitz curve, and 1 means it is the first (and only) curve of that type in the standard. This is all fine and common, except for the Koblitz part. Koblitz curves are a special kind of elliptic curves that have some internal structure that can be used to speed up calculations. Standards bodies have tended to shy away from Koblitz curves out of fear that this internal structure could someday be exploited to yield a new attack. Indeed certain Koblitz curves, but not secp256k1, lose a couple dozen bits of security to a known attack.

Most standards use what are called random curves when they are using prime fields. SEC2 also includes random curves, and the very next one after secp256k1 is called secp256r1. This curve, secp256r1, is widely standardized and used, including by the U.S. government, which calls it P-256.

I don't know the rationale behind using secp256k1. It has the potential for speed - I've seen estimates from 33% to 50% speedup - but the techniques are quite esoteric as it is not a conventional Koblitz curve, and I doubt that the OpenSSL implementation exploits this. I'm not losing much sleep over the theoretical possibility of an attack on secp256k1, but it is likely to be less widely implemented. I looked at BouncyCastle, a widely used Java crypto library, and they had commented out the code for secp256k1. Whereas secp256r1 (P-256) might well be a default curve for the native crypto keys in future OS's.

It wouldn't be a change to make lightly, but we might want to consider changing to this more widely used standard curve. We'd have to mark the new keys to distinguish them, and be prepared to handle both kinds of signatures.

One question is whether we would ever reach a point where clients could eliminate support for the old curve? Maybe just miners could retain support, and the fact that a transaction got into a block with some confirmations would be good enough evidence that it was valid.