Is secp256r1 more secure than secp256k1?

Question

Curves secp256r1 and secp256k1 are both examples of two elliptic curves used in various asymmetric cryptography.

Googling for these shows most of the top results are Bitcoin related. I've heard the claim that…

Satoshi picked non-standard crypto which conventional wisdom says will be cracked in 5-10 years.

There is this discussion on bitcointalk with various opinions to both sides of the argument (also check out this article). I would like to take it away from Bitcoin and into the general cryptographic question: is secp256r1 indeed more secure in some sense than secp256k1?

Answer 1

The main difference is that secp256k1 is a Koblitz curve, while secp256r1 is not. Koblitz curves are known to be a few bits weaker than other curves, but since we are talking about 256-bit curves, neither is broken in "5-10 years" unless there's a breakthrough.

The other difference is how the parameters have been chosen. In secp256r1 they are supposedly from random numbers, however, it is impossible to prove that's really the case. See e.g. these slides from Bernstein and Lange for an easily understandable treatment.

The Koblitz curve, on the other hand, has had its parameters chosen relatively rigidly. The post runeks linked in the comments has an explanation for why they were chosen.

So rather than saying one is more secure, I would say that the risks are different. If neither curve has backdoors or accidental weaknesses, both are secure. The few extra bits of security secp256r1 has won't matter unless you happen to own e.g. a moderately sized quantum computer that can just manage one but not the other. It would have been easier to backdoor the secp256r1 curve, but on the other hand, Koblitz curves as a class could be completely weak in some way not currently known.

I.e. which to prefer is somewhat subjective. If you don't like Koblitz curves but are afraid secp256r1 is backdoored, there's always the option to use some other curve designed according to criteria you like. (Though you cannot, of course, change what BTC uses.)

Answer 2

The curves secp256r1 and secp256k1 have comparable security.

If we consider only the best known attacks today, they have very close security. Both curves are defined over prime fields and have no known weakness, therefore the best attack that applies is Pollard's Rho. Its complexity is: $\sqrt{\frac{{\pi}n}{2m}}$ where $n$ is the order of the curve (if it's prime, such as in our cases) and $m$ is the order of the automorphism (see this paper for the details of the following).

Now, all elliptic curves have an automorphism of order 2, this is provided by the point inversion map, i.e., the fact that for $P=(x,y); -P=(x,-y)$.

secp256k1 have an additional automorphism because it belongs to a special class of elliptic curves, sometimes referred to as Koblitz (although this has lead to some confusion, and some people have mistakenly called it a binary curve), which have an additional automorphism. This allows to map the the point $P=(x,y)$ to either $\lambda P=(\beta x,y)$ or $\lambda^2 P=(\beta^2 x,y)$ where $\beta = \sqrt[3]{1} \pmod{p},\lambda = \sqrt[3]{1} \pmod{n}$. This can be combined with the inversion map and achieve order 6. Given the two numerical values for the orders, using base 2 logs we obtain:

Security secp256r1 = $\log_2\sqrt{\frac{{\pi}n_{secp256r1}}{4}}=127.83$

Security secp256k1 = $\log_2\sqrt{\frac{{\pi}n_{secp256k1}}{12}}=127.03$

Which are comparable.

Then, considering rigidity, secp256k1 is more rigid than secp256r1. So it is theoretically possible that secp256r1 was chosen to belong to a secret class of elliptic curves that are not as secure as we think.

Then, considering special class of elliptic curves, secp256k1 belongs to a special class, because its parameters were not randomly chosen, while those of secp256r1 looks random (but we can't be sure due to secp256r1 rigidity issue). Thus it is theoretically possible that secp256k1's class will be found not as secure as we currently think. But this class is well known, and so far the only issue is that additional negation map, which, by the way allows for faster scalar multiplication computation than, e.g., secp256r1.

It is difficult to judge how the rigidity and special class considerations affects the overall security of the curves. On one hand the NSA generated secp256r1 using a process that people don't fully trust, on the other hand secp256k1 has been chosen to belong to a special class of elliptic curves.

In my personal opinion these two facts cancel each other. Therefore, in this case, I chose to stick to the current best known attack as measure of security and conclude that they have comparable security.

Answer 3

Here's a good amount of hard data on a variety of curves, well-analysed and the findings summarised in a readable way:

http://safecurves.cr.yp.to/

The article linked from this answer is not nearly up to the same standard of analysis and, I would argue, deceptive, whether maliciously (v. unlikely) or just due to lack of understanding of basic research methodology.

Answer 4

First secp256r1 is a random and secp256k1 is a Koblitz curve. So according to this article:

Koblitz curves should be avoided, [...] as they does not have enough warranty on crypto analytic activity and effectively they are:

• Not part of NSA Suite-B cryptography selection
• Not part of ECC Brainpool selection
• Not part of ANSI X9.62 selection
• Not part of OpenPGP ECC extension selection
• Not part of Kerberos extension for ECC curve selection