lib/bitcoin.py

   1 # -*- coding: utf-8 -*-
   2 #!/usr/bin/env python
   3 #
   4 # Electrum - lightweight Bitcoin client
   5 # Copyright (C) 2011 thomasv@gitorious
   6 #
   7 # This program is free software: you can redistribute it and/or modify
   8 # it under the terms of the GNU General Public License as published by
   9 # the Free Software Foundation, either version 3 of the License, or
  10 # (at your option) any later version.
  11 #
  12 # This program is distributed in the hope that it will be useful,
  13 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  15 # GNU General Public License for more details.
  16 #
  17 # You should have received a copy of the GNU General Public License
  18 # along with this program. If not, see <http://www.gnu.org/licenses/>.
  19
  20 import hashlib
  21 import base64
  22 import re
  23 import sys
  24 import hmac
  25
  26
  27 try:
  28     import ecdsa
  29 except ImportError:
  30     sys.exit("Error: python-ecdsa does not seem to be installed. Try 'sudo pip install ecdsa'")
  31
  32 try:
  33     import aes
  34 except ImportError:
  35     sys.exit("Error: AES does not seem to be installed. Try 'sudo pip install slowaes'")
  36
  37 try:
  38     import pbkdf2
  39 except ImportError:
  40     sys.exit("Error: pbkdf2 does not seem to be installed. Try 'sudo pip install pbkdf2'")
  41
  42
  43
  44 from util import print_error
  45
  46
  47
  48 # AES encryption
  49 EncodeAES = lambda secret, s: base64.b64encode(aes.encryptData(secret,s))
  50 DecodeAES = lambda secret, e: aes.decryptData(secret, base64.b64decode(e))
  51
  52 def pw_encode(s, password):
  53     if password:
  54         secret = Hash(password)
  55         return EncodeAES(secret, s.encode("utf8"))
  56     else:
  57         return s
  58
  59 def pw_decode(s, password):
  60     if password is not None:
  61         secret = Hash(password)
  62         try:
  63             d = DecodeAES(secret, s).decode("utf8")
  64         except Exception:
  65             raise Exception('Invalid password')
  66         return d
  67     else:
  68         return s
  69
  70
  71
  72
  73
  74 def rev_hex(s):
  75     return s.decode('hex')[::-1].encode('hex')
  76
  77 def int_to_hex(i, length=1):
  78     s = hex(i)[2:].rstrip('L')
  79     s = "0"*(2*length - len(s)) + s
  80     return rev_hex(s)
  81
  82 def var_int(i):
  83     # https://en.bitcoin.it/wiki/Protocol_specification#Variable_length_integer
  84     if i<0xfd:
  85         return int_to_hex(i)
  86     elif i<=0xffff:
  87         return "fd"+int_to_hex(i,2)
  88     elif i<=0xffffffff:
  89         return "fe"+int_to_hex(i,4)
  90     else:
  91         return "ff"+int_to_hex(i,8)
  92
  93 def op_push(i):
  94     if i<0x4c:
  95         return int_to_hex(i)
  96     elif i<0xff:
  97         return '4c' + int_to_hex(i)
  98     elif i<0xffff:
  99         return '4d' + int_to_hex(i,2)
 100     else:
 101         return '4e' + int_to_hex(i,4)
 102
 103
 104
 105 def sha256(x):
 106     return hashlib.sha256(x).digest()
 107
 108 def Hash(x):
 109     if type(x) is unicode: x=x.encode('utf-8')
 110     return sha256(sha256(x))
 111
 112 hash_encode = lambda x: x[::-1].encode('hex')
 113 hash_decode = lambda x: x.decode('hex')[::-1]
 114 hmac_sha_512 = lambda x,y: hmac.new(x, y, hashlib.sha512).digest()
 115
 116 def mnemonic_to_seed(mnemonic, passphrase):
 117     from pbkdf2 import PBKDF2
 118     import hmac
 119     PBKDF2_ROUNDS = 2048
 120     return PBKDF2(mnemonic, 'mnemonic' + passphrase, iterations = PBKDF2_ROUNDS, macmodule = hmac, digestmodule = hashlib.sha512).read(64)
 121
 122 from version import SEED_PREFIX
 123 is_new_seed = lambda x: hmac_sha_512("Seed version", x.encode('utf8')).encode('hex')[0:2].startswith(SEED_PREFIX)
 124
 125 def is_old_seed(seed):
 126     import mnemonic
 127     words = seed.strip().split()
 128     try:
 129         mnemonic.mn_decode(words)
 130         uses_electrum_words = True
 131     except Exception:
 132         uses_electrum_words = False
 133
 134     try:
 135         seed.decode('hex')
 136         is_hex = (len(seed) == 32)
 137     except Exception:
 138         is_hex = False
 139
 140     return is_hex or (uses_electrum_words and len(words) == 12)
 141
 142
 143 # pywallet openssl private key implementation
 144
 145 def i2d_ECPrivateKey(pkey, compressed=False):
 146     if compressed:
 147         key = '3081d30201010420' + \
 148               '%064x' % pkey.secret + \
 149               'a081a53081a2020101302c06072a8648ce3d0101022100' + \
 150               '%064x' % _p + \
 151               '3006040100040107042102' + \
 152               '%064x' % _Gx + \
 153               '022100' + \
 154               '%064x' % _r + \
 155               '020101a124032200'
 156     else:
 157         key = '308201130201010420' + \
 158               '%064x' % pkey.secret + \
 159               'a081a53081a2020101302c06072a8648ce3d0101022100' + \
 160               '%064x' % _p + \
 161               '3006040100040107044104' + \
 162               '%064x' % _Gx + \
 163               '%064x' % _Gy + \
 164               '022100' + \
 165               '%064x' % _r + \
 166               '020101a144034200'
 167
 168     return key.decode('hex') + i2o_ECPublicKey(pkey.pubkey, compressed)
 169
 170 def i2o_ECPublicKey(pubkey, compressed=False):
 171     # public keys are 65 bytes long (520 bits)
 172     # 0x04 + 32-byte X-coordinate + 32-byte Y-coordinate
 173     # 0x00 = point at infinity, 0x02 and 0x03 = compressed, 0x04 = uncompressed
 174     # compressed keys: <sign> <x> where <sign> is 0x02 if y is even and 0x03 if y is odd
 175     if compressed:
 176         if pubkey.point.y() & 1:
 177             key = '03' + '%064x' % pubkey.point.x()
 178         else:
 179             key = '02' + '%064x' % pubkey.point.x()
 180     else:
 181         key = '04' + \
 182               '%064x' % pubkey.point.x() + \
 183               '%064x' % pubkey.point.y()
 184
 185     return key.decode('hex')
 186
 187 # end pywallet openssl private key implementation
 188
 189
 190
 191 ############ functions from pywallet #####################
 192
 193 def hash_160(public_key):
 194     try:
 195         md = hashlib.new('ripemd160')
 196         md.update(sha256(public_key))
 197         return md.digest()
 198     except Exception:
 199         import ripemd
 200         md = ripemd.new(sha256(public_key))
 201         return md.digest()
 202
 203
 204 def public_key_to_bc_address(public_key):
 205     h160 = hash_160(public_key)
 206     return hash_160_to_bc_address(h160)
 207
 208 def hash_160_to_bc_address(h160, addrtype = 0):
 209     vh160 = chr(addrtype) + h160
 210     h = Hash(vh160)
 211     addr = vh160 + h[0:4]
 212     return b58encode(addr)
 213
 214 def bc_address_to_hash_160(addr):
 215     bytes = b58decode(addr, 25)
 216     return ord(bytes[0]), bytes[1:21]
 217
 218
 219 __b58chars = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
 220 __b58base = len(__b58chars)
 221
 222 def b58encode(v):
 223     """ encode v, which is a string of bytes, to base58."""
 224
 225     long_value = 0L
 226     for (i, c) in enumerate(v[::-1]):
 227         long_value += (256**i) * ord(c)
 228
 229     result = ''
 230     while long_value >= __b58base:
 231         div, mod = divmod(long_value, __b58base)
 232         result = __b58chars[mod] + result
 233         long_value = div
 234     result = __b58chars[long_value] + result
 235
 236     # Bitcoin does a little leading-zero-compression:
 237     # leading 0-bytes in the input become leading-1s
 238     nPad = 0
 239     for c in v:
 240         if c == '\0': nPad += 1
 241         else: break
 242
 243     return (__b58chars[0]*nPad) + result
 244
 245 def b58decode(v, length):
 246     """ decode v into a string of len bytes."""
 247     long_value = 0L
 248     for (i, c) in enumerate(v[::-1]):
 249         long_value += __b58chars.find(c) * (__b58base**i)
 250
 251     result = ''
 252     while long_value >= 256:
 253         div, mod = divmod(long_value, 256)
 254         result = chr(mod) + result
 255         long_value = div
 256     result = chr(long_value) + result
 257
 258     nPad = 0
 259     for c in v:
 260         if c == __b58chars[0]: nPad += 1
 261         else: break
 262
 263     result = chr(0)*nPad + result
 264     if length is not None and len(result) != length:
 265         return None
 266
 267     return result
 268
 269
 270 def EncodeBase58Check(vchIn):
 271     hash = Hash(vchIn)
 272     return b58encode(vchIn + hash[0:4])
 273
 274 def DecodeBase58Check(psz):
 275     vchRet = b58decode(psz, None)
 276     key = vchRet[0:-4]
 277     csum = vchRet[-4:]
 278     hash = Hash(key)
 279     cs32 = hash[0:4]
 280     if cs32 != csum:
 281         return None
 282     else:
 283         return key
 284
 285 def PrivKeyToSecret(privkey):
 286     return privkey[9:9+32]
 287
 288 def SecretToASecret(secret, compressed=False, addrtype=0):
 289     vchIn = chr((addrtype+128)&255) + secret
 290     if compressed: vchIn += '\01'
 291     return EncodeBase58Check(vchIn)
 292
 293 def ASecretToSecret(key, addrtype=0):
 294     vch = DecodeBase58Check(key)
 295     if vch and vch[0] == chr((addrtype+128)&255):
 296         return vch[1:]
 297     else:
 298         return False
 299
 300 def regenerate_key(sec):
 301     b = ASecretToSecret(sec)
 302     if not b:
 303         return False
 304     b = b[0:32]
 305     return EC_KEY(b)
 306
 307 def GetPubKey(pubkey, compressed=False):
 308     return i2o_ECPublicKey(pubkey, compressed)
 309
 310 def GetPrivKey(pkey, compressed=False):
 311     return i2d_ECPrivateKey(pkey, compressed)
 312
 313 def GetSecret(pkey):
 314     return ('%064x' % pkey.secret).decode('hex')
 315
 316 def is_compressed(sec):
 317     b = ASecretToSecret(sec)
 318     return len(b) == 33
 319
 320
 321 def public_key_from_private_key(sec):
 322     # rebuild public key from private key, compressed or uncompressed
 323     pkey = regenerate_key(sec)
 324     assert pkey
 325     compressed = is_compressed(sec)
 326     public_key = GetPubKey(pkey.pubkey, compressed)
 327     return public_key.encode('hex')
 328
 329
 330 def address_from_private_key(sec):
 331     public_key = public_key_from_private_key(sec)
 332     address = public_key_to_bc_address(public_key.decode('hex'))
 333     return address
 334
 335
 336 def is_valid(addr):
 337     return is_address(addr)
 338
 339
 340 def is_address(addr):
 341     ADDRESS_RE = re.compile('[1-9A-HJ-NP-Za-km-z]{26,}\\Z')
 342     if not ADDRESS_RE.match(addr): return False
 343     try:
 344         addrtype, h = bc_address_to_hash_160(addr)
 345     except Exception:
 346         return False
 347     return addr == hash_160_to_bc_address(h, addrtype)
 348
 349
 350 def is_private_key(key):
 351     try:
 352         k = ASecretToSecret(key)
 353         return k is not False
 354     except:
 355         return False
 356
 357
 358 ########### end pywallet functions #######################
 359
 360 try:
 361     from ecdsa.ecdsa import curve_secp256k1, generator_secp256k1
 362 except Exception:
 363     print "cannot import ecdsa.curve_secp256k1. You probably need to upgrade ecdsa.\nTry: sudo pip install --upgrade ecdsa"
 364     exit()
 365
 366 from ecdsa.curves import SECP256k1
 367 from ecdsa.ellipticcurve import Point
 368 from ecdsa.util import string_to_number, number_to_string
 369
 370 def msg_magic(message):
 371     varint = var_int(len(message))
 372     encoded_varint = "".join([chr(int(varint[i:i+2], 16)) for i in xrange(0, len(varint), 2)])
 373     return "\x18Bitcoin Signed Message:\n" + encoded_varint + message
 374
 375
 376 def verify_message(address, signature, message):
 377     try:
 378         EC_KEY.verify_message(address, signature, message)
 379         return True
 380     except Exception as e:
 381         print_error("Verification error: {0}".format(e))
 382         return False
 383
 384
 385 def encrypt_message(message, pubkey):
 386     return EC_KEY.encrypt_message(message, pubkey.decode('hex'))
 387
 388
 389 def chunks(l, n):
 390     return [l[i:i+n] for i in xrange(0, len(l), n)]
 391
 392
 393 def ECC_YfromX(x,curved=curve_secp256k1, odd=True):
 394     _p = curved.p()
 395     _a = curved.a()
 396     _b = curved.b()
 397     for offset in range(128):
 398         Mx = x + offset
 399         My2 = pow(Mx, 3, _p) + _a * pow(Mx, 2, _p) + _b % _p
 400         My = pow(My2, (_p+1)/4, _p )
 401
 402         if curved.contains_point(Mx,My):
 403             if odd == bool(My&1):
 404                 return [My,offset]
 405             return [_p-My,offset]
 406     raise Exception('ECC_YfromX: No Y found')
 407
 408
 409 def negative_point(P):
 410     return Point( P.curve(), P.x(), -P.y(), P.order() )
 411
 412
 413 def point_to_ser(P, comp=True ):
 414     if comp:
 415         return ( ('%02x'%(2+(P.y()&1)))+('%064x'%P.x()) ).decode('hex')
 416     return ( '04'+('%064x'%P.x())+('%064x'%P.y()) ).decode('hex')
 417
 418
 419 def ser_to_point(Aser):
 420     curve = curve_secp256k1
 421     generator = generator_secp256k1
 422     _r  = generator.order()
 423     assert Aser[0] in ['\x02','\x03','\x04']
 424     if Aser[0] == '\x04':
 425         return Point( curve, string_to_number(Aser[1:33]), string_to_number(Aser[33:]), _r )
 426     Mx = string_to_number(Aser[1:])
 427     return Point( curve, Mx, ECC_YfromX(Mx, curve, Aser[0]=='\x03')[0], _r )
 428
 429
 430
 431 class MyVerifyingKey(ecdsa.VerifyingKey):
 432     @classmethod
 433     def from_signature(klass, sig, recid, h, curve):
 434         """ See http://www.secg.org/download/aid-780/sec1-v2.pdf, chapter 4.1.6 """
 435         from ecdsa import util, numbertheory
 436         import msqr
 437         curveFp = curve.curve
 438         G = curve.generator
 439         order = G.order()
 440         # extract r,s from signature
 441         r, s = util.sigdecode_string(sig, order)
 442         # 1.1
 443         x = r + (recid/2) * order
 444         # 1.3
 445         alpha = ( x * x * x  + curveFp.a() * x + curveFp.b() ) % curveFp.p()
 446         beta = msqr.modular_sqrt(alpha, curveFp.p())
 447         y = beta if (beta - recid) % 2 == 0 else curveFp.p() - beta
 448         # 1.4 the constructor checks that nR is at infinity
 449         R = Point(curveFp, x, y, order)
 450         # 1.5 compute e from message:
 451         e = string_to_number(h)
 452         minus_e = -e % order
 453         # 1.6 compute Q = r^-1 (sR - eG)
 454         inv_r = numbertheory.inverse_mod(r,order)
 455         Q = inv_r * ( s * R + minus_e * G )
 456         return klass.from_public_point( Q, curve )
 457
 458
 459 class EC_KEY(object):
 460     def __init__( self, k ):
 461         secret = string_to_number(k)
 462         self.pubkey = ecdsa.ecdsa.Public_key( generator_secp256k1, generator_secp256k1 * secret )
 463         self.privkey = ecdsa.ecdsa.Private_key( self.pubkey, secret )
 464         self.secret = secret
 465
 466     def get_public_key(self, compressed=True):
 467         return point_to_ser(self.pubkey.point, compressed).encode('hex')
 468
 469     def sign_message(self, message, compressed, address):
 470         private_key = ecdsa.SigningKey.from_secret_exponent( self.secret, curve = SECP256k1 )
 471         public_key = private_key.get_verifying_key()
 472         signature = private_key.sign_digest_deterministic( Hash( msg_magic(message) ), hashfunc=hashlib.sha256, sigencode = ecdsa.util.sigencode_string )
 473         assert public_key.verify_digest( signature, Hash( msg_magic(message) ), sigdecode = ecdsa.util.sigdecode_string)
 474         for i in range(4):
 475             sig = base64.b64encode( chr(27 + i + (4 if compressed else 0)) + signature )
 476             try:
 477                 self.verify_message( address, sig, message)
 478                 return sig
 479             except Exception:
 480                 continue
 481         else:
 482             raise Exception("error: cannot sign message")
 483
 484
 485     @classmethod
 486     def verify_message(self, address, signature, message):
 487         sig = base64.b64decode(signature)
 488         if len(sig) != 65: raise Exception("Wrong encoding")
 489
 490         nV = ord(sig[0])
 491         if nV < 27 or nV >= 35:
 492             raise Exception("Bad encoding")
 493         if nV >= 31:
 494             compressed = True
 495             nV -= 4
 496         else:
 497             compressed = False
 498
 499         recid = nV - 27
 500         h = Hash( msg_magic(message) )
 501         public_key = MyVerifyingKey.from_signature( sig[1:], recid, h, curve = SECP256k1 )
 502
 503         # check public key
 504         public_key.verify_digest( sig[1:], h, sigdecode = ecdsa.util.sigdecode_string)
 505
 506         # check that we get the original signing address
 507         addr = public_key_to_bc_address( point_to_ser(public_key.pubkey.point, compressed) )
 508         if address != addr:
 509             raise Exception("Bad signature")
 510
 511
 512     # ecies encryption/decryption methods; aes-256-cbc is used as the cipher; hmac-sha256 is used as the mac
 513
 514     @classmethod
 515     def encrypt_message(self, message, pubkey):
 516
 517         pk = ser_to_point(pubkey)
 518         if not ecdsa.ecdsa.point_is_valid(generator_secp256k1, pk.x(), pk.y()):
 519             raise Exception('invalid pubkey')
 520
 521         ephemeral_exponent = number_to_string(ecdsa.util.randrange(pow(2,256)), generator_secp256k1.order())
 522         ephemeral = EC_KEY(ephemeral_exponent)
 523
 524         ecdh_key = (pk * ephemeral.privkey.secret_multiplier).x()
 525         ecdh_key = ('%064x' % ecdh_key).decode('hex')
 526         key = hashlib.sha512(ecdh_key).digest()
 527         key_e, key_m = key[:32], key[32:]
 528
 529         iv_ciphertext = aes.encryptData(key_e, message)
 530
 531         ephemeral_pubkey = ephemeral.get_public_key(compressed=True).decode('hex')
 532         encrypted = 'BIE1' + ephemeral_pubkey + iv_ciphertext
 533         mac = hmac.new(key_m, encrypted, hashlib.sha256).digest()
 534
 535         return base64.b64encode(encrypted + mac)
 536
 537
 538     def decrypt_message(self, encrypted):
 539
 540         encrypted = base64.b64decode(encrypted)
 541
 542         if len(encrypted) < 85:
 543             raise Exception('invalid ciphertext: length')
 544
 545         magic = encrypted[:4]
 546         ephemeral_pubkey = encrypted[4:37]
 547         iv_ciphertext = encrypted[37:-32]
 548         mac = encrypted[-32:]
 549
 550         if magic != 'BIE1':
 551             raise Exception('invalid ciphertext: invalid magic bytes')
 552
 553         try:
 554             ephemeral_pubkey = ser_to_point(ephemeral_pubkey)
 555         except AssertionError, e:
 556             raise Exception('invalid ciphertext: invalid ephemeral pubkey')
 557
 558         if not ecdsa.ecdsa.point_is_valid(generator_secp256k1, ephemeral_pubkey.x(), ephemeral_pubkey.y()):
 559             raise Exception('invalid ciphertext: invalid ephemeral pubkey')
 560
 561         ecdh_key = (ephemeral_pubkey * self.privkey.secret_multiplier).x()
 562         ecdh_key = ('%064x' % ecdh_key).decode('hex')
 563         key = hashlib.sha512(ecdh_key).digest()
 564         key_e, key_m = key[:32], key[32:]
 565         if mac != hmac.new(key_m, encrypted[:-32], hashlib.sha256).digest():
 566             raise Exception('invalid ciphertext: invalid mac')
 567
 568         return aes.decryptData(key_e, iv_ciphertext)
 569
 570
 571 ###################################### BIP32 ##############################
 572
 573 random_seed = lambda n: "%032x"%ecdsa.util.randrange( pow(2,n) )
 574 BIP32_PRIME = 0x80000000
 575
 576
 577 def get_pubkeys_from_secret(secret):
 578     # public key
 579     private_key = ecdsa.SigningKey.from_string( secret, curve = SECP256k1 )
 580     public_key = private_key.get_verifying_key()
 581     K = public_key.to_string()
 582     K_compressed = GetPubKey(public_key.pubkey,True)
 583     return K, K_compressed
 584
 585
 586 # Child private key derivation function (from master private key)
 587 # k = master private key (32 bytes)
 588 # c = master chain code (extra entropy for key derivation) (32 bytes)
 589 # n = the index of the key we want to derive. (only 32 bits will be used)
 590 # If n is negative (i.e. the 32nd bit is set), the resulting private key's
 591 #  corresponding public key can NOT be determined without the master private key.
 592 # However, if n is positive, the resulting private key's corresponding
 593 #  public key can be determined without the master private key.
 594 def CKD_priv(k, c, n):
 595     is_prime = n & BIP32_PRIME
 596     return _CKD_priv(k, c, rev_hex(int_to_hex(n,4)).decode('hex'), is_prime)
 597
 598 def _CKD_priv(k, c, s, is_prime):
 599     import hmac
 600     from ecdsa.util import string_to_number, number_to_string
 601     order = generator_secp256k1.order()
 602     keypair = EC_KEY(k)
 603     cK = GetPubKey(keypair.pubkey,True)
 604     data = chr(0) + k + s if is_prime else cK + s
 605     I = hmac.new(c, data, hashlib.sha512).digest()
 606     k_n = number_to_string( (string_to_number(I[0:32]) + string_to_number(k)) % order , order )
 607     c_n = I[32:]
 608     return k_n, c_n
 609
 610 # Child public key derivation function (from public key only)
 611 # K = master public key
 612 # c = master chain code
 613 # n = index of key we want to derive
 614 # This function allows us to find the nth public key, as long as n is
 615 #  non-negative. If n is negative, we need the master private key to find it.
 616 def CKD_pub(cK, c, n):
 617     if n & BIP32_PRIME: raise
 618     return _CKD_pub(cK, c, rev_hex(int_to_hex(n,4)).decode('hex'))
 619
 620 # helper function, callable with arbitrary string
 621 def _CKD_pub(cK, c, s):
 622     import hmac
 623     from ecdsa.util import string_to_number, number_to_string
 624     order = generator_secp256k1.order()
 625     I = hmac.new(c, cK + s, hashlib.sha512).digest()
 626     curve = SECP256k1
 627     pubkey_point = string_to_number(I[0:32])*curve.generator + ser_to_point(cK)
 628     public_key = ecdsa.VerifyingKey.from_public_point( pubkey_point, curve = SECP256k1 )
 629     c_n = I[32:]
 630     cK_n = GetPubKey(public_key.pubkey,True)
 631     return cK_n, c_n
 632
 633
 634
 635 def deserialize_xkey(xkey):
 636     xkey = DecodeBase58Check(xkey)
 637     assert len(xkey) == 78
 638     assert xkey[0:4].encode('hex') in ["0488ade4", "0488b21e"]
 639     depth = ord(xkey[4])
 640     fingerprint = xkey[5:9]
 641     child_number = xkey[9:13]
 642     c = xkey[13:13+32]
 643     if xkey[0:4].encode('hex') == "0488ade4":
 644         K_or_k = xkey[13+33:]
 645     else:
 646         K_or_k = xkey[13+32:]
 647     return depth, fingerprint, child_number, c, K_or_k
 648
 649
 650
 651 def bip32_root(seed):
 652     import hmac
 653     seed = seed.decode('hex')
 654     I = hmac.new("Bitcoin seed", seed, hashlib.sha512).digest()
 655     master_k = I[0:32]
 656     master_c = I[32:]
 657     K, cK = get_pubkeys_from_secret(master_k)
 658     xprv = ("0488ADE4" + "00" + "00000000" + "00000000").decode("hex") + master_c + chr(0) + master_k
 659     xpub = ("0488B21E" + "00" + "00000000" + "00000000").decode("hex") + master_c + cK
 660     return EncodeBase58Check(xprv), EncodeBase58Check(xpub)
 661
 662
 663
 664 def bip32_private_derivation(xprv, branch, sequence):
 665     depth, fingerprint, child_number, c, k = deserialize_xkey(xprv)
 666     assert sequence.startswith(branch)
 667     sequence = sequence[len(branch):]
 668     for n in sequence.split('/'):
 669         if n == '': continue
 670         i = int(n[:-1]) + BIP32_PRIME if n[-1] == "'" else int(n)
 671         parent_k = k
 672         k, c = CKD_priv(k, c, i)
 673         depth += 1
 674
 675     _, parent_cK = get_pubkeys_from_secret(parent_k)
 676     fingerprint = hash_160(parent_cK)[0:4]
 677     child_number = ("%08X"%i).decode('hex')
 678     K, cK = get_pubkeys_from_secret(k)
 679     xprv = "0488ADE4".decode('hex') + chr(depth) + fingerprint + child_number + c + chr(0) + k
 680     xpub = "0488B21E".decode('hex') + chr(depth) + fingerprint + child_number + c + cK
 681     return EncodeBase58Check(xprv), EncodeBase58Check(xpub)
 682
 683
 684
 685 def bip32_public_derivation(xpub, branch, sequence):
 686     depth, fingerprint, child_number, c, cK = deserialize_xkey(xpub)
 687     assert sequence.startswith(branch)
 688     sequence = sequence[len(branch):]
 689     for n in sequence.split('/'):
 690         if n == '': continue
 691         i = int(n)
 692         parent_cK = cK
 693         cK, c = CKD_pub(cK, c, i)
 694         depth += 1
 695
 696     fingerprint = hash_160(parent_cK)[0:4]
 697     child_number = ("%08X"%i).decode('hex')
 698     xpub = "0488B21E".decode('hex') + chr(depth) + fingerprint + child_number + c + cK
 699     return EncodeBase58Check(xpub)
 700
 701
 702
 703
 704 def bip32_private_key(sequence, k, chain):
 705     for i in sequence:
 706         k, chain = CKD_priv(k, chain, i)
 707     return SecretToASecret(k, True)
 708
 709
 710
 711
 712 ################################## transactions
 713
 714 MIN_RELAY_TX_FEE = 1000
 715
 716
 717
 718 import unittest
 719 class Test_bitcoin(unittest.TestCase):
 720
 721     def test_crypto(self):
 722         for message in ["Chancellor on brink of second bailout for banks", chr(255)*512]:
 723             self.do_test_crypto(message)
 724
 725     def do_test_crypto(self, message):
 726         G = generator_secp256k1
 727         _r  = G.order()
 728         pvk = ecdsa.util.randrange( pow(2,256) ) %_r
 729
 730         Pub = pvk*G
 731         pubkey_c = point_to_ser(Pub,True)
 732         pubkey_u = point_to_ser(Pub,False)
 733         addr_c = public_key_to_bc_address(pubkey_c)
 734         addr_u = public_key_to_bc_address(pubkey_u)
 735
 736         #print "Private key            ", '%064x'%pvk
 737         eck = EC_KEY(number_to_string(pvk,_r))
 738
 739         #print "Compressed public key  ", pubkey_c.encode('hex')
 740         enc = EC_KEY.encrypt_message(message, pubkey_c)
 741         dec = eck.decrypt_message(enc)
 742         assert dec == message
 743
 744         #print "Uncompressed public key", pubkey_u.encode('hex')
 745         enc2 = EC_KEY.encrypt_message(message, pubkey_u)
 746         dec2 = eck.decrypt_message(enc)
 747         assert dec2 == message
 748
 749         signature = eck.sign_message(message, True, addr_c)
 750         #print signature
 751         EC_KEY.verify_message(addr_c, signature, message)
 752
 753
 754
 755     def test_bip32(self):
 756         # see https://en.bitcoin.it/wiki/BIP_0032_TestVectors
 757         xpub, xprv = self.do_test_bip32("000102030405060708090a0b0c0d0e0f", "m/0'/1/2'/2/1000000000")
 758         assert xpub == "xpub6H1LXWLaKsWFhvm6RVpEL9P4KfRZSW7abD2ttkWP3SSQvnyA8FSVqNTEcYFgJS2UaFcxupHiYkro49S8yGasTvXEYBVPamhGW6cFJodrTHy"
 759         assert xprv == "xprvA41z7zogVVwxVSgdKUHDy1SKmdb533PjDz7J6N6mV6uS3ze1ai8FHa8kmHScGpWmj4WggLyQjgPie1rFSruoUihUZREPSL39UNdE3BBDu76"
 760
 761         xpub, xprv = self.do_test_bip32("fffcf9f6f3f0edeae7e4e1dedbd8d5d2cfccc9c6c3c0bdbab7b4b1aeaba8a5a29f9c999693908d8a8784817e7b7875726f6c696663605d5a5754514e4b484542","m/0/2147483647'/1/2147483646'/2")
 762         assert xpub == "xpub6FnCn6nSzZAw5Tw7cgR9bi15UV96gLZhjDstkXXxvCLsUXBGXPdSnLFbdpq8p9HmGsApME5hQTZ3emM2rnY5agb9rXpVGyy3bdW6EEgAtqt"
 763         assert xprv == "xprvA2nrNbFZABcdryreWet9Ea4LvTJcGsqrMzxHx98MMrotbir7yrKCEXw7nadnHM8Dq38EGfSh6dqA9QWTyefMLEcBYJUuekgW4BYPJcr9E7j"
 764
 765
 766     def do_test_bip32(self, seed, sequence):
 767         xprv, xpub = bip32_root(seed)
 768         assert sequence[0:2] == "m/"
 769         path = 'm'
 770         sequence = sequence[2:]
 771         for n in sequence.split('/'):
 772             child_path = path + '/' + n
 773             if n[-1] != "'":
 774                 xpub2 = bip32_public_derivation(xpub, path, child_path)
 775             xprv, xpub = bip32_private_derivation(xprv, path, child_path)
 776             if n[-1] != "'":
 777                 assert xpub == xpub2
 778             path = child_path
 779
 780         return xpub, xprv
 781
 782
 783     def test_aes(self):
 784         s = u'\u66f4\u7a33\u5b9a\u7684\u4ea4\u6613\u5e73\u53f0'
 785         self.do_test_aes(s, s)
 786
 787     def do_test_aes(self, s, p):
 788         enc = pw_encode(s, p)
 789         dec = pw_decode(enc, p)
 790         assert dec == s
 791
 792
 793 if __name__ == "__main__":
 794     unittest.main()