1 # -*- coding: utf-8 -*-
4 # Electrum - lightweight Bitcoin client
5 # Copyright (C) 2011 thomasv@gitorious
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.
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.
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/>.
26 from util import print_error
27 from version import SEED_PREFIX
32 sys.exit("Error: python-ecdsa does not seem to be installed. Try 'sudo pip install ecdsa'")
37 sys.exit("Error: AES does not seem to be installed. Try 'sudo pip install slowaes'")
39 ################################## transactions
41 MIN_RELAY_TX_FEE = 1000
45 EncodeAES = lambda secret, s: base64.b64encode(aes.encryptData(secret,s))
46 DecodeAES = lambda secret, e: aes.decryptData(secret, base64.b64decode(e))
49 def pw_encode(s, password):
51 secret = Hash(password)
52 return EncodeAES(secret, s.encode("utf8"))
57 def pw_decode(s, password):
58 if password is not None:
59 secret = Hash(password)
61 d = DecodeAES(secret, s).decode("utf8")
63 raise Exception('Invalid password')
70 return s.decode('hex')[::-1].encode('hex')
73 def int_to_hex(i, length=1):
74 s = hex(i)[2:].rstrip('L')
75 s = "0"*(2*length - len(s)) + s
80 # https://en.bitcoin.it/wiki/Protocol_specification#Variable_length_integer
84 return "fd"+int_to_hex(i,2)
86 return "fe"+int_to_hex(i,4)
88 return "ff"+int_to_hex(i,8)
95 return '4c' + int_to_hex(i)
97 return '4d' + int_to_hex(i,2)
99 return '4e' + int_to_hex(i,4)
103 return hashlib.sha256(x).digest()
107 if type(x) is unicode: x=x.encode('utf-8')
108 return sha256(sha256(x))
111 hash_encode = lambda x: x[::-1].encode('hex')
112 hash_decode = lambda x: x.decode('hex')[::-1]
113 hmac_sha_512 = lambda x,y: hmac.new(x, y, hashlib.sha512).digest()
116 def mnemonic_to_seed(mnemonic, passphrase):
117 from pbkdf2 import PBKDF2
120 return PBKDF2(mnemonic, 'mnemonic' + passphrase, iterations = PBKDF2_ROUNDS, macmodule = hmac, digestmodule = hashlib.sha512).read(64)
123 is_new_seed = lambda x: hmac_sha_512("Seed version", x.encode('utf8')).encode('hex')[0:2].startswith(SEED_PREFIX)
125 def is_old_seed(seed):
127 words = seed.strip().split()
129 mnemonic.mn_decode(words)
130 uses_electrum_words = True
132 uses_electrum_words = False
136 is_hex = (len(seed) == 32)
140 return is_hex or (uses_electrum_words and len(words) == 12)
143 # pywallet openssl private key implementation
145 def i2d_ECPrivateKey(pkey, compressed=False):
147 key = '3081d30201010420' + \
148 '%064x' % pkey.secret + \
149 'a081a53081a2020101302c06072a8648ce3d0101022100' + \
151 '3006040100040107042102' + \
157 key = '308201130201010420' + \
158 '%064x' % pkey.secret + \
159 'a081a53081a2020101302c06072a8648ce3d0101022100' + \
161 '3006040100040107044104' + \
168 return key.decode('hex') + i2o_ECPublicKey(pkey.pubkey, compressed)
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
176 if pubkey.point.y() & 1:
177 key = '03' + '%064x' % pubkey.point.x()
179 key = '02' + '%064x' % pubkey.point.x()
182 '%064x' % pubkey.point.x() + \
183 '%064x' % pubkey.point.y()
185 return key.decode('hex')
187 # end pywallet openssl private key implementation
191 ############ functions from pywallet #####################
193 def hash_160(public_key):
195 md = hashlib.new('ripemd160')
196 md.update(sha256(public_key))
200 md = ripemd.new(sha256(public_key))
204 def public_key_to_bc_address(public_key):
205 h160 = hash_160(public_key)
206 return hash_160_to_bc_address(h160)
208 def hash_160_to_bc_address(h160, addrtype = 0):
209 vh160 = chr(addrtype) + h160
211 addr = vh160 + h[0:4]
212 return b58encode(addr)
214 def bc_address_to_hash_160(addr):
215 bytes = b58decode(addr, 25)
216 return ord(bytes[0]), bytes[1:21]
219 __b58chars = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
220 __b58base = len(__b58chars)
224 """ encode v, which is a string of bytes, to base58."""
227 for (i, c) in enumerate(v[::-1]):
228 long_value += (256**i) * ord(c)
231 while long_value >= __b58base:
232 div, mod = divmod(long_value, __b58base)
233 result = __b58chars[mod] + result
235 result = __b58chars[long_value] + result
237 # Bitcoin does a little leading-zero-compression:
238 # leading 0-bytes in the input become leading-1s
241 if c == '\0': nPad += 1
244 return (__b58chars[0]*nPad) + result
247 def b58decode(v, length):
248 """ decode v into a string of len bytes."""
250 for (i, c) in enumerate(v[::-1]):
251 long_value += __b58chars.find(c) * (__b58base**i)
254 while long_value >= 256:
255 div, mod = divmod(long_value, 256)
256 result = chr(mod) + result
258 result = chr(long_value) + result
262 if c == __b58chars[0]: nPad += 1
265 result = chr(0)*nPad + result
266 if length is not None and len(result) != length:
272 def EncodeBase58Check(vchIn):
274 return b58encode(vchIn + hash[0:4])
277 def DecodeBase58Check(psz):
278 vchRet = b58decode(psz, None)
289 def PrivKeyToSecret(privkey):
290 return privkey[9:9+32]
293 def SecretToASecret(secret, compressed=False, addrtype=0):
294 vchIn = chr((addrtype+128)&255) + secret
295 if compressed: vchIn += '\01'
296 return EncodeBase58Check(vchIn)
298 def ASecretToSecret(key, addrtype=0):
299 vch = DecodeBase58Check(key)
300 if vch and vch[0] == chr((addrtype+128)&255):
305 def regenerate_key(sec):
306 b = ASecretToSecret(sec)
313 def GetPubKey(pubkey, compressed=False):
314 return i2o_ECPublicKey(pubkey, compressed)
317 def GetPrivKey(pkey, compressed=False):
318 return i2d_ECPrivateKey(pkey, compressed)
322 return ('%064x' % pkey.secret).decode('hex')
325 def is_compressed(sec):
326 b = ASecretToSecret(sec)
330 def public_key_from_private_key(sec):
331 # rebuild public key from private key, compressed or uncompressed
332 pkey = regenerate_key(sec)
334 compressed = is_compressed(sec)
335 public_key = GetPubKey(pkey.pubkey, compressed)
336 return public_key.encode('hex')
339 def address_from_private_key(sec):
340 public_key = public_key_from_private_key(sec)
341 address = public_key_to_bc_address(public_key.decode('hex'))
346 return is_address(addr)
349 def is_address(addr):
350 ADDRESS_RE = re.compile('[1-9A-HJ-NP-Za-km-z]{26,}\\Z')
351 if not ADDRESS_RE.match(addr): return False
353 addrtype, h = bc_address_to_hash_160(addr)
356 return addr == hash_160_to_bc_address(h, addrtype)
359 def is_private_key(key):
361 k = ASecretToSecret(key)
362 return k is not False
367 ########### end pywallet functions #######################
370 from ecdsa.ecdsa import curve_secp256k1, generator_secp256k1
372 print "cannot import ecdsa.curve_secp256k1. You probably need to upgrade ecdsa.\nTry: sudo pip install --upgrade ecdsa"
375 from ecdsa.curves import SECP256k1
376 from ecdsa.ellipticcurve import Point
377 from ecdsa.util import string_to_number, number_to_string
379 def msg_magic(message):
380 varint = var_int(len(message))
381 encoded_varint = "".join([chr(int(varint[i:i+2], 16)) for i in xrange(0, len(varint), 2)])
382 return "\x18Bitcoin Signed Message:\n" + encoded_varint + message
385 def verify_message(address, signature, message):
387 EC_KEY.verify_message(address, signature, message)
389 except Exception as e:
390 print_error("Verification error: {0}".format(e))
394 def encrypt_message(message, pubkey):
395 return EC_KEY.encrypt_message(message, pubkey.decode('hex'))
399 return [l[i:i+n] for i in xrange(0, len(l), n)]
402 def ECC_YfromX(x,curved=curve_secp256k1, odd=True):
406 for offset in range(128):
408 My2 = pow(Mx, 3, _p) + _a * pow(Mx, 2, _p) + _b % _p
409 My = pow(My2, (_p+1)/4, _p )
411 if curved.contains_point(Mx,My):
412 if odd == bool(My&1):
414 return [_p-My,offset]
415 raise Exception('ECC_YfromX: No Y found')
418 def negative_point(P):
419 return Point( P.curve(), P.x(), -P.y(), P.order() )
422 def point_to_ser(P, comp=True ):
424 return ( ('%02x'%(2+(P.y()&1)))+('%064x'%P.x()) ).decode('hex')
425 return ( '04'+('%064x'%P.x())+('%064x'%P.y()) ).decode('hex')
428 def ser_to_point(Aser):
429 curve = curve_secp256k1
430 generator = generator_secp256k1
431 _r = generator.order()
432 assert Aser[0] in ['\x02','\x03','\x04']
433 if Aser[0] == '\x04':
434 return Point( curve, string_to_number(Aser[1:33]), string_to_number(Aser[33:]), _r )
435 Mx = string_to_number(Aser[1:])
436 return Point( curve, Mx, ECC_YfromX(Mx, curve, Aser[0]=='\x03')[0], _r )
440 class MyVerifyingKey(ecdsa.VerifyingKey):
442 def from_signature(klass, sig, recid, h, curve):
443 """ See http://www.secg.org/download/aid-780/sec1-v2.pdf, chapter 4.1.6 """
444 from ecdsa import util, numbertheory
446 curveFp = curve.curve
449 # extract r,s from signature
450 r, s = util.sigdecode_string(sig, order)
452 x = r + (recid/2) * order
454 alpha = ( x * x * x + curveFp.a() * x + curveFp.b() ) % curveFp.p()
455 beta = msqr.modular_sqrt(alpha, curveFp.p())
456 y = beta if (beta - recid) % 2 == 0 else curveFp.p() - beta
457 # 1.4 the constructor checks that nR is at infinity
458 R = Point(curveFp, x, y, order)
459 # 1.5 compute e from message:
460 e = string_to_number(h)
462 # 1.6 compute Q = r^-1 (sR - eG)
463 inv_r = numbertheory.inverse_mod(r,order)
464 Q = inv_r * ( s * R + minus_e * G )
465 return klass.from_public_point( Q, curve )
468 class EC_KEY(object):
469 def __init__( self, k ):
470 secret = string_to_number(k)
471 self.pubkey = ecdsa.ecdsa.Public_key( generator_secp256k1, generator_secp256k1 * secret )
472 self.privkey = ecdsa.ecdsa.Private_key( self.pubkey, secret )
475 def get_public_key(self, compressed=True):
476 return point_to_ser(self.pubkey.point, compressed).encode('hex')
478 def sign_message(self, message, compressed, address):
479 private_key = ecdsa.SigningKey.from_secret_exponent( self.secret, curve = SECP256k1 )
480 public_key = private_key.get_verifying_key()
481 signature = private_key.sign_digest_deterministic( Hash( msg_magic(message) ), hashfunc=hashlib.sha256, sigencode = ecdsa.util.sigencode_string )
482 assert public_key.verify_digest( signature, Hash( msg_magic(message) ), sigdecode = ecdsa.util.sigdecode_string)
484 sig = base64.b64encode( chr(27 + i + (4 if compressed else 0)) + signature )
486 self.verify_message( address, sig, message)
491 raise Exception("error: cannot sign message")
495 def verify_message(self, address, signature, message):
496 sig = base64.b64decode(signature)
497 if len(sig) != 65: raise Exception("Wrong encoding")
500 if nV < 27 or nV >= 35:
501 raise Exception("Bad encoding")
509 h = Hash( msg_magic(message) )
510 public_key = MyVerifyingKey.from_signature( sig[1:], recid, h, curve = SECP256k1 )
513 public_key.verify_digest( sig[1:], h, sigdecode = ecdsa.util.sigdecode_string)
515 # check that we get the original signing address
516 addr = public_key_to_bc_address( point_to_ser(public_key.pubkey.point, compressed) )
518 raise Exception("Bad signature")
521 # ecies encryption/decryption methods; aes-256-cbc is used as the cipher; hmac-sha256 is used as the mac
524 def encrypt_message(self, message, pubkey):
526 pk = ser_to_point(pubkey)
527 if not ecdsa.ecdsa.point_is_valid(generator_secp256k1, pk.x(), pk.y()):
528 raise Exception('invalid pubkey')
530 ephemeral_exponent = number_to_string(ecdsa.util.randrange(pow(2,256)), generator_secp256k1.order())
531 ephemeral = EC_KEY(ephemeral_exponent)
533 ecdh_key = (pk * ephemeral.privkey.secret_multiplier).x()
534 ecdh_key = ('%064x' % ecdh_key).decode('hex')
535 key = hashlib.sha512(ecdh_key).digest()
536 key_e, key_m = key[:32], key[32:]
538 iv_ciphertext = aes.encryptData(key_e, message)
540 ephemeral_pubkey = ephemeral.get_public_key(compressed=True).decode('hex')
541 encrypted = 'BIE1' + ephemeral_pubkey + iv_ciphertext
542 mac = hmac.new(key_m, encrypted, hashlib.sha256).digest()
544 return base64.b64encode(encrypted + mac)
547 def decrypt_message(self, encrypted):
549 encrypted = base64.b64decode(encrypted)
551 if len(encrypted) < 85:
552 raise Exception('invalid ciphertext: length')
554 magic = encrypted[:4]
555 ephemeral_pubkey = encrypted[4:37]
556 iv_ciphertext = encrypted[37:-32]
557 mac = encrypted[-32:]
560 raise Exception('invalid ciphertext: invalid magic bytes')
563 ephemeral_pubkey = ser_to_point(ephemeral_pubkey)
564 except AssertionError, e:
565 raise Exception('invalid ciphertext: invalid ephemeral pubkey')
567 if not ecdsa.ecdsa.point_is_valid(generator_secp256k1, ephemeral_pubkey.x(), ephemeral_pubkey.y()):
568 raise Exception('invalid ciphertext: invalid ephemeral pubkey')
570 ecdh_key = (ephemeral_pubkey * self.privkey.secret_multiplier).x()
571 ecdh_key = ('%064x' % ecdh_key).decode('hex')
572 key = hashlib.sha512(ecdh_key).digest()
573 key_e, key_m = key[:32], key[32:]
574 if mac != hmac.new(key_m, encrypted[:-32], hashlib.sha256).digest():
575 raise Exception('invalid ciphertext: invalid mac')
577 return aes.decryptData(key_e, iv_ciphertext)
580 ###################################### BIP32 ##############################
582 random_seed = lambda n: "%032x"%ecdsa.util.randrange( pow(2,n) )
583 BIP32_PRIME = 0x80000000
586 def get_pubkeys_from_secret(secret):
588 private_key = ecdsa.SigningKey.from_string( secret, curve = SECP256k1 )
589 public_key = private_key.get_verifying_key()
590 K = public_key.to_string()
591 K_compressed = GetPubKey(public_key.pubkey,True)
592 return K, K_compressed
595 # Child private key derivation function (from master private key)
596 # k = master private key (32 bytes)
597 # c = master chain code (extra entropy for key derivation) (32 bytes)
598 # n = the index of the key we want to derive. (only 32 bits will be used)
599 # If n is negative (i.e. the 32nd bit is set), the resulting private key's
600 # corresponding public key can NOT be determined without the master private key.
601 # However, if n is positive, the resulting private key's corresponding
602 # public key can be determined without the master private key.
603 def CKD_priv(k, c, n):
604 is_prime = n & BIP32_PRIME
605 return _CKD_priv(k, c, rev_hex(int_to_hex(n,4)).decode('hex'), is_prime)
607 def _CKD_priv(k, c, s, is_prime):
609 from ecdsa.util import string_to_number, number_to_string
610 order = generator_secp256k1.order()
612 cK = GetPubKey(keypair.pubkey,True)
613 data = chr(0) + k + s if is_prime else cK + s
614 I = hmac.new(c, data, hashlib.sha512).digest()
615 k_n = number_to_string( (string_to_number(I[0:32]) + string_to_number(k)) % order , order )
619 # Child public key derivation function (from public key only)
620 # K = master public key
621 # c = master chain code
622 # n = index of key we want to derive
623 # This function allows us to find the nth public key, as long as n is
624 # non-negative. If n is negative, we need the master private key to find it.
625 def CKD_pub(cK, c, n):
626 if n & BIP32_PRIME: raise
627 return _CKD_pub(cK, c, rev_hex(int_to_hex(n,4)).decode('hex'))
629 # helper function, callable with arbitrary string
630 def _CKD_pub(cK, c, s):
632 from ecdsa.util import string_to_number, number_to_string
633 order = generator_secp256k1.order()
634 I = hmac.new(c, cK + s, hashlib.sha512).digest()
636 pubkey_point = string_to_number(I[0:32])*curve.generator + ser_to_point(cK)
637 public_key = ecdsa.VerifyingKey.from_public_point( pubkey_point, curve = SECP256k1 )
639 cK_n = GetPubKey(public_key.pubkey,True)
643 BITCOIN_HEADER_PRIV = "0488ade4"
644 BITCOIN_HEADER_PUB = "0488b21e"
646 TESTNET_HEADER_PRIV = "04358394"
647 TESTNET_HEADER_PUB = "043587cf"
649 BITCOIN_HEADERS = (BITCOIN_HEADER_PUB, BITCOIN_HEADER_PRIV)
650 TESTNET_HEADERS = (TESTNET_HEADER_PUB, TESTNET_HEADER_PRIV)
652 def _get_headers(testnet):
653 """Returns the correct headers for either testnet or bitcoin, in the form
654 of a 2-tuple, like (public, private)."""
656 return TESTNET_HEADERS
658 return BITCOIN_HEADERS
661 def deserialize_xkey(xkey):
663 xkey = DecodeBase58Check(xkey)
664 assert len(xkey) == 78
666 xkey_header = xkey[0:4].encode('hex')
667 # Determine if the key is a bitcoin key or a testnet key.
668 if xkey_header in TESTNET_HEADERS:
669 head = TESTNET_HEADER_PRIV
670 elif xkey_header in BITCOIN_HEADERS:
671 head = BITCOIN_HEADER_PRIV
673 raise Exception("Unknown xkey header: '%s'" % xkey_header)
676 fingerprint = xkey[5:9]
677 child_number = xkey[9:13]
679 if xkey[0:4].encode('hex') == head:
680 K_or_k = xkey[13+33:]
682 K_or_k = xkey[13+32:]
683 return depth, fingerprint, child_number, c, K_or_k
686 def get_xkey_name(xkey, testnet=False):
687 depth, fingerprint, child_number, c, K = deserialize_xkey(xkey)
688 n = int(child_number.encode('hex'), 16)
690 child_id = "%d'"%(n - BIP32_PRIME)
698 raise BaseException("xpub depth error")
701 def xpub_from_xprv(xprv, testnet=False):
702 depth, fingerprint, child_number, c, k = deserialize_xkey(xprv)
703 K, cK = get_pubkeys_from_secret(k)
704 header_pub, _ = _get_headers(testnet)
705 xpub = header_pub.decode('hex') + chr(depth) + fingerprint + child_number + c + cK
706 return EncodeBase58Check(xpub)
709 def bip32_root(seed, testnet=False):
711 header_pub, header_priv = _get_headers(testnet)
712 seed = seed.decode('hex')
713 I = hmac.new("Bitcoin seed", seed, hashlib.sha512).digest()
716 K, cK = get_pubkeys_from_secret(master_k)
717 xprv = (header_priv + "00" + "00000000" + "00000000").decode("hex") + master_c + chr(0) + master_k
718 xpub = (header_pub + "00" + "00000000" + "00000000").decode("hex") + master_c + cK
719 return EncodeBase58Check(xprv), EncodeBase58Check(xpub)
722 def bip32_private_derivation(xprv, branch, sequence, testnet=False):
723 header_pub, header_priv = _get_headers(testnet)
724 depth, fingerprint, child_number, c, k = deserialize_xkey(xprv)
725 assert sequence.startswith(branch)
726 sequence = sequence[len(branch):]
727 for n in sequence.split('/'):
729 i = int(n[:-1]) + BIP32_PRIME if n[-1] == "'" else int(n)
731 k, c = CKD_priv(k, c, i)
734 _, parent_cK = get_pubkeys_from_secret(parent_k)
735 fingerprint = hash_160(parent_cK)[0:4]
736 child_number = ("%08X"%i).decode('hex')
737 K, cK = get_pubkeys_from_secret(k)
738 xprv = header_priv.decode('hex') + chr(depth) + fingerprint + child_number + c + chr(0) + k
739 xpub = header_pub.decode('hex') + chr(depth) + fingerprint + child_number + c + cK
740 return EncodeBase58Check(xprv), EncodeBase58Check(xpub)
743 def bip32_public_derivation(xpub, branch, sequence, testnet=False):
744 header_pub, _ = _get_headers(testnet)
745 depth, fingerprint, child_number, c, cK = deserialize_xkey(xpub)
746 assert sequence.startswith(branch)
747 sequence = sequence[len(branch):]
748 for n in sequence.split('/'):
752 cK, c = CKD_pub(cK, c, i)
755 fingerprint = hash_160(parent_cK)[0:4]
756 child_number = ("%08X"%i).decode('hex')
757 xpub = header_pub.decode('hex') + chr(depth) + fingerprint + child_number + c + cK
758 return EncodeBase58Check(xpub)
761 def bip32_private_key(sequence, k, chain):
763 k, chain = CKD_priv(k, chain, i)
764 return SecretToASecret(k, True)