Source code for pycoin.ecdsa.Curve

# Adapted from code written in 2005 by Peter Pearson and placed in the public domain.

from .Point import Point

def _leftmost_bit(x):
    # this is closer to constant time than bit-twiddling hacks like those in
    assert x > 0
    result = 1
    while result <= x:
        result <<= 1
    return result >> 1

[docs]class Curve(object): """ This class implements an `Elliptic curve <>`_ intended for use in `Elliptic curve cryptography <>`_ An elliptic curve ``EC<p, a, b>`` for a (usually large) prime p and integers a and b is a `group <>`_. The members of the group are (x, y) points (where x and y are integers over the field of integers modulo p) that satisfy the relation ``y**2 = x**3 + a*x + b (mod p)``. There is a group operation ``+`` and an extra point known as the "point at infinity" thrown in to act as the identity for the group. The group operation is a truly marvelous property of this construct, a description of which this margin is too narrow to contain, so please refer to the links above for more information. :param p: a prime :param a: an integer coefficient :param b: an integer constant :param order: (optional) the order of the group made up by the points on the curve. Any point on the curve times the order is the identity for this group (the point at infinity). Although this is optional, it's required for some operations. """ def __init__(self, p, a, b, order=None): """ """ self._p = p self._a = a self._b = b self._order = order self._infinity = Point(None, None, self)
[docs] def p(self): """ :returns: the prime modulus of the curve. """ return self._p
[docs] def order(self): """ :returns: the order of the curve. """ return self._order
[docs] def infinity(self): """:returns: the "point at infinity" (also known as 0, or the identity).""" return self._infinity
[docs] def contains_point(self, x, y): """ :param x: x coordinate of a point :param y: y coordinate of a point :returns: True if the point (x, y) is on the curve, False otherwise """ if x is None and y is None: return True return (y * y - (x * x * x + self._a * x + self._b)) % self._p == 0
[docs] def add(self, p0, p1): """ :param p0: a point :param p1: a point :returns: the sum of the two points """ p = self._p infinity = self._infinity if p0 == infinity: return p1 if p1 == infinity: return p0 x0, y0 = p0 x1, y1 = p1 if (x0 - x1) % p == 0: if (y0 + y1) % p == 0: return infinity else: slope = ((3 * x0 * x0 + self._a) * self.inverse_mod(2 * y0, p)) % p else: slope = ((y1 - y0) * self.inverse_mod(x1 - x0, p)) % p x3 = (slope * slope - x0 - x1) % p y3 = (slope * (x0 - x3) - y0) % p return self.Point(x3, y3)
[docs] def multiply(self, p, e): """ multiply a point by an integer. :param p: a point :param e: an integer :returns: the result, equivalent to adding p to itself e times """ if self._order: e %= self._order if p == self._infinity or e == 0: return self._infinity e3 = 3 * e i = _leftmost_bit(e3) >> 1 result = p while i > 1: result += result if (e3 & i): v = [result, result+p] else: v = [result-p, result] result = v[0 if (e & i) else 1] i >>= 1 return result
[docs] def inverse_mod(self, a, m): """ :param a: an integer :param m: another integer :returns: the value ``b`` such that ``a * b == 1 (mod m)`` """ if a < 0 or m <= a: a = a % m # From Ferguson and Schneier, roughly: c, d = a, m uc, vc, ud, vd = 1, 0, 0, 1 while c != 0: q, c, d = divmod(d, c) + (c,) uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc # At this point, d is the GCD, and ud*a+vd*m = d. # If d == 1, this means that ud is a inverse. assert d == 1 if ud > 0: return ud else: return ud + m
[docs] def Point(self, x, y): """ :returns: a :class:`Point <.Point>` object with coordinates ``(x, y)`` """ return Point(x, y, self)
def __repr__(self): return '{}({!r},{!r},{!r})'.format(self.__class__.__name__, self._p, self._a, self._b) def __str__(self): return 'y^2 = x^3 + {}*x + {} (mod {})'.format(self._a, self._b, self._p)