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