Repository: tlsfuzzer/python-ecdsa

Issue:
3 Bugs on general ECC calculation
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()))
```

Discussion:

Patch:
diff --git a/src/ecdsa/ellipticcurve.py b/src/ecdsa/ellipticcurve.py
index 1ea04a4..a982c1e 100644
--- a/src/ecdsa/ellipticcurve.py
+++ b/src/ecdsa/ellipticcurve.py
@@ -633,7 +633,7 @@ class PointJacobi(AbstractPoint):
         """
         x1, y1, z1 = self.__coords
         if other is INFINITY:
-            return not y1 or not z1
+            return not z1
         if isinstance(other, Point):
             x2, y2, z2 = other.x(), other.y(), 1
         elif isinstance(other, PointJacobi):
@@ -723,11 +723,13 @@ class PointJacobi(AbstractPoint):
 
     def to_affine(self):
         """Return point in affine form."""
-        _, y, z = self.__coords
-        if not y or not z:
+        _, _, z = self.__coords
+        p = self.__curve.p()
+        if not (z % p):
             return INFINITY
         self.scale()
         x, y, z = self.__coords
+        assert z == 1
         return Point(self.__curve, x, y, self.__order)
 
     @staticmethod
@@ -759,7 +761,7 @@ class PointJacobi(AbstractPoint):
         # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-mdbl-2007-bl
         XX, YY = X1 * X1 % p, Y1 * Y1 % p
         if not YY:
-            return 0, 0, 1
+            return 0, 0, 0
         YYYY = YY * YY % p
         S = 2 * ((X1 + YY) ** 2 - XX - YYYY) % p
         M = 3 * XX + a
@@ -773,13 +775,13 @@ class PointJacobi(AbstractPoint):
         """Add a point to itself, arbitrary z."""
         if Z1 == 1:
             return self._double_with_z_1(X1, Y1, p, a)
-        if not Y1 or not Z1:
-            return 0, 0, 1
+        if not Z1:
+            return 0, 0, 0
         # after:
         # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl
         XX, YY = X1 * X1 % p, Y1 * Y1 % p
         if not YY:
-            return 0, 0, 1
+            return 0, 0, 0
         YYYY = YY * YY % p
         ZZ = Z1 * Z1 % p
         S = 2 * ((X1 + YY) ** 2 - XX - YYYY) % p
@@ -795,14 +797,14 @@ class PointJacobi(AbstractPoint):
         """Add a point to itself."""
         X1, Y1, Z1 = self.__coords
 
-        if not Y1:
+        if not Z1:
             return INFINITY
 
         p, a = self.__curve.p(), self.__curve.a()
 
         X3, Y3, Z3 = self._double(X1, Y1, Z1, p, a)
 
-        if not Y3 or not Z3:
+        if not Z3:
             return INFINITY
         return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
 
@@ -886,10 +888,10 @@ class PointJacobi(AbstractPoint):
 
     def _add(self, X1, Y1, Z1, X2, Y2, Z2, p):
         """add two points, select fastest method."""
-        if not Y1 or not Z1:
-            return X2, Y2, Z2
-        if not Y2 or not Z2:
-            return X1, Y1, Z1
+        if not Z1:
+            return X2 % p, Y2 % p, Z2 % p
+        if not Z2:
+            return X1 % p, Y1 % p, Z1 % p
         if Z1 == Z2:
             if Z1 == 1:
                 return self._add_with_z_1(X1, Y1, X2, Y2, p)
@@ -917,7 +919,7 @@ class PointJacobi(AbstractPoint):
 
         X3, Y3, Z3 = self._add(X1, Y1, Z1, X2, Y2, Z2, p)
 
-        if not Y3 or not Z3:
+        if not Z3:
             return INFINITY
         return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
 
@@ -927,7 +929,7 @@ class PointJacobi(AbstractPoint):
 
     def _mul_precompute(self, other):
         """Multiply point by integer with precomputation table."""
-        X3, Y3, Z3, p = 0, 0, 1, self.__curve.p()
+        X3, Y3, Z3, p = 0, 0, 0, self.__curve.p()
         _add = self._add
         for X2, Y2 in self.__precompute:
             if other % 2:
@@ -940,7 +942,7 @@ class PointJacobi(AbstractPoint):
             else:
                 other //= 2
 
-        if not Y3 or not Z3:
+        if not Z3:
             return INFINITY
         return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
 
@@ -959,7 +961,7 @@ class PointJacobi(AbstractPoint):
 
         self = self.scale()
         X2, Y2, _ = self.__coords
-        X3, Y3, Z3 = 0, 0, 1
+        X3, Y3, Z3 = 0, 0, 0
         p, a = self.__curve.p(), self.__curve.a()
         _double = self._double
         _add = self._add
@@ -972,7 +974,7 @@ class PointJacobi(AbstractPoint):
             elif i > 0:
                 X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, 1, p)
 
-        if not Y3 or not Z3:
+        if not Z3:
             return INFINITY
 
         return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
@@ -1001,7 +1003,7 @@ class PointJacobi(AbstractPoint):
             other_mul = other_mul % self.__order
 
         # (X3, Y3, Z3) is the accumulator
-        X3, Y3, Z3 = 0, 0, 1
+        X3, Y3, Z3 = 0, 0, 0
         p, a = self.__curve.p(), self.__curve.a()
 
         # as we have 6 unique points to work with, we can't scale all of them,
@@ -1025,7 +1027,7 @@ class PointJacobi(AbstractPoint):
         # when the self and other sum to infinity, we need to add them
         # one by one to get correct result but as that's very unlikely to
         # happen in regular operation, we don't need to optimise this case
-        if not pApB_Y or not pApB_Z:
+        if not pApB_Z:
             return self * self_mul + other * other_mul
 
         # gmp object creation has cumulatively higher overhead than the
@@ -1070,7 +1072,7 @@ class PointJacobi(AbstractPoint):
                     assert B > 0
                     X3, Y3, Z3 = _add(X3, Y3, Z3, pApB_X, pApB_Y, pApB_Z, p)
 
-        if not Y3 or not Z3:
+        if not Z3:
             return INFINITY
 
         return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
@@ -1154,6 +1156,8 @@ class Point(AbstractPoint):
 
         Note: only points that lay on the same curve can be equal.
         """
+        if other is INFINITY:
+            return self.__x is None or self.__y is None
         if isinstance(other, Point):
             return (
                 self.__curve == other.__curve
@@ -1220,7 +1224,12 @@ class Point(AbstractPoint):
         # From X9.62 D.3.2:
 
         e3 = 3 * e
-        negative_self = Point(self.__curve, self.__x, -self.__y, self.__order)
+        negative_self = Point(
+            self.__curve,
+            self.__x,
+            (-self.__y) % self.__curve.p(),
+            self.__order,
+        )
         i = leftmost_bit(e3) // 2
         result = self
         # print("Multiplying %s by %d (e3 = %d):" % (self, other, e3))
@@ -1247,7 +1256,6 @@ class Point(AbstractPoint):
 
     def double(self):
         """Return a new point that is twice the old."""
-
         if self == INFINITY:
             return INFINITY
 
@@ -1261,6 +1269,9 @@ class Point(AbstractPoint):
             * numbertheory.inverse_mod(2 * self.__y, p)
         ) % p
 
+        if not l:
+            return INFINITY
+
         x3 = (l * l - 2 * self.__x) % p
         y3 = (l * (self.__x - x3) - self.__y) % p
 


Test patch:
diff --git a/src/ecdsa/test_ellipticcurve.py b/src/ecdsa/test_ellipticcurve.py
index 9bf0951..864cf10 100644
--- a/src/ecdsa/test_ellipticcurve.py
+++ b/src/ecdsa/test_ellipticcurve.py
@@ -83,6 +83,11 @@ class TestCurve(unittest.TestCase):
         c192 = CurveFp(p, -3, b)
         self.assertNotEqual(self.c_23, c192)
 
+    def test_inequality_curves_by_b_only(self):
+        a = CurveFp(23, 1, 0)
+        b = CurveFp(23, 1, 1)
+        self.assertNotEqual(a, b)
+
     def test_usability_in_a_hashed_collection_curves(self):
         {self.c_23: None}
 
@@ -184,6 +189,33 @@ class TestPoint(unittest.TestCase):
         self.assertEqual(p3.x(), x3)
         self.assertEqual(p3.y(), y3)
 
+    def test_double_to_infinity(self):
+        p1 = Point(self.c_23, 11, 20)
+        p2 = p1.double()
+        self.assertEqual((p2.x(), p2.y()), (4, 0))
+        self.assertNotEqual(p2, INFINITY)
+        p3 = p2.double()
+        self.assertEqual(p3, INFINITY)
+        self.assertIs(p3, INFINITY)
+
+    def test_add_self_to_infinity(self):
+        p1 = Point(self.c_23, 11, 20)
+        p2 = p1 + p1
+        self.assertEqual((p2.x(), p2.y()), (4, 0))
+        self.assertNotEqual(p2, INFINITY)
+        p3 = p2 + p2
+        self.assertEqual(p3, INFINITY)
+        self.assertIs(p3, INFINITY)
+
+    def test_mul_to_infinity(self):
+        p1 = Point(self.c_23, 11, 20)
+        p2 = p1 * 2
+        self.assertEqual((p2.x(), p2.y()), (4, 0))
+        self.assertNotEqual(p2, INFINITY)
+        p3 = p2 * 2
+        self.assertEqual(p3, INFINITY)
+        self.assertIs(p3, INFINITY)
+
     def test_multiply(self):
         x1, y1, m, x3, y3 = (3, 10, 2, 7, 12)
         p1 = Point(self.c_23, x1, y1)
@@ -224,6 +256,12 @@ class TestPoint(unittest.TestCase):
         c = CurveFp(100, -3, 100)
         self.assertNotEqual(self.g_23, c)
 
+    def test_inequality_diff_y(self):
+        p1 = Point(self.c_23, 6, 4)
+        p2 = Point(self.c_23, 6, 19)
+
+        self.assertNotEqual(p1, p2)
+
     def test_to_bytes_from_bytes(self):
         p = Point(self.c_23, 3, 10)
 
diff --git a/src/ecdsa/test_jacobi.py b/src/ecdsa/test_jacobi.py
index 9a46afe..f811b92 100644
--- a/src/ecdsa/test_jacobi.py
+++ b/src/ecdsa/test_jacobi.py
@@ -14,7 +14,7 @@ import platform
 import hypothesis.strategies as st
 from hypothesis import given, assume, settings, example
 
-from .ellipticcurve import CurveFp, PointJacobi, INFINITY
+from .ellipticcurve import CurveFp, PointJacobi, INFINITY, Point
 from .ecdsa import (
     generator_256,
     curve_256,
@@ -92,14 +92,21 @@ class TestJacobi(unittest.TestCase):
         self.assertIs(pj, INFINITY)
 
     def test_double_with_zero_equivalent_point(self):
-        pj = PointJacobi(curve_256, 0, curve_256.p(), 1)
+        pj = PointJacobi(curve_256, 0, 0, 0)
 
         pj = pj.double()
 
         self.assertIs(pj, INFINITY)
 
-    def test_double_with_zero_equivalent_point_non_1_z(self):
-        pj = PointJacobi(curve_256, 0, curve_256.p(), 2)
+    def test_double_with_zero_equivalent_point_non_zero_z_non_zero_y(self):
+        pj = PointJacobi(curve_256, 0, 1, curve_256.p())
+
+        pj = pj.double()
+
+        self.assertIs(pj, INFINITY)
+
+    def test_double_with_zero_equivalent_point_non_zero_z(self):
+        pj = PointJacobi(curve_256, 0, 0, curve_256.p())
 
         pj = pj.double()
 
@@ -113,7 +120,7 @@ class TestJacobi(unittest.TestCase):
         self.assertEqual(pa, pj)
 
     def test_to_affine_with_zero_point(self):
-        pj = PointJacobi(curve_256, 0, 0, 1)
+        pj = PointJacobi(curve_256, 0, 0, 0)
 
         pa = pj.to_affine()
 
@@ -144,7 +151,7 @@ class TestJacobi(unittest.TestCase):
 
     def test_add_zero_point_to_affine(self):
         pa = PointJacobi.from_affine(generator_256).to_affine()
-        pj = PointJacobi(curve_256, 0, 0, 1)
+        pj = PointJacobi(curve_256, 0, 0, 0)
 
         s = pj + pa
 
@@ -195,8 +202,35 @@ class TestJacobi(unittest.TestCase):
 
         self.assertNotEqual(pj, INFINITY)
 
+    def test_compare_non_zero_bad_scale_with_infinity(self):
+        pj = PointJacobi(curve_256, 1, 1, 0)
+        self.assertEqual(pj, INFINITY)
+
+    def test_eq_x_0_on_curve_with_infinity(self):
+        c_23 = CurveFp(23, 1, 1)
+        pj = PointJacobi(c_23, 0, 1, 1)
+
+        self.assertTrue(c_23.contains_point(0, 1))
+
+        self.assertNotEqual(pj, INFINITY)
+
+    def test_eq_y_0_on_curve_with_infinity(self):
+        c_23 = CurveFp(23, 1, 1)
+        pj = PointJacobi(c_23, 4, 0, 1)
+
+        self.assertTrue(c_23.contains_point(4, 0))
+
+        self.assertNotEqual(pj, INFINITY)
+
+    def test_eq_with_same_x_different_y(self):
+        c_23 = CurveFp(23, 1, 1)
+        p_a = PointJacobi(c_23, 0, 22, 1)
+        p_b = PointJacobi(c_23, 0, 1, 1)
+
+        self.assertNotEqual(p_a, p_b)
+
     def test_compare_zero_point_with_infinity(self):
-        pj = PointJacobi(curve_256, 0, 0, 1)
+        pj = PointJacobi(curve_256, 0, 0, 0)
 
         self.assertEqual(pj, INFINITY)
 
@@ -579,6 +613,18 @@ class TestJacobi(unittest.TestCase):
 
         self.assertEqual(ret.to_affine(), w_a + w_b)
 
+    def test_mul_add_zero(self):
+        j_g = PointJacobi.from_affine(generator_256)
+
+        w_a = generator_256 * 255
+        w_b = generator_256 * (0 * 0xA8)
+
+        j_b = j_g * 0xA8
+
+        ret = j_g.mul_add(255, j_b, 0)
+
+        self.assertEqual(ret.to_affine(), w_a + w_b)
+
     def test_mul_add_large(self):
         j_g = PointJacobi.from_affine(generator_256)
         b = PointJacobi.from_affine(j_g * 255)
@@ -619,6 +665,20 @@ class TestJacobi(unittest.TestCase):
 
         self.assertEqual(j_g.mul_add(4, dbl_neg, 2), INFINITY)
 
+    @given(
+        st.integers(min_value=0, max_value=int(generator_112r2.order() - 1)),
+        st.integers(min_value=0, max_value=int(generator_112r2.order() - 1)),
+        st.integers(min_value=0, max_value=int(generator_112r2.order() - 1)),
+    )
+    @example(693, 2, 3293)  # values that will hit all the conditions for NAF
+    def test_mul_add_random(self, mul1, mul2, mul3):
+        p_a = PointJacobi.from_affine(generator_112r2)
+        p_b = generator_112r2 * mul2
+
+        res = p_a.mul_add(mul1, p_b, mul3)
+
+        self.assertEqual(res, p_a * mul1 + p_b * mul3)
+
     def test_equality(self):
         pj1 = PointJacobi(curve=CurveFp(23, 1, 1, 1), x=2, y=3, z=1, order=1)
         pj2 = PointJacobi(curve=CurveFp(23, 1, 1, 1), x=2, y=3, z=1, order=1)
@@ -641,6 +701,78 @@ class TestJacobi(unittest.TestCase):
 
         self.assertEqual((x, y, z), (2, 3, 1))
 
+    def test_double_to_infinity(self):
+        c_23 = CurveFp(23, 1, 1)
+        p = PointJacobi(c_23, 11, 20, 1)
+        p2 = p.double()
+        self.assertEqual((p2.x(), p2.y()), (4, 0))
+        self.assertNotEqual(p2, INFINITY)
+        p3 = p2.double()
+        self.assertEqual(p3, INFINITY)
+        self.assertIs(p3, INFINITY)
+
+    def test_double_to_x_0(self):
+        c_23_2 = CurveFp(23, 1, 2)
+        p = PointJacobi(c_23_2, 9, 2, 1)
+        p2 = p.double()
+
+        self.assertEqual((p2.x(), p2.y()), (0, 18))
+
+    def test_mul_to_infinity(self):
+        c_23 = CurveFp(23, 1, 1)
+        p = PointJacobi(c_23, 11, 20, 1)
+        p2 = p * 2
+        self.assertEqual((p2.x(), p2.y()), (4, 0))
+        self.assertNotEqual(p2, INFINITY)
+        p3 = p2 * 2
+        self.assertEqual(p3, INFINITY)
+        self.assertIs(p3, INFINITY)
+
+    def test_add_to_infinity(self):
+        c_23 = CurveFp(23, 1, 1)
+        p = PointJacobi(c_23, 11, 20, 1)
+        p2 = p + p
+        self.assertEqual((p2.x(), p2.y()), (4, 0))
+        self.assertNotEqual(p2, INFINITY)
+        p3 = p2 + p2
+        self.assertEqual(p3, INFINITY)
+        self.assertIs(p3, INFINITY)
+
+    def test_mul_to_x_0(self):
+        c_23 = CurveFp(23, 1, 1)
+        p = PointJacobi(c_23, 9, 7, 1)
+
+        p2 = p * 13
+        self.assertEqual((p2.x(), p2.y()), (0, 22))
+
+    def test_mul_to_y_0(self):
+        c_23 = CurveFp(23, 1, 1)
+        p = PointJacobi(c_23, 9, 7, 1)
+
+        p2 = p * 14
+        self.assertEqual((p2.x(), p2.y()), (4, 0))
+
+    def test_add_to_x_0(self):
+        c_23 = CurveFp(23, 1, 1)
+        p = PointJacobi(c_23, 9, 7, 1)
+
+        p2 = p * 12 + p
+        self.assertEqual((p2.x(), p2.y()), (0, 22))
+
+    def test_add_to_y_0(self):
+        c_23 = CurveFp(23, 1, 1)
+        p = PointJacobi(c_23, 9, 7, 1)
+
+        p2 = p * 13 + p
+        self.assertEqual((p2.x(), p2.y()), (4, 0))
+
+    def test_add_diff_z_to_infinity(self):
+        c_23 = CurveFp(23, 1, 1)
+        p = PointJacobi(c_23, 9, 7, 1)
+
+        c = p * 20 + p * 8
+        self.assertIs(c, INFINITY)
+
     def test_pickle(self):
         pj = PointJacobi(curve=CurveFp(23, 1, 1, 1), x=2, y=3, z=1, order=1)
         self.assertEqual(pickle.loads(pickle.dumps(pj)), pj)
@@ -751,3 +883,52 @@ class TestJacobi(unittest.TestCase):
             gen._PointJacobi__precompute,
             generator_112r2._PointJacobi__precompute,
         )
+
+
+class TestZeroCurve(unittest.TestCase):
+    """Tests with curve that has (0, 0) on the curve."""
+
+    def setUp(self):
+        self.curve = CurveFp(23, 1, 0)
+
+    def test_zero_point_on_curve(self):
+        self.assertTrue(self.curve.contains_point(0, 0))
+
+    def test_double_to_0_0_point(self):
+        p = PointJacobi(self.curve, 1, 18, 1)
+
+        d = p.double()
+
+        self.assertNotEqual(d, INFINITY)
+        self.assertEqual((0, 0), (d.x(), d.y()))
+
+    def test_double_to_0_0_point_with_non_one_z(self):
+        z = 2
+        p = PointJacobi(self.curve, 1 * z**2, 18 * z**3, z)
+
+        d = p.double()
+
+        self.assertNotEqual(d, INFINITY)
+        self.assertEqual((0, 0), (d.x(), d.y()))
+
+    def test_mul_to_0_0_point(self):
+        p = PointJacobi(self.curve, 11, 13, 1)
+
+        d = p * 12
+
+        self.assertNotEqual(d, INFINITY)
+        self.assertEqual((0, 0), (d.x(), d.y()))
+
+    def test_double_of_0_0_point(self):
+        p = PointJacobi(self.curve, 0, 0, 1)
+
+        d = p.double()
+
+        self.assertIs(d, INFINITY)
+
+    def test_compare_to_old_implementation(self):
+        p = PointJacobi(self.curve, 11, 13, 1)
+        p_c = Point(self.curve, 11, 13)
+
+        for i in range(24):
+            self.assertEqual(p * i, p_c * i)
diff --git a/src/ecdsa/test_pyecdsa.py b/src/ecdsa/test_pyecdsa.py
index 0a4ed8a..4187895 100644
--- a/src/ecdsa/test_pyecdsa.py
+++ b/src/ecdsa/test_pyecdsa.py
@@ -856,6 +856,22 @@ class ECDSA(unittest.TestCase):
 
         self.assertIn("Invalid X9.62 encoding", str(exp.exception))
 
+    def test_hybrid_decoding_with_inconsistent_encoding_and_no_validation(
+        self,
+    ):
+        sk = SigningKey.from_secret_exponent(123456789)
+        vk = sk.verifying_key
+
+        enc = vk.to_string("hybrid")
+        self.assertEqual(enc[:1], b"\x06")
+        enc = b"\x07" + enc[1:]
+
+        b = VerifyingKey.from_string(
+            enc, valid_encodings=("hybrid",), validate_point=False
+        )
+
+        self.assertEqual(vk, b)
+
     def test_compressed_decoding_with_blocked_format(self):
         enc = (
             b"\x02"
@@ -898,6 +914,17 @@ class ECDSA(unittest.TestCase):
         with self.assertRaises(MalformedPointError):
             VerifyingKey.from_string(b"\x07" + enc)
 
+    def test_decoding_with_inconsistent_hybrid_odd_point(self):
+        sk = SigningKey.from_secret_exponent(123456791)
+        vk = sk.verifying_key
+
+        enc = vk.to_string("hybrid")
+        self.assertEqual(enc[:1], b"\x07")
+        enc = b"\x06" + enc[1:]
+
+        with self.assertRaises(MalformedPointError):
+            b = VerifyingKey.from_string(enc, valid_encodings=("hybrid",))
+
     def test_decoding_with_point_not_on_curve(self):
         enc = (
             b"\x0c\xe0\x1d\xe0d\x1c\x8eS\x8a\xc0\x9eK\xa8x !\xd5\xc2\xc3"