Source code for pycoin.ecdsa.Generator

import os

from .intstream import from_bytes

from .Curve import Curve
from .Point import Point

from .rfc6979 import deterministic_generate_k


[docs]class Generator(Curve, Point): """ A Generator is a specific point on an elliptic curve that defines a `trapdoor function <https://en.wikipedia.org/wiki/Trapdoor_function>`_ from integers to curve points. :param p: the prime for the :class:`Curve <pycoin.ecdsa.Curve.Curve>` :param a: the a value for the :class:`Curve <pycoin.ecdsa.Curve.Curve>` :param b: the b value for the :class:`Curve <pycoin.ecdsa.Curve.Curve>` :param basis: a :class:`Point <pycoin.ecdsa.Point.Point>` on the given :class:`Curve <pycoin.ecdsa.Curve.Curve>` :param order: the order for the :class:`Curve <pycoin.ecdsa.Curve.Curve>` The constructor raises :class:`NoSuchPointError` if the point is invalid. The point at infinity is ``(x, y) == (None, None)``. """ def __new__(self, p, a, b, basis, order): # since Generator extends tuple (via Point), we need to override __new__ return tuple.__new__(self, basis) def __init__(self, p, a, b, basis, order, entropy_f=os.urandom): """ Set up a group with generator basis for the curve y^2 = x^3 + x*a + b (mod p). The order is the order of the group (it's generally predetermined for a given curve; how it's calculated is complicated). The entropy function creates a blinding factor, to mitigate side channel attacks. """ Curve.__init__(self, p, a, b, order) Point.__init__(self, basis[0], basis[1], self) self._powers = [] Gp = self for _ in range(256): self._powers.append(Gp) Gp += Gp assert p % 4 == 3, "p % 4 must be 3 due to modular_sqrt optimization" self._mod_sqrt_power = (p + 1) // 4 self._blinding_factor = from_bytes(entropy_f(32)) % self._order self._minus_blinding_factor_g = self.raw_mul(-self._blinding_factor)
[docs] def modular_sqrt(self, a): """ :return: n where ``n * n == a (mod p) for the curve's prime p``. If no such n exists, an arbitrary value will be returned. """ return pow(a, self._mod_sqrt_power, self._p)
[docs] def inverse(self, a): ":return: n where ``a * n == 1 (mod p) for the curve's prime p``." return self.inverse_mod(a, self._order)
[docs] def points_for_x(self, x): """ :param: x: an integer x coordinate :return: (p0, p1) where each p is a :class:`Point` with given x coordinate, and p0's y value is even. To get a point with particular parity, use:: points_for_x(x)[1 if is_y_supposed_to_be_odd else 0] """ p = self._p alpha = (pow(x, 3, p) + self._a * x + self._b) % p y0 = self.modular_sqrt(alpha) if y0 == 0: raise ValueError("no y value for %d" % x) p0, p1 = [self.Point(x, _) for _ in (y0, p - y0)] if y0 & 1 == 0: return (p0, p1) return (p1, p0)
[docs] def possible_public_pairs_for_signature(self, value, signature, y_parity=None): """ :param: value: an integer value :param: signature: an ``(r, s)`` pair of integers representing an ecdsa signature of ``value`` :param: y_parity: (optional) for a given value and signature, there are either two points that sign it, or none if the signature is invalid. One of the points has an even y value, the other an odd. If this parameter is set, only points whose y value matches this value will be returned in the list. :return: a list of :class:`Point <pycoin.ecdsa.Point.Point>` objects p where each p is a possible public key for which ``signature`` correctly signs the given ``value``. If something goes wrong, this list will be empty. """ r, s = signature try: points = self.points_for_x(r) except ValueError: return [] if y_parity is not None: if y_parity & 1: points = points[1:] else: points = points[:1] inv_r = self.inverse(r) s_over_r = s * inv_r minus_E_over_r = -(inv_r * value) * self try: return [s_over_r * p + minus_E_over_r for p in points] except ValueError: return []
[docs] def raw_mul(self, e): """ :param: e: an integer value :returns: e * self This method uses a precomputed table as an optimization. """ e %= self._order P = self._infinity for bit in range(256): # add the power of the generator every time to make it more time-deterministic a = [P, P + self._powers[bit]] # choose the correct result P = a[e & 1] e >>= 1 return P
[docs] def __mul__(self, e): """Multiply the generator by an integer. Uses the blinding factor.""" return self.raw_mul(e + self._blinding_factor) + self._minus_blinding_factor_g
def __rmul__(self, e): """Multiply the generator by an integer.""" return self.__mul__(e)
[docs] def verify(self, public_pair, val, sig): """ :param: public_pair: a :class:`Point <pycoin.ecdsa.Point.Point>` on the curve :param: val: an integer value :param: sig: a pair of integers ``(r, s)`` representing an ecdsa signature :returns: True if and only if the signature ``sig`` is a valid signature of ``val`` using ``public_pair`` public key. """ order = self._order if val == 0: return False r, s = sig if r < 1 or r >= order or s < 1 or s >= order: return False s_inverse = self.inverse(s) u1 = val * s_inverse u2 = r * s_inverse point = u1 * self + u2 * self.Point(*public_pair) v = point[0] % order return v == r
[docs] def sign_with_recid(self, secret_exponent, val, gen_k=None): """ :param: secret_exponent: a :class:`Point <pycoin.ecdsa.Point.Point>` on the curve :param: val: an integer value :param: gen_k: a function generating __k values__ :returns: a tuple of integers ``(r, s, recid)`` where ``(r, s)`` represents an ecdsa signature of ``val`` with public key ``self * secret_exponent``; and ``recid`` is the **recovery id**, a number from 0-3 used to eliminate ambiguity about which public key signed the value. If gen_k is set, it will be called with (n, secret_exponent, val), and an unguessable K value should be returned. Otherwise, the default K value, generated according to rfc6979 will be used. """ if val == 0: raise ValueError() if gen_k is None: gen_k = deterministic_generate_k n = self._order k = gen_k(n, secret_exponent, val) while True: p1 = k * self r = p1[0] s = (self.inverse(k) * (val + (secret_exponent * r) % n)) % n if r != 0 and s != 0: recid = p1[1] & 1 if p1[1] > self._p: recid += 2 return r, s, recid k += 1
[docs] def sign(self, secret_exponent, val, gen_k=None): """ :param: secret_exponent: a :class:`Point <pycoin.ecdsa.Point.Point>` on the curve :param: val: an integer value :param: gen_k: a function generating __k values__ :returns: a pair of integers ``(r, s)`` represents an ecdsa signature of ``val`` with public key ``self * secret_exponent``. If gen_k is set, it will be called with (n, secret_exponent, val), and an unguessable K value should be returned. Otherwise, the default K value, generated according to rfc6979 will be used. """ return self.sign_with_recid(secret_exponent, val, gen_k)[0:2]