v0.1.7

1 files changed, 935 insertions, 198 deletions

diff --git a/frozen_deps/ecdsa/ellipticcurve.py b/frozen_deps/ecdsa/ellipticcurve.py
index 25565df..d6f7146 100644
--- a/frozen_deps/ecdsa/ellipticcurve.py
+++ b/frozen_deps/ecdsa/ellipticcurve.py
@@ -25,13 +25,12 @@
 #   Signature checking (5.4.2):
 #     - Verify that r and s are in [1,n-1].
 #
-# Version of 2008.11.25.
-#
 # Revision history:
 #    2005.12.31 - Initial version.
 #    2008.11.25 - Change CurveFp.is_on to contains_point.
 #
 # Written in 2005 by Peter Pearson and placed in the public domain.
+# Modified extensively as part of python-ecdsa.
 
 from __future__ import division
 
@@ -39,7 +38,7 @@ try:
     from gmpy2 import mpz
 
     GMPY = True
-except ImportError:
+except ImportError:  # pragma: no branch
     try:
         from gmpy import mpz
 
@@ -50,14 +49,19 @@ except ImportError:
 
 from six import python_2_unicode_compatible
 from . import numbertheory
-from ._rwlock import RWLock
+from ._compat import normalise_bytes, int_to_bytes, bit_length, bytes_to_int
+from .errors import MalformedPointError
+from .util import orderlen, string_to_number, number_to_string
 
 
 @python_2_unicode_compatible
 class CurveFp(object):
-    """Elliptic Curve over the field of integers modulo a prime."""
+    """
+    :term:`Short Weierstrass Elliptic Curve <short Weierstrass curve>` over a
+    prime field.
+    """
 
-    if GMPY:
+    if GMPY:  # pragma: no branch
 
         def __init__(self, p, a, b, h=None):
             """
@@ -75,7 +79,7 @@ class CurveFp(object):
             # gmpy with it
             self.__h = h
 
-    else:
+    else:  # pragma: no branch
 
         def __init__(self, p, a, b, h=None):
             """
@@ -92,17 +96,25 @@ class CurveFp(object):
             self.__h = h
 
     def __eq__(self, other):
+        """Return True if other is an identical curve, False otherwise.
+
+        Note: the value of the cofactor of the curve is not taken into account
+        when comparing curves, as it's derived from the base point and
+        intrinsic curve characteristic (but it's complex to compute),
+        only the prime and curve parameters are considered.
+        """
         if isinstance(other, CurveFp):
-            """Return True if the curves are identical, False otherwise."""
+            p = self.__p
             return (
                 self.__p == other.__p
-                and self.__a == other.__a
-                and self.__b == other.__b
+                and self.__a % p == other.__a % p
+                and self.__b % p == other.__b % p
             )
         return NotImplemented
 
     def __ne__(self, other):
-        return not (self == other)
+        """Return False if other is an identical curve, True otherwise."""
+        return not self == other
 
     def __hash__(self):
         return hash((self.__p, self.__a, self.__b))
@@ -132,9 +144,356 @@ class CurveFp(object):
         )
 
 
-class PointJacobi(object):
+class CurveEdTw(object):
+    """Parameters for a Twisted Edwards Elliptic Curve"""
+
+    if GMPY:  # pragma: no branch
+
+        def __init__(self, p, a, d, h=None, hash_func=None):
+            """
+            The curve of points satisfying a*x^2 + y^2 = 1 + d*x^2*y^2 (mod p).
+
+            h is the cofactor of the curve.
+            hash_func is the hash function associated with the curve
+             (like SHA-512 for Ed25519)
+            """
+            self.__p = mpz(p)
+            self.__a = mpz(a)
+            self.__d = mpz(d)
+            self.__h = h
+            self.__hash_func = hash_func
+
+    else:
+
+        def __init__(self, p, a, d, h=None, hash_func=None):
+            """
+            The curve of points satisfying a*x^2 + y^2 = 1 + d*x^2*y^2 (mod p).
+
+            h is the cofactor of the curve.
+            hash_func is the hash function associated with the curve
+             (like SHA-512 for Ed25519)
+            """
+            self.__p = p
+            self.__a = a
+            self.__d = d
+            self.__h = h
+            self.__hash_func = hash_func
+
+    def __eq__(self, other):
+        """Returns True if other is an identical curve."""
+        if isinstance(other, CurveEdTw):
+            p = self.__p
+            return (
+                self.__p == other.__p
+                and self.__a % p == other.__a % p
+                and self.__d % p == other.__d % p
+            )
+        return NotImplemented
+
+    def __ne__(self, other):
+        """Return False if the other is an identical curve, True otherwise."""
+        return not self == other
+
+    def __hash__(self):
+        return hash((self.__p, self.__a, self.__d))
+
+    def contains_point(self, x, y):
+        """Is the point (x, y) on this curve?"""
+        return (
+            self.__a * x * x + y * y - 1 - self.__d * x * x * y * y
+        ) % self.__p == 0
+
+    def p(self):
+        return self.__p
+
+    def a(self):
+        return self.__a
+
+    def d(self):
+        return self.__d
+
+    def hash_func(self, data):
+        return self.__hash_func(data)
+
+    def cofactor(self):
+        return self.__h
+
+    def __str__(self):
+        return "CurveEdTw(p={0}, a={1}, d={2}, h={3})".format(
+            self.__p,
+            self.__a,
+            self.__d,
+            self.__h,
+        )
+
+
+class AbstractPoint(object):
+    """Class for common methods of elliptic curve points."""
+
+    @staticmethod
+    def _from_raw_encoding(data, raw_encoding_length):
+        """
+        Decode public point from :term:`raw encoding`.
+
+        :term:`raw encoding` is the same as the :term:`uncompressed` encoding,
+        but without the 0x04 byte at the beginning.
+        """
+        # real assert, from_bytes() should not call us with different length
+        assert len(data) == raw_encoding_length
+        xs = data[: raw_encoding_length // 2]
+        ys = data[raw_encoding_length // 2 :]
+        # real assert, raw_encoding_length is calculated by multiplying an
+        # integer by two so it will always be even
+        assert len(xs) == raw_encoding_length // 2
+        assert len(ys) == raw_encoding_length // 2
+        coord_x = string_to_number(xs)
+        coord_y = string_to_number(ys)
+
+        return coord_x, coord_y
+
+    @staticmethod
+    def _from_compressed(data, curve):
+        """Decode public point from compressed encoding."""
+        if data[:1] not in (b"\x02", b"\x03"):
+            raise MalformedPointError("Malformed compressed point encoding")
+
+        is_even = data[:1] == b"\x02"
+        x = string_to_number(data[1:])
+        p = curve.p()
+        alpha = (pow(x, 3, p) + (curve.a() * x) + curve.b()) % p
+        try:
+            beta = numbertheory.square_root_mod_prime(alpha, p)
+        except numbertheory.Error as e:
+            raise MalformedPointError(
+                "Encoding does not correspond to a point on curve", e
+            )
+        if is_even == bool(beta & 1):
+            y = p - beta
+        else:
+            y = beta
+        return x, y
+
+    @classmethod
+    def _from_hybrid(cls, data, raw_encoding_length, validate_encoding):
+        """Decode public point from hybrid encoding."""
+        # real assert, from_bytes() should not call us with different types
+        assert data[:1] in (b"\x06", b"\x07")
+
+        # primarily use the uncompressed as it's easiest to handle
+        x, y = cls._from_raw_encoding(data[1:], raw_encoding_length)
+
+        # but validate if it's self-consistent if we're asked to do that
+        if validate_encoding and (
+            y & 1
+            and data[:1] != b"\x07"
+            or (not y & 1)
+            and data[:1] != b"\x06"
+        ):
+            raise MalformedPointError("Inconsistent hybrid point encoding")
+
+        return x, y
+
+    @classmethod
+    def _from_edwards(cls, curve, data):
+        """Decode a point on an Edwards curve."""
+        data = bytearray(data)
+        p = curve.p()
+        # add 1 for the sign bit and then round up
+        exp_len = (bit_length(p) + 1 + 7) // 8
+        if len(data) != exp_len:
+            raise MalformedPointError("Point length doesn't match the curve.")
+        x_0 = (data[-1] & 0x80) >> 7
+
+        data[-1] &= 0x80 - 1
+
+        y = bytes_to_int(data, "little")
+        if GMPY:
+            y = mpz(y)
+
+        x2 = (
+            (y * y - 1)
+            * numbertheory.inverse_mod(curve.d() * y * y - curve.a(), p)
+            % p
+        )
+
+        try:
+            x = numbertheory.square_root_mod_prime(x2, p)
+        except numbertheory.Error as e:
+            raise MalformedPointError(
+                "Encoding does not correspond to a point on curve", e
+            )
+
+        if x % 2 != x_0:
+            x = -x % p
+
+        return x, y
+
+    @classmethod
+    def from_bytes(
+        cls, curve, data, validate_encoding=True, valid_encodings=None
+    ):
+        """
+        Initialise the object from byte encoding of a point.
+
+        The method does accept and automatically detect the type of point
+        encoding used. It supports the :term:`raw encoding`,
+        :term:`uncompressed`, :term:`compressed`, and :term:`hybrid` encodings.
+
+        Note: generally you will want to call the ``from_bytes()`` method of
+        either a child class, PointJacobi or Point.
+
+        :param data: single point encoding of the public key
+        :type data: :term:`bytes-like object`
+        :param curve: the curve on which the public key is expected to lay
+        :type curve: ~ecdsa.ellipticcurve.CurveFp
+        :param validate_encoding: whether to verify that the encoding of the
+            point is self-consistent, defaults to True, has effect only
+            on ``hybrid`` encoding
+        :type validate_encoding: bool
+        :param valid_encodings: list of acceptable point encoding formats,
+            supported ones are: :term:`uncompressed`, :term:`compressed`,
+            :term:`hybrid`, and :term:`raw encoding` (specified with ``raw``
+            name). All formats by default (specified with ``None``).
+        :type valid_encodings: :term:`set-like object`
+
+        :raises `~ecdsa.errors.MalformedPointError`: if the public point does
+            not lay on the curve or the encoding is invalid
+
+        :return: x and y coordinates of the encoded point
+        :rtype: tuple(int, int)
+        """
+        if not valid_encodings:
+            valid_encodings = set(
+                ["uncompressed", "compressed", "hybrid", "raw"]
+            )
+        if not all(
+            i in set(("uncompressed", "compressed", "hybrid", "raw"))
+            for i in valid_encodings
+        ):
+            raise ValueError(
+                "Only uncompressed, compressed, hybrid or raw encoding "
+                "supported."
+            )
+        data = normalise_bytes(data)
+
+        if isinstance(curve, CurveEdTw):
+            return cls._from_edwards(curve, data)
+
+        key_len = len(data)
+        raw_encoding_length = 2 * orderlen(curve.p())
+        if key_len == raw_encoding_length and "raw" in valid_encodings:
+            coord_x, coord_y = cls._from_raw_encoding(
+                data, raw_encoding_length
+            )
+        elif key_len == raw_encoding_length + 1 and (
+            "hybrid" in valid_encodings or "uncompressed" in valid_encodings
+        ):
+            if data[:1] in (b"\x06", b"\x07") and "hybrid" in valid_encodings:
+                coord_x, coord_y = cls._from_hybrid(
+                    data, raw_encoding_length, validate_encoding
+                )
+            elif data[:1] == b"\x04" and "uncompressed" in valid_encodings:
+                coord_x, coord_y = cls._from_raw_encoding(
+                    data[1:], raw_encoding_length
+                )
+            else:
+                raise MalformedPointError(
+                    "Invalid X9.62 encoding of the public point"
+                )
+        elif (
+            key_len == raw_encoding_length // 2 + 1
+            and "compressed" in valid_encodings
+        ):
+            coord_x, coord_y = cls._from_compressed(data, curve)
+        else:
+            raise MalformedPointError(
+                "Length of string does not match lengths of "
+                "any of the enabled ({0}) encodings of the "
+                "curve.".format(", ".join(valid_encodings))
+            )
+        return coord_x, coord_y
+
+    def _raw_encode(self):
+        """Convert the point to the :term:`raw encoding`."""
+        prime = self.curve().p()
+        x_str = number_to_string(self.x(), prime)
+        y_str = number_to_string(self.y(), prime)
+        return x_str + y_str
+
+    def _compressed_encode(self):
+        """Encode the point into the compressed form."""
+        prime = self.curve().p()
+        x_str = number_to_string(self.x(), prime)
+        if self.y() & 1:
+            return b"\x03" + x_str
+        return b"\x02" + x_str
+
+    def _hybrid_encode(self):
+        """Encode the point into the hybrid form."""
+        raw_enc = self._raw_encode()
+        if self.y() & 1:
+            return b"\x07" + raw_enc
+        return b"\x06" + raw_enc
+
+    def _edwards_encode(self):
+        """Encode the point according to RFC8032 encoding."""
+        self.scale()
+        x, y, p = self.x(), self.y(), self.curve().p()
+
+        # add 1 for the sign bit and then round up
+        enc_len = (bit_length(p) + 1 + 7) // 8
+        y_str = int_to_bytes(y, enc_len, "little")
+        if x % 2:
+            y_str[-1] |= 0x80
+        return y_str
+
+    def to_bytes(self, encoding="raw"):
+        """
+        Convert the point to a byte string.
+
+        The method by default uses the :term:`raw encoding` (specified
+        by `encoding="raw"`. It can also output points in :term:`uncompressed`,
+        :term:`compressed`, and :term:`hybrid` formats.
+
+        For points on Edwards curves `encoding` is ignored and only the
+        encoding defined in RFC 8032 is supported.
+
+        :return: :term:`raw encoding` of a public on the curve
+        :rtype: bytes
+        """
+        assert encoding in ("raw", "uncompressed", "compressed", "hybrid")
+        curve = self.curve()
+        if isinstance(curve, CurveEdTw):
+            return self._edwards_encode()
+        elif encoding == "raw":
+            return self._raw_encode()
+        elif encoding == "uncompressed":
+            return b"\x04" + self._raw_encode()
+        elif encoding == "hybrid":
+            return self._hybrid_encode()
+        else:
+            return self._compressed_encode()
+
+    @staticmethod
+    def _naf(mult):
+        """Calculate non-adjacent form of number."""
+        ret = []
+        while mult:
+            if mult % 2:
+                nd = mult % 4
+                if nd >= 2:
+                    nd -= 4
+                ret.append(nd)
+                mult -= nd
+            else:
+                ret.append(0)
+            mult //= 2
+        return ret
+
+
+class PointJacobi(AbstractPoint):
     """
-    Point on an elliptic curve. Uses Jacobi coordinates.
+    Point on a short Weierstrass elliptic curve. Uses Jacobi coordinates.
 
     In Jacobian coordinates, there are three parameters, X, Y and Z.
     They correspond to affine parameters 'x' and 'y' like so:
@@ -158,88 +517,115 @@ class PointJacobi(object):
           generator=True
         :param bool generator: the point provided is a curve generator, as
           such, it will be commonly used with scalar multiplication. This will
-          cause to precompute multiplication table for it
+          cause to precompute multiplication table generation for it
         """
+        super(PointJacobi, self).__init__()
         self.__curve = curve
-        # since it's generally better (faster) to use scaled points vs unscaled
-        # ones, use writer-biased RWLock for locking:
-        self._update_lock = RWLock()
-        if GMPY:
-            self.__x = mpz(x)
-            self.__y = mpz(y)
-            self.__z = mpz(z)
+        if GMPY:  # pragma: no branch
+            self.__coords = (mpz(x), mpz(y), mpz(z))
             self.__order = order and mpz(order)
-        else:
-            self.__x = x
-            self.__y = y
-            self.__z = z
+        else:  # pragma: no branch
+            self.__coords = (x, y, z)
             self.__order = order
         self.__generator = generator
         self.__precompute = []
 
-    def _maybe_precompute(self):
-        if self.__generator:
-            # since we lack promotion of read-locks to write-locks, we do a
-            # "acquire-read-lock, check, acquire-write-lock plus recheck" cycle
-            try:
-                self._update_lock.reader_acquire()
-                if self.__precompute:
-                    return
-            finally:
-                self._update_lock.reader_release()
-
-            try:
-                self._update_lock.writer_acquire()
-                if self.__precompute:
-                    return
-                order = self.__order
-                assert order
-                i = 1
-                order *= 2
-                doubler = PointJacobi(
-                    self.__curve, self.__x, self.__y, self.__z, order
-                )
-                order *= 2
-                self.__precompute.append((doubler.x(), doubler.y()))
+    @classmethod
+    def from_bytes(
+        cls,
+        curve,
+        data,
+        validate_encoding=True,
+        valid_encodings=None,
+        order=None,
+        generator=False,
+    ):
+        """
+        Initialise the object from byte encoding of a point.
+
+        The method does accept and automatically detect the type of point
+        encoding used. It supports the :term:`raw encoding`,
+        :term:`uncompressed`, :term:`compressed`, and :term:`hybrid` encodings.
+
+        :param data: single point encoding of the public key
+        :type data: :term:`bytes-like object`
+        :param curve: the curve on which the public key is expected to lay
+        :type curve: ~ecdsa.ellipticcurve.CurveFp
+        :param validate_encoding: whether to verify that the encoding of the
+            point is self-consistent, defaults to True, has effect only
+            on ``hybrid`` encoding
+        :type validate_encoding: bool
+        :param valid_encodings: list of acceptable point encoding formats,
+            supported ones are: :term:`uncompressed`, :term:`compressed`,
+            :term:`hybrid`, and :term:`raw encoding` (specified with ``raw``
+            name). All formats by default (specified with ``None``).
+        :type valid_encodings: :term:`set-like object`
+        :param int order: the point order, must be non zero when using
+            generator=True
+        :param bool generator: the point provided is a curve generator, as
+            such, it will be commonly used with scalar multiplication. This
+            will cause to precompute multiplication table generation for it
+
+        :raises `~ecdsa.errors.MalformedPointError`: if the public point does
+            not lay on the curve or the encoding is invalid
 
-                while i < order:
-                    i *= 2
-                    doubler = doubler.double().scale()
-                    self.__precompute.append((doubler.x(), doubler.y()))
+        :return: Point on curve
+        :rtype: PointJacobi
+        """
+        coord_x, coord_y = super(PointJacobi, cls).from_bytes(
+            curve, data, validate_encoding, valid_encodings
+        )
+        return PointJacobi(curve, coord_x, coord_y, 1, order, generator)
 
-            finally:
-                self._update_lock.writer_release()
+    def _maybe_precompute(self):
+        if not self.__generator or self.__precompute:
+            return
+
+        # since this code will execute just once, and it's fully deterministic,
+        # depend on atomicity of the last assignment to switch from empty
+        # self.__precompute to filled one and just ignore the unlikely
+        # situation when two threads execute it at the same time (as it won't
+        # lead to inconsistent __precompute)
+        order = self.__order
+        assert order
+        precompute = []
+        i = 1
+        order *= 2
+        coord_x, coord_y, coord_z = self.__coords
+        doubler = PointJacobi(self.__curve, coord_x, coord_y, coord_z, order)
+        order *= 2
+        precompute.append((doubler.x(), doubler.y()))
+
+        while i < order:
+            i *= 2
+            doubler = doubler.double().scale()
+            precompute.append((doubler.x(), doubler.y()))
+
+        self.__precompute = precompute
 
     def __getstate__(self):
-        try:
-            self._update_lock.reader_acquire()
-            state = self.__dict__.copy()
-        finally:
-            self._update_lock.reader_release()
-        del state["_update_lock"]
+        # while this code can execute at the same time as _maybe_precompute()
+        # is updating the __precompute or scale() is updating the __coords,
+        # there is no requirement for consistency between __coords and
+        # __precompute
+        state = self.__dict__.copy()
         return state
 
     def __setstate__(self, state):
         self.__dict__.update(state)
-        self._update_lock = RWLock()
 
     def __eq__(self, other):
-        """Compare two points with each-other."""
-        try:
-            self._update_lock.reader_acquire()
-            if other is INFINITY:
-                return not self.__y or not self.__z
-            x1, y1, z1 = self.__x, self.__y, self.__z
-        finally:
-            self._update_lock.reader_release()
+        """Compare for equality two points with each-other.
+
+        Note: only points that lay on the same curve can be equal.
+        """
+        x1, y1, z1 = self.__coords
+        if other is INFINITY:
+            return not y1 or not z1
         if isinstance(other, Point):
             x2, y2, z2 = other.x(), other.y(), 1
         elif isinstance(other, PointJacobi):
-            try:
-                other._update_lock.reader_acquire()
-                x2, y2, z2 = other.__x, other.__y, other.__z
-            finally:
-                other._update_lock.reader_release()
+            x2, y2, z2 = other.__coords
         else:
             return NotImplemented
         if self.__curve != other.curve():
@@ -256,6 +642,10 @@ class PointJacobi(object):
             y1 * zz2 * z2 - y2 * zz1 * z1
         ) % p == 0
 
+    def __ne__(self, other):
+        """Compare for inequality two points with each-other."""
+        return not self == other
+
     def order(self):
         """Return the order of the point.
 
@@ -276,17 +666,12 @@ class PointJacobi(object):
         call x() and y() on the returned instance. Or call `scale()`
         and then x() and y() on the returned instance.
         """
-        try:
-            self._update_lock.reader_acquire()
-            if self.__z == 1:
-                return self.__x
-            x = self.__x
-            z = self.__z
-        finally:
-            self._update_lock.reader_release()
+        x, _, z = self.__coords
+        if z == 1:
+            return x
         p = self.__curve.p()
         z = numbertheory.inverse_mod(z, p)
-        return x * z ** 2 % p
+        return x * z**2 % p
 
     def y(self):
         """
@@ -297,17 +682,12 @@ class PointJacobi(object):
         call x() and y() on the returned instance. Or call `scale()`
         and then x() and y() on the returned instance.
         """
-        try:
-            self._update_lock.reader_acquire()
-            if self.__z == 1:
-                return self.__y
-            y = self.__y
-            z = self.__z
-        finally:
-            self._update_lock.reader_release()
+        _, y, z = self.__coords
+        if z == 1:
+            return y
         p = self.__curve.p()
         z = numbertheory.inverse_mod(z, p)
-        return y * z ** 3 % p
+        return y * z**3 % p
 
     def scale(self):
         """
@@ -315,37 +695,28 @@ class PointJacobi(object):
 
         Modifies point in place, returns self.
         """
-        try:
-            self._update_lock.reader_acquire()
-            if self.__z == 1:
-                return self
-        finally:
-            self._update_lock.reader_release()
+        x, y, z = self.__coords
+        if z == 1:
+            return self
 
-        try:
-            self._update_lock.writer_acquire()
-            # scaling already scaled point is safe (as inverse of 1 is 1) and
-            # quick so we don't need to optimise for the unlikely event when
-            # two threads hit the lock at the same time
-            p = self.__curve.p()
-            z_inv = numbertheory.inverse_mod(self.__z, p)
-            zz_inv = z_inv * z_inv % p
-            self.__x = self.__x * zz_inv % p
-            self.__y = self.__y * zz_inv * z_inv % p
-            # we are setting the z last so that the check above will return
-            # true only after all values were already updated
-            self.__z = 1
-        finally:
-            self._update_lock.writer_release()
+        # scaling is deterministic, so even if two threads execute the below
+        # code at the same time, they will set __coords to the same value
+        p = self.__curve.p()
+        z_inv = numbertheory.inverse_mod(z, p)
+        zz_inv = z_inv * z_inv % p
+        x = x * zz_inv % p
+        y = y * zz_inv * z_inv % p
+        self.__coords = (x, y, 1)
         return self
 
     def to_affine(self):
         """Return point in affine form."""
-        if not self.__y or not self.__z:
+        _, y, z = self.__coords
+        if not y or not z:
             return INFINITY
         self.scale()
-        # after point is scaled, it's immutable, so no need to perform locking
-        return Point(self.__curve, self.__x, self.__y, self.__order)
+        x, y, z = self.__coords
+        return Point(self.__curve, x, y, self.__order)
 
     @staticmethod
     def from_affine(point, generator=False):
@@ -359,7 +730,8 @@ class PointJacobi(object):
             point.curve(), point.x(), point.y(), 1, point.order(), generator
         )
 
-    # plese note that all the methods that use the equations from hyperelliptic
+    # please note that all the methods that use the equations from
+    # hyperelliptic
     # are formatted in a way to maximise performance.
     # Things that make code faster: multiplying instead of taking to the power
     # (`xx = x * x; xxxx = xx * xx % p` is faster than `xxxx = x**4 % p` and
@@ -389,7 +761,7 @@ class PointJacobi(object):
         """Add a point to itself, arbitrary z."""
         if Z1 == 1:
             return self._double_with_z_1(X1, Y1, p, a)
-        if not Z1:
+        if not Y1 or not Z1:
             return 0, 0, 1
         # after:
         # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl
@@ -409,17 +781,13 @@ class PointJacobi(object):
 
     def double(self):
         """Add a point to itself."""
-        if not self.__y:
+        X1, Y1, Z1 = self.__coords
+
+        if not Y1:
             return INFINITY
 
         p, a = self.__curve.p(), self.__curve.a()
 
-        try:
-            self._update_lock.reader_acquire()
-            X1, Y1, Z1 = self.__x, self.__y, self.__z
-        finally:
-            self._update_lock.reader_release()
-
         X3, Y3, Z3 = self._double(X1, Y1, Z1, p, a)
 
         if not Y3 or not Z3:
@@ -438,7 +806,7 @@ class PointJacobi(object):
         if not H and not r:
             return self._double_with_z_1(X1, Y1, p, self.__curve.a())
         V = X1 * I
-        X3 = (r ** 2 - J - 2 * V) % p
+        X3 = (r**2 - J - 2 * V) % p
         Y3 = (r * (V - X3) - 2 * Y1 * J) % p
         Z3 = 2 * H % p
         return X3, Y3, Z3
@@ -532,16 +900,9 @@ class PointJacobi(object):
             raise ValueError("The other point is on different curve")
 
         p = self.__curve.p()
-        try:
-            self._update_lock.reader_acquire()
-            X1, Y1, Z1 = self.__x, self.__y, self.__z
-        finally:
-            self._update_lock.reader_release()
-        try:
-            other._update_lock.reader_acquire()
-            X2, Y2, Z2 = other.__x, other.__y, other.__z
-        finally:
-            other._update_lock.reader_release()
+        X1, Y1, Z1 = self.__coords
+        X2, Y2, Z2 = other.__coords
+
         X3, Y3, Z3 = self._add(X1, Y1, Z1, X2, Y2, Z2, p)
 
         if not Y3 or not Z3:
@@ -571,25 +932,9 @@ class PointJacobi(object):
             return INFINITY
         return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
 
-    @staticmethod
-    def _naf(mult):
-        """Calculate non-adjacent form of number."""
-        ret = []
-        while mult:
-            if mult % 2:
-                nd = mult % 4
-                if nd >= 2:
-                    nd = nd - 4
-                ret += [nd]
-                mult -= nd
-            else:
-                ret += [0]
-            mult //= 2
-        return ret
-
     def __mul__(self, other):
         """Multiply point by an integer."""
-        if not self.__y or not other:
+        if not self.__coords[1] or not other:
             return INFINITY
         if other == 1:
             return self
@@ -601,8 +946,7 @@ class PointJacobi(object):
             return self._mul_precompute(other)
 
         self = self.scale()
-        # once scaled, point is immutable, not need to lock
-        X2, Y2 = self.__x, self.__y
+        X2, Y2, _ = self.__coords
         X3, Y3, Z3 = 0, 0, 1
         p, a = self.__curve.p(), self.__curve.a()
         _double = self._double
@@ -621,29 +965,20 @@ class PointJacobi(object):
 
         return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
 
-    @staticmethod
-    def _leftmost_bit(x):
-        """Return integer with the same magnitude as x but only one bit set"""
-        assert x > 0
-        result = 1
-        while result <= x:
-            result = 2 * result
-        return result // 2
-
     def mul_add(self, self_mul, other, other_mul):
         """
         Do two multiplications at the same time, add results.
 
         calculates self*self_mul + other*other_mul
         """
-        if other is INFINITY or other_mul == 0:
+        if other == INFINITY or other_mul == 0:
             return self * self_mul
         if self_mul == 0:
             return other * other_mul
         if not isinstance(other, PointJacobi):
             other = PointJacobi.from_affine(other)
         # when the points have precomputed answers, then multiplying them alone
-        # is faster (as it uses NAF)
+        # is faster (as it uses NAF and no point doublings)
         self._maybe_precompute()
         other._maybe_precompute()
         if self.__precompute and other.__precompute:
@@ -653,32 +988,75 @@ class PointJacobi(object):
             self_mul = self_mul % self.__order
             other_mul = other_mul % self.__order
 
-        i = self._leftmost_bit(max(self_mul, other_mul)) * 2
+        # (X3, Y3, Z3) is the accumulator
         X3, Y3, Z3 = 0, 0, 1
         p, a = self.__curve.p(), self.__curve.a()
-        self = self.scale()
-        # after scaling, point is immutable, no need for locking
-        X1, Y1 = self.__x, self.__y
-        other = other.scale()
-        X2, Y2 = other.__x, other.__y
-        both = self + other
-        if both is INFINITY:
-            X4, Y4 = 0, 0
-        else:
-            both.scale()
-            X4, Y4 = both.__x, both.__y
+
+        # as we have 6 unique points to work with, we can't scale all of them,
+        # but do scale the ones that are used most often
+        self.scale()
+        X1, Y1, Z1 = self.__coords
+        other.scale()
+        X2, Y2, Z2 = other.__coords
+
         _double = self._double
         _add = self._add
-        while i > 1:
+
+        # with NAF we have 3 options: no add, subtract, add
+        # so with 2 points, we have 9 combinations:
+        # 0, -A, +A, -B, -A-B, +A-B, +B, -A+B, +A+B
+        # so we need 4 combined points:
+        mAmB_X, mAmB_Y, mAmB_Z = _add(X1, -Y1, Z1, X2, -Y2, Z2, p)
+        pAmB_X, pAmB_Y, pAmB_Z = _add(X1, Y1, Z1, X2, -Y2, Z2, p)
+        mApB_X, mApB_Y, mApB_Z = _add(X1, -Y1, Z1, X2, Y2, Z2, p)
+        pApB_X, pApB_Y, pApB_Z = _add(X1, Y1, Z1, X2, Y2, Z2, p)
+        # 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:
+            return self * self_mul + other * other_mul
+
+        # gmp object creation has cumulatively higher overhead than the
+        # speedup we get from calculating the NAF using gmp so ensure use
+        # of int()
+        self_naf = list(reversed(self._naf(int(self_mul))))
+        other_naf = list(reversed(self._naf(int(other_mul))))
+        # ensure that the lists are the same length (zip() will truncate
+        # longer one otherwise)
+        if len(self_naf) < len(other_naf):
+            self_naf = [0] * (len(other_naf) - len(self_naf)) + self_naf
+        elif len(self_naf) > len(other_naf):
+            other_naf = [0] * (len(self_naf) - len(other_naf)) + other_naf
+
+        for A, B in zip(self_naf, other_naf):
             X3, Y3, Z3 = _double(X3, Y3, Z3, p, a)
-            i = i // 2
 
-            if self_mul & i and other_mul & i:
-                X3, Y3, Z3 = _add(X3, Y3, Z3, X4, Y4, 1, p)
-            elif self_mul & i:
-                X3, Y3, Z3 = _add(X3, Y3, Z3, X1, Y1, 1, p)
-            elif other_mul & i:
-                X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, 1, p)
+            # conditions ordered from most to least likely
+            if A == 0:
+                if B == 0:
+                    pass
+                elif B < 0:
+                    X3, Y3, Z3 = _add(X3, Y3, Z3, X2, -Y2, Z2, p)
+                else:
+                    assert B > 0
+                    X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, Z2, p)
+            elif A < 0:
+                if B == 0:
+                    X3, Y3, Z3 = _add(X3, Y3, Z3, X1, -Y1, Z1, p)
+                elif B < 0:
+                    X3, Y3, Z3 = _add(X3, Y3, Z3, mAmB_X, mAmB_Y, mAmB_Z, p)
+                else:
+                    assert B > 0
+                    X3, Y3, Z3 = _add(X3, Y3, Z3, mApB_X, mApB_Y, mApB_Z, p)
+            else:
+                assert A > 0
+                if B == 0:
+                    X3, Y3, Z3 = _add(X3, Y3, Z3, X1, Y1, Z1, p)
+                elif B < 0:
+                    X3, Y3, Z3 = _add(X3, Y3, Z3, pAmB_X, pAmB_Y, pAmB_Z, p)
+                else:
+                    assert B > 0
+                    X3, Y3, Z3 = _add(X3, Y3, Z3, pApB_X, pApB_Y, pApB_Z, p)
 
         if not Y3 or not Z3:
             return INFINITY
@@ -687,21 +1065,17 @@ class PointJacobi(object):
 
     def __neg__(self):
         """Return negated point."""
-        try:
-            self._update_lock.reader_acquire()
-            return PointJacobi(
-                self.__curve, self.__x, -self.__y, self.__z, self.__order
-            )
-        finally:
-            self._update_lock.reader_release()
+        x, y, z = self.__coords
+        return PointJacobi(self.__curve, x, -y, z, self.__order)
 
 
-class Point(object):
-    """A point on an elliptic curve. Altering x and y is forbidding,
-     but they can be read by the x() and y() methods."""
+class Point(AbstractPoint):
+    """A point on a short Weierstrass elliptic curve. Altering x and y is
+    forbidden, but they can be read by the x() and y() methods."""
 
     def __init__(self, curve, x, y, order=None):
         """curve, x, y, order; order (optional) is the order of this point."""
+        super(Point, self).__init__()
         self.__curve = curve
         if GMPY:
             self.__x = x and mpz(x)
@@ -720,8 +1094,54 @@ class Point(object):
         if curve and curve.cofactor() != 1 and order:
             assert self * order == INFINITY
 
+    @classmethod
+    def from_bytes(
+        cls,
+        curve,
+        data,
+        validate_encoding=True,
+        valid_encodings=None,
+        order=None,
+    ):
+        """
+        Initialise the object from byte encoding of a point.
+
+        The method does accept and automatically detect the type of point
+        encoding used. It supports the :term:`raw encoding`,
+        :term:`uncompressed`, :term:`compressed`, and :term:`hybrid` encodings.
+
+        :param data: single point encoding of the public key
+        :type data: :term:`bytes-like object`
+        :param curve: the curve on which the public key is expected to lay
+        :type curve: ~ecdsa.ellipticcurve.CurveFp
+        :param validate_encoding: whether to verify that the encoding of the
+            point is self-consistent, defaults to True, has effect only
+            on ``hybrid`` encoding
+        :type validate_encoding: bool
+        :param valid_encodings: list of acceptable point encoding formats,
+            supported ones are: :term:`uncompressed`, :term:`compressed`,
+            :term:`hybrid`, and :term:`raw encoding` (specified with ``raw``
+            name). All formats by default (specified with ``None``).
+        :type valid_encodings: :term:`set-like object`
+        :param int order: the point order, must be non zero when using
+            generator=True
+
+        :raises `~ecdsa.errors.MalformedPointError`: if the public point does
+            not lay on the curve or the encoding is invalid
+
+        :return: Point on curve
+        :rtype: Point
+        """
+        coord_x, coord_y = super(Point, cls).from_bytes(
+            curve, data, validate_encoding, valid_encodings
+        )
+        return Point(curve, coord_x, coord_y, order)
+
     def __eq__(self, other):
-        """Return True if the points are identical, False otherwise."""
+        """Return True if the points are identical, False otherwise.
+
+        Note: only points that lay on the same curve can be equal.
+        """
         if isinstance(other, Point):
             return (
                 self.__curve == other.__curve
@@ -730,6 +1150,10 @@ class Point(object):
             )
         return NotImplemented
 
+    def __ne__(self, other):
+        """Returns False if points are identical, True otherwise."""
+        return not self == other
+
     def __neg__(self):
         return Point(self.__curve, self.__x, self.__curve.p() - self.__y)
 
@@ -843,5 +1267,318 @@ class Point(object):
         return self.__order
 
 
+class PointEdwards(AbstractPoint):
+    """Point on Twisted Edwards curve.
+
+    Internally represents the coordinates on the curve using four parameters,
+    X, Y, Z, T. They correspond to affine parameters 'x' and 'y' like so:
+
+    x = X / Z
+    y = Y / Z
+    x*y = T / Z
+    """
+
+    def __init__(self, curve, x, y, z, t, order=None, generator=False):
+        """
+        Initialise a point that uses the extended coordinates internally.
+        """
+        super(PointEdwards, self).__init__()
+        self.__curve = curve
+        if GMPY:  # pragma: no branch
+            self.__coords = (mpz(x), mpz(y), mpz(z), mpz(t))
+            self.__order = order and mpz(order)
+        else:  # pragma: no branch
+            self.__coords = (x, y, z, t)
+            self.__order = order
+        self.__generator = generator
+        self.__precompute = []
+
+    @classmethod
+    def from_bytes(
+        cls,
+        curve,
+        data,
+        validate_encoding=None,
+        valid_encodings=None,
+        order=None,
+        generator=False,
+    ):
+        """
+        Initialise the object from byte encoding of a point.
+
+        `validate_encoding` and `valid_encodings` are provided for
+        compatibility with Weierstrass curves, they are ignored for Edwards
+        points.
+
+        :param data: single point encoding of the public key
+        :type data: :term:`bytes-like object`
+        :param curve: the curve on which the public key is expected to lay
+        :type curve: ecdsa.ellipticcurve.CurveEdTw
+        :param None validate_encoding: Ignored, encoding is always validated
+        :param None valid_encodings: Ignored, there is just one encoding
+            supported
+        :param int order: the point order, must be non zero when using
+            generator=True
+        :param bool generator: Flag to mark the point as a curve generator,
+            this will cause the library to pre-compute some values to
+            make repeated usages of the point much faster
+
+        :raises `~ecdsa.errors.MalformedPointError`: if the public point does
+            not lay on the curve or the encoding is invalid
+
+        :return: Initialised point on an Edwards curve
+        :rtype: PointEdwards
+        """
+        coord_x, coord_y = super(PointEdwards, cls).from_bytes(
+            curve, data, validate_encoding, valid_encodings
+        )
+        return PointEdwards(
+            curve, coord_x, coord_y, 1, coord_x * coord_y, order, generator
+        )
+
+    def _maybe_precompute(self):
+        if not self.__generator or self.__precompute:
+            return self.__precompute
+
+        # since this code will execute just once, and it's fully deterministic,
+        # depend on atomicity of the last assignment to switch from empty
+        # self.__precompute to filled one and just ignore the unlikely
+        # situation when two threads execute it at the same time (as it won't
+        # lead to inconsistent __precompute)
+        order = self.__order
+        assert order
+        precompute = []
+        i = 1
+        order *= 2
+        coord_x, coord_y, coord_z, coord_t = self.__coords
+        prime = self.__curve.p()
+
+        doubler = PointEdwards(
+            self.__curve, coord_x, coord_y, coord_z, coord_t, order
+        )
+        # for "protection" against Minerva we need 1 or 2 more bits depending
+        # on order bit size, but it's easier to just calculate one
+        # point more always
+        order *= 4
+
+        while i < order:
+            doubler = doubler.scale()
+            coord_x, coord_y = doubler.x(), doubler.y()
+            coord_t = coord_x * coord_y % prime
+            precompute.append((coord_x, coord_y, coord_t))
+
+            i *= 2
+            doubler = doubler.double()
+
+        self.__precompute = precompute
+        return self.__precompute
+
+    def x(self):
+        """Return affine x coordinate."""
+        X1, _, Z1, _ = self.__coords
+        if Z1 == 1:
+            return X1
+        p = self.__curve.p()
+        z_inv = numbertheory.inverse_mod(Z1, p)
+        return X1 * z_inv % p
+
+    def y(self):
+        """Return affine y coordinate."""
+        _, Y1, Z1, _ = self.__coords
+        if Z1 == 1:
+            return Y1
+        p = self.__curve.p()
+        z_inv = numbertheory.inverse_mod(Z1, p)
+        return Y1 * z_inv % p
+
+    def curve(self):
+        """Return the curve of the point."""
+        return self.__curve
+
+    def order(self):
+        return self.__order
+
+    def scale(self):
+        """
+        Return point scaled so that z == 1.
+
+        Modifies point in place, returns self.
+        """
+        X1, Y1, Z1, _ = self.__coords
+        if Z1 == 1:
+            return self
+
+        p = self.__curve.p()
+        z_inv = numbertheory.inverse_mod(Z1, p)
+        x = X1 * z_inv % p
+        y = Y1 * z_inv % p
+        t = x * y % p
+        self.__coords = (x, y, 1, t)
+        return self
+
+    def __eq__(self, other):
+        """Compare for equality two points with each-other.
+
+        Note: only points on the same curve can be equal.
+        """
+        x1, y1, z1, t1 = self.__coords
+        if other is INFINITY:
+            return not x1 or not t1
+        if isinstance(other, PointEdwards):
+            x2, y2, z2, t2 = other.__coords
+        else:
+            return NotImplemented
+        if self.__curve != other.curve():
+            return False
+        p = self.__curve.p()
+
+        # cross multiply to eliminate divisions
+        xn1 = x1 * z2 % p
+        xn2 = x2 * z1 % p
+        yn1 = y1 * z2 % p
+        yn2 = y2 * z1 % p
+        return xn1 == xn2 and yn1 == yn2
+
+    def __ne__(self, other):
+        """Compare for inequality two points with each-other."""
+        return not self == other
+
+    def _add(self, X1, Y1, Z1, T1, X2, Y2, Z2, T2, p, a):
+        """add two points, assume sane parameters."""
+        # after add-2008-hwcd-2
+        # from https://hyperelliptic.org/EFD/g1p/auto-twisted-extended.html
+        # NOTE: there are more efficient formulas for Z1 or Z2 == 1
+        A = X1 * X2 % p
+        B = Y1 * Y2 % p
+        C = Z1 * T2 % p
+        D = T1 * Z2 % p
+        E = D + C
+        F = ((X1 - Y1) * (X2 + Y2) + B - A) % p
+        G = B + a * A
+        H = D - C
+        if not H:
+            return self._double(X1, Y1, Z1, T1, p, a)
+        X3 = E * F % p
+        Y3 = G * H % p
+        T3 = E * H % p
+        Z3 = F * G % p
+
+        return X3, Y3, Z3, T3
+
+    def __add__(self, other):
+        """Add point to another."""
+        if other == INFINITY:
+            return self
+        if (
+            not isinstance(other, PointEdwards)
+            or self.__curve != other.__curve
+        ):
+            raise ValueError("The other point is on a different curve.")
+
+        p, a = self.__curve.p(), self.__curve.a()
+        X1, Y1, Z1, T1 = self.__coords
+        X2, Y2, Z2, T2 = other.__coords
+
+        X3, Y3, Z3, T3 = self._add(X1, Y1, Z1, T1, X2, Y2, Z2, T2, p, a)
+
+        if not X3 or not T3:
+            return INFINITY
+        return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
+
+    def __radd__(self, other):
+        """Add other to self."""
+        return self + other
+
+    def _double(self, X1, Y1, Z1, T1, p, a):
+        """Double the point, assume sane parameters."""
+        # after "dbl-2008-hwcd"
+        # from https://hyperelliptic.org/EFD/g1p/auto-twisted-extended.html
+        # NOTE: there are more efficient formulas for Z1 == 1
+        A = X1 * X1 % p
+        B = Y1 * Y1 % p
+        C = 2 * Z1 * Z1 % p
+        D = a * A % p
+        E = ((X1 + Y1) * (X1 + Y1) - A - B) % p
+        G = D + B
+        F = G - C
+        H = D - B
+        X3 = E * F % p
+        Y3 = G * H % p
+        T3 = E * H % p
+        Z3 = F * G % p
+
+        return X3, Y3, Z3, T3
+
+    def double(self):
+        """Return point added to itself."""
+        X1, Y1, Z1, T1 = self.__coords
+
+        if not X1 or not T1:
+            return INFINITY
+
+        p, a = self.__curve.p(), self.__curve.a()
+
+        X3, Y3, Z3, T3 = self._double(X1, Y1, Z1, T1, p, a)
+
+        if not X3 or not T3:
+            return INFINITY
+        return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
+
+    def __rmul__(self, other):
+        """Multiply point by an integer."""
+        return self * other
+
+    def _mul_precompute(self, other):
+        """Multiply point by integer with precomputation table."""
+        X3, Y3, Z3, T3, p, a = 0, 1, 1, 0, self.__curve.p(), self.__curve.a()
+        _add = self._add
+        for X2, Y2, T2 in self.__precompute:
+            rem = other % 4
+            if rem == 0 or rem == 2:
+                other //= 2
+            elif rem == 3:
+                other = (other + 1) // 2
+                X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, -X2, Y2, 1, -T2, p, a)
+            else:
+                assert rem == 1
+                other = (other - 1) // 2
+                X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, X2, Y2, 1, T2, p, a)
+
+        if not X3 or not T3:
+            return INFINITY
+
+        return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
+
+    def __mul__(self, other):
+        """Multiply point by an integer."""
+        X2, Y2, Z2, T2 = self.__coords
+        if not X2 or not T2 or not other:
+            return INFINITY
+        if other == 1:
+            return self
+        if self.__order:
+            # order*2 as a "protection" for Minerva
+            other = other % (self.__order * 2)
+        if self._maybe_precompute():
+            return self._mul_precompute(other)
+
+        X3, Y3, Z3, T3 = 0, 1, 1, 0  # INFINITY in extended coordinates
+        p, a = self.__curve.p(), self.__curve.a()
+        _double = self._double
+        _add = self._add
+
+        for i in reversed(self._naf(other)):
+            X3, Y3, Z3, T3 = _double(X3, Y3, Z3, T3, p, a)
+            if i < 0:
+                X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, -X2, Y2, Z2, -T2, p, a)
+            elif i > 0:
+                X3, Y3, Z3, T3 = _add(X3, Y3, Z3, T3, X2, Y2, Z2, T2, p, a)
+
+        if not X3 or not T3:
+            return INFINITY
+
+        return PointEdwards(self.__curve, X3, Y3, Z3, T3, self.__order)
+
+
 # This one point is the Point At Infinity for all purposes:
 INFINITY = Point(None, None, None)