1
$\begingroup$

I was looking inside the basics of ecc and found the examples from Internet either uses continuous domain curve or use a very small prime number p like 17 in a discrete domain to show the points.

I am really curious that if I can find a point with a really big p in practice. For example, secp256k1 is using a really big p=2^256−2^32−977 in domain (p,a,b,G,n,h).

Below is the python code I use to deduct possible integer of y from solving equation with range of integer x. To my surprise that there is no finding even in 1 million range!

So my question is, is below code right? And secondly, if it is right or corrected by some real expert, which value range should I try?

P.S. I am wondering how generator point G is selected, too. But that might need deeper understanding to the topic.

import math

# secp256k1
# y**2 = x**3 + 7 (mod p)
P = 2**256 - 2**32 - 977
A = 0
B = 7

# nist P256
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
A = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291

def in_curve(x):
    curve = x**3 + A*x + B
    y_float = math.sqrt(curve)
    if abs(math.modf(y_float)[0]) < 0.0001 or \
          (1 - abs(math.modf(y_float)[0]) < 0.0001):
        # print(y_float)
        # bug: y_int = int(math.modf(y_float)[1])
        y_int = int(round(y_float))
        if y_int * y_int == (curve):
            print(y_int)
            return y_int
    return None
 
for x in range(1, 1000000):
    y = in_curve(x)
    if y is not None:
        print(x, y)

Update 1

The previous code is wrong, since floating point sqrt() will cause unacceptable error when converting it back to integer.

But, after replacing math.sqrt() to math.isqrt(), it still doesn't make things reasonable.

Update 2

Thanks to the tips from all replied in the thread. Using generator point to verify my algorithm, I now clearly know why I was failing.

The point is, besides using % for all multiplication and additions, I should also use modular square root to find the solution, instead of integer square root along with %. That is totally a misuse of % for sure.

The modified code pass the test with some test vectors.

import modular_sqrt
#  e.g. I was using code from https://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python
# please ask permission if usage is beyond educational hobbyist area and always list the credit being a decent human ;-)

# nist P256, taken from https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf
P = 115792089210356248762697446949407573530086143415290314195533631308867097853951
A = -3
B = 41058363725152142129326129780047268409114441015993725554835256314039467401291
Gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286
Gy = 36134250956749795798585127919587881956611106672985015071877198253568414405109

def get_y_in_curve(x):
    y2 = x**3 + A*x + B
    y_int = modular_sqrt(y2, P)
    if y_int and ((y_int * y_int) % P) == (y2 % P):
        return y_int
    return None

assert get_y_in_curve(Gx) == Gy
Improve this question
$\endgroup$
4
  • $\begingroup$ The code is incorrect. Main issue is that Elliptic Curve crypto does not work with $x$ and $y$ in an infinite set. It uses a finite field. secp256k1 uses the field $\mathbb F_p$, also the ring of integers modulo $p$. Thus the code should compute it's curve reduced modulo P, and compute (when it exists) a modular square root of that; see this for one method. Please improve or close the question. $\endgroup$
    – fgrieu ♦
    Sep 15, 2021 at 9:12
  • $\begingroup$ @fgrieu Yes, I realized my mistake right after Daniel pointed it out. Now the question is updated with corrected algorithm. Do you want me to close the question since it was wrong? Or keep it as an example of how things should be done with in Finite space of ECC. Or even just how things could go wrong when hooping from infinite space "curve" to finite space? :) $\endgroup$
    – Match Man
    Sep 15, 2021 at 10:05
  • $\begingroup$ The updated question is OK. Since the answer helped, I think the best is to accept it, and all will be fine. Note on the new code: it would be more elegant to rename curve to y2 ; compute it modulo P earlier on (e.g. y2 = (x**3 + A*x + B) % P or y2 = (pow(x, 3, P) + A*x + B) % P) ; and to reuse it in y_int = modular_sqrt(y2) and if ((y_int * y_int) % P) == y2:. It's not immediately clear what modular_sqrt does when it fails. Independently, is using another person's modular_sqrt OK in the context? That's the involved part! $\endgroup$
    – fgrieu ♦
    Sep 15, 2021 at 10:14
  • 1
    $\begingroup$ The code is refactored. modular_sqrt will return 0 for failure and new code also added that check. I don't use Eli's code directly but refer his code as an example. $\endgroup$
    – Match Man
    Sep 16, 2021 at 21:17

1 Answer 1

Reset to default
3
$\begingroup$

I'm not quite sure what you mean by $p$ and I'm not sure what you meant for your code to print out.

However, it looks like you are trying to find integer valued points on the elliptic curve $y^2=x^3+7$ by exhausting over $x$ values and I can't spot a bug other than the print statement. BUT Siegel showed that in general elliptic curves over the rational numbers only have a finite number of integer valued points and we expect these to be very rare indeed. In fact for the curve that you have picked there are no integer points whatsoever.

You might be trying to find integers $x$ and $y$ so that $y^2\equiv x^3+7\pmod p$ for some large prime $p$. In this case you should take square roots mod $p$ rather than over the real numbers. This uses a different computation. Choosing a large prime $p$ and then taking any $x$ value has an approximately 50% chance of finding a suitable $y$ by taking a modular square root of $x^3+17$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I added the meaning of p in question. It is so big so that I don't have to do modulation with any small number like 1 billion... > In fact for the curve that you have picked there are no integer points whatsoever. < So there is some round up operation when calculating secp256k1? Wonder how it goes. $\endgroup$
    – Match Man
    Sep 14, 2021 at 20:30
  • 1
    $\begingroup$ Oh I see. In that case, if you try to generate points without using any modular arithmetic, it won't work because they would then be integral points and there are none on this curve. Note that "small" numbers that are not perfect squares can still have square roots mod $p$ if one is prepared to use modular arithmetic. $\endgroup$
    – Daniel S
    Sep 14, 2021 at 20:34
  • $\begingroup$ Do you mean that I should change if y_int * y_int == (x^3 + 7) to if y_int * y_int == (x^3 + 7) % P, where P =2^256−2^32−977? My understanding is that secp256k1 is defined over ℤp, so previous floating point calculation is just to find if y is close enough to be an integer. There are really a lot of possible candidates in 1 million but none of them is really one... $\endgroup$
    – Match Man
    Sep 14, 2021 at 20:42
  • 1
    $\begingroup$ No. I mean that (using the fact that $p\equiv 3\pmod 4$), you should replace y_float=math.sqrt(x^3+7) with y_int=pow(x^3+7,(p+1)/4,p) and then check if y_int*y_int==(x^3+7)%p. This won't give you a small value of $y$, but there is not a solution with a small value of both $x$ and $y$. Check out the link on computing square roots mod $p$. $\endgroup$
    – Daniel S
    Sep 14, 2021 at 20:58
  • $\begingroup$ Got it. Question is updated with correct operation now. Thanks. $\endgroup$
    – Match Man
    Sep 15, 2021 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.