path: root/frozen_deps/ecdsa/ellipticcurve.py

#! /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 __ne__(self, other):
        return not (self == other)

    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._update_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.__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()))

                while i < order:
                    i *= 2
                    doubler = doubler.double().scale()
                    self.__precompute.append((doubler.x(), doubler.y()))

            finally:
                self._update_lock.writer_release()

    def __getstate__(self):
        try:
            self._update_lock.reader_acquire()
            state = self.__dict__.copy()
        finally:
            self._update_lock.reader_release()
        del state["_update_lock"]
        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()
        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()
        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._update_lock.reader_acquire()
            if self.__z == 1:
                return self.__x