Bitcoin Forum
August 19, 2022, 02:15:20 AM *
News: Latest Bitcoin Core release: 23.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Question about public key decompression algorithm (ECC_YfromX(...))  (Read 188 times)
flipperfish
Sr. Member
****
Offline Offline

Activity: 350
Merit: 251


Dolphie Selfie


View Profile
December 09, 2017, 10:58:38 AM
Merited by aplistir (1)
 #1

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):

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...
1660875320
Hero Member
*
Offline Offline

Posts: 1660875320

View Profile Personal Message (Offline)

Ignore
1660875320
Reply with quote  #2

1660875320
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1660875320
Hero Member
*
Offline Offline

Posts: 1660875320

View Profile Personal Message (Offline)

Ignore
1660875320
Reply with quote  #2

1660875320
Report to moderator
1660875320
Hero Member
*
Offline Offline

Posts: 1660875320

View Profile Personal Message (Offline)

Ignore
1660875320
Reply with quote  #2

1660875320
Report to moderator
1660875320
Hero Member
*
Offline Offline

Posts: 1660875320

View Profile Personal Message (Offline)

Ignore
1660875320
Reply with quote  #2

1660875320
Report to moderator
aplistir
Full Member
***
Offline Offline

Activity: 379
Merit: 196



View Profile
December 09, 2017, 01:55:03 PM
 #2

  • 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?


 

My Address: 121f7zb2U4g9iM4MiJTDhEzqeZGHzq5wLh
flipperfish
Sr. Member
****
Offline Offline

Activity: 350
Merit: 251


Dolphie Selfie


View Profile
December 09, 2017, 02:14:23 PM
 #3

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 )
aplistir
Full Member
***
Offline Offline

Activity: 379
Merit: 196



View Profile
December 09, 2017, 03:11:34 PM
Last edit: December 09, 2017, 03:27:59 PM by aplistir
 #4

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.   Huh

My Address: 121f7zb2U4g9iM4MiJTDhEzqeZGHzq5wLh
aplistir
Full Member
***
Offline Offline

Activity: 379
Merit: 196



View Profile
February 07, 2018, 02:02:35 PM
 #5

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.

My Address: 121f7zb2U4g9iM4MiJTDhEzqeZGHzq5wLh
flipperfish
Sr. Member
****
Offline Offline

Activity: 350
Merit: 251


Dolphie Selfie


View Profile
February 07, 2018, 05:41:40 PM
 #6

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.
aplistir
Full Member
***
Offline Offline

Activity: 379
Merit: 196



View Profile
February 08, 2018, 09:00:17 PM
 #7

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.

My Address: 121f7zb2U4g9iM4MiJTDhEzqeZGHzq5wLh
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!