Comments (7)
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.
from fastecdsa.
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...
from fastecdsa.
Tried to make a pull request 😮
from fastecdsa.
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).
from fastecdsa.
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.
from fastecdsa.
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
from fastecdsa.
@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.
from fastecdsa.
Related Issues (20)
- deep learning for fastecdsa HOT 3
- Point extend HOT 11
- Bug: multiplication of Point by negative const produces wrong results HOT 15
- [Question] - Different Signatures for same input HOT 2
- Scalar Inversion HOT 3
- Cannot install in macOS BigSur (M1 chip) HOT 23
- MacOS Monerray Apple Silicon Python 3.9 issue with install/import HOT 3
- tag 2.2.2 unsigned, PyPI upload missing a signature file HOT 2
- I can run this tutorial in termux HOT 1
- Python.h not found on WSL Ubuntu 20.04 installation HOT 1
- installation error on shared hosting HOT 1
- does not install with python3.9 HOT 6
- Is it possible for this to be used with Micropython? HOT 3
- Error while installing ecdsa HOT 1
- how do I calculate recover_id from signature HOT 1
- Import Issues on macOS Monterey, Python 3.9, M1 Max
- symbol not found in flat namespace '___gmpz_add' HOT 1
- getting y public key from compressed public key HOT 1
- unresolved external symbol __gmpz_set HOT 1
- symbol not found in flat namespace '___gmpz_add' Error in version 2.3.2 HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from fastecdsa.