🖤

[digaran]

😏

[1714816036]

1714816036

[1714816036]

1714816036

[1714816036]

1714816036

[j2002ba2]

There is an elliptic curve equation, which is taken modulo P. This produces a group with N points.

Now you'd like to change the modulo to N, and get a group with P points.

Congratulations! There are many many such curves.

But there's a caveat.

Taking something modulo P does not produce an integer. Instead the result is a "number modulo P". The "something" could be any of infinite numbers, both positive, negative, rational, irrational, etc.

So the real curve could be y^2 = x^3 + kPx + B, which reduces to y^2 = x^3 + B (mod P), and you could vary k in order to get the desired number of points modulo N. Or in a rare cases y^2 = x^3 + kPx + B + mP, if more flexibility is needed.

That means: the curves in different modulo are not related in any way.

Any curve in one modulo is equivalent to any curve in any other modulo.

Zero bits of information are gained here.


Edit:
BTW, there is no curve possible with P=97 and N=67 or vice-versa. The number of points possible lays in the interval P+1±2√P, which gives [79, 117] mod 97, and [52, 84] mod 67.

[tromp]

Have you ever tried to replace p with n to see what happens? I have and I can say you can break ECC by doing it, don't just panic yet, I have difficulty figuring out to map a point from e.g, n = 67, p = 97 to a curve with n = 97, p = 67. something that could give away a clue from first curve points to the second curve points.

There's something called the secq256k1 curve [1]. Note that

> although the two curves are isomorphic, the actual isomorphism is not efficiently computable — as far as we’re aware

[1] https://hackmd.io/@dJO3Nbl4RTirkR2uDM6eOA/Bk0NvC8Vo

[garlonicon]

that was just an example

For such small numbers, you can even bruteforce it, and see, that if you have y^2=x^3+7, then for p=67, the only correct answer is n=79. If you use n=97, it wouldn't work. For example, this is correct:

Code:

p=79
K=GF(p)
a=K(0)
b=K(7)
E=EllipticCurve(K,(a,b))
G=E(1,18)
h=1
E.set_order(67*h)
d=1
P=d*G
print(P[0],P[1])

And this is also correct:

Code:

p=67
K=GF(p)
a=K(0)
b=K(7)
E=EllipticCurve(K,(a,b))
G=E(2,22)
h=1
E.set_order(79*h)
d=1
P=d*G
print(P[0],P[1])

But if you change 79 into 97, you will get this error:

Code:

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In [1], line 8
      6 G=E(Integer(2),Integer(22))
      7 h=Integer(1)
----> 8 E.set_order(Integer(97)*h)
      9 d=Integer(1)
     10 P=d*G

File /home/sc_serv/sage/src/sage/schemes/elliptic_curves/ell_finite_field.py:1433, in EllipticCurve_finite_field.set_order(self, value, check, num_checks)
   1431 a,b = Hasse_bounds(q,1)
   1432 if not a <= value <= b:
-> 1433     raise ValueError('Value %s illegal (not an integer in the Hasse range)' % value)
   1434 # Is value*random == identity?
   1435 for i in range(num_checks):

ValueError: Value 97 illegal (not an integer in the Hasse range)

Which means, for a given curve equation, and a given p-value, you can get only very specific n-value, and you should compute it exactly, and not guess or pick randomly, because then your curve will be invalid.

[ecdsa123]

def set_order(self, value, num_checks=8) ( see link below)

Code:

        q = self.base_field().order()
        a,b = Hasse_bounds(q,1)
        #a = q + 1 - 2*q.isqrt()
        #b = q + 1 + 2*q.isqrt()
        if not value in ZZ:
            raise ValueError('Value %s illegal (not an integer in the Hasse range)'%value)

        if not a <= value <= b:
            raise ValueError('Value %s illegal (not an integer in the Hasse range)'%value)

        # Is value*random == identity?
        for i in range(num_checks):
            G = self.random_point()
            if value * G != self(0):
                raise ValueError('Value %s illegal (multiple of random point not the identity)'%value)

the part of is value*random ==identity as multiply of random point not the idntity is very intresting

link : https://github.com/sagemath/sagesmc/blob/master/src/sage/schemes/elliptic_curves/ell_finite_field.py

[garlonicon]

the part of is value*random ==identity as multiply of random point not the idntity is very intresting

Of course, it is obvious. It has to be there, to correctly handle the point at infinity. Every single point, multiplied by n-value, should give the point at infinity. Because (n-1) gives you "-1", then obviously, n-value should give you zero. This particular test is very fast, and if you put some n-value there, then you can just multiply your point by that, and you have to reach infinity. Or, you can multiply by (n-1), and check, that your x-value is identical, and y-value is flipped.

Also, in the same way, if you have any two points, and you want to move them from one curve to another, then you can just compute "x^3-y^2+b=0", and then, l-value will be some big number (I make it non-negative to make things easier), and r-value will be zero. Both values modulo p-value have to be zero. And then, you can compute gcd(first,second), to check, if a given pair of points can be moved to a curve with some different p-value.

[ecdsa123]

Code:

p=67
K=GF(p)
a=K(0)
b=K(7)
E=EllipticCurve(K,(a,b))
G=E.random_point()
h=1
q=E.order()
print("E.order()==",q)
a,b = Hasse_bounds(q,1)
print("Hasse bound min=",a,"Hasse bound max=",b)
q=E.set_order(Integer(a+8)*h)
print("i=",i,"work for E.order()=",E.order())
d=1
G=E(Integer(2),Integer(22))
P=d*G
print(P[0],P[1])

result:

Code:

E.order()== 79
Hasse bound min= 63 Hasse bound max= 97
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In [1], line 12
     10 a,b = Hasse_bounds(q,Integer(1))
     11 print("Hasse bound min=",a,"Hasse bound max=",b)
---> 12 q=E.set_order(Integer(a+Integer(8))*h)
     13 print("i=",i,"work for E.order()=",E.order())
     14 d=Integer(1)

File /home/sc_serv/sage/src/sage/schemes/elliptic_curves/ell_finite_field.py:1438, in EllipticCurve_finite_field.set_order(self, value, check, num_checks)
   1436         G = self.random_point()
   1437         if value * G != self(0):
-> 1438             raise ValueError('Value %s illegal (multiple of random point not the identity)' % value)
   1440 # TODO: It might help some of PARI's algorithms if we
   1441 # could copy this over to the .pari_curve() as well.
   1442 # At the time of writing, this appears to be tricky to
   1443 # do in a non-hacky way because cypari2 doesn't expose
   1444 # "member functions" of PARI objects.
   1446 self._order = value

ValueError: Value 71 illegal (multiple of random point not the identity)

As you see we got ValueError: Value 71 illegal (multiple of random point not the identity)

[garlonicon]

Value 71 illegal (multiple of random point not the identity)

Of course. For y^2=x^3+7 and p=67, the only valid value is n=79. Nothing else will work in that specific case. And you can even use brute force, to compute 67x67 bitmap, and check every single (x,y) coordinate, if "((y^2)%67)==((x^3+7)%67)". You will get only 78 such points, and one point at infinity, which means n=79 is the only possible answer here.

And then, if you have any point (x,y), then by multiplying it by 78, you will get (x,-y), and then the combination of those two will give you the same result as multiplication by 79: the point at infinity.