Bitcoin Forum

Bitcoin => Electrum => Topic started by: flipperfish on December 09, 2017, 10:58:38 AM


Title: Question about public key decompression algorithm (ECC_YfromX(...))
Post by: flipperfish on December 09, 2017, 10:58:38 AM
I'm currently trying to understand electrum's approach to decompress compressed public keys. However, I'm struggling with two things:

  • What is the meaning of the offset? Why is it needed? Other implementations seem to be fine without it.
    What are the mathematical foundations? Why does x + offset still result in the same y (or does it?)?
  • When calculating y^2, why is the coefficent a multiplied by x^2 instead of just x, like in the basic elliptic curve equation?
    Could this be a bug, that has not yet been discovered, because a is 0 in secp256k1?


This is the function in question (in lib/bitcoin.py (https://github.com/spesmilo/electrum/blob/b88fa2046c9263cfee4d94d695addda356c1a42e/lib/bitcoin.py#L654)):

Code:
def ECC_YfromX(x,curved=curve_secp256k1, odd=True):
    _p = curved.p()
    _a = curved.a()
    _b = curved.b()
    for offset in range(128):
        Mx = x + offset
        My2 = pow(Mx, 3, _p) + _a * pow(Mx, 2, _p) + _b % _p
        My = pow(My2, (_p+1)//4, _p )

        if curved.contains_point(Mx,My):
            if odd == bool(My&1):
                return [My,offset]
            return [_p-My,offset]
    raise Exception('ECC_YfromX: No Y found')


I'm glad for any help or pointers in the right direction...

Title: Re: Question about public key decompression algorithm (ECC_YfromX(...))
Post by: aplistir on December 09, 2017, 01:55:03 PM
Quote from: flipperfish on December 09, 2017, 10:58:38 AM
  • What is the meaning of the offset? Why is it needed? Other implementations seem to be fine without it.
    What are the mathematical foundations? Why does x + offset still result in the same y (or does it?)?
  • When calculating y^2, why is the coefficent a multiplied by x^2 instead of just x, like in the basic elliptic curve equation?
    Could this be a bug, that has not yet been discovered, because a is 0 in secp256k1?

Code:
def ECC_YfromX(x,curved=curve_secp256k1, odd=True):
    _p = curved.p()
    _a = curved.a()
    _b = curved.b()
    for offset in range(128):
        Mx = x + offset
        My2 = pow(Mx, 3, _p) + _a * pow(Mx, 2, _p) + _b % _p
        My = pow(My2, (_p+1)//4, _p )

        if curved.contains_point(Mx,My):
            if odd == bool(My&1):
                return [My,offset]
            return [_p-My,offset]
    raise Exception('ECC_YfromX: No Y found')
I'm glad for any help or pointers in the right direction...

Quite an interesting find.
You are right, it does seem to be a "bug" to have a*x² in there. It should be a*x, but would be even better if there were no "a" at all, because as you said a=0 in the curve bitcoin uses (y²=x³+7)

Also interesting to have _b % _p at the end. Why take a mod of curve parameter b? How could it ever be bigger than p? It is a curve parameter that never changes.

Maybe Electrum devs want to be prepared for bitcoin changing the curve it uses ?? (never going to happen)
It is not very efficient to do 128 times  "_a * pow(Mx, 2, _p)" and  "_b % _p" for no reason, when the numbers are as big as they are (256bit).

Also as you said. the offset is quite confusing.  but both the "My" and offset are returned to the calling function and sent to Point() in the end, and Point() is an imported function (from ecdsa.ellipticcurve import Point) And I did not look what it does with the offset value.

One more thing that confuses me is the line:
Code:
My = pow(My2, (_p+1)//4, _p )
That is an interesting way to take a squareroot in finite field. I know sqrt is a heavy operation in finite field, but never seen it taken like that. Could that be what is behind the whole offset thing...  an easier way to find a sqrt?


 

Title: Re: Question about public key decompression algorithm (ECC_YfromX(...))
Post by: flipperfish on December 09, 2017, 02:14:23 PM
Quote
but both the "My" and offset are returned to the calling function and sent to Point() in the end

To me it looks like only the My is sent to Point() (there is a \[0] after the call, easy to miss):
Code:
return Point( curve, Mx, ECC_YfromX(Mx, curve, Aser[0] == 0x03)[0], _r )


The way of doing the square root seems to only work for 3 mod 4 fields. I have seen this in other implementations, too. A good explanation is here: https://www.johannes-bauer.com/compsci/ecc/#anchor11
Code:
My = pow(My2, (_p+1)//4, _p )

Title: Re: Question about public key decompression algorithm (ECC_YfromX(...))
Post by: aplistir on December 09, 2017, 03:11:34 PM
Quote from: flipperfish on December 09, 2017, 02:14:23 PM
Quote
but both the "My" and offset are returned to the calling function and sent to Point() in the end

To me it looks like only the My is sent to Point() (there is a \[0] after the call, easy to miss):
Code:
return Point( curve, Mx, ECC_YfromX(Mx, curve, Aser[0] == 0x03)[0], _r )
Did not notice that.
Re-reading the code, my opinion is now that the offset must always be "0" otherwise it would return the y-coordinate of a wrong point!!!!!!
I can see no reason why the for loop wont go through with the first try with offset 0. That is if the x is a valid x point on the curve. IF x is not valid, then that function returns y from a wrong point !

Quote from: flipperfish
The way of doing the square root seems to only work for 3 mod 4 fields. I have seen this in other implementations, too. A good explanation is here: https://www.johannes-bauer.com/compsci/ecc/#anchor11
Code:
My = pow(My2, (_p+1)//4, _p )

Now I understand the sqrt. Thanks for explaining that. Btw, there is another bug in there. It should be (_p+1)/4 and not (_p+1)//4 Shouldn't it?
I was wondering how is it possible to omit the remainder of dividing by 4. But by luck in this case (p+1) does divide by 4 nicely. So there is no remainder and it works with bitcoin curve.
Edit: Just realized that "/" and "//" both work the same here, because both would omit the remainder here...

Also if the  ECC_YfromX() function assumes that p%4=3 (and p+1 is divisible by 4) when taking the sqrt, it definitely cannot handle changing the curve that bitcoin uses. So the whole "_a * pow(Mx, 2, _p) + _b % _p" part is pointless and could be changed to simply be "+7" (or + _b)

Quite worrying to see that kind of code in my favorite wallet program.   ???

Title: Re: Question about public key decompression algorithm (ECC_YfromX(...))
Post by: aplistir on February 07, 2018, 02:02:35 PM
Quote from: flipperfish on December 09, 2017, 10:58:38 AM
I'm currently trying to understand electrum's approach to decompress compressed public keys. However, I'm struggling with two things:

  • What is the meaning of the offset? Why is it needed? Other implementations seem to be fine without it.
    What are the mathematical foundations? Why does x + offset still result in the same y (or does it?)?
  • When calculating y^2, why is the coefficent a multiplied by x^2 instead of just x, like in the basic elliptic curve equation?
    Could this be a bug, that has not yet been discovered, because a is 0 in secp256k1?


Did you ever forward your find to the Electrum team so that they can take a look at it and fix it?

It is indeed strange that they have the "offset" variable, which could only ever return false results if it is not 0

On the other hand. When does Electrum use that function? I suppose it is used very rarely, and that is why that bug has not been found before.

Title: Re: Question about public key decompression algorithm (ECC_YfromX(...))
Post by: flipperfish on February 07, 2018, 05:41:40 PM
Quote from: aplistir on February 07, 2018, 02:02:35 PM
Quote from: flipperfish on December 09, 2017, 10:58:38 AM
I'm currently trying to understand electrum's approach to decompress compressed public keys. However, I'm struggling with two things:

  • What is the meaning of the offset? Why is it needed? Other implementations seem to be fine without it.
    What are the mathematical foundations? Why does x + offset still result in the same y (or does it?)?
  • When calculating y^2, why is the coefficent a multiplied by x^2 instead of just x, like in the basic elliptic curve equation?
    Could this be a bug, that has not yet been discovered, because a is 0 in secp256k1?


Did you ever forward your find to the Electrum team so that they can take a look at it and fix it?

It is indeed strange that they have the "offset" variable, which could only ever return false results if it is not 0

On the other hand. When does Electrum use that function? I suppose it is used very rarely, and that is why that bug has not been found before.


No, I didn't forward. I had the hope that they would notice it here. If you are more active on github than me, feel free to report it.
I think I stumbled over it, when I tried to understand the signature verification part. If I remember correctly, the python ecdsa module can only take uncompressed public keys and that's where it's used.

Title: Re: Question about public key decompression algorithm (ECC_YfromX(...))
Post by: aplistir on February 08, 2018, 09:00:17 PM
Quote from: flipperfish on February 07, 2018, 05:41:40 PM
No, I didn't forward. I had the hope that they would notice it here. If you are more active on github than me, feel free to report it.
I think I stumbled over it, when I tried to understand the signature verification part. If I remember correctly, the python ecdsa module can only take uncompressed public keys and that's where it's used.

Ok. good to know.
I will try to report it to the Electrum dev team sometime this week or the next.
It is great to get as many bugs fixed as possible.


Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines