#! /usr/bin/env python
class CurveFp( object ):
def __init__( self, p, a, b ):
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
class Point( object ):
def __init__( self, curve, x, y, order = None ):
self.__curve = curve
self.__x = x
self.__y = y
self.__order = order
if self.__curve: assert self.__curve.contains_point( x, y )
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
INFINITY = Point( None, None, None )
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
_p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2FL
_r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141L
_b = 0x0000000000000000000000000000000000000000000000000000000000000007L
_a = 0x0000000000000000000000000000000000000000000000000000000000000000L
_Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798L
_Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L
class Signature( object ):
def __init__( self, r, s ):
self.r = r
self.s = 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."
if not n * point == INFINITY:
raise RuntimeError, "Generator point order is bad."
if point.x() < 0 or n <= point.x() or point.y() < 0 or n <= point.y():
raise RuntimeError, "Generator point has x or y out of range."
def verifies( self, hash, signature ):
G = self.generator
n = G.order()
hash = 0xc0e2d0a89a348de88fda08211c70d1d7e52ccef2eb9459911bf977d587784c6e
r = 0xd47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1
s = 0x44e1ff2dfd8102cf7a47c21d5c9fd5701610d04953c6836596b4fe9dd2f53e3e
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 * c ) % n
u2 = ( r * c ) % n
xy = u1 * G + u2 * self.point
v = xy.x() % n
print(c)
print(u1)
print(u2)
print(xy)
print(v)
print(r)
IyEgL3Vzci9iaW4vZW52IHB5dGhvbgoKCmNsYXNzIEN1cnZlRnAoIG9iamVjdCApOgogIGRlZiBfX2luaXRfXyggc2VsZiwgcCwgYSwgYiApOgogICAgc2VsZi5fX3AgPSBwCiAgICBzZWxmLl9fYSA9IGEKICAgIHNlbGYuX19iID0gYgoKICBkZWYgcCggc2VsZiApOgogICAgcmV0dXJuIHNlbGYuX19wCgogIGRlZiBhKCBzZWxmICk6CiAgICByZXR1cm4gc2VsZi5fX2EKCiAgZGVmIGIoIHNlbGYgKToKICAgIHJldHVybiBzZWxmLl9fYgoKICBkZWYgY29udGFpbnNfcG9pbnQoIHNlbGYsIHgsIHkgKToKICAgIHJldHVybiAoIHkgKiB5IC0gKCB4ICogeCAqIHggKyBzZWxmLl9fYSAqIHggKyBzZWxmLl9fYiApICkgJSBzZWxmLl9fcCA9PSAwCgpjbGFzcyBQb2ludCggb2JqZWN0ICk6CiAgZGVmIF9faW5pdF9fKCBzZWxmLCBjdXJ2ZSwgeCwgeSwgb3JkZXIgPSBOb25lICk6CiAgICBzZWxmLl9fY3VydmUgPSBjdXJ2ZQogICAgc2VsZi5fX3ggPSB4CiAgICBzZWxmLl9feSA9IHkKICAgIHNlbGYuX19vcmRlciA9IG9yZGVyCiAgICBpZiBzZWxmLl9fY3VydmU6IGFzc2VydCBzZWxmLl9fY3VydmUuY29udGFpbnNfcG9pbnQoIHgsIHkgKQogICAgaWYgb3JkZXI6IGFzc2VydCBzZWxmICogb3JkZXIgPT0gSU5GSU5JVFkKIAogIGRlZiBfX2FkZF9fKCBzZWxmLCBvdGhlciApOgogICAgaWYgb3RoZXIgPT0gSU5GSU5JVFk6IHJldHVybiBzZWxmCiAgICBpZiBzZWxmID09IElORklOSVRZOiByZXR1cm4gb3RoZXIKICAgIGFzc2VydCBzZWxmLl9fY3VydmUgPT0gb3RoZXIuX19jdXJ2ZQogICAgaWYgc2VsZi5fX3ggPT0gb3RoZXIuX194OgogICAgICBpZiAoIHNlbGYuX195ICsgb3RoZXIuX195ICkgJSBzZWxmLl9fY3VydmUucCgpID09IDA6CiAgICAgICAgcmV0dXJuIElORklOSVRZCiAgICAgIGVsc2U6CiAgICAgICAgcmV0dXJuIHNlbGYuZG91YmxlKCkKCiAgICBwID0gc2VsZi5fX2N1cnZlLnAoKQogICAgbCA9ICggKCBvdGhlci5fX3kgLSBzZWxmLl9feSApICogXAogICAgICAgICAgaW52ZXJzZV9tb2QoIG90aGVyLl9feCAtIHNlbGYuX194LCBwICkgKSAlIHAKICAgIHgzID0gKCBsICogbCAtIHNlbGYuX194IC0gb3RoZXIuX194ICkgJSBwCiAgICB5MyA9ICggbCAqICggc2VsZi5fX3ggLSB4MyApIC0gc2VsZi5fX3kgKSAlIHAKICAgIHJldHVybiBQb2ludCggc2VsZi5fX2N1cnZlLCB4MywgeTMgKQoKICBkZWYgX19tdWxfXyggc2VsZiwgb3RoZXIgKToKICAgIGRlZiBsZWZ0bW9zdF9iaXQoIHggKToKICAgICAgYXNzZXJ0IHggPiAwCiAgICAgIHJlc3VsdCA9IDFMCiAgICAgIHdoaWxlIHJlc3VsdCA8PSB4OiByZXN1bHQgPSAyICogcmVzdWx0CiAgICAgIHJldHVybiByZXN1bHQgLyAyCgogICAgZSA9IG90aGVyCiAgICBpZiBzZWxmLl9fb3JkZXI6IGUgPSBlICUgc2VsZi5fX29yZGVyCiAgICBpZiBlID09IDA6IHJldHVybiBJTkZJTklUWQogICAgaWYgc2VsZiA9PSBJTkZJTklUWTogcmV0dXJuIElORklOSVRZCiAgICBhc3NlcnQgZSA+IDAKICAgIGUzID0gMyAqIGUKICAgIG5lZ2F0aXZlX3NlbGYgPSBQb2ludCggc2VsZi5fX2N1cnZlLCBzZWxmLl9feCwgLXNlbGYuX195LCBzZWxmLl9fb3JkZXIgKQogICAgaSA9IGxlZnRtb3N0X2JpdCggZTMgKSAvIDIKICAgIHJlc3VsdCA9IHNlbGYKICAgIHdoaWxlIGkgPiAxOgogICAgICByZXN1bHQgPSByZXN1bHQuZG91YmxlKCkKICAgICAgaWYgKCBlMyAmIGkgKSAhPSAwIGFuZCAoIGUgJiBpICkgPT0gMDogcmVzdWx0ID0gcmVzdWx0ICsgc2VsZgogICAgICBpZiAoIGUzICYgaSApID09IDAgYW5kICggZSAmIGkgKSAhPSAwOiByZXN1bHQgPSByZXN1bHQgKyBuZWdhdGl2ZV9zZWxmCiAgICAgIGkgPSBpIC8gMgogICAgcmV0dXJuIHJlc3VsdAoKICBkZWYgX19ybXVsX18oIHNlbGYsIG90aGVyICk6CiAgICByZXR1cm4gc2VsZiAqIG90aGVyCgogIGRlZiBfX3N0cl9fKCBzZWxmICk6CiAgICBpZiBzZWxmID09IElORklOSVRZOiByZXR1cm4gImluZmluaXR5IgogICAgcmV0dXJuICIoJWQsJWQpIiAlICggc2VsZi5fX3gsIHNlbGYuX195ICkKCiAgZGVmIGRvdWJsZSggc2VsZiApOgogICAgaWYgc2VsZiA9PSBJTkZJTklUWToKICAgICAgcmV0dXJuIElORklOSVRZCgogICAgcCA9IHNlbGYuX19jdXJ2ZS5wKCkKICAgIGEgPSBzZWxmLl9fY3VydmUuYSgpCiAgICBsID0gKCAoIDMgKiBzZWxmLl9feCAqIHNlbGYuX194ICsgYSApICogXAogICAgICAgICAgaW52ZXJzZV9tb2QoIDIgKiBzZWxmLl9feSwgcCApICkgJSBwCiAgICB4MyA9ICggbCAqIGwgLSAyICogc2VsZi5fX3ggKSAlIHAKICAgIHkzID0gKCBsICogKCBzZWxmLl9feCAtIHgzICkgLSBzZWxmLl9feSApICUgcAogICAgcmV0dXJuIFBvaW50KCBzZWxmLl9fY3VydmUsIHgzLCB5MyApCgogIGRlZiB4KCBzZWxmICk6CiAgICByZXR1cm4gc2VsZi5fX3gKCiAgZGVmIHkoIHNlbGYgKToKICAgIHJldHVybiBzZWxmLl9feQoKICBkZWYgY3VydmUoIHNlbGYgKToKICAgIHJldHVybiBzZWxmLl9fY3VydmUKICAKICBkZWYgb3JkZXIoIHNlbGYgKToKICAgIHJldHVybiBzZWxmLl9fb3JkZXIKICAgIApJTkZJTklUWSA9IFBvaW50KCBOb25lLCBOb25lLCBOb25lICkKCmRlZiBpbnZlcnNlX21vZCggYSwgbSApOgogIGlmIGEgPCAwIG9yIG0gPD0gYTogYSA9IGEgJSBtCiAgYywgZCA9IGEsIG0KICB1YywgdmMsIHVkLCB2ZCA9IDEsIDAsIDAsIDEKICB3aGlsZSBjICE9IDA6CiAgICBxLCBjLCBkID0gZGl2bW9kKCBkLCBjICkgKyAoIGMsICkKICAgIHVjLCB2YywgdWQsIHZkID0gdWQgLSBxKnVjLCB2ZCAtIHEqdmMsIHVjLCB2YwogIGFzc2VydCBkID09IDEKICBpZiB1ZCA+IDA6IHJldHVybiB1ZAogIGVsc2U6IHJldHVybiB1ZCArIG0KCgpfcCA9IDB4RkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkVGRkZGRkMyRkwKX3IgPSAweEZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZFQkFBRURDRTZBRjQ4QTAzQkJGRDI1RThDRDAzNjQxNDFMCl9iID0gMHgwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDA3TApfYSA9IDB4MDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMEwKX0d4ID0gMHg3OUJFNjY3RUY5RENCQkFDNTVBMDYyOTVDRTg3MEIwNzAyOUJGQ0RCMkRDRTI4RDk1OUYyODE1QjE2RjgxNzk4TApfR3kgPSAweDQ4M2FkYTc3MjZhM2M0NjU1ZGE0ZmJmYzBlMTEwOGE4ZmQxN2I0NDhhNjg1NTQxOTljNDdkMDhmZmIxMGQ0YjhMCgpjbGFzcyBTaWduYXR1cmUoIG9iamVjdCApOgogIGRlZiBfX2luaXRfXyggc2VsZiwgciwgcyApOgogICAgc2VsZi5yID0gcgogICAgc2VsZi5zID0gcwogICAgCmNsYXNzIFB1YmxpY19rZXkoIG9iamVjdCApOgogIGRlZiBfX2luaXRfXyggc2VsZiwgZ2VuZXJhdG9yLCBwb2ludCApOgogICAgc2VsZi5jdXJ2ZSA9IGdlbmVyYXRvci5jdXJ2ZSgpCiAgICBzZWxmLmdlbmVyYXRvciA9IGdlbmVyYXRvcgogICAgc2VsZi5wb2ludCA9IHBvaW50CiAgICBuID0gZ2VuZXJhdG9yLm9yZGVyKCkKICAgIGlmIG5vdCBuOgogICAgICByYWlzZSBSdW50aW1lRXJyb3IsICJHZW5lcmF0b3IgcG9pbnQgbXVzdCBoYXZlIG9yZGVyLiIKICAgIGlmIG5vdCBuICogcG9pbnQgPT0gSU5GSU5JVFk6CiAgICAgIHJhaXNlIFJ1bnRpbWVFcnJvciwgIkdlbmVyYXRvciBwb2ludCBvcmRlciBpcyBiYWQuIgogICAgaWYgcG9pbnQueCgpIDwgMCBvciBuIDw9IHBvaW50LngoKSBvciBwb2ludC55KCkgPCAwIG9yIG4gPD0gcG9pbnQueSgpOgogICAgICByYWlzZSBSdW50aW1lRXJyb3IsICJHZW5lcmF0b3IgcG9pbnQgaGFzIHggb3IgeSBvdXQgb2YgcmFuZ2UuIgoKICBkZWYgdmVyaWZpZXMoIHNlbGYsIGhhc2gsIHNpZ25hdHVyZSApOgogICAgRyA9IHNlbGYuZ2VuZXJhdG9yCiAgICBuID0gRy5vcmRlcigpCiAgICBoYXNoID0gMHhjMGUyZDBhODlhMzQ4ZGU4OGZkYTA4MjExYzcwZDFkN2U1MmNjZWYyZWI5NDU5OTExYmY5NzdkNTg3Nzg0YzZlCiAgICByID0gMHhkNDdjZTRjMDI1YzM1ZWM0NDBiYzgxZDk5ODM0YTYyNDg3NTE2MWEyNmJmNTZlZjdmZGMwZjVkNTJmODQzYWQxCiAgICBzID0gMHg0NGUxZmYyZGZkODEwMmNmN2E0N2MyMWQ1YzlmZDU3MDE2MTBkMDQ5NTNjNjgzNjU5NmI0ZmU5ZGQyZjUzZTNlCiAgICBpZiByIDwgMSBvciByID4gbi0xOiByZXR1cm4gRmFsc2UKICAgIGlmIHMgPCAxIG9yIHMgPiBuLTE6IHJldHVybiBGYWxzZQogICAgYyA9IGludmVyc2VfbW9kKCBzLCBuICkKICAgIHUxID0gKCBoYXNoICogYyApICUgbgogICAgdTIgPSAoIHIgKiBjICkgJSBuCiAgICB4eSA9IHUxICogRyArIHUyICogc2VsZi5wb2ludAogICAgdiA9IHh5LngoKSAlIG4KCiAgICBwcmludChjKQogICAgcHJpbnQodTEpCiAgICBwcmludCh1MikKICAgIHByaW50KHh5KQogICAgcHJpbnQodikKICAgIHByaW50KHIp