How does Electrum make a keypair out of a seed?

Question

Electrum uses a seed of 12 words to generate a keypair and then hierarchically generates addresses out of that keypair.

I know how to generate hierarchic addresses from a keypair, but what I don't understand is how Electrum generates a keypair from the seed. I understand the seed consists of words coming from a 2048 length wordlist, but after that it is unclear to me how it starts to generate the sequence of addresses.

---

I'd like to do the HD generation in either Java / C++ / Python or C#. If I can understand the process, I might be able to reproduce it myself and generate hierarchical addresses from a seed.

---

EDIT:

A day later I find this Java implementation... Thanks for the answers!

https://github.com/harningt/atomun-mnemonic

Answer 1

Wallets created by Electrum 1.x have seeds containing 12 words (24 words is also possible for custom-created seeds). Given a zero-based array of seed_words of that length, this pseudocode calculates the master_private_key:

i = 0
while i < length(seed_words):
    # convert each word into an int in the range [0,1625]
    # based on the word's position in the sorted word list
    seed_ints[i] = lookup_seed_word(seed_words[i])
    i = i + 1

num_words  = 1626
num_words2 = num_words * num_words
seed_hex_str = ""
i = 0
while i < length(seed_words):
    # (hex8 converts an int into an ASCII string of
    # exactly 8 zero-padded lowercase hex digits;
    # % is the integer remainder operator
    seed_hex_str = seed_hex_str + hex8( seed_ints[i    ]
                    + num_words  * (   (seed_ints[i + 1] - seed_ints[i    ]) % num_words )
                    + num_words2 * (   (seed_ints[i + 2] - seed_ints[i + 1]) % num_words ))
    i = i + 3

unstretched_seed = ascii_string_to_byte_array(seed_hex_str)
seed = byte_array()  # an empty byte array
i = 0
while i < 100000:
    # sha256 operates on and produces byte arrays
    seed = sha256(seed + unstretched_seed)
    i = i + 1

master_private_key = byte_array_to_int(seed, order=big_endian)

In case you're wondering, it seems that the reason the seed_ints calculation looks overly complex may be to avoid infringing on a patent.

For comparison, wallets created by Electrum 2.x typically have seeds containing 13 words, however they will on occasion have fewer. (It's technically possible to construct seeds of nearly any length which will be accepted when restoring an Electrum 2.x wallet.) Here's the pseudocode which calculates a BIP-32 extended master private key:

# Electrum 2.x doesn't separate mnemonic words with spaces in sentences for any CJK
# scripts when calculating the checksum or deriving a binary seed (even though this
# seems inappropriate for some CJK scripts such as Hiragana as used by the ja wordlist)
if language is CJK:
    space = ""
else:
    space = " "

seed_phrase = ""
i = 0
do:
    word = seed_words[i]
    normalize_unicode(word, normalization=nfkd)
    remove_unicode_combining_marks(word)  # e.g. accent marks
    seed_phrase = seed_phrase + word
    i = i + 1
    if i ≥ length(seed_words):
        exit-loop
    seed_phrase = seed_phrase + space

seed_utf8 = unicode_to_byte_array(seed_phrase, format=utf8)

if hmac_sha512(key="Seed version", message=seed_utf8)[0] ≠ 1:
    fail("invalid checksum")

stretched_seed = pbkdf2_hmac_sha512(password=seed_utf8, salt="electrum", iterations=2048, output_length=64)
seed_bytes = hmac_sha512(key="Bitcoin seed", message=stretched_seed)

private_key        = byte_array_to_int(seed_bytes[0..31], order=big_endian)
chain_code_bytes   = seed_bytes[32..63]
master_private_key = create_bip32_extended_private_key(private_key, chain_code_bytes)

BIP-39, an alternative derivation technique, is similar to Electrum 2.x but not identical.