1  """
  2  Arithmetic Expressions
  3  """
  4  import hashlib
  5  import re
  6  
  7  P = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
  8  A = 0
  9  Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
 10  Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
 11  G = (Gx, Gy)
 12  
 13  
 14  def inv(a, n):
 15      """Inversion"""
 16      lm, hm = 1, 0
 17      low, high = a % n, n
 18      while low > 1:
 19          r = high // low
 20          nm, new = hm - lm * r, high - low * r
 21          lm, low, hm, high = nm, new, lm, low
 22      return lm % n
 23  
 24  
 25  def get_code_string(base):
 26      """Returns string according to base value"""
 27      if base == 2:
 28          return b'01'
 29      if base == 10:
 30          return b'0123456789'
 31      if base == 16:
 32          return b'0123456789abcdef'
 33      if base == 58:
 34          return b'123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
 35      if base == 256:
 36          try:
 37              return b''.join([chr(x) for x in range(256)])
 38          except TypeError:
 39              return bytes([x for x in range(256)])
 40  
 41      raise ValueError("Invalid base!")
 42  
 43  
 44  def encode(val, base, minlen=0):
 45      """Returns the encoded string"""
 46      code_string = get_code_string(base)
 47      result = b''
 48      while val > 0:
 49          val, i = divmod(val, base)
 50          result = code_string[i:i + 1] + result
 51      if len(result) < minlen:
 52          result = code_string[0:1] * (minlen - len(result)) + result
 53      return result
 54  
 55  
 56  def decode(string, base):
 57      """Returns the decoded string"""
 58      code_string = get_code_string(base)
 59      result = 0
 60      if base == 16:
 61          string = string.lower()
 62      while string:
 63          result *= base
 64          result += code_string.find(string[0])
 65          string = string[1:]
 66      return result
 67  
 68  
 69  def changebase(string, frm, to, minlen=0):
 70      """Change base of the string"""
 71      return encode(decode(string, frm), to, minlen)
 72  
 73  
 74  def base10_add(a, b):
 75      """Adding the numbers that are of base10"""
 76      # pylint: disable=too-many-function-args
 77      if a is None:
 78          return b[0], b[1]
 79      if b is None:
 80          return a[0], a[1]
 81      if a[0] == b[0]:
 82          if a[1] == b[1]:
 83              return base10_double(a[0], a[1])
 84          return None
 85      m = ((b[1] - a[1]) * inv(b[0] - a[0], P)) % P
 86      x = (m * m - a[0] - b[0]) % P
 87      y = (m * (a[0] - x) - a[1]) % P
 88      return (x, y)
 89  
 90  
 91  def base10_double(a):
 92      """Double the numbers that are of base10"""
 93      if a is None:
 94          return None
 95      m = ((3 * a[0] * a[0] + A) * inv(2 * a[1], P)) % P
 96      x = (m * m - 2 * a[0]) % P
 97      y = (m * (a[0] - x) - a[1]) % P
 98      return (x, y)
 99  
100  
101  def base10_multiply(a, n):
102      """Multiply the numbers that are of base10"""
103      if n == 0:
104          return G
105      if n == 1:
106          return a
107      n, m = divmod(n, 2)
108      if m == 0:
109          return base10_double(base10_multiply(a, n))
110      if m == 1:
111          return base10_add(base10_double(base10_multiply(a, n)), a)
112      return None
113  
114  
115  def hex_to_point(h):
116      """Converting hexadecimal to point value"""
117      return (decode(h[2:66], 16), decode(h[66:], 16))
118  
119  
120  def point_to_hex(p):
121      """Converting point value to hexadecimal"""
122      return b'04' + encode(p[0], 16, 64) + encode(p[1], 16, 64)
123  
124  
125  def multiply(privkey, pubkey):
126      """Multiplying keys"""
127      return point_to_hex(base10_multiply(
128          hex_to_point(pubkey), decode(privkey, 16)))
129  
130  
131  def privtopub(privkey):
132      """Converting key from private to public"""
133      return point_to_hex(base10_multiply(G, decode(privkey, 16)))
134  
135  
136  def add(p1, p2):
137      """Adding two public keys"""
138      if len(p1) == 32:
139          return encode(decode(p1, 16) + decode(p2, 16) % P, 16, 32)
140      return point_to_hex(base10_add(hex_to_point(p1), hex_to_point(p2)))
141  
142  
143  def hash_160(string):
144      """Hashed version of public key"""
145      intermed = hashlib.sha256(string).digest()
146      ripemd160 = hashlib.new('ripemd160')
147      ripemd160.update(intermed)
148      return ripemd160.digest()
149  
150  
151  def dbl_sha256(string):
152      """Double hashing (SHA256)"""
153      return hashlib.sha256(hashlib.sha256(string).digest()).digest()
154  
155  
156  def bin_to_b58check(inp):
157      """Convert binary to base58"""
158      inp_fmtd = '\x00' + inp
159      leadingzbytes = len(re.match('^\x00*', inp_fmtd).group(0))
160      checksum = dbl_sha256(inp_fmtd)[:4]
161      return '1' * leadingzbytes + changebase(inp_fmtd + checksum, 256, 58)
162  
163  
164  def pubkey_to_address(pubkey):
165      """Convert a public key (in hex) to a Bitcoin address"""
166      return bin_to_b58check(hash_160(changebase(pubkey, 16, 256)))