A asymmetric key question on ECDSA and Bitcoin

[fevirfevir]

Hi all,

In my quest to further understand the mechanics of Bitcoin, I ran into a asymmetric key question.

The Bitcoin wiki simply states that for creating private/public keys, Bitcoin applies the Elliptic Curve Digital Signature Algorithm or ECDSA (https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm). In the Bitcoin developer guide it reads that Bitcoin uses the Elliptic Curve Digital Signature Algorithm (ECDSA) with the secp256k1 curve (https://bitcoin.org/en/developer-guide#transactions).
However, in this scientific article (http://link.springer.com/chapter/10.1007%2F978-3-319-12400-1_35#page-1) it reads that Bitcoin uses the “Elliptic Curve DSA over the NIST P-256 curve”.

This overview of curves http://safecurves.cr.yp.to/  indicates that the two curves above are not considered safe.

When I Google for “bitcoin ecdsa "p-256" site:github.com” and “bitcoin ecdsa "secp256" site:github.com”, both return results. The code itself doesn't provide an answer, to me  (sorry, lousy coder here).

So, my questions are:
1. Which ECDSA curve is used in Bitcoin to generate a private key? Where does it read in the code?
2. Why are both curves mentioned on Bitcoin's Github?
3. If either is used, is that a smart thing to do, considering that both are not considered safe? Wouldn't it be better to use a 'safe' curve?
4. Would it be possible to use both curves amongst multiple users, depending on a user's preferences?
5. Extending that question, if someone found a major flaw in the ECDSA algorithm currently used, would it be possible to switch to another ECDSA algorithm? (no worries, I didn't find a major flaw :-) )

Thanks for reading.

Fevir

[Kazimir]

1. Which ECDSA curve is used in Bitcoin to generate a private key? Where does it read in the code?

Bitcoin's ECDSA uses secp256k1.

What code? There are multiple Bitcoin implementations. For example, in bitcoinjs: https://github.com/bitcoinjs/bitcoinjs-lib/search?q=secp256k1

2. Why are both curves mentioned on Bitcoin's Github?

Not sure, I assume P-256 might have been discussed as an alternative. But it's definitely secp256k1.

3. If either is used, is that a smart thing to do, considering that both are not considered safe? Wouldn't it be better to use a 'safe' curve?

'Safe' is very relative here. It refers to certain mathematical properties, which are still purely theoretical and having absolutely no implications for real life safety. At least not yet, and this is extremely unlikely to change within the foreseeable future. Even if a vulnerability would come to light, it's typically discovered as a theoretical, possible issue in the distant future, with many years between moment of discovery and actual possibility to effectively put in in practice.

Remember, even with its 'unsafe' curves like secp256k1, Bitcoin is still lightyears ahead of regular financial system and payment protocols (like wire transfers, online banking, visa, paypal, etc) in terms of security.

If I'm not mistaken, Satoshi chose secp256k1 because:
1. it's provably not rigged, i.e. uses only deterministic constants, and no funny, arbitrary, supposedly 'pseudo random' or other suspicious values.
2. speed, secp256k1 signature and validation could be performed considerably faster than other, 'heavier' curves (although one could argue if that's still a legitimate criterium).

4. Would it be possible to use both curves amongst multiple users, depending on a user's preferences?

Yes, a signature could start with a version bit or byte or something, although obviously this would require a hard fork.

5. Extending that question, if someone found a major flaw in the ECDSA algorithm currently used, would it be possible to switch to another ECDSA algorithm? (no worries, I didn't find a major flaw :-) )

Yes. Although again this would require a hard fork of course. Same for the hashing algorithms involved (e.g. if sha256 is broken). Bitcoin is not 'set in stone', whenever the need arises and consensus is reached (and I think, when future security is at stake, consensus will be reached much easier than the ongoing blocksize debate) then Bitcoin could adapt.

[jl2012]

Yes, a signature could start with a version bit or byte or something, although obviously this would require a hard fork.

Any new OP codes (including signature checking codes) could be introduced by soft fork (Consider P2SH-like technique)

[fevirfevir]

Great answers, that really is helpful. Thanks!

[gmaxwell]

FWIW that site isn't an "overview of curves", it's a site that exists to promote the authors solution.  While their curve selection is a fine one, some of the criteria they choose is rather tortured and the things secp256k1 "fails" are not really relevant (at least for our usage).  Meanwhile, there are other criteria which they've not included which they could have which their own perferred choices would fail-- for example, having a cofactor (which has actually resulted in vulnerabilities in protocols people created; ... which I'm not aware of happening as a result of e.g. a failure to have a unified addition law-- something they've faulted curves for because in theory the extra complexity ~might~ result in a bad implementation).   The page is thoughful overall and lists a number of interesting considerations, but it's the discussion thats interesting and worthwhile. The binary yes/no on the site does a disservice.