fork(1) download
copy 
  1. #! /usr/bin/env python
  2.  
  3.  
  4. class CurveFp( object ):
  5.   def __init__( self, p, a, b ):
  6.     self.__p = p
  7.     self.__a = a
  8.     self.__b = b
  9.  
  10.   def p( self ):
  11.     return self.__p
  12.  
  13.   def a( self ):
  14.     return self.__a
  15.  
  16.   def b( self ):
  17.     return self.__b
  18.  
  19.   def contains_point( self, x, y ):
  20.     return ( y * y - ( x * x * x + self.__a * x + self.__b ) ) % self.__p == 0
  21.  
  22. class Point( object ):
  23.   def __init__( self, curve, x, y, order = None ):
  24.     self.__curve = curve
  25.     self.__x = x
  26.     self.__y = y
  27.     self.__order = order
  28.     if self.__curve: assert self.__curve.contains_point( x, y )
  29.     if order: assert self * order == INFINITY
  30.  
  31.   def __add__( self, other ):
  32.     if other == INFINITY: return self
  33.     if self == INFINITY: return other
  34.     assert self.__curve == other.__curve
  35.     if self.__x == other.__x:
  36.       if ( self.__y + other.__y ) % self.__curve.p() == 0:
  37.         return INFINITY
  38.       else:
  39.         return self.double()
  40.  
  41.     p = self.__curve.p()
  42.     l = ( ( other.__y - self.__y ) * \
  43.           inverse_mod( other.__x - self.__x, p ) ) % p
  44.     x3 = ( l * l - self.__x - other.__x ) % p
  45.     y3 = ( l * ( self.__x - x3 ) - self.__y ) % p
  46.     return Point( self.__curve, x3, y3 )
  47.  
  48.   def __mul__( self, other ):
  49.     def leftmost_bit( x ):
  50.       assert x > 0
  51.       result = 1L
  52.       while result <= x: result = 2 * result
  53.       return result / 2
  54.  
  55.     e = other
  56.     if self.__order: e = e % self.__order
  57.     if e == 0: return INFINITY
  58.     if self == INFINITY: return INFINITY
  59.     assert e > 0
  60.     e3 = 3 * e
  61.     negative_self = Point( self.__curve, self.__x, -self.__y, self.__order )
  62.     i = leftmost_bit( e3 ) / 2
  63.     result = self
  64.     while i > 1:
  65.       result = result.double()
  66.       if ( e3 & i ) != 0 and ( e & i ) == 0: result = result + self
  67.       if ( e3 & i ) == 0 and ( e & i ) != 0: result = result + negative_self
  68.       i = i / 2
  69.     return result
  70.  
  71.   def __rmul__( self, other ):
  72.     return self * other
  73.  
  74.   def __str__( self ):
  75.     if self == INFINITY: return "infinity"
  76.     return "(%d,%d)" % ( self.__x, self.__y )
  77.  
  78.   def double( self ):
  79.     if self == INFINITY:
  80.       return INFINITY
  81.  
  82.     p = self.__curve.p()
  83.     a = self.__curve.a()
  84.     l = ( ( 3 * self.__x * self.__x + a ) * \
  85.           inverse_mod( 2 * self.__y, p ) ) % p
  86.     x3 = ( l * l - 2 * self.__x ) % p
  87.     y3 = ( l * ( self.__x - x3 ) - self.__y ) % p
  88.     return Point( self.__curve, x3, y3 )
  89.  
  90.   def x( self ):
  91.     return self.__x
  92.  
  93.   def y( self ):
  94.     return self.__y
  95.  
  96.   def curve( self ):
  97.     return self.__curve
  98.  
  99.   def order( self ):
  100.     return self.__order
  101.  
  102. INFINITY = Point( None, None, None )
  103.  
  104. def inverse_mod( a, m ):
  105.   if a < 0 or m <= a: a = a % m
  106.   c, d = a, m
  107.   uc, vc, ud, vd = 1, 0, 0, 1
  108.   while c != 0:
  109.     q, c, d = divmod( d, c ) + ( c, )
  110.     uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc
  111.   assert d == 1
  112.   if ud > 0: return ud
  113.   else: return ud + m
  114.  
  115.  
  116. _p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2FL
  117. _r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141L
  118. _b = 0x0000000000000000000000000000000000000000000000000000000000000007L
  119. _a = 0x0000000000000000000000000000000000000000000000000000000000000000L
  120. _Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798L
  121. _Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8L
  122.  
  123. class Signature( object ):
  124.   def __init__( self, r, s ):
  125.     self.r = r
  126.     self.s = s
  127.  
  128. class Public_key( object ):
  129.   def __init__( self, generator, point ):
  130.     self.curve = generator.curve()
  131.     self.generator = generator
  132.     self.point = point
  133.     n = generator.order()
  134.     if not n:
  135.       raise RuntimeError, "Generator point must have order."
  136.     if not n * point == INFINITY:
  137.       raise RuntimeError, "Generator point order is bad."
  138.     if point.x() < 0 or n <= point.x() or point.y() < 0 or n <= point.y():
  139.       raise RuntimeError, "Generator point has x or y out of range."
  140.  
  141.   def verifies( self, hash, signature ):
  142.     G = self.generator
  143.     n = G.order()
  144.     hash = 0xc0e2d0a89a348de88fda08211c70d1d7e52ccef2eb9459911bf977d587784c6e
  145.     r = 0xd47ce4c025c35ec440bc81d99834a624875161a26bf56ef7fdc0f5d52f843ad1
  146.     s = 0x44e1ff2dfd8102cf7a47c21d5c9fd5701610d04953c6836596b4fe9dd2f53e3e
  147.     if r < 1 or r > n-1: return False
  148.     if s < 1 or s > n-1: return False
  149.     c = inverse_mod( s, n )
  150.     u1 = ( hash * c ) % n
  151.     u2 = ( r * c ) % n
  152.     xy = u1 * G + u2 * self.point
  153.     v = xy.x() % n
  154.     return v == r
  155.  
  156.     print(c)
  157.     print(u1)
  158.     print(u2)
  159.     print(xy)
  160.     print(v)
  161.     print(r)
Success #stdin #stdout 0.04s 63888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CGLklH
language:
Python (PyPy 2.7.13)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!