p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = p-3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
r = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
x = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
y = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5

class CurveFp(object):
  def __init__(self, p, a, b):
    assert 3 == p % 4
    self.__p = p
    self.__a = a
    self.__b = b

  def p(self):
    return self.__p

  def a(self):
    return self.__a

  def b(self):
     return self.__b

  def contains_point(self, x, y):
    return (y * y - (x * x * x + self.__a * x + self.__b)) % self.__p == 0

  def complete_point(self, x):
    y = square_roots(x * x * x + self.__a * x + self.__b, self.__p)
    y = y[0]
    if self.contains_point(x, y):
        return Point(self, x, y)
    else:
        return INFINITY

class Point(object):
  def __init__(self, curve, x, y, order=None):
    self.__curve = curve
    self.__x = x
    self.__y = y
    self.__order = order
    if order:
      assert self * order == INFINITY

  def __add__(self, other):
    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) * 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):
    def leftmost_bit(x):
      assert x > 0
      result = 1L
      while result <= x:
          result = 2 * result
      return result / 2

    e = other
    if self.__order:
        e = e % self.__order
    if e == 0:
        return INFINITY
    if self == INFINITY:
        return INFINITY
    assert e > 0
    e3 = 3 * e
    negative_self = Point(self.__curve, self.__x, -self.__y, self.__order)
    i = leftmost_bit(e3) / 2
    result = self
    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
      i = i / 2
    return result

  def __rmul__(self, other):
    return self * other

  def __str__(self):
    if self == INFINITY:
        return "infinity"
    return "(%d,%d)" % (self.__x, self.__y)

  def double(self):
    if self == INFINITY:
          return INFINITY

    p = self.__curve.p()
    a = self.__curve.a()
    l = ((3 * self.__x * self.__x + a) *
            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

def inverse_mod(a, m):
  if a < 0 or m <= a:
    a = a % m
  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
  assert d == 1
  if ud > 0:
    return ud
  else:
    return ud + m

#square roots for moduli 3 (mod 4)
def square_roots(a, m):
  s = pow(a, (m + 1) / 4, m)
  return s, m - s

INFINITY = Point(None, None, None)

def urandom(size):
  return '\x04'*size; # chosen by fair dice roll
                      # guaranteed to be random

class Signature(object):
  def __init__(self, r, s):
    self.r = r
    self.s = s
  def __str__(self):
    return '(' + str(self.r) + ',' + str(self.s) + ')'

class Public_key(object):
  def __init__(self, generator, point):
    self.curve = generator.curve()
    self.generator = generator
    self.point = point
    n = generator.order()
    if not n:
      raise RuntimeError, "Generator point must have order."

  def verifies(self, hash_digest, signature):
    try:
      G = self.generator
      n = G.order()
      r = signature.r
      s = signature.s
      if r < 1 or r > n-1: return False
      if s < 1 or s > n-1: return False
      c = inverse_mod(s, n)
      u1 = (hash_digest * c) % n
      u2 = (r * c) % n
      xy = u1 * G + u2 * self.point
      v = xy.x() % n
      return v == r
    except:
      return False

  def __str__(self):
    return str(self.point)

class Private_key(object):
  def __init__(self, public_key, secret_multiplier):
    self.public_key = public_key
    self.secret_multiplier = secret_multiplier

  def sign(self, hash_digest, k):
    G = self.public_key.generator
    n = G.order()
    k = k % n
    p1 = k * G
    r = p1.x()
    if r == 0: raise RuntimeError, "amazingly unlucky random number r"
    s = ( inverse_mod(k, n) * (hash_digest + (self.secret_multiplier * r) % n) ) % n
    if s == 0: raise RuntimeError, "amazingly unlucky random number s"
    return Signature(r, s)