Multiple bugs involving infinity implementation

[pkreissel]

There is a serious bug in the implementation of "infinity" in this package.

Steps to reproduce

from ecpy.curves import Curve, Point
curve = Curve.get_curve("Ed25519")
G = curve.generator
n = curve.order
print((G*n) == (G*(n-1) + G) ) #false - "incorrect"
print((G*n).is_infinity)  #true - "correct"
print((G*(n-1) + G).is_infinity) #false - "incorrect"

torsion = curve.decode_point(bytearray.fromhex("c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa"))
print((torsion*n).is_infinity) #true - "incorrect"

Expected output

• Obviously we would expect Gn and G(n-1)+G to be equal,
• and we would expect them both to be "infinity".
• We would also expect, that multiplying a torsion point, that is not in the same subgroup as G, with n would lead to a point that is NOT infinity.

Observed Output

• Gn and G(n+1)+G is not equal
• For the Point G*(n+1) + G "is_infinity" is set to false (the result is numerically correct though).
• (torsion*n).is_infinity result is "True"

Suggested Fix

Replace the current complex "hard coded" implementation of "infinity" with a simple dynamic check.
curve.generator * curve.order should always result in infinity, thus we can easily check points against that result, if we want to check wether they are in fact infinity.

[cslashm]

Hi, thanks for repporting

"Obviously we would expect Gn and G(n+1)+G to be equal,"
I guess you mean n-1.

Meanwhile I will have a look a that in the coming days.

I need to have a 'Infinity' point that could be consider as any other point.

Did you make the same test on "secp" curve?

[pkreissel]

Hey,

Yes, I mean n-1, I corrected that above.

I wrote a short test testing for problem 1 and 2 for all curves with cofactor 1, this test passes:

from ecpy.curves import Curve, Point
from ecpy.curve_defs import curves
for defs in curves:
    if defs['cofactor'] == 1:
        curve = Curve.get_curve(defs["name"])
        G = curve.generator
        n = curve.order
        assert((G*n) == (G*(n-1) + G) ) 
        assert((G*n).is_infinity)
        assert((G*(n-1) + G).is_infinity)

But it doesn't pass for Ed448 and Ed25519. Curve448 and Curve25519 even throw errors before even getting to the "asserts"

I don't know the torsion points for the other high-cofactor-curves, so I have to research them first to test for problem 3.

However I already found one cause for problem 3:
In Point Multiplication Ecpy just assumes, that anything multiplied by curve order is infinity. This is not true however for curves with cofactor > 1.