Extended Keys

require 'openssl' # HMAC
require 'ecdsa'   # sudo gem install ecdsa

# ----
# Seed
# ----
seed = "67f93560761e20617de26e0cb84f7234aaf373ed2e66295c3d7397e6d7ebe882ea396d5d293808b0defd7edd2babd4c091ad942e6a9351e6d075a29d4df872af"
puts "seed: #{seed}"
puts

# --------------------
# Generate Master Keys
# --------------------
# seed
# |
# m

# HMAC
hmac = OpenSSL::HMAC.hexdigest(OpenSSL::Digest::SHA512.new, "Bitcoin seed", [seed].pack("H*")) # digest, key, data
master_private_key = hmac[0..63] # left side of digest
master_chain_code = hmac[64..-1] # right side of digest

# > The SHA512-HMAC function is reused because it is already part of the standard elsewhere, but it takes a key in addition to the data being hashed.
# As the key can be arbitrary, we opted to use to make sure the key derivation was Bitcoin-specific. -- Pieter Wuille

# Get Public Key (multiply generator point by private key)
master_public_key = ECDSA::Group::Secp256k1.generator.multiply_by_scalar(master_private_key.to_i(16)) # multiply generator point by private key
master_public_key = ECDSA::Format::PointOctetString.encode(master_public_key, compression: true).unpack("H*")[0] # encode to compressed public key format

puts "master_chain_code:  #{master_chain_code}"  #=> 463223aac10fb13f291a1bc76bc26003d98da661cb76df61e750c139826dea8b
puts "master_private_key: #{master_private_key}" #=> f79bb0d317b310b261a55a8ab393b4c8a1aba6fa4d08aef379caba502d5d67f9
puts "master_public_key:  #{master_public_key}"  #=> 0252c616d91a2488c1fd1f0f172e98f7d1f6e51f8f389b2f8d632a8b490d5f6da9
puts

# --------------------------
# Child Extended Private Key
# --------------------------
# m
# |- m/0
# |- m/1
# |- m/2
# .
# .
# .
# |- m/2147483648 (hardened - m/0')
parent_private_key = master_private_key
parent_chain_code  = master_chain_code
i = 0 # child number

# Normal (parent public key can create child public key for this private key)
if i < 2**31
    point = ECDSA::Group::Secp256k1.generator.multiply_by_scalar(parent_private_key.to_i(16)) # multiply generator point by private key
    point = ECDSA::Format::PointOctetString.encode(point, compression: true).unpack("H*")[0] # encode to compressed public key format
    data = [point].pack("H*") + [i].pack("N")     # point(private_key) i
end

# > This means that it is possible to give someone a parent extended key (public key + chain code), and they can derive all public keys in the chain. -- Pieter Wuille

# Hardened (parent public key cannot create public key for this private key)
if i >= 2**31
  data = ["00"].pack("H*") + [parent_private_key].pack("H*") + [i].pack("N")  # 0x00 private_key i
end

# > Hardened derivation should be the default unless there is a good reason why you need to be able to generate public keys without access to the private key. -- Pieter Wuille
# > You cannot derive hardened public keys from xpubs, because hardening is specifically designed to make exactly that impossible. -- Pieter Wuille

# Put data and key through hmac
key = [parent_chain_code].pack("H*") # chain code is key for hmac
hmac = OpenSSL::HMAC.hexdigest(OpenSSL::Digest::SHA512.new, key, data) # digest, key, data
il = hmac[0..63]  # left side of intermediate key [32 bytes]
ir = hmac[64..-1] # right side of intermediate key [32 bytes]

# Chain code is last 32 bytes
child_chain_code = ir

if child_chain_code.to_i(16) >= ECDSA::Group::Secp256k1.order
    raise "Chain code is greater than the order of the curve. Try the next index."
end

# Work out the corresponding public key too (optional)
child_private_key = (il.to_i(16) + parent_private_key.to_i(16)) % ECDSA::Group::Secp256k1.order # (il + parent_key) % n
child_private_key = child_private_key.to_s(16).rjust(64, '0') # convert to hex (and make sure it's 32 bytes long)

if child_private_key.to_i(16) == 0
    raise "Child private key is zero. Try the next index."
end

child_public_key = ECDSA::Group::Secp256k1.generator.multiply_by_scalar(child_private_key.to_i(16)) # work out the public key for this too
child_public_key = ECDSA::Format::PointOctetString.encode(child_public_key, compression: true).unpack("H*")[0] # encode to compressed public key format

puts "child_chain_code:   #{child_chain_code}"
puts "child_private_key:  #{child_private_key}"
puts "child_public_key:   #{child_public_key}"
puts

# -------------------------
# Child Extended Public Key
# -------------------------
# m -------- p
#            |- p/0
#            |- p/1
#            |- p/3
parent_public_key = master_public_key
parent_chain_code = master_chain_code
i = 0 # child number

if i >= 2**31
    raise "Can't create hardened child public keys from parent public keys."
end

key = [parent_chain_code].pack("H*")
data = [parent_public_key].pack("H*") + [i].pack("N") # 32-bit unsigned, network (big-endian) byte order

# Put data and key through hmac
hmac = OpenSSL::HMAC.hexdigest(OpenSSL::Digest::SHA512.new, key, data)
il = hmac[0..63]  # left side of intermediate key [32 bytes]
ir = hmac[64..-1] # right side of intermediate key [32 bytes]

# Chain code is last 32 bytes
child_chain_code = hmac[64..-1]

if il.to_i(16) >= ECDSA::Group::Secp256k1.order
    raise "Result of digest is greater than the order of the curve. Try the next index."
end

# Work out the child public key
point_hmac   = ECDSA::Group::Secp256k1.generator.multiply_by_scalar(il.to_i(16))                               # convert hmac il to a point
point_public = ECDSA::Format::PointOctetString.decode([parent_public_key].pack("H*"), ECDSA::Group::Secp256k1) # convert parent_public_key to a point
point = point_hmac.add_to_point(point_public)                                                                  # point addition

if (point == ECDSA::Group::Secp256k1.infinity)
    raise "Child public key point is at point of infinity. Try the next index."
end

child_public_key = ECDSA::Format::PointOctetString.encode(point, compression: true).unpack("H*")[0] # encode to compress public key

puts "child_chain_code:   #{child_chain_code}"
puts "child_public_key:   #{child_public_key}"
puts

# --------------------------
# Extended Key Serialization
# --------------------------

# Utils - Needed for creating the fingerprint and checksum, and converting hex string to Base58
# -----
require 'digest'

def create_fingerprint(parent_public_key)
    hash160 = Digest::RMD160.digest(Digest::SHA256.digest([parent_public_key].pack("H*"))) # hash160 it
    fingerprint = hash160[0...4].unpack("H*").join # take first 4 bytes (and convert to hex)
    return fingerprint
end

def hash256(hex)
    binary = [hex].pack("H*")
    hash1 = Digest::SHA256.digest(binary)
    hash2 = Digest::SHA256.digest(hash1)
    result = hash2.unpack("H*")[0]
    return result
end

def checksum(hex)
    hash = hash256(hex) # Hash the data through SHA256 twice
    return hash[0...8]  # Return the first 4 bytes (8 characters)
end

def base58_encode(hex)
    chars = %w[
      1 2 3 4 5 6 7 8 9
    A B C D E F G H   J K L M N   P Q R S T U V W X Y Z
    a b c d e f g h i j k   m n o p q r s t u v w x y z
    ]
    base = chars.length

    i = hex.to_i(16)
    buffer = String.new

    while i > 0
        remainder = i % base
        i = i / base
        buffer = chars[remainder] + buffer
    end

    # add '1's to the start based on number of leading bytes of zeros
    leading_zero_bytes = (hex.match(/^([0]+)/) ? $1 : '').size / 2

    ("1"*leading_zero_bytes) + buffer
end

# ---------
# Serialize
# ---------
parent_public_key = master_public_key # needed to create fingerprint

chain_code  = child_chain_code # m/0
private_key = child_private_key # m/0

# version + depth + fingerprint + childnumber + chain_code + key + (checksum)
#
# version:     puts xprv or xpub at the start
# depth:       how many times this child has been derived from master key (0 = master key)
# fingerprint: created from parent public key (allows you to spot adjacent xprv and xpubs)
# childnumber: the index of this child key from the parent
# chain_code:  the current chain code being used for this key
# key:         the private or public key you want to create a serialized extended key for (prepend 0x00 for private)

version     = "0488ade4" # private = 0x0488ade4 (xprv), public = 0x0488b21e (xpub)
depth       = "01"
fingerprint = create_fingerprint(parent_public_key) #=> "018c1259"
childnumber = "00000000" # 4 byte hexadecimal string
chain_code  = chain_code
key         = "00" + private_key  # prepend 00 to private keys (to make them 33 bytes, the same as public keys)

serialized = version + depth + fingerprint + childnumber + chain_code + key
extended_private_key = base58_encode(serialized + checksum(serialized))

puts "extended_private_key: #{extended_private_key}"

<?php
// Note: Requires https://github.com/Bit-Wasp/secp256k1-php

// ------------------
// Seed to Master Key
// ------------------

$seed = "67f93560761e20617de26e0cb84f7234aaf373ed2e66295c3d7397e6d7ebe882ea396d5d293808b0defd7edd2babd4c091ad942e6a9351e6d075a29d4df872af";
echo "seed: $seed".PHP_EOL;
echo PHP_EOL;

// Hash it through HMAC-SHA512 and split in to two halves
// 
//             seed
//              |
//            |----|
//            |HMAC|
//            |----|
//              |
// |    priv    | chain code |
// 
$hmac = hash_hmac("sha512", hex2bin($seed), "Bitcoin seed"); // algo, data, key, raw_output (optional)
$master_private_key = substr($hmac, 0, 64); // first half is private key
$master_chain_code = substr($hmac, 64);     // second half is chain code
//
// m (priv, chain_code)
// 
echo "master_chain_code:  $master_chain_code".PHP_EOL;
echo "master_private_key: $master_private_key".PHP_EOL;

// Use elliptic curve mathematics to go from private key to the public key
// 
// priv -> pub
// 
$context = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY); // set curve context
$point = null; secp256k1_ec_pubkey_create($context, $point, hex2bin($master_private_key)); // get public key point
$serialized = ''; secp256k1_ec_pubkey_serialize($context, $serialized, $point, SECP256K1_EC_COMPRESSED); // serialize to compressed public key
$master_public_key = bin2hex($serialized);

// 
// m (priv, pub, chain_code)
// 
echo "master_public_key:  $master_public_key".PHP_EOL;
echo PHP_EOL;

// ---------------------------------------------------------
// Parent Extended Private Key to Child Extended Private Key (m/0)
// ---------------------------------------------------------
// m (priv, pub, chain code)
// |
// m/0 (priv, pub, chain code)
$parent_private_key = $master_private_key; // get private key of parent
$parent_chain_code  = $master_chain_code;   // get chain code of parent
$i = 0;                                    // the index of this child from parent

// Normal Child (extended public key can derive its public keys)
if ($i < 2**31) { // first half of possible indexes are normal children
    // Get public key point for the parent private key
    $parent_public_key = $master_public_key; // you can derive this from the parent private key using the elliptic curve mathematics above
    // The `data` for the upcoming HMAC is the parent public key + index
    //  data = | parent public key (33 bytes) | i (4 bytes) |
    $data = pack("H*", $parent_public_key).pack("N", $i);
}

// Hardened Child (extended public key cannot derive its public keys)
if ($i >= 2**31 ) { // second half of possible indexes are hardened children
    //  data = | 00 | parent private key (32 bytes) | i (4 bytes) |
    $data = pack("H*", "00").pack("H*", $master_private_key).pack("N", $i);
}

// Put data (public key or private key) and chain code through HMAC-SHA512
$hmac = hash_hmac("sha512", $data, hex2bin($parent_chain_code)); // algo, data, key
$left = substr($hmac, 0, 64);
$right = substr($hmac, 64);

// Child chain code is right side of HMAC-SHA512 
// m
// |
// m/0 (chain code)
$child_chain_code = $right;
echo "child_chain_code:   $child_chain_code".PHP_EOL;

// Check child chain code is valid (not greater than the number of points on the curve)
if (hexdec($child_chain_code) >= 115792089237316195423570985008687907852837564279074904382605163141518161494337) {
    throw new Exception("Child chain code is greater than or equal to the order of the elliptic curve. Try next index.");
}

// Calculate child private key (left side of hmac + parent private key) % order
function bchexdec($hex) { // need a utility function to work with addition of large hexadecimal numbers
    if(strlen($hex) == 1) {
        return hexdec($hex);
    } else {
        $remain = substr($hex, 0, -1);
        $last = substr($hex, -1);
        return bcadd(bcmul(16, bchexdec($remain)), hexdec($last));
    }
}

function bcdechex($dec) { // need a utility function to convert large integer back to hexadecimal
    $last = bcmod($dec, 16);
    $remain = bcdiv(bcsub($dec, $last), 16);

    if($remain == 0) {
        return dechex($last);
    } else {
        return bcdechex($remain).dechex($last);
    }
}

// child private key = (left + parent private key) % order
// m
// |
// m/0 (priv)
$add = bcadd(bchexdec($left), bchexdec($parent_private_key)); // add left side of hmac to parent private key
$mod = bcmod($add, "115792089237316195423570985008687907852837564279074904382605163141518161494337"); // modulus the order of the curve
$child_private_key = str_pad(bcdechex($mod), 64, "0", STR_PAD_LEFT); // ensure it is 64 chars (prepend zeros)

// Check child private key is valid (not zero)
if (hexdec($child_private_key === 0)) {
    throw new Exception("Child private key is zero (so it's invalid). Try next index.");
}
echo "child_private_key:  $child_private_key".PHP_EOL;

// calculate corresponding child public key from this child private key
// m
// |
// m/0 (pub)
$context = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY); // set curve context
$point = null; secp256k1_ec_pubkey_create($context, $point, hex2bin($child_private_key)); // get public key point
$serialized = ''; secp256k1_ec_pubkey_serialize($context, $serialized, $point, SECP256K1_EC_COMPRESSED); // serialize to compressed public key
$child_public_key = bin2hex($serialized);
echo "child_public_key:   $child_public_key".PHP_EOL; // note may need to pad hex
echo PHP_EOL;

// -------------------------------------------------------
// Parent Extended Public Key to Child Extended Public Key (m/0)
// -------------------------------------------------------
// m -------- p (pub, chain code)
//            |
//            p/0 (pub, chain code)
$parent_public_key = $master_public_key; // get public key of parent
$parent_chain_code = $master_chain_code; // get chain code of parent
$i = 0;                                  // the index of this child from parent

// Check that you're not trying to create a hardened child public key (extended public keys cannot access public keys of hardened extended private key children)
if ($i >= 2**31) {
    throw new Exception("Cannot create a hardened extended child public key. Hardened children of extended private key are private.");
}

// Put data (parent public key + i) and chain code through HMAC-SHA512
$hmac = hash_hmac("sha512", pack("H*", $parent_public_key).pack("N", $i), hex2bin($parent_chain_code)); // same data as when creating normal child extended private key
$left = substr($hmac, 0, 64);
$right = substr($hmac, 64);

// Child chain code is right side of HMAC-SHA512 
// m -------- p
//            |
//            |p/0 (chain code)
$child_chain_code = $right;
echo "child_chain_code:   $child_chain_code".PHP_EOL;

// Check child chain code is valid (not greater or equal to than the number of points on the curve)
if (hexdec($child_chain_code) >= 115792089237316195423570985008687907852837564279074904382605163141518161494337) {
    throw new Exception("Child chain code is greater than or equal to the order of the elliptic curve. Try next index.");
}

// Calculate child public key: point(parent public key) + hmac left
// m -------- p
//            |
//            |p/0 (pub)

// point (parent public key)
$context = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY);                 // set curve context
$point_public = null; secp256k1_ec_pubkey_parse($context, $point_public, hex2bin($parent_public_key));  // point(parent public key)

// add point(hmac left) to point(parent public key)
secp256k1_ec_pubkey_tweak_add($context, $point_public, hex2bin($left)); // add hmac left to the parent public key point
$add = ''; secp256k1_ec_pubkey_serialize($context, $add, $point_public, SECP256K1_EC_COMPRESSED); // serialize to compressed key
$child_public_key = unpack("H*", $add)[1];
echo "child_public_key:   $child_public_key".PHP_EOL;
echo PHP_EOL;

// ----------------------
// Serialize Extended Key 
// ----------------------
$parent_public_key = $master_public_key; // needed for creating fingerprint

$chain_code = $child_chain_code;
$private_key = $child_private_key;

// | version | depth  | parent fingerprint |  index  | chain code | key (private or public) |
// | 4 bytes | 1 byte |      4 bytes       | 4 bytes |  32 bytes  |        33 bytes         |  = 78 bytes

function create_fingerprint($parent_public_key) {
    $hash160 = hash("ripemd160", hash("sha256", hex2bin($parent_public_key), true)); // hash160 the parent public key
    return substr($hash160, 0, 8); // return first 4 bytes (8 hex characters)
}

$version     = "0488ade4";               // 0488ade4 = private (xprv), 0488b21e = public (xpub)
$depth       = "01";                     // how many times this child has been derived from master key (0 = master key)
$fingerprint = create_fingerprint($parent_public_key); // fingerprint of parent key - first 4 bytes of hash160(parent public key) (00000000 = master key)
$index       = "00000000";               // the index of this child key from the parent (4 byte hexadecimal string)
$chain_code  = $chain_code;              // chain code for this key
$key         = "00".$private_key;        // private or public key you want to create a serialized extended key for (prepend 0x00 for private)

// Serialize the data
$serialized = $version.$depth.$fingerprint.$index.$chain_code.$key;

// Create a checksum for it (hash twice through sha256 and take first 4 bytes)
$checksum = substr(hash("sha256", hash("sha256", hex2bin($serialized), true)), 0, 8);

// Base58 encode the serialized+checksum
function base58_encode($hex){
  	$base58chars = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

    if (strlen($hex) == 0) {
        return '';
    }

    // Convert the hex string to a base10 integer
    $num = gmp_strval(gmp_init($hex, 16), 58);

    // Check that number isn't just 0 - which would be all padding.
    if ($num != '0') {
        $num = strtr($num, '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv', $base58chars);
    }
    else {
        $num = '';
    }

    // Pad the leading 1's
    $pad = '';
    $n = 0;
    while (substr($hex, $n, 2) == '00') {
        $pad .= '1';
        $n += 2;
    }

    return $pad . $num;
}

$master_extended_private_key = base58_encode($serialized.$checksum);
echo "master_extended_private_key: $master_extended_private_key".PHP_EOL;