Subscribed unsubscribe Subscribe Subscribe

Bitcoin blog

Essence of Bitcoin is innovation that may be related to remittance and asset holding rights and liberation and freedom

Encrypted Private Keys

Overview
BIP0038 propose standerd specification that encrypting private key by passphrase and encode in Base58Chack.Even in situation where the key is exposed,It will be able to save to safe backup media and transfer between wallets.When performing the encryption must know the passphrase.


f:id:adrenaline2017:20170505134751j:plain


Encryption steps
1. Calculate address(ASCII),and take the first 4 bytes of SHA256 double hash

2. Generate key from the passphrase using scrypt.passphrase encoded in UTF-8 and normalize using Unicode Normalization Form C(NFC)
※n=16384, r=8, p=8, length=64(n, r, p are provisional)

3. Split the key(64 bytes) in half,and call them derivedhalf1 and derivedhalf2

4. Do AES256Encrypt, call the 16-byte result "encryptedhalf1,2"

5. Encode concatenation of the following using Base58check
※0x01 0x42 + 0xC0(flagbyte) + salt + encryptedhalf1 + encryptedhalf2
※When case of non-EC-multiplied keys without compression


Encryption code

def encrypt(privkeyhex, addr, passphrase):
    a = bytes(addr, 'ascii')
    salt = hashlib.sha256(hashlib.sha256(a).digest()).digest()[0:4]
    key = scrypt.scrypt(bytes(passphrase, "utf-8"), salt, 16384, 8, 8)
    derived_half1, derived_half2 = key[:32], key[32:]
    aes = AES.new(derived_half2)
    encrypted_half1 = _encrypt_xor(privkeyhex[:32], derived_half1[:16], aes)
    encrypted_half2 = _encrypt_xor(privkeyhex[32:], derived_half1[16:], aes)
    payload = (b'\x01' + b'\x42' + b'\xc0' +
               salt + encrypted_half1 + encrypted_half2)
    checksum = hashlib.sha256(hashlib.sha256(payload).digest()).digest()[:4]
    privatkey = hexlify(payload + checksum).decode('ascii')
    return Base58(privatkey)

def encrypt(privkeyhex, addr, passphrase):
→When privkeyhex wif format,Please convert "wif" to "normal"
→The value of "addr" use to be generated from "privkeyhex"

a = bytes(addr, 'ascii')
→Calculate address(ASCII)

salt = hashlib.sha256(hashlib.sha256(a).digest()).digest()[0:4]
→Take the first 4 bytes of SHA256 double hash

key = scrypt.scrypt(bytes(passphrase, "utf-8"), salt, 16384, 8, 8)
→Generate key from the passphrase using scrypt

derived_half1, derived_half2 = key[:32], key[32:]
→Split the key in half,first half call to "derivedhalf1" and latter half "derivedhalf2"

aes = AES.new(derived_half2)
AES calculation useing python module(AES.new)

encrypted_half1 = _encrypt_xor(privkeyhex[:32], derived_half1[:16], aes)
→Do AES256Encrypt,use first half of privkeyhex(32byte) and 16byte of derived_half1.
※About"_encrypt_xor" see here

payload = (b'\x01' + b'\x42' + b'\xc0' + salt + encrypted_half1 + encrypted_half2)
→0x01 0x42 + flagbyte + salt + encryptedhalf1 + encryptedhalf2

Generate encrypted private key is the Base58Check-encode the above concatenation.


Decryption steps
1. Use encrypted private key and passphrase

2. Derive derivedhalf1 and derivedhalf2 by passing the passphrase and addresshash into scrypt function

3. Decrypt encryptedhalf1 and encryptedhalf2 using AES256Decrypt

4. Merge them to form the encrypted private key


Decryption code

def decrypt(encrypted_privkey, passphrase):
    d = unhexlify(base58decode(encrypted_privkey))
    d = d[2:]   
    flagbyte = d[0:1]
    d = d[1:]
    salt = d[0:4]
    d = d[4:-4]
    key = scrypt.scrypt(bytes(passphrase, "utf-8"), salt, 16384, 8, 8)
    derivedhalf1 = key[0:32]
    derivedhalf2 = key[32:64]
    encryptedhalf1 = d[0:16]
    encryptedhalf2 = d[16:32]
    aes = AES.new(derivedhalf2)
    decryptedhalf2 = aes.decrypt(encryptedhalf2)
    decryptedhalf1 = aes.decrypt(encryptedhalf1)
    privraw = decryptedhalf1 + decryptedhalf2
    privraw = ('4x' % (int(hexlify(privraw), 16) ^
                          int(hexlify(derivedhalf1), 16)))
    return privraw

def decrypt(encrypted_privkey, passphrase):
→Use encrypted private key and passphrase

d = unhexlify(base58decode(encrypted_privkey))
→Decode encrypted private key by Base58Check
→Binary data representing a character string in hexadecimal notation

d = d[1:]
→get payload

d = d[4:-4]
→Encrypted_half1 + encrypted_half2(last 4 bytes is checksum,so cut out)

derivedhalf1 = key[0:32]
→Derive derivedhalf1 and derivedhalf2 by passing the passphrase and addresshash into scrypt function

decryptedhalf1 = aes.decrypt(encryptedhalf1)
→Decrypt encryptedhalf1 using AES256Decrypt

Merge them to form the encrypted private key


The code is used in this article,it have posted on GitHub.

Hierarchical Deterministic Wallets

Oveview
The type is leading-edge deterministic wallets that are described in BIP 0032.Just have to copy root-seed,You can restore overall HD wallet,backup of millions keys or HD wallet , and export.
It can generate public key without users have exposure to private key.In other words,possible to generate in independent environments,private key will be able to storage in safe place.


f:id:adrenaline2017:20170410133107j:plain


Generate HD wallets from seed
1.Secure pseudo-random number generator generate to Root Seed(128-256 bits)

2.Root Seed(512bit) is generated using PBKDF2(key extended function)from seed(128-256bits)

3.Hash value is calculated from Root Seed by using HMAC-SHA512

4.Left half of hash become 'Master private key',and right half of hash become 'Master chain code'

5.The generate method of master public key is exactly the same method which was introduced in past articles(using ECDSA to private key)

f:id:adrenaline2017:20170412093735j:plain


Master private key & Master chain code

def bip32_master_key(seed):
    I = hmac.new(bytes("Bitcoin seed", 'utf-8'), seed, hashlib.sha512).digest()

    vbytes = b'\x04\x88\xAD\xE4'
    depth = 0
    fingerprint = b'\x00\x00\x00\x00'
    i = b'\x00\x00\x00\x00'
    chaincode = encode(decode(I[32:], 256), 256, 32)
    keydata = b'\x00'+(I[:32]+b'\x01')[:-1]

    bindata = vbytes + bytes([depth % 256]) + fingerprint + i + chaincode + keydata
    string=bindata+hashlib.sha256(hashlib.sha256(bindata).digest()).digest()[:4]
    return encode(decode(string, 256), 58, 0)

bip32_masterprivatekey = bip32_master_key(privatekey)

def bip32_master_key(seed):
→"seed" use Root seed(512bit)

I = hmac.new(bytes("Bitcoin seed", 'utf-8'), seed, hashlib.sha512).digest()
→Calculate of Hmac use Python module ※showing 1 to 3 of above procedure

chaincode = encode(decode(I[32:], 256), 256, 32)
→Generate master chain code

bindata = vbytes + bytes([depth % 256]) + fingerprint + i + chaincode + keydata
→Encode by Base58chack for sum ① to ⑥
①vbytes(Prefix of private key defined by BIP32)
②depth(Derived path depth)
③fingerprin(Connection with parents)
④i(Key index)
⑤chaincode(Master chaincode)
⑥keydata(Master private key)
※The value is 0 for initial state about ② to ④

string=bindata+hashlib.sha256(hashlib.sha256(bindata).digest()).digest()
→Behind bin data add checksum generate to Master private key.


Master public key

def bip32_master_public_key(rawtuple):
    dbin = encode(decode(rawtuple, 58), 256, 0)
    
    vbytes = dbin[0:4]
    depth = dbin[4]
    fingerprint = dbin[5:9]
    i = dbin[9:13]
    chaincode = dbin[13:45]
    key = dbin[46:78]+b'\x01'
    newvbytes = b'\x04\x88\xB2\x1E'
     
    pub = fast_multiply(G, decode(key[:32], 256))
    keydata = bytes([2+(pub[1] % 2)]) + encode(pub[0], 256, 32)
    
    bindata = newvbytes + bytes([depth % 256]) + fingerprint + i + chaincode + keydata
    return encode(decode((bindata+hashlib.sha256(hashlib.sha256(bindata).digest()).digest()[:4]), 256), 58, 0)

bip32_masterpublickey = bip32_master_public_key(bip32_masterprivatekey)

dbin = encode(decode(rawtuple, 58), 256, 0)
→Convert hex to byte data of 256-hex,It contains the following information.
①dbin[0:4]:vbytes(4byte)
②dbin[4]:depth(1byte)
③dbin[5:9]:fingerprint(4byte)
④dbin[9:13]:i(4byte)
⑤dbin[13:45]:chain code(33byte)
⑥dbin[46:78]:key(33byte)

pub = fast_multiply(G, privkey)
→Use ECDSA to private key

keydata = bytes([2+(pub[1] % 2)]) + encode(pub[0], 256, 32)
→Generate compressed public key

bindata = newvbytes + bytes([depth % 256]) + fingerprint + i + chaincode + keydata
→Add edited data from ① to ⑥

encode(decode((bindata+hashlib.sha256(hashlib.sha256(bindata)...
→It encode by Base58chack


Address

def pubkey_to_address(pubkey):
    dbin = encode(decode(pubkey, 58), 256, 0)
    key = dbin[45:78]
    return bin_to_b58check(bin_hash160(key))

bip32_address = pubkey_to_address(bip32_masterpublickey)

Generate process of address is exactly the same previous method.
As noteworthy,the key data Included in Master public key is not start from 46-byte but 45-byte.

※The code is used in this article,it have posted on GitHub.


Derivation of child private key
Deterministic Wallets created child key from parent key using "Child key derivation (CKD)" functions.

1.Parent Public Key(264-bit) is generated from Parent Private Key(256-bit: uncompressed key)

2.Hash the below combination in HMAC-SHA 512
Parent Public Key(264-bit), Parent Chain Code(256-bit), Index number(32-bit)

3.Hashed value of left half is child private key,and other half is child chain code(256-bits)

f:id:adrenaline2017:20170412135512j:plain

def bip32_ckd_prv(data, i = int(i)):
    dbin = encode(decode(data, 58), 256, 0)
    vbytes = dbin[0:4]
    depth = dbin[4] + 1
    chaincode = dbin[13:45]
    key = dbin[46:78]+b'\x01'
    fingerprint = bin_hash160(privkey_to_pubkey(key))[:4]
    keyindex = encode(i, 256, 4)
    I = hmac.new(chaincode, privkey_to_pubkey(key)+ encode(i, 256, 4), hashlib.sha512).digest()
    chaincode = encode(decode(I[32:], 256), 256, 32)
    newkey = encode((decode((I[:32]+B'\x01')[:32], 256) + decode(key[:32], 256)) % N, 256, 32)+b'\x01'
    newkey = b'\x00'+newkey[:-1]
    
    bindata = vbytes + bytes([depth % 256]) + fingerprint + keyindex + chaincode + newkey
    return encode(decode(bindata+ hashlib.sha256(hashlib.sha256(bindata).digest()).digest()[:4], 256), 58, 0)

print(bip32_ckd_prv(bip32_masterprivatekey, 1))

depth = dbin[4] + 1
→The depth of the derived path is deepened only one

key = dbin[46:78]+b'\x01'
→Private key add suffix 0x01 when WIF-compressed format

I = hmac.new(chaincode, privkey_to_pubkey(key)...
→HMAC hashed to parent public key and parent chain Code and key index

newkey = encode((decode((I[:32]+B'\x01')[:32]...
→Child private key is derived from add front half of hash to parente private key

bindata = vbytes + bytes([depth % 256])...
→prefix + depth + fingerprint + i + chaincode + keydata


Derivation of child public key
Hierarchical Deterministic Wallets have very useful characteristics that can generate child public key from a parent public key without using a private key.

1.Hash the below combination in HMAC-SHA 512
Parent Public Key(264-bit), Parent Chain Code(256-bit), Index number(32-bit)

2.Hashed value of left half is child public key,and other half is child chain code(256-bits)

f:id:adrenaline2017:20170428142049j:plain

def bip32_ckd(data, i = int(i)):
    dbin = encode(decode(data, 58), 256, 0)
    vbytes = dbin[0:4]
    depth = dbin[4] + 1
    key = dbin[45:78]
    fingerprint = bin_hash160(key)[:4]
    i = encode(i, 256, 4)
    chaincode = dbin[13:45]
    I = hmac.new(chaincode, key + i, hashlib.sha512).digest()
    chaincode = encode(decode(I[32:], 256), 256, 32)
    pub = decode_pubkey(privkey_to_pubkey(I[:32]))
    keydata = add_pubkeys(bytes([2+((pub)[1] % 2)]) + encode((pub)[0], 256, 32), key)
    
    bindata = vbytes + bytes([depth % 256]) + fingerprint + i + chaincode + keydata
    string = bindata+hashlib.sha256(hashlib.sha256(bindata).digest()).digest()[:4]
    return encode(decode(string, 256), 58, 0)        

ckd_publickey  = bip32_ckd(bip32_masterpublickey, 1)

pub = decode_pubkey(privkey_to_pubkey(I[:32]))
→Compressed public key is derived, it use to calculate x and y coordinate

keydata = add_pubkeys(bytes([2+((pub)[1] % 2)]) + encode((pub)[0], 256, 32), key)
→On jacobian coordinate,Add x coordinate and prefix(2 or 3) to Master public key

Add suffix(first 4byte) of double hashed bindata to bindata,it encode by chack58encode.


hardened derivation
Hardened derivation pubkey is generated child chain code using parent privkey instead of parent pubkey,destroy relationship between pubkey and child chain code.
Nomal derivation fanction use index for 2 to 2^32-1(0x80000000 to 0xFFFFFFFF),Hardened derivation function use 0 to 2^31 -1(0x0 to 0x7FFFFFFF).

Why destory relationship?
Method of generating branch of pubkey from extended pubkey has potential risk.
Because extended pubkey is included in chain code,if single child privkey leak out become all child privkey leak out.

f:id:adrenaline2017:20170428184433j:plain


Extended key
Extended private key(parent privkey + chain code)
It possible to generate child privkey and child pubkey.
Expanded privkey can create complete branch root.
Prefix become "xprv"

xprv9tyUQV64JT5qs3RSTJkXCWKMyUgoQp7F3hA1xzG6...

Extended public key(parent pubkey + chain code)
It possible to generate child pubkey.
Expand privkey can create branch of pubkey only.
Prefix become "xpub"

xpub67xpozcx8pe95XVuZLHXZeG6XWXHpGq6Qv5cmNfi...


The code is used in this article,it have posted on Github.


HD wallet path
The key of HD wallet is determined uniquely using "pass".
Tree hierarchies are separated by slashes.
" ' " indicates that hardened derivation is used.
" m " shows that is generated private key from master privkey.
" M " is generated public key from master public key.

f:id:adrenaline2017:20170503131156j:plain


HD wallet tree
Parent extended key can generate child key of 4 billion,
however data move to other wallet, takes an enormous amount of time.
Two BIP0043 and BIP0044 proposing for this problem solution.

BIP0043/BIP0044
BIP0043 proposed the first level of BIP32 tree structure to be used as "purpose".
By extending this BIP, BIP 0044 defines the number "44 '" representing t "purpose" based on BIP 0043.
The first layer is " m / 44 ' / " and "44” show number of purpose.
It means that wallet adapt construction of BIP0044.
BIP0044 aim to improve Wallet's compatibility by unifying rules.

m / purpose' / coin_type' / account' / change / address_index

purpose :Become "44" at all time

coin_type' :Kinds of coin(if Bitcoin"m/44'/0' " or Litecoin's "m/44'/2'")

account' :Multiple accounts number(i)

charge :HD wallet has two subtree("1" is receive address, other is charge address)

address_index:It is generated from HD wallet as child of charge.

f:id:adrenaline2017:20170503131750j:plain

Mnemonic code

Overview
Mnemonic code is English words representing random numbers used as Wallet master keys.
Passphrase is easy to remember for human beings(passphrase 12 to 24 words).
Mnemonic is used to regenerate the seed (master key), regenerating wallet and all keys from this seed.


mnemonic code example

ten enable powder skull spot volume tragic search engage faculty tag pencil 
crowd record business same pudding bulb swear pony blush noise divert typical 


Flow
1.Generate entropy of 128 bits to 256 bits
2.Get the first 4 bits of SHA 256 hash of random array(=checksum)
3.Add this checksum to the end of the random array
4.Divide this array into 11 bit portions
5.Use as an index of 2048 predetermined English word dictionaries
6.Generate 12 to 24 English words representing mnemonic code


Code
1.Generate entropy

from random import choice
from binascii import hexlify

for i in range(10):
    data = ''.join(chr(choice(range(0, 256))) for _ in range(8 * (i % 3 + 2)))
    data = data.encode('latin1')
    h = (hexlify(data))
    print(h.decode('utf8'))

data = ''.join(chr(choice(range(0, 256))) for _ in range(8 * (i % 3 + 2)))
→Random Unicode of 16,24,36bytes

data = data.encode('latin1')
→Encode roman font

h = (hexlify(data))
→Convert to hexadecimal

(h.decode('utf8'))
→Decode to utf-8


2.Generate English word dictionaries

#Reading to list of mnemonic code 
with open('english.txt', 'r') as f:
    wordlist = [w.strip() for w in f.readlines()]
    print(wordlist)

with open('english.txt', 'r') as f:
→Read predetermined dictionary of 2048 English words

wordlist = [w.strip() for w in f.readlines()]
→List of 2048 English words

※Please refer to this english.txt.


3.Generate mnemonic code word

def to_mnemonic(self, data):
        h = hashlib.sha256(data).hexdigest()
        b = bin(int(binascii.hexlify(data), 16))[2:].zfill(len(data) * 8) + \
            bin(int(h, 16))[2:].zfill(256)[:len(data) * 8 // 32]
        result = []
        
        for i in range(len(b) // 11):
            idx = int(b[i * 11:(i + 1) * 11], 2)
            result.append(self.wordlist[idx])
        result_phrase = ' '.join(result)
        return result_phrase

h = hashlib.sha256(data).hexdigest()
→Get SHA 256 hash of random array

bin(int(h, 16))[2:].zfill(256)[:len(data) * 8 // 32]
→Get the first 4 bits of SHA 256 hash of random array(checksum)

bin(int(binascii.hexlify(data), 16))[2:].zfill(len(data) * 8) + bin(int(h, 16))[2:].zfill(256)[:len(data) * 8 // 32]
→Add this checksum to the end of the random array

for i in range(len(b) // 11)
→Divide this array into 11 bit portions

idx = int(b[i * 11:(i + 1) * 11], 2)result.append(self.wordlist[idx])
→Generate 12 to 24 English words representing mnemonic code.


Seed
Seed (512 bits) is generated by using key extension function(PBKDF2) from mnemonic code.
The resulting seed is used to generate deterministic wallet and all keys.

def normalize_string(txt):
        if isinstance(txt, bytes):
            utxt = txt.decode('utf8')
        elif isinstance(txt, str):
            utxt = txt
        else:
            raise TypeError("String value expected")
        return unicodedata.normalize('NFKD', utxt)

def to_seed(mnemonic, passphrase=''):
        mnemonic = normalize_string(mnemonic)
        passphrase = normalize_string(passphrase)
        return PBKDF2(mnemonic, u'mnemonic' + passphrase, iterations=2048,
                      macmodule=hmac, digestmodule=hashlib.sha512).read(64)

def normalize_string(txt):
→Decode with utf-8 when text equal byte format
Unicode normalization(Normalization form compatibility decomposition)

PBKDF2(mnemonic, u'mnemonic' + passphrase, iterations=2048,macmodule=hmac, digestmodule=hashlib.sha512).read(64)
→PBKDF2 iterate hash function(hmac) thousands of times.by so doing, trying to spend time on brute force attack.
→pasword, pasward+slat(short string), iteration, macmodule, digestmodle


The code is used in this article,it have posted on GitHub.

Remove all ads