Bug in evaluate and/or point_is_on_curve function?

[olalonde]

x = 14899878097
y = secp256k1.evaluate(14899878097)
Point(x, y, curve=secp256k1)

Results in:

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-92-e37ebd4d2471> in <module>
      1 x = 14899878097
      2 y = secp256k1.evaluate(14899878097)
----> 3 Point(x, y, curve=secp256k1)

~/.pyenv/versions/3.7.0/envs/phemex-puzzle/lib/python3.7/site-packages/fastecdsa/point.py in __init__(self, x, y, curve)
     31         if not (x == 0 and y == 1 and curve is None) and not curve.is_point_on_curve((x, y)):
     32             raise ValueError(
---> 33                 'coordinates are not on curve <{}>\n\tx={:x}\n\ty={:x}'.format(curve.name, x, y))
     34         else:
     35             self.x = x

ValueError: coordinates are not on curve <secp256k1>
    x=3781a18d1
    y=29c04c1ef9a7fd2ea7b8569578

[olalonde]

I narrowed down the problem a bit.. I tried to find y from 14899878097 using two different libraries (https://bitcoin.stackexchange.com/questions/86234/how-to-uncompress-a-public-key and https://github.com/ofek/bit/blob/master/bit/curve.py) and they both give 26231617881706184850666176805736269196222162329503324915111945351251945838730. Yet, I'm getting the ValueError: coordinates are not on curve <secp256k1> error with Point(14899878097, 26231617881706184850666176805736269196222162329503324915111945351251945838730, curve=secp256k1).

Point(14899878097, 26231617881706184850666176805736269196222162329503324915111945351251945838730, curve=secp256k1)

As far as I can tell this point is on the curve but yet ecdsa is raising the error.

[olalonde]

After digging a bit into this, it appears that Bitcoin uses a slightly different version of the elliptic curve equation. Instead of y = (x^3 + ax + b)^1/2 % p, it uses y = (x^3 + ax + b)^TONELLI_SHANKS_CONSTANT % p where TONELLI_SHANKS_CONSTANT = (p + 1) // 4. In python:

FIELD_SIZE = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
GROUP_ORDER = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
TONELLI_SHANKS_CONSTANT = (FIELD_SIZE + 1) // 4

y = pow(x ** 3 + 7, TONELLI_SHANKS_CONSTANT, FIELD_SIZE)

Not sure if that helps...

[olalonde]

Tried to make a pull request 😮

[antonio-fr]

The Bitcoin curve is still a standard elliptic curve y^2 = x^3 + ax + b (mod p). When p modulo is prime, one can use z^-1 mod p = z^(p-2) mod p (from Euler theorem) : z^(1/2) = z^2^1/4 = z^(p+1)/4 (plus if p % 4 == 3).

[AntonKueltz]

Sorry for the late response. Your usage of evaluate to get y is incorrect. Note that the Weierstrass curve equation is y^2 = x^3 + ax + b (mod p). From the evaluate docstring - Evaluate the elliptic curve polynomial at 'x'. This means that evaluate yields y^2, not y, and you can get y as follows -

x = 14899878097
y2 = secp256k1.evaluate(14899878097)
from fastecdsa.util import mod_sqrt
roots = mod_sqrt(y2, secp256k1.p)

This will set roots to -

(89560471355610010572904808202951638657047822336137239124345638656656888832933,
26231617881706184850666176805736269196222162329503324915111945351251945838730)

Note that the second value is the root you expected. We then have the issue that this x/y pair is not on the curve. Indeed we can verify that it is not via both this library and this online elliptic curve tool. In fact no point with x = 14899878097 exists on this curve.

It may be that this is some form of an invalid curve attack, or it could just be a bad / malformed key. I can't remember off the top of my head why the math works out such that we can compute y for the point but it doesn't actually yield a valid x/y coordinate.

[AntonKueltz]

ecdsa also indicates this point is not on the curve -

In [1]: from ecdsa.curves import SECP256k1

In [2]: SECP256k1.curve.contains_point(14899878097, 2623161788170618485066617680
   ...: 5736269196222162329503324915111945351251945838730)
Out[2]: False

[AntonKueltz]

@olalonde I'm going to go ahead and close this issue and the related PR since the behavior appears to be correct. If you have any issues with that let me know and we can re-open / discuss.