aboutsummaryrefslogtreecommitdiff
path: root/freezed_deps/ecdsa/ellipticcurve.py
diff options
context:
space:
mode:
Diffstat (limited to 'freezed_deps/ecdsa/ellipticcurve.py')
-rw-r--r--freezed_deps/ecdsa/ellipticcurve.py780
1 files changed, 780 insertions, 0 deletions
diff --git a/freezed_deps/ecdsa/ellipticcurve.py b/freezed_deps/ecdsa/ellipticcurve.py
new file mode 100644
index 0000000..3420454
--- /dev/null
+++ b/freezed_deps/ecdsa/ellipticcurve.py
@@ -0,0 +1,780 @@
+#! /usr/bin/env python
+# -*- coding: utf-8 -*-
+#
+# Implementation of elliptic curves, for cryptographic applications.
+#
+# This module doesn't provide any way to choose a random elliptic
+# curve, nor to verify that an elliptic curve was chosen randomly,
+# because one can simply use NIST's standard curves.
+#
+# Notes from X9.62-1998 (draft):
+# Nomenclature:
+# - Q is a public key.
+# The "Elliptic Curve Domain Parameters" include:
+# - q is the "field size", which in our case equals p.
+# - p is a big prime.
+# - G is a point of prime order (5.1.1.1).
+# - n is the order of G (5.1.1.1).
+# Public-key validation (5.2.2):
+# - Verify that Q is not the point at infinity.
+# - Verify that X_Q and Y_Q are in [0,p-1].
+# - Verify that Q is on the curve.
+# - Verify that nQ is the point at infinity.
+# Signature generation (5.3):
+# - Pick random k from [1,n-1].
+# 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.
+
+from __future__ import division
+
+try:
+ from gmpy2 import mpz
+ GMPY = True
+except ImportError:
+ try:
+ from gmpy import mpz
+ GMPY = True
+ except ImportError:
+ GMPY = False
+
+
+from six import python_2_unicode_compatible
+from . import numbertheory
+from ._rwlock import RWLock
+
+
+@python_2_unicode_compatible
+class CurveFp(object):
+ """Elliptic Curve over the field of integers modulo a prime."""
+
+ if GMPY:
+ def __init__(self, p, a, b, h=None):
+ """
+ The curve of points satisfying y^2 = x^3 + a*x + b (mod p).
+
+ h is an integer that is the cofactor of the elliptic curve domain
+ parameters; it is the number of points satisfying the elliptic curve
+ equation divided by the order of the base point. It is used for selection
+ of efficient algorithm for public point verification.
+ """
+ self.__p = mpz(p)
+ self.__a = mpz(a)
+ self.__b = mpz(b)
+ # h is not used in calculations and it can be None, so don't use
+ # gmpy with it
+ self.__h = h
+ else:
+ def __init__(self, p, a, b, h=None):
+ """
+ The curve of points satisfying y^2 = x^3 + a*x + b (mod p).
+
+ h is an integer that is the cofactor of the elliptic curve domain
+ parameters; it is the number of points satisfying the elliptic curve
+ equation divided by the order of the base point. It is used for selection
+ of efficient algorithm for public point verification.
+ """
+ self.__p = p
+ self.__a = a
+ self.__b = b
+ self.__h = h
+
+ def __eq__(self, other):
+ if isinstance(other, CurveFp):
+ """Return True if the curves are identical, False otherwise."""
+ return self.__p == other.__p \
+ and self.__a == other.__a \
+ and self.__b == other.__b
+ return NotImplemented
+
+ def __hash__(self):
+ return hash((self.__p, self.__a, self.__b))
+
+ def p(self):
+ return self.__p
+
+ def a(self):
+ return self.__a
+
+ def b(self):
+ return self.__b
+
+ def cofactor(self):
+ return self.__h
+
+ def contains_point(self, x, y):
+ """Is the point (x,y) on this curve?"""
+ return (y * y - ((x * x + self.__a) * x + self.__b)) % self.__p == 0
+
+ def __str__(self):
+ return "CurveFp(p=%d, a=%d, b=%d, h=%d)" % (
+ self.__p, self.__a, self.__b, self.__h)
+
+
+class PointJacobi(object):
+ """
+ Point on an 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:
+
+ x = X / Z²
+ y = Y / Z³
+ """
+ def __init__(self, curve, x, y, z, order=None, generator=False):
+ """
+ Initialise a point that uses Jacobi representation internally.
+
+ :param CurveFp curve: curve on which the point resides
+ :param int x: the X parameter of Jacobi representation (equal to x when
+ converting from affine coordinates
+ :param int y: the Y parameter of Jacobi representation (equal to y when
+ converting from affine coordinates
+ :param int z: the Z parameter of Jacobi representation (equal to 1 when
+ converting from affine coordinates
+ :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 for it
+ """
+ self.__curve = curve
+ # since it's generally better (faster) to use scaled points vs unscaled
+ # ones, use writer-biased RWLock for locking:
+ self._scale_lock = RWLock()
+ if GMPY:
+ self.__x = mpz(x)
+ self.__y = mpz(y)
+ self.__z = mpz(z)
+ self.__order = order and mpz(order)
+ else:
+ self.__x = x
+ self.__y = y
+ self.__z = z
+ self.__order = order
+ self.__precompute = []
+ if generator:
+ assert order
+ i = 1
+ order *= 2
+ doubler = PointJacobi(curve, x, y, z, order)
+ order *= 2
+ self.__precompute.append((doubler.x(), doubler.y()))
+
+ while i < order:
+ i *= 2
+ doubler = doubler.double().scale()
+ self.__precompute.append((doubler.x(), doubler.y()))
+
+ def __eq__(self, other):
+ """Compare two points with each-other."""
+ try:
+ self._scale_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._scale_lock.reader_release()
+ if isinstance(other, Point):
+ x2, y2, z2 = other.x(), other.y(), 1
+ elif isinstance(other, PointJacobi):
+ try:
+ other._scale_lock.reader_acquire()
+ x2, y2, z2 = other.__x, other.__y, other.__z
+ finally:
+ other._scale_lock.reader_release()
+ else:
+ return NotImplemented
+ if self.__curve != other.curve():
+ return False
+ p = self.__curve.p()
+
+ zz1 = z1 * z1 % p
+ zz2 = z2 * z2 % p
+
+ # compare the fractions by bringing them to the same denominator
+ # depend on short-circuit to save 4 multiplications in case of inequality
+ return (x1 * zz2 - x2 * zz1) % p == 0 and \
+ (y1 * zz2 * z2 - y2 * zz1 * z1) % p == 0
+
+ def order(self):
+ """Return the order of the point.
+
+ None if it is undefined.
+ """
+ return self.__order
+
+ def curve(self):
+ """Return curve over which the point is defined."""
+ return self.__curve
+
+ def x(self):
+ """
+ Return affine x coordinate.
+
+ This method should be used only when the 'y' coordinate is not needed.
+ It's computationally more efficient to use `to_affine()` and then
+ call x() and y() on the returned instance. Or call `scale()`
+ and then x() and y() on the returned instance.
+ """
+ try:
+ self._scale_lock.reader_acquire()
+ if self.__z == 1:
+ return self.__x
+ x = self.__x
+ z = self.__z
+ finally:
+ self._scale_lock.reader_release()
+ p = self.__curve.p()
+ z = numbertheory.inverse_mod(z, p)
+ return x * z**2 % p
+
+ def y(self):
+ """
+ Return affine y coordinate.
+
+ This method should be used only when the 'x' coordinate is not needed.
+ It's computationally more efficient to use `to_affine()` and then
+ call x() and y() on the returned instance. Or call `scale()`
+ and then x() and y() on the returned instance.
+ """
+ try:
+ self._scale_lock.reader_acquire()
+ if self.__z == 1:
+ return self.__y
+ y = self.__y
+ z = self.__z
+ finally:
+ self._scale_lock.reader_release()
+ p = self.__curve.p()
+ z = numbertheory.inverse_mod(z, p)
+ return y * z**3 % p
+
+ def scale(self):
+ """
+ Return point scaled so that z == 1.
+
+ Modifies point in place, returns self.
+ """
+ try:
+ self._scale_lock.reader_acquire()
+ if self.__z == 1:
+ return self
+ finally:
+ self._scale_lock.reader_release()
+
+ try:
+ self._scale_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._scale_lock.writer_release()
+ return self
+
+ def to_affine(self):
+ """Return point in affine form."""
+ if not self.__y or not self.__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)
+
+ @staticmethod
+ def from_affine(point, generator=False):
+ """Create from an affine point.
+
+ :param bool generator: set to True to make the point to precalculate
+ multiplication table - useful for public point when verifying many
+ signatures (around 100 or so) or for generator points of a curve.
+ """
+ return PointJacobi(point.curve(), point.x(), point.y(), 1,
+ point.order(), generator)
+
+ # plese 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
+ # `pow(x, 4, p)`),
+ # multiple assignments at the same time (`x1, x2 = self.x1, self.x2` is
+ # faster than `x1 = self.x1; x2 = self.x2`),
+ # similarly, sometimes the `% p` is skipped if it makes the calculation
+ # faster and the result of calculation is later reduced modulo `p`
+
+ def _double_with_z_1(self, X1, Y1, p, a):
+ """Add a point to itself with z == 1."""
+ # after:
+ # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-mdbl-2007-bl
+ XX, YY = X1 * X1 % p, Y1 * Y1 % p
+ if not YY:
+ return 0, 0, 1
+ YYYY = YY * YY % p
+ S = 2 * ((X1 + YY)**2 - XX - YYYY) % p
+ M = 3 * XX + a
+ T = (M * M - 2 * S) % p
+ # X3 = T
+ Y3 = (M * (S - T) - 8 * YYYY) % p
+ Z3 = 2 * Y1 % p
+ return T, Y3, Z3
+
+ def _double(self, X1, Y1, Z1, p, a):
+ """Add a point to itself, arbitrary z."""
+ if Z1 == 1:
+ return self._double_with_z_1(X1, Y1, p, a)
+ if not Z1:
+ return 0, 0, 1
+ # after:
+ # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl
+ XX, YY = X1 * X1 % p, Y1 * Y1 % p
+ if not YY:
+ return 0, 0, 1
+ YYYY = YY * YY % p
+ ZZ = Z1 * Z1 % p
+ S = 2 * ((X1 + YY)**2 - XX - YYYY) % p
+ M = (3 * XX + a * ZZ * ZZ) % p
+ T = (M * M - 2 * S) % p
+ # X3 = T
+ Y3 = (M * (S - T) - 8 * YYYY) % p
+ Z3 = ((Y1 + Z1)**2 - YY - ZZ) % p
+
+ return T, Y3, Z3
+
+ def double(self):
+ """Add a point to itself."""
+ if not self.__y:
+ return INFINITY
+
+ p, a = self.__curve.p(), self.__curve.a()
+
+ try:
+ self._scale_lock.reader_acquire()
+ X1, Y1, Z1 = self.__x, self.__y, self.__z
+ finally:
+ self._scale_lock.reader_release()
+
+ X3, Y3, Z3 = self._double(X1, Y1, Z1, p, a)
+
+ if not Y3 or not Z3:
+ return INFINITY
+ return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
+
+ def _add_with_z_1(self, X1, Y1, X2, Y2, p):
+ """add points when both Z1 and Z2 equal 1"""
+ # after:
+ # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-mmadd-2007-bl
+ H = X2 - X1
+ HH = H * H
+ I = 4 * HH % p
+ J = H * I
+ r = 2 * (Y2 - Y1)
+ 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
+ Y3 = (r * (V - X3) - 2 * Y1 * J) % p
+ Z3 = 2 * H % p
+ return X3, Y3, Z3
+
+ def _add_with_z_eq(self, X1, Y1, Z1, X2, Y2, p):
+ """add points when Z1 == Z2"""
+ # after:
+ # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-zadd-2007-m
+ A = (X2 - X1)**2 % p
+ B = X1 * A % p
+ C = X2 * A
+ D = (Y2 - Y1)**2 % p
+ if not A and not D:
+ return self._double(X1, Y1, Z1, p, self.__curve.a())
+ X3 = (D - B - C) % p
+ Y3 = ((Y2 - Y1) * (B - X3) - Y1 * (C - B)) % p
+ Z3 = Z1 * (X2 - X1) % p
+ return X3, Y3, Z3
+
+ def _add_with_z2_1(self, X1, Y1, Z1, X2, Y2, p):
+ """add points when Z2 == 1"""
+ # after:
+ # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-madd-2007-bl
+ Z1Z1 = Z1 * Z1 % p
+ U2, S2 = X2 * Z1Z1 % p, Y2 * Z1 * Z1Z1 % p
+ H = (U2 - X1) % p
+ HH = H * H % p
+ I = 4 * HH % p
+ J = H * I
+ r = 2 * (S2 - Y1) % p
+ if not r and not H:
+ return self._double_with_z_1(X2, Y2, p, self.__curve.a())
+ V = X1 * I
+ X3 = (r * r - J - 2 * V) % p
+ Y3 = (r * (V - X3) - 2 * Y1 * J) % p
+ Z3 = ((Z1 + H)**2 - Z1Z1 - HH) % p
+ return X3, Y3, Z3
+
+ def _add_with_z_ne(self, X1, Y1, Z1, X2, Y2, Z2, p):
+ """add points with arbitrary z"""
+ # after:
+ # http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-add-2007-bl
+ Z1Z1 = Z1 * Z1 % p
+ Z2Z2 = Z2 * Z2 % p
+ U1 = X1 * Z2Z2 % p
+ U2 = X2 * Z1Z1 % p
+ S1 = Y1 * Z2 * Z2Z2 % p
+ S2 = Y2 * Z1 * Z1Z1 % p
+ H = U2 - U1
+ I = 4 * H * H % p
+ J = H * I % p
+ r = 2 * (S2 - S1) % p
+ if not H and not r:
+ return self._double(X1, Y1, Z1, p, self.__curve.a())
+ V = U1 * I
+ X3 = (r * r - J - 2 * V) % p
+ Y3 = (r * (V - X3) - 2 * S1 * J) % p
+ Z3 = ((Z1 + Z2)**2 - Z1Z1 - Z2Z2) * H % p
+
+ return X3, Y3, Z3
+
+ def __radd__(self, other):
+ """Add other to self."""
+ return self + other
+
+ def _add(self, X1, Y1, Z1, X2, Y2, Z2, p):
+ """add two points, select fastest method."""
+ if not Y1 or not Z1:
+ return X2, Y2, Z2
+ if not Y2 or not Z2:
+ return X1, Y1, Z1
+ if Z1 == Z2:
+ if Z1 == 1:
+ return self._add_with_z_1(X1, Y1, X2, Y2, p)
+ return self._add_with_z_eq(X1, Y1, Z1, X2, Y2, p)
+ if Z1 == 1:
+ return self._add_with_z2_1(X2, Y2, Z2, X1, Y1, p)
+ if Z2 == 1:
+ return self._add_with_z2_1(X1, Y1, Z1, X2, Y2, p)
+ return self._add_with_z_ne(X1, Y1, Z1, X2, Y2, Z2, p)
+
+ def __add__(self, other):
+ """Add two points on elliptic curve."""
+ if self == INFINITY:
+ return other
+ if other == INFINITY:
+ return self
+ if isinstance(other, Point):
+ other = PointJacobi.from_affine(other)
+ if self.__curve != other.__curve:
+ raise ValueError("The other point is on different curve")
+
+ p = self.__curve.p()
+ try:
+ self._scale_lock.reader_acquire()
+ X1, Y1, Z1 = self.__x, self.__y, self.__z
+ finally:
+ self._scale_lock.reader_release()
+ try:
+ other._scale_lock.reader_acquire()
+ X2, Y2, Z2 = other.__x, other.__y, other.__z
+ finally:
+ other._scale_lock.reader_release()
+ X3, Y3, Z3 = self._add(X1, Y1, Z1, X2, Y2, Z2, p)
+
+ if not Y3 or not Z3:
+ return INFINITY
+ return PointJacobi(self.__curve, X3, Y3, Z3, 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, p = 0, 0, 1, self.__curve.p()
+ _add = self._add
+ for X2, Y2 in self.__precompute:
+ if other % 2:
+ if other % 4 >= 2:
+ other = (other + 1)//2
+ X3, Y3, Z3 = _add(X3, Y3, Z3, X2, -Y2, 1, p)
+ else:
+ other = (other - 1)//2
+ X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, 1, p)
+ else:
+ other //= 2
+
+ if not Y3 or not Z3:
+ 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:
+ return INFINITY
+ if other == 1:
+ return self
+ if self.__order:
+ # order*2 as a protection for Minerva
+ other = other % (self.__order*2)
+ if self.__precompute:
+ return self._mul_precompute(other)
+
+ self = self.scale()
+ # once scaled, point is immutable, not need to lock
+ X2, Y2 = self.__x, self.__y
+ X3, Y3, Z3 = 0, 0, 1
+ p, a = self.__curve.p(), self.__curve.a()
+ _double = self._double
+ _add = self._add
+ # since adding points when at least one of them is scaled
+ # is quicker, reverse the NAF order
+ for i in reversed(self._naf(other)):
+ X3, Y3, Z3 = _double(X3, Y3, Z3, p, a)
+ if i < 0:
+ X3, Y3, Z3 = _add(X3, Y3, Z3, X2, -Y2, 1, p)
+ elif i > 0:
+ X3, Y3, Z3 = _add(X3, Y3, Z3, X2, Y2, 1, p)
+
+ if not Y3 or not Z3:
+ return INFINITY
+
+ return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
+
+ @staticmethod
+ def _leftmost_bit(x):
+ """Return integer with the same magnitude as x but hamming weight of 1"""
+ 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:
+ 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)
+ if self.__precompute and other.__precompute:
+ return self * self_mul + other * other_mul
+
+ if self.__order:
+ 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 = 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).scale()
+ X4, Y4 = both.__x, both.__y
+ _double = self._double
+ _add = self._add
+ while i > 1:
+ 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)
+
+ if not Y3 or not Z3:
+ return INFINITY
+
+ return PointJacobi(self.__curve, X3, Y3, Z3, self.__order)
+
+ def __neg__(self):
+ """Return negated point."""
+ try:
+ self._scale_lock.reader_acquire()
+ return PointJacobi(self.__curve, self.__x, -self.__y, self.__z,
+ self.__order)
+ finally:
+ self._scale_lock.reader_release()
+
+
+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."""
+ def __init__(self, curve, x, y, order=None):
+ """curve, x, y, order; order (optional) is the order of this point."""
+ self.__curve = curve
+ if GMPY:
+ self.__x = x and mpz(x)
+ self.__y = y and mpz(y)
+ self.__order = order and mpz(order)
+ else:
+ self.__x = x
+ self.__y = y
+ self.__order = order
+ # self.curve is allowed to be None only for INFINITY:
+ if self.__curve:
+ assert self.__curve.contains_point(x, y)
+ # for curves with cofactor 1, all points that are on the curve are scalar
+ # multiples of the base point, so performing multiplication is not
+ # necessary to verify that. See Section 3.2.2.1 of SEC 1 v2
+ if curve and curve.cofactor() != 1 and order:
+ assert self * order == INFINITY
+
+ def __eq__(self, other):
+ """Return True if the points are identical, False otherwise."""
+ if isinstance(other, Point):
+ return self.__curve == other.__curve \
+ and self.__x == other.__x \
+ and self.__y == other.__y
+ return NotImplemented
+
+ def __neg__(self):
+ return Point(self.__curve, self.__x, self.__curve.p() - self.__y)
+
+ def __add__(self, other):
+ """Add one point to another point."""
+
+ # X9.62 B.3:
+
+ if not isinstance(other, Point):
+ return NotImplemented
+ if other == INFINITY:
+ return self
+ if self == INFINITY:
+ return other
+ assert self.__curve == other.__curve
+ if self.__x == other.__x:
+ if (self.__y + other.__y) % self.__curve.p() == 0:
+ return INFINITY
+ else:
+ return self.double()
+
+ p = self.__curve.p()
+
+ l = ((other.__y - self.__y) * \
+ numbertheory.inverse_mod(other.__x - self.__x, p)) % p
+
+ x3 = (l * l - self.__x - other.__x) % p
+ y3 = (l * (self.__x - x3) - self.__y) % p
+
+ return Point(self.__curve, x3, y3)
+
+ def __mul__(self, other):
+ """Multiply a point by an integer."""
+
+ def leftmost_bit(x):
+ assert x > 0
+ result = 1
+ while result <= x:
+ result = 2 * result
+ return result // 2
+
+ e = other
+ if e == 0 or (self.__order and e % self.__order == 0):
+ return INFINITY
+ if self == INFINITY:
+ return INFINITY
+ if e < 0:
+ return (-self) * (-e)
+
+ # From X9.62 D.3.2:
+
+ e3 = 3 * e
+ negative_self = Point(self.__curve, self.__x, -self.__y, self.__order)
+ i = leftmost_bit(e3) // 2
+ result = self
+ # print_("Multiplying %s by %d (e3 = %d):" % (self, other, e3))
+ while i > 1:
+ result = result.double()
+ if (e3 & i) != 0 and (e & i) == 0:
+ result = result + self
+ if (e3 & i) == 0 and (e & i) != 0:
+ result = result + negative_self
+ # print_(". . . i = %d, result = %s" % ( i, result ))
+ i = i // 2
+
+ return result
+
+ def __rmul__(self, other):
+ """Multiply a point by an integer."""
+
+ return self * other
+
+ def __str__(self):
+ if self == INFINITY:
+ return "infinity"
+ return "(%d,%d)" % (self.__x, self.__y)
+
+ def double(self):
+ """Return a new point that is twice the old."""
+
+ if self == INFINITY:
+ return INFINITY
+
+ # X9.62 B.3:
+
+ p = self.__curve.p()
+ a = self.__curve.a()
+
+ l = ((3 * self.__x * self.__x + a) * \
+ numbertheory.inverse_mod(2 * self.__y, p)) % p
+
+ x3 = (l * l - 2 * self.__x) % p
+ y3 = (l * (self.__x - x3) - self.__y) % p
+
+ return Point(self.__curve, x3, y3)
+
+ def x(self):
+ return self.__x
+
+ def y(self):
+ return self.__y
+
+ def curve(self):
+ return self.__curve
+
+ def order(self):
+ return self.__order
+
+
+# This one point is the Point At Infinity for all purposes:
+INFINITY = Point(None, None, None)