|
Title: Why we use X in compressed keys and signatures instead of Y? Post by: ondrere on April 04, 2020, 01:01:53 PM 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?
Title: Re: Why we use X in compressed keys and signatures instead of Y? Post by: gmaxwell on April 04, 2020, 02:03:13 PM 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). Title: Re: Why we use X in compressed keys and signatures instead of Y? Post by: Coding Enthusiast on April 04, 2020, 03:23:17 PM 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) 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). Title: Re: Why we use X in compressed keys and signatures instead of Y? Post by: gmaxwell on April 04, 2020, 03:31:34 PM 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.Title: Re: Why we use X in compressed keys and signatures instead of Y? Post by: Coding Enthusiast on April 04, 2020, 03:55:03 PM 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 (https://github.com/microsoft/referencesource/blob/a7bd3242bd7732dec4aebb21fbc0f6de61c2545e/System.Numerics/System/Numerics/BigInteger.cs#L1035-L1041) arbitrary length integers and a quick benchmark didn't show any difference. Title: Re: Why we use X in compressed keys and signatures instead of Y? Post by: aliashraf on April 04, 2020, 05:10:06 PM 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?Title: Re: Why we use X in compressed keys and signatures instead of Y? Post by: Coding Enthusiast on April 04, 2020, 06:06:12 PM You mean integers? Yes, both math and English failed me at the same time :P |