Merge pull request #223 from tomato42/small-curves

Add support for small curves

13 files changed, 356 insertions, 79 deletions

diff --git a/.travis.yml b/.travis.yml
index 3ebeff4..3bbd9ac 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -17,6 +17,8 @@ matrix:
   include:
       - python: 2.7
         env: INSTRUMENTAL=yes
+        dist: bionic
+        sudo: true
       - python: 2.6
         env: TOX_ENV=py26
       - python: 2.7
@@ -117,17 +119,16 @@ script:
   - |
       if [[ $INSTRUMENTAL && $TRAVIS_PULL_REQUEST != "false" ]]; then
         git checkout $PR_FIRST^
-        files="$(ls src/ecdsa/test*.py)"
-        instrumental -t ecdsa -i 'test.*|.*_version|.*_compat' `which pytest` $files
+        instrumental -t ecdsa -i 'test.*|.*_version|.*_compat' `which pytest` src/ecdsa/test*.py
         instrumental -f .instrumental.cov -s
         instrumental -f .instrumental.cov -s | python diff-instrumental.py --save .diff-instrumental
         git checkout $BRANCH
-        instrumental -t ecdsa -i 'test.*|.*_version' `which pytest` src/ecdsa
+        instrumental -t ecdsa -i 'test.*|.*_version|.*_compat' `which pytest` src/ecdsa/test*.py
         instrumental -f .instrumental.cov -sr
       fi
   - |
       if [[ $INSTRUMENTAL && $TRAVIS_PULL_REQUEST == "false" ]]; then
-        instrumental -t ecdsa -i 'test.*|.*_version' `which pytest` src/ecdsa
+        instrumental -t ecdsa -i 'test.*|.*_version|.*_compat' `which pytest` src/ecdsa
         instrumental -f .instrumental.cov -s
         # just log the values when merging
         instrumental -f .instrumental.cov -s | python diff-instrumental.py
diff --git a/src/ecdsa/__init__.py b/src/ecdsa/__init__.py
index 4ae0a11..80ae50f 100644
--- a/src/ecdsa/__init__.py
+++ b/src/ecdsa/__init__.py
@@ -19,6 +19,10 @@ from .curves import (
     BRAINPOOLP320r1,
     BRAINPOOLP384r1,
     BRAINPOOLP512r1,
+    SECP112r1,
+    SECP112r2,
+    SECP128r1,
+    SECP160r1,
 )
 from .ecdh import (
     ECDH,
@@ -72,5 +76,9 @@ _hush_pyflakes = [
     BRAINPOOLP320r1,
     BRAINPOOLP384r1,
     BRAINPOOLP512r1,
+    SECP112r1,
+    SECP112r2,
+    SECP128r1,
+    SECP160r1,
 ]
 del _hush_pyflakes
diff --git a/src/ecdsa/curves.py b/src/ecdsa/curves.py
index 9a10380..90cdd52 100644
--- a/src/ecdsa/curves.py
+++ b/src/ecdsa/curves.py
@@ -10,6 +10,10 @@ __all__ = [
     "UnknownCurveError",
     "orderlen",
     "Curve",
+    "SECP112r1",
+    "SECP112r2",
+    "SECP128r1",
+    "SECP160r1",
     "NIST192p",
     "NIST224p",
     "NIST256p",
@@ -40,7 +44,7 @@ class Curve:
         self.generator = generator
         self.order = generator.order()
         self.baselen = orderlen(self.order)
-        self.verifying_key_length = 2 * self.baselen
+        self.verifying_key_length = 2 * orderlen(curve.p())
         self.signature_length = 2 * self.baselen
         self.oid = oid
         self.encoded_oid = der.encode_oid(*oid)
@@ -49,6 +53,43 @@ class Curve:
         return self.name
 
 
+# the SEC curves
+SECP112r1 = Curve(
+    "SECP112r1",
+    ecdsa.curve_112r1,
+    ecdsa.generator_112r1,
+    (1, 3, 132, 0, 6),
+    "secp112r1",
+)
+
+
+SECP112r2 = Curve(
+    "SECP112r2",
+    ecdsa.curve_112r2,
+    ecdsa.generator_112r2,
+    (1, 3, 132, 0, 7),
+    "secp112r2",
+)
+
+
+SECP128r1 = Curve(
+    "SECP128r1",
+    ecdsa.curve_128r1,
+    ecdsa.generator_128r1,
+    (1, 3, 132, 0, 28),
+    "secp128r1",
+)
+
+
+SECP160r1 = Curve(
+    "SECP160r1",
+    ecdsa.curve_160r1,
+    ecdsa.generator_160r1,
+    (1, 3, 132, 0, 8),
+    "secp160r1",
+)
+
+
 # the NIST curves
 NIST192p = Curve(
     "NIST192p",
@@ -167,6 +208,7 @@ BRAINPOOLP512r1 = Curve(
 )
 
 
+# no order in particular, but keep previously added curves first
 curves = [
     NIST192p,
     NIST224p,
@@ -181,6 +223,10 @@ curves = [
     BRAINPOOLP320r1,
     BRAINPOOLP384r1,
     BRAINPOOLP512r1,
+    SECP112r1,
+    SECP112r2,
+    SECP128r1,
+    SECP160r1,
 ]
 
 
diff --git a/src/ecdsa/ecdh.py b/src/ecdsa/ecdh.py
index 9173279..a12e94e 100644
--- a/src/ecdsa/ecdh.py
+++ b/src/ecdsa/ecdh.py
@@ -304,7 +304,7 @@ class ECDH(object):
         :rtype: byte string
         """
         return number_to_string(
-            self.generate_sharedsecret(), self.private_key.curve.order
+            self.generate_sharedsecret(), self.private_key.curve.curve.p()
         )
 
     def generate_sharedsecret(self):
diff --git a/src/ecdsa/ecdsa.py b/src/ecdsa/ecdsa.py
index d785a45..9f11d50 100644
--- a/src/ecdsa/ecdsa.py
+++ b/src/ecdsa/ecdsa.py
@@ -294,6 +294,74 @@ def point_is_valid(generator, x, y):
     return True
 
 
+# secp112r1 curve
+_p = int(remove_whitespace("DB7C 2ABF62E3 5E668076 BEAD208B"), 16)
+# s = 00F50B02 8E4D696E 67687561 51752904 72783FB1
+_a = int(remove_whitespace("DB7C 2ABF62E3 5E668076 BEAD2088"), 16)
+_b = int(remove_whitespace("659E F8BA0439 16EEDE89 11702B22"), 16)
+_Gx = int(remove_whitespace("09487239 995A5EE7 6B55F9C2 F098"), 16)
+_Gy = int(remove_whitespace("A89C E5AF8724 C0A23E0E 0FF77500"), 16)
+_r = int(remove_whitespace("DB7C 2ABF62E3 5E7628DF AC6561C5"), 16)
+_h = 1
+curve_112r1 = ellipticcurve.CurveFp(_p, _a, _b, _h)
+generator_112r1 = ellipticcurve.PointJacobi(
+    curve_112r1, _Gx, _Gy, 1, _r, generator=True
+)
+
+
+# secp112r2 curve
+_p = int(remove_whitespace("DB7C 2ABF62E3 5E668076 BEAD208B"), 16)
+# s = 022757A1 114D69E 67687561 51755316 C05E0BD4
+_a = int(remove_whitespace("6127 C24C05F3 8A0AAAF6 5C0EF02C"), 16)
+_b = int(remove_whitespace("51DE F1815DB5 ED74FCC3 4C85D709"), 16)
+_Gx = int(remove_whitespace("4BA30AB5 E892B4E1 649DD092 8643"), 16)
+_Gy = int(remove_whitespace("ADCD 46F5882E 3747DEF3 6E956E97"), 16)
+_r = int(remove_whitespace("36DF 0AAFD8B8 D7597CA1 0520D04B"), 16)
+_h = 4
+curve_112r2 = ellipticcurve.CurveFp(_p, _a, _b, _h)
+generator_112r2 = ellipticcurve.PointJacobi(
+    curve_112r2, _Gx, _Gy, 1, _r, generator=True
+)
+
+
+# secp128r1 curve
+_p = int(remove_whitespace("FFFFFFFD FFFFFFFF FFFFFFFF FFFFFFFF"), 16)
+# S = 000E0D4D 69E6768 75615175 0CC03A44 73D03679
+# a and b are mod p, so a is equal to p-3, or simply -3
+# _a = -3
+_b = int(remove_whitespace("E87579C1 1079F43D D824993C 2CEE5ED3"), 16)
+_Gx = int(remove_whitespace("161FF752 8B899B2D 0C28607C A52C5B86"), 16)
+_Gy = int(remove_whitespace("CF5AC839 5BAFEB13 C02DA292 DDED7A83"), 16)
+_r = int(remove_whitespace("FFFFFFFE 00000000 75A30D1B 9038A115"), 16)
+_h = 1
+curve_128r1 = ellipticcurve.CurveFp(_p, -3, _b, _h)
+generator_128r1 = ellipticcurve.PointJacobi(
+    curve_128r1, _Gx, _Gy, 1, _r, generator=True
+)
+
+
+# secp160r1
+_p = int(remove_whitespace("FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 7FFFFFFF"), 16)
+# S = 1053CDE4 2C14D696 E6768756 1517533B F3F83345
+# a and b are mod p, so a is equal to p-3, or simply -3
+# _a = -3
+_b = int(remove_whitespace("1C97BEFC 54BD7A8B 65ACF89F 81D4D4AD C565FA45"), 16)
+_Gx = int(
+    remove_whitespace("4A96B568 8EF57328 46646989 68C38BB9 13CBFC82"), 16,
+)
+_Gy = int(
+    remove_whitespace("23A62855 3168947D 59DCC912 04235137 7AC5FB32"), 16,
+)
+_r = int(
+    remove_whitespace("01 00000000 00000000 0001F4C8 F927AED3 CA752257"), 16,
+)
+_h = 1
+curve_160r1 = ellipticcurve.CurveFp(_p, -3, _b, _h)
+generator_160r1 = ellipticcurve.PointJacobi(
+    curve_160r1, _Gx, _Gy, 1, _r, generator=True
+)
+
+
 # NIST Curve P-192:
 _p = 6277101735386680763835789423207666416083908700390324961279
 _r = 6277101735386680763835789423176059013767194773182842284081
diff --git a/src/ecdsa/keys.py b/src/ecdsa/keys.py
index c4b3f06..8edd99c 100644
--- a/src/ecdsa/keys.py
+++ b/src/ecdsa/keys.py
@@ -124,6 +124,38 @@ class MalformedPointError(AssertionError):
     pass
 
 
+def _truncate_and_convert_digest(digest, curve, allow_truncate):
+    """Truncates and converts digest to an integer."""
+    if not allow_truncate:
+        if len(digest) > curve.baselen:
+            raise BadDigestError(
+                "this curve ({0}) is too short "
+                "for the length of your digest ({1})".format(
+                    curve.name, 8 * len(digest)
+                )
+            )
+    else:
+        digest = digest[: curve.baselen]
+    number = string_to_number(digest)
+    if allow_truncate:
+        max_length = bit_length(curve.order)
+        # we don't use bit_length(number) as that truncates leading zeros
+        length = len(digest) * 8
+
+        # See NIST FIPS 186-4:
+        #
+        # When the length of the output of the hash function is greater
+        # than N (i.e., the bit length of q), then the leftmost N bits of
+        # the hash function output block shall be used in any calculation
+        # using the hash function output during the generation or
+        # verification of a digital signature.
+        #
+        # as such, we need to shift-out the low-order bits:
+        number >>= max(0, length - max_length)
+
+    return number
+
+
 class VerifyingKey(object):
     """
     Class for handling keys that can verify signatures (public keys).
@@ -240,12 +272,12 @@ class VerifyingKey(object):
         order = curve.order
         # real assert, from_string() should not call us with different length
         assert len(string) == curve.verifying_key_length
-        xs = string[: curve.baselen]
-        ys = string[curve.baselen :]
-        if len(xs) != curve.baselen:
-            raise MalformedPointError("Unexpected length of encoded x")
-        if len(ys) != curve.baselen:
-            raise MalformedPointError("Unexpected length of encoded y")
+        xs = string[: curve.verifying_key_length // 2]
+        ys = string[curve.verifying_key_length // 2 :]
+        # real assert, verifying_key_length is calculated by multiplying an
+        # integer by two so it will always be even
+        assert len(xs) == curve.verifying_key_length // 2
+        assert len(ys) == curve.verifying_key_length // 2
         x = string_to_number(xs)
         y = string_to_number(ys)
 
@@ -339,7 +371,7 @@ class VerifyingKey(object):
                 raise MalformedPointError(
                     "Invalid X9.62 encoding of the public point"
                 )
-        elif sig_len == curve.baselen + 1:
+        elif sig_len == curve.verifying_key_length // 2 + 1:
             point = cls._from_compressed(string, curve)
         else:
             raise MalformedPointError(
@@ -435,7 +467,13 @@ class VerifyingKey(object):
 
     @classmethod
     def from_public_key_recovery(
-        cls, signature, data, curve, hashfunc=sha1, sigdecode=sigdecode_string
+        cls,
+        signature,
+        data,
+        curve,
+        hashfunc=sha1,
+        sigdecode=sigdecode_string,
+        allow_truncate=True,
     ):
         """
         Return keys that can be used as verifiers of the provided signature.
@@ -458,6 +496,9 @@ class VerifyingKey(object):
             a tuple with two integers, "r" as the first one and "s" as the
             second one. See :func:`ecdsa.util.sigdecode_string` and
             :func:`ecdsa.util.sigdecode_der` for examples.
+        :param bool allow_truncate: if True, the provided hashfunc can generate
+            values larger than the bit size of the order of the curve, the
+            extra bits (at the end of the digest) will be truncated.
         :type sigdecode: callable
 
         :return: Initialised VerifyingKey objects
@@ -466,7 +507,12 @@ class VerifyingKey(object):
         data = normalise_bytes(data)
         digest = hashfunc(data).digest()
         return cls.from_public_key_recovery_with_digest(
-            signature, digest, curve, hashfunc=hashfunc, sigdecode=sigdecode
+            signature,
+            digest,
+            curve,
+            hashfunc=hashfunc,
+            sigdecode=sigdecode,
+            allow_truncate=allow_truncate,
         )
 
     @classmethod
@@ -477,6 +523,7 @@ class VerifyingKey(object):
         curve,
         hashfunc=sha1,
         sigdecode=sigdecode_string,
+        allow_truncate=False,
     ):
         """
         Return keys that can be used as verifiers of the provided signature.
@@ -500,7 +547,10 @@ class VerifyingKey(object):
             second one. See :func:`ecdsa.util.sigdecode_string` and
             :func:`ecdsa.util.sigdecode_der` for examples.
         :type sigdecode: callable
-
+        :param bool allow_truncate: if True, the provided hashfunc can generate
+            values larger than the bit size of the order of the curve (and
+            the length of provided `digest`), the extra bits (at the end of the
+            digest) will be truncated.
 
         :return: Initialised VerifyingKey object
         :rtype: VerifyingKey
@@ -510,7 +560,9 @@ class VerifyingKey(object):
         sig = ecdsa.Signature(r, s)
 
         digest = normalise_bytes(digest)
-        digest_as_number = string_to_number(digest)
+        digest_as_number = _truncate_and_convert_digest(
+            digest, curve, allow_truncate
+        )
         pks = sig.recover_public_keys(digest_as_number, generator)
 
         # Transforms the ecdsa.Public_key object into a VerifyingKey
@@ -521,14 +573,14 @@ class VerifyingKey(object):
 
     def _raw_encode(self):
         """Convert the public key to the :term:`raw encoding`."""
-        order = self.pubkey.order
+        order = self.curve.curve.p()
         x_str = number_to_string(self.pubkey.point.x(), order)
         y_str = number_to_string(self.pubkey.point.y(), order)
         return x_str + y_str
 
     def _compressed_encode(self):
         """Encode the public point into the compressed form."""
-        order = self.pubkey.order
+        order = self.curve.curve.p()
         x_str = number_to_string(self.pubkey.point.x(), order)
         if self.pubkey.point.y() & 1:
             return b("\x03") + x_str
@@ -717,27 +769,9 @@ class VerifyingKey(object):
         # signature doesn't have to be a bytes-like-object so don't normalise
         # it, the decoders will do that
         digest = normalise_bytes(digest)
-        if not allow_truncate and len(digest) > self.curve.baselen:
-            raise BadDigestError(
-                "this curve (%s) is too short "
-                "for your digest (%d)" % (self.curve.name, 8 * len(digest))
-            )
-        number = string_to_number(digest)
-        if allow_truncate:
-            max_length = bit_length(self.curve.order)
-            # we don't use bit_length(number) as that truncates leading zeros
-            length = len(digest) * 8
-
-            # See NIST FIPS 186-4:
-            #
-            # When the length of the output of the hash function is greater
-            # than N (i.e., the bit length of q), then the leftmost N bits of
-            # the hash function output block shall be used in any calculation
-            # using the hash function output during the generation or
-            # verification of a digital signature.
-            #
-            # as such, we need to shift-out the low-order bits:
-            number >>= max(0, length - max_length)
+        number = _truncate_and_convert_digest(
+            digest, self.curve, allow_truncate,
+        )
 
         try:
             r, s = sigdecode(signature, self.pubkey.order)
@@ -1409,14 +1443,9 @@ class SigningKey(object):
         :rtype: bytes or sigencode function dependant type
         """
         digest = normalise_bytes(digest)
-        if allow_truncate:
-            digest = digest[: self.curve.baselen]
-        if len(digest) > self.curve.baselen:
-            raise BadDigestError(
-                "this curve (%s) is too short "
-                "for your digest (%d)" % (self.curve.name, 8 * len(digest))
-            )
-        number = string_to_number(digest)
+        number = _truncate_and_convert_digest(
+            digest, self.curve, allow_truncate,
+        )
         r, s = self.sign_number(number, entropy, k)
         return sigencode(r, s, self.privkey.order)
 
diff --git a/src/ecdsa/numbertheory.py b/src/ecdsa/numbertheory.py
index 5ff1c27..03577c7 100644
--- a/src/ecdsa/numbertheory.py
+++ b/src/ecdsa/numbertheory.py
@@ -220,11 +220,14 @@ def square_root_mod_prime(a, p):
     raise RuntimeError("No b found.")
 
 
+# because all the inverse_mod code is arch/environment specific, and coveralls
+# expects it to execute equal number of times, we need to waive it by
+# adding the "no branch" pragma to all branches
 if GMPY2:  # pragma: no branch
 
     def inverse_mod(a, m):
         """Inverse of a mod m."""
-        if a == 0:
+        if a == 0:  # pragma: no branch
             return 0
         return powmod(a, -1, m)
 
@@ -237,14 +240,14 @@ elif GMPY:  # pragma: no branch
         # only using the native `pow()` function, and `pow()` in gmpy sanity
         # checks the parameters before passing them on to underlying
         # implementation
-        if a == 0:
+        if a == 0:  # pragma: no branch
             return 0
         a = mpz(a)
         m = mpz(m)
 
         lm, hm = mpz(1), mpz(0)
         low, high = a % m, m
-        while low > 1:
+        while low > 1:  # pragma: no branch
             r = high // low
             lm, low, hm, high = hm - lm * r, high - low * r, lm, low
 
@@ -255,7 +258,7 @@ elif sys.version_info >= (3, 8):  # pragma: no branch
 
     def inverse_mod(a, m):
         """Inverse of a mod m."""
-        if a == 0:
+        if a == 0:  # pragma: no branch
             return 0
         return pow(a, -1, m)
 
@@ -265,12 +268,12 @@ else:  # pragma: no branch
     def inverse_mod(a, m):
         """Inverse of a mod m."""
 
-        if a == 0:
+        if a == 0:  # pragma: no branch
             return 0
 
         lm, hm = 1, 0
         low, high = a % m, m
-        while low > 1:
+        while low > 1:  # pragma: no branch
             r = high // low
             lm, low, hm, high = hm - lm * r, high - low * r, lm, low
 
diff --git a/src/ecdsa/test_ecdh.py b/src/ecdsa/test_ecdh.py
index d84429c..32d8825 100644
--- a/src/ecdsa/test_ecdh.py
+++ b/src/ecdsa/test_ecdh.py
@@ -375,7 +375,7 @@ def test_ecdh_with_openssl(vcurve):
         if hlp.find("-derive") == 0:  # pragma: no cover
             pytest.skip("system openssl does not support `pkeyutl -derive`")
     except RunOpenSslError:  # pragma: no cover
-        pytest.skip("system openssl does not support `pkeyutl -derive`")
+        pytest.skip("system openssl could not be executed")
 
     if os.path.isdir("t"):  # pragma: no branch
         shutil.rmtree("t")
@@ -412,25 +412,20 @@ def test_ecdh_with_openssl(vcurve):
 
     assert secret1 == secret2
 
-    try:
-        run_openssl(
-            "pkeyutl -derive -inkey t/privkey1.pem -peerkey t/pubkey2.pem -out t/secret1"
-        )
-        run_openssl(
-            "pkeyutl -derive -inkey t/privkey2.pem -peerkey t/pubkey1.pem -out t/secret2"
-        )
-    except RunOpenSslError:  # pragma: no cover
-        pytest.skip("system openssl does not support `pkeyutl -derive`")
-        return
+    run_openssl(
+        "pkeyutl -derive -inkey t/privkey1.pem -peerkey t/pubkey2.pem -out t/secret1"
+    )
+    run_openssl(
+        "pkeyutl -derive -inkey t/privkey2.pem -peerkey t/pubkey1.pem -out t/secret2"
+    )
 
     with open("t/secret1", "rb") as e:
         ssl_secret1 = e.read()
     with open("t/secret1", "rb") as e:
         ssl_secret2 = e.read()
 
-    if len(ssl_secret1) != vk1.curve.baselen:  # pragma: no cover
-        pytest.skip("system openssl does not support `pkeyutl -derive`")
-        return
+    assert len(ssl_secret1) == vk1.curve.verifying_key_length // 2
+    assert len(secret1) == vk1.curve.verifying_key_length // 2
 
     assert ssl_secret1 == ssl_secret2
     assert secret1 == ssl_secret1
diff --git a/src/ecdsa/test_jacobi.py b/src/ecdsa/test_jacobi.py
index 4a938a3..4fdbe54 100644
--- a/src/ecdsa/test_jacobi.py
+++ b/src/ecdsa/test_jacobi.py
@@ -210,7 +210,8 @@ class TestJacobi(unittest.TestCase):
     @example(0)
     @example(int(generator_brainpoolp160r1.order()))
     def test_precompute(self, mul):
-        precomp = PointJacobi.from_affine(generator_brainpoolp160r1, True)
+        precomp = generator_brainpoolp160r1
+        self.assertTrue(precomp._PointJacobi__precompute)
         pj = PointJacobi.from_affine(generator_brainpoolp160r1)
 
         a = precomp * mul
@@ -383,7 +384,7 @@ class TestJacobi(unittest.TestCase):
         self.assertEqual(j_g * 2, j_g.mul_add(1, j_g, 1))
 
     def test_mul_add_precompute(self):
-        j_g = PointJacobi.from_affine(generator_256, True)
+        j_g = PointJacobi.from_affine(generator_brainpoolp160r1, True)
         b = PointJacobi.from_affine(j_g * 255, True)
 
         self.assertEqual(j_g * 256, j_g + b)
@@ -391,7 +392,7 @@ class TestJacobi(unittest.TestCase):
         self.assertEqual(j_g * (5 + 255 * 7), j_g.mul_add(5, b, 7))
 
     def test_mul_add_precompute_large(self):
-        j_g = PointJacobi.from_affine(generator_256, True)
+        j_g = PointJacobi.from_affine(generator_brainpoolp160r1, True)
         b = PointJacobi.from_affine(j_g * 255, True)
 
         self.assertEqual(j_g * 256, j_g + b)
diff --git a/src/ecdsa/test_keys.py b/src/ecdsa/test_keys.py
index 406a5bf..b25403f 100644
--- a/src/ecdsa/test_keys.py
+++ b/src/ecdsa/test_keys.py
@@ -150,6 +150,8 @@ class TestVerifyingKeyFromDer(unittest.TestCase):
         )
         cls.vk2 = VerifyingKey.from_pem(key_str)
 
+        cls.sk2 = SigningKey.generate(vk.curve)
+
     def test_custom_hashfunc(self):
         vk = VerifyingKey.from_der(self.key_bytes, hashlib.sha256)
 
@@ -196,10 +198,20 @@ class TestVerifyingKeyFromDer(unittest.TestCase):
         self.assertEqual(self.vk, self.sk.get_verifying_key())
 
     def test_inequality_on_verifying_keys(self):
-        self.assertNotEqual(self.vk, self.vk2)
+        # use `==` to workaround instrumental <-> unittest compat issue
+        self.assertFalse(self.vk == self.vk2)
 
     def test_inequality_on_verifying_keys_not_implemented(self):
-        self.assertNotEqual(self.vk, None)
+        # use `==` to workaround instrumental <-> unittest compat issue
+        self.assertFalse(self.vk == None)
+
+    def test_VerifyingKey_inequality_on_same_curve(self):
+        # use `==` to workaround instrumental <-> unittest compat issue
+        self.assertFalse(self.vk == self.sk2.verifying_key)
+
+    def test_SigningKey_inequality_on_same_curve(self):
+        # use `==` to workaround instrumental <-> unittest compat issue
+        self.assertFalse(self.sk == self.sk2)
 
 
 class TestSigningKey(unittest.TestCase):
@@ -271,10 +283,12 @@ class TestSigningKey(unittest.TestCase):
         self.assertTrue(vk.verify(sig, b"other message"))
 
     def test_inequality_on_signing_keys(self):
-        self.assertNotEqual(self.sk1, self.sk2)
+        # use `==` to workaround instrumental <-> unittest compat issue
+        self.assertFalse(self.sk1 == self.sk2)
 
     def test_inequality_on_signing_keys_not_implemented(self):
-        self.assertNotEqual(self.sk1, None)
+        # use `==` to workaround instrumental <-> unittest compat issue
+        self.assertFalse(self.sk1 == None)
 
 
 # test VerifyingKey.verify()
diff --git a/src/ecdsa/test_numbertheory.py b/src/ecdsa/test_numbertheory.py
index 4912c57..b121b87 100644
--- a/src/ecdsa/test_numbertheory.py
+++ b/src/ecdsa/test_numbertheory.py
@@ -207,6 +207,38 @@ HYP_SLOW_SETTINGS = dict(HYP_SETTINGS)
 HYP_SLOW_SETTINGS["max_examples"] = 10
 
 
+class TestIsPrime(unittest.TestCase):
+    def test_very_small_prime(self):
+        assert is_prime(23)
+
+    def test_very_small_composite(self):
+        assert not is_prime(22)
+
+    def test_small_prime(self):
+        assert is_prime(123456791)
+
+    def test_special_composite(self):
+        assert not is_prime(10261)
+
+    def test_medium_prime_1(self):
+        # nextPrime[2^256]
+        assert is_prime(2 ** 256 + 0x129)
+
+    def test_medium_prime_2(self):
+        # nextPrime(2^256+0x129)
+        assert is_prime(2 ** 256 + 0x12D)
+
+    def test_medium_trivial_composite(self):
+        assert not is_prime(2 ** 256 + 0x130)
+
+    def test_medium_non_trivial_composite(self):
+        assert not is_prime(2 ** 256 + 0x12F)
+
+    def test_large_prime(self):
+        # nextPrime[2^2048]
+        assert is_prime(2 ** 2048 + 0x3D5)
+
+
 class TestNumbertheory(unittest.TestCase):
     def test_gcd(self):
         assert gcd(3 * 5 * 7, 3 * 5 * 11, 3 * 5 * 13) == 3 * 5
diff --git a/src/ecdsa/test_pyecdsa.py b/src/ecdsa/test_pyecdsa.py
index 65b6716..d904b93 100644
--- a/src/ecdsa/test_pyecdsa.py
+++ b/src/ecdsa/test_pyecdsa.py
@@ -26,6 +26,10 @@ from .util import sigdecode_der, sigdecode_strings
 from .util import number_to_string, encoded_oid_ecPublicKey, MalformedSignature
 from .curves import Curve, UnknownCurveError
 from .curves import (
+    SECP112r1,
+    SECP112r2,
+    SECP128r1,
+    SECP160r1,
     NIST192p,
     NIST224p,
     NIST256p,
@@ -310,8 +314,15 @@ class ECDSA(unittest.TestCase):
             def order(self):
                 return 123456789
 
+        class FakeCurveFp:
+            def p(self):
+                return int(
+                    "6525534529039240705020950546962731340"
+                    "4541085228058844382513856749047873406763"
+                )
+
         badcurve = Curve(
-            "unknown", None, FakeGenerator(), (1, 2, 3, 4, 5, 6), None
+            "unknown", FakeCurveFp(), FakeGenerator(), (1, 2, 3, 4, 5, 6), None
         )
         badpub.curve = badcurve
         badder = badpub.to_der()
@@ -616,7 +627,7 @@ class ECDSA(unittest.TestCase):
 
     def test_public_key_recovery(self):
         # Create keys
-        curve = NIST256p
+        curve = BRAINPOOLP160r1
 
         sk = SigningKey.generate(curve=curve)
         vk = sk.get_verifying_key()
@@ -649,7 +660,7 @@ class ECDSA(unittest.TestCase):
 
     def test_public_key_recovery_with_custom_hash(self):
         # Create keys
-        curve = NIST256p
+        curve = BRAINPOOLP160r1
 
         sk = SigningKey.generate(curve=curve, hashfunc=sha256)
         vk = sk.get_verifying_key()
@@ -660,7 +671,7 @@ class ECDSA(unittest.TestCase):
 
         # Recover verifying keys
         recovered_vks = VerifyingKey.from_public_key_recovery(
-            signature, data, curve, hashfunc=sha256
+            signature, data, curve, hashfunc=sha256, allow_truncate=True
         )
 
         # Test if each pk is valid
@@ -866,6 +877,34 @@ class OpenSSL(unittest.TestCase):
     # sig: 5:OpenSSL->python 6:python->OpenSSL
 
     @pytest.mark.skipif(
+        "secp112r1" not in OPENSSL_SUPPORTED_CURVES,
+        reason="system openssl does not support secp112r1",
+    )
+    def test_from_openssl_secp112r1(self):
+        return self.do_test_from_openssl(SECP112r1)
+
+    @pytest.mark.skipif(
+        "secp112r2" not in OPENSSL_SUPPORTED_CURVES,
+        reason="system openssl does not support secp112r2",
+    )
+    def test_from_openssl_secp112r2(self):
+        return self.do_test_from_openssl(SECP112r2)
+
+    @pytest.mark.skipif(
+        "secp128r1" not in OPENSSL_SUPPORTED_CURVES,
+        reason="system openssl does not support secp128r1",
+    )
+    def test_from_openssl_secp128r1(self):
+        return self.do_test_from_openssl(SECP128r1)
+
+    @pytest.mark.skipif(
+        "secp160r1" not in OPENSSL_SUPPORTED_CURVES,
+        reason="system openssl does not support secp160r1",
+    )
+    def test_from_openssl_secp160r1(self):
+        return self.do_test_from_openssl(SECP160r1)
+
+    @pytest.mark.skipif(
         "prime192v1" not in OPENSSL_SUPPORTED_CURVES,
         reason="system openssl does not support prime192v1",
     )
@@ -1030,6 +1069,34 @@ class OpenSSL(unittest.TestCase):
         self.assertEqual(sk, sk_from_p8)
 
     @pytest.mark.skipif(
+        "secp112r1" not in OPENSSL_SUPPORTED_CURVES,
+        reason="system openssl does not support secp112r1",
+    )
+    def test_to_openssl_secp112r1(self):
+        self.do_test_to_openssl(SECP112r1)
+
+    @pytest.mark.skipif(
+        "secp112r2" not in OPENSSL_SUPPORTED_CURVES,
+        reason="system openssl does not support secp112r2",
+    )
+    def test_to_openssl_secp112r2(self):
+        self.do_test_to_openssl(SECP112r2)
+
+    @pytest.mark.skipif(
+        "secp128r1" not in OPENSSL_SUPPORTED_CURVES,
+        reason="system openssl does not support secp128r1",
+    )
+    def test_to_openssl_secp128r1(self):
+        self.do_test_to_openssl(SECP128r1)
+
+    @pytest.mark.skipif(
+        "secp160r1" not in OPENSSL_SUPPORTED_CURVES,
+        reason="system openssl does not support secp160r1",
+    )
+    def test_to_openssl_secp160r1(self):
+        self.do_test_to_openssl(SECP160r1)
+
+    @pytest.mark.skipif(
         "prime192v1" not in OPENSSL_SUPPORTED_CURVES,
         reason="system openssl does not support prime192v1",
     )
diff --git a/tox.ini b/tox.ini
index 4b072c3..60562de 100644
--- a/tox.ini
+++ b/tox.ini
@@ -55,6 +55,19 @@ basepython=python2.7
 [testenv:gmpy2py39]
 basepython=python3.9
 
+[testenv:instrumental]
+basepython = python2.7
+deps =
+     gmpy2
+     instrumental
+     hypothesis
+     pytest>=4.6.0
+     coverage==4.5.4
+     six
+commands =
+         instrumental -t ecdsa -i 'test.*|.*_version|.*_compat' {envbindir}/pytest {posargs:src/ecdsa}
+         instrumental -f .instrumental.cov -sr
+
 [testenv:coverage]
 sitepackages=True
 whitelist_externals=coverage