diff options
Diffstat (limited to 'frozen_deps/ecdsa/ellipticcurve.py')
| -rw-r--r-- | frozen_deps/ecdsa/ellipticcurve.py | 1133 |
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) |