3 Bugs on general ECC calculation

[caoweiquan322]

Here I construct a ECC $y^2 = x^3 + x + 1 mod 23$ . And starting from point $(9, 7)$. Here are three bugs I found. Any body who is intreated can reproduce the bugs easily.

from ecdsa.ellipticcurve import CurveFp, Point, PointJacobi


if __name__ == '__main__':
    curve = CurveFp(23, 1, 1)
    G = PointJacobi(curve, 9, 7, 1)
    G_affine = G.to_affine()
    print('14*G+G==15*G:', 14*G + G == 15*G)  # Bug1: 14*G + G != 15*G !!!
    print('14*G+G==15*G:', 14*G_affine + G_affine == 15*G_affine)
    G_27 = 27*G  # Bug2: This results in a negative y coordinate.
    print('G_27: (%d, %d)' % (G_27.x(), G_27.y()))
    G_affine_27 = 27*G_affine  # Bug3: This raises an exception.
    print('G_affine_27: (%d, %d)' % (G_affine_27.x(), G_affine_27.y()))

[tomato42]

This curve has order 27, which is not prime (it's 3**3), that's why there are some errors when using it (the code doesn't expect point doubling to return an INFINITY as that requires non-prime order), so Bug2 and Bug3 are valid, though minor.

but that also means that 14 * G + G != 15 * G as 14 * G is INFINITY, so the expected result is 14 * G + G == G which is true

see result of the multiplying against subsequent multiples:

for i in range(30):
   a = G * i
   print(f"{i}: {a.x()} {a.y()}")

0: None None
1: 9 7
2: 6 19
3: 1 7
4: 13 16
5: 19 5
6: 7 11
7: 11 20
8: 5 19
9: 18 20
10: 12 4
11: 3 10
12: 17 20
13: 0 22
14: None None
15: 0 1
16: 17 3
17: 3 13
18: 12 19
19: 18 3
20: 5 4
21: 11 3
22: 7 12
23: 19 18
24: 13 7
25: 1 16
26: 6 4
27: 9 16
28: None None
29: 9 7

[caoweiquan322]

Agree with most of the reply, except that:

1. Curve's order is 28, not 27.
2. $14*G$ is not infinity, but point $(4, 0)$. So this line is incorrect: "14: None None".

[tomato42]

hmm, true, G*14 should be (4, 0)... and it actually is by the equations used, it's just converted to INFINITY because of wrong checks... will need to check the special cases some more but the first draft of the fixes is in #344