Regarding secp256k1's security

[BlackHatCoiner]

I had read that while the key size of secp256k1 is 256 bits, the security level is 128 bits and I was trying to understand why, so please enlighten me.

Is it because there are two different private keys that return the same x coordinate? For instance, these private keys:

Code:

1
115792089237316195423570985008687907852837564279074904382605163141518161494336

Will return the same x-coordinate:

Code:

x: 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
y: 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

x: 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
y: b7c52588d95c3b9aa25b0403f1eef75702e84bb7597aabe663b82f6f04ef2777

These private keys:

Code:

2
115792089237316195423570985008687907852837564279074904382605163141518161494335

Will also return the same x-coordinate:

Code:

x: c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
y: e51e970159c23cc65c3a7be6b99315110809cd9acd992f1edc9bce55af301705

x: c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5
y: 1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a

And generally any number a and n-a return the same x-coordinate. So while the x-coordinate is 256 bits long, there are actually 2¹²⁸ different combinations it can take, but the y-coordinate between a and n-a will always give a different sign. Thus, the different combinations of a compressed public key are 2 * 2¹²⁸ or 2¹²⁹.

Am I wrong?

[1715197303]

1715197303

[1715197303]

1715197303

[1715197303]

1715197303

[1715197303]

1715197303

[NotATether]

There are actually 6 combinations so only 2^42.666666...7 unique combos.

You have just discovered an endomorphism, where two different Y's will solve the curve equation: y^2 = x^3 + 7

i.e. these two privkeys make two different but opposite Y's (because 115792089237316195423570985008687907852837564279074904382605163141518161494336 is just n-1 or, equivalently [mod n: the cyclic group 0..n, n-1...2n, etc.], it is -1).

And -1^2 = 1^2 = 1.

Now the other 3 combinations - and why only 3? see the next section - come from the X term.

Notice how the X is cubed which means it has three different roots if you consider it as a polynomial. There's obviously X, but there's also 0+Xi and 0-Xi (complex numbers). It follows the pattern [X + Yi], where the Y coord is an imaginary number.

This goes to say that if e.g. (7,0) was a valid point, then that, (0,7) and (0,n-7) would all reference similar points.

And (x,y), (y,x) and (y, n-x) would similarly reference similar points as well.

Now multiply 2*3 combos (endomorphisms) and you get a total of 6 endomorphisms: (x,y), (y,x) (y, n-x)  and (x,n-y), (n-y, x), (n-y, n-x).

It isn't something like they'd all have the same Y-point, but these points are accessible from the same X-coordinate as well. (See e.g. Roots of x^3+7 example)

So although the unique combos are drastically reduced, there is still the heavy operation of EC multiplication to do for all of them to get all the public keys, which severely slows down the number of combos you can generate per second (a few hundred thousand? I don't remember  )

[j2002ba2]

I had read that while the key size of secp256k1 is 256 bits, the security level is 128 bits and I was trying to understand why, so please enlighten me.

Is it because there are two different private keys that return the same x coordinate?

No.

The average number of group operations to find a private key from a public one using Pollard Rho is O(sqrt(N)), N being the group order.

Since N≈2²⁵⁶, sqrt(N)≈2¹²⁸, giving 128 bit security.

[pooya87]

https://crypto.stackexchange.com/questions/70260/why-is-the-strength-of-an-elliptic-curve-cryptography-ecc-half-the-size-of-the

I should add an explanation which may help. You should know that security of everything is usually measured in the maximum number of tries it takes to break it. Imagine if I selected a number between 0 and 10. You may need to make 10 guesses to find my number at worse case scenario so the security of my algorithm is "10" and since usually cryptography (and computer in general) is using base2 it is reported in bit. This is similar to entropy security. A 12-bit entropy has 128 bits of security because you may need to make 2¹²⁸ guesses to find the correct entropy.

[o_e_l_e_o]

And generally any number a and n-a return the same x-coordinate. So while the x-coordinate is 256 bits long, there are actually 2¹²⁸ different combinations it can take, but the y-coordinate between a and n-a will always give a different sign. Thus, the different combinations of a compressed public key are 2 * 2¹²⁸ or 2¹²⁹.

Given that the private key k produces the public key (x,y), and the private key -k mod n produces the public key (x,-y mod p), I am confused as to where you are getting 2¹²⁸ valid x coordinates from. Given that there are n-1 valid private keys, then there will be (n-1)/2 possible x coordinates, which is a number just less than 2²⁵⁵.

And therefore, given that each of these (n-1)/2 possible x coordinates can have two valid y coordinates, it gives a total of (n-1) valid uncompressed public keys, and the same number of valid compressed public keys.