Why we use X in compressed keys and signatures instead of Y?

[ondrere]

Now we have r=(k*basePoint).x in signatures and (privKey*basePoint).x in compressed keys. We have y^2=x^3+7 function, so having given x we can calculate y^2 and then we have two possible y values matching this equation. Instead, when we have some y, we can calculate x=cbrt(y^2-7) and there is only one matching x. So the question is: why x value was chosen instead of y? Are there some performance-related issues?

[gmaxwell]

we can calculate x=cbrt(y^2-7) and there is only one matching x

Nope, there are three solutions to the cuberoot. Which is also an answer to your question: there are more possibilities.

(I haven't checked for this post but the cuberoot is also likely more expensive to calculate).

[Coding Enthusiast]

Nope, there are three solutions to the cuberoot. Which is also an answer to your question: there are more possibilities.

Shouldn't it be only one solution since we are only working with positive integers?

(I haven't checked for this post but the cuberoot is also likely more expensive to calculate).

On secp256k1 thanks to P ≡ 7 (mod 9) we can compute cube root by computing one side to the power of [(p+2)/9]

Code:

x = ModPow(y^2 - 7, (P+2)/9, P)

Considering the fact that we compute square root in a similar fashion thanks to P ≡ 3 (mod 4):

Code:

y = ModPow(x^3 + 7, (P+1)/4, P)

And assuming there is no other faster method that I don't know about, they are pretty much of the same speed. Also ignoring the fact that finding y (square root) has a possible additional step of negating y.

PS. ModPow above is modular power, in .net it is found under System.Numerics.BigInteger.ModPow(BigInteger value, BigInteger exponent, BigInteger modulus); and in python it is same pow method with 3 inputs with the same order (value, exponent, modulus).

[gmaxwell]

Shouldn't it be only one solution since we are only working with real numbers?

No, we're working in a finite field. And in this field there are non-trivial cube roots of unity:


sage: F=FiniteField(2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1)
sage: F(1)^3
1
sage: F(55594575648329892869085402983802832744385952214688224221778511981742606582254)^3
1
sage: F(60197513588986302554485582024885075108884032450952339817679072026166228089408)^3
1

they are pretty much of the same speed.

Did you compute efficient power ladders for each value? There is a factor of 100 difference in speed between e.g. a hamming weight 1 256-bit exponent and a hamming 128 256-bit exponent. It won't be that big a difference, but you can't assume the speed is similar just because the process is similar.

[Coding Enthusiast]

Did you compute efficient power ladders for each value? There is a factor of 100 difference in speed between e.g. a hamming weight 1 256-bit exponent and a hamming 128 256-bit exponent. It won't be that big a difference, but you can't assume the speed is similar just because the process is similar.

Good to know.
I'm just using .net core's arbitrary length integers and a quick benchmark didn't show any difference.

[aliashraf]

Nope, there are three solutions to the cuberoot. Which is also an answer to your question: there are more possibilities.

Shouldn't it be only one solution since we are only working with real numbers?

You mean integers?

[Coding Enthusiast]

You mean integers?

Yes, both math and English failed me at the same time