Кодирование микробиблиотеки BIP39 на Java

BIP39 - это протокол, который описывает, как создать удобочитаемое мнемоническое предложение и как преобразовать эту мнемонику в семя, которое затем может создать криптокошелек HD (BIP32 / BIP44).

Например:

mnemonic:
    talk smoke guess belt become ritual
    powder lyrics annual tomorrow relief witness
passphrase: m3d1um

Создает сид BIP39:

da8fefd74e5ce5cd644aa4f73ef265f80e95e622331039cd33b223f069282347f071740d29bec6aed7e25159bcda9589566dd23152269a49b64490a95f684c34

Запоминать, записывать без ошибок и передавать мнемонику и необязательную парольную фразу намного проще, чем делать то же самое с семенем.

Мнемоника BIP39 сегодня используется во многих программных кошельках, а также в топовых аппаратных кошельках, таких как Trezor и Ledger.

Вы можете прочитать полное описание BIP39 здесь: https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki

Но как разработчик программного обеспечения я лучше понимаю, вижу ли я код. Существует много библиотек, и все они очень сложные, потому что, конечно же, они делают больше, чем просто BIP39. В этой статье я расскажу о создании микробиблиотеки BIP39.

Код, который я предоставлю, будет тщательно прокомментирован и не будет преобразован во многие хорошо названные методы единственной ответственности. Это не мой обычный стиль и не то, что вы увидите в опубликованном репозитории git, это всего лишь первый набросок этих функций.

Открытый интерфейс BIP39 выполняет три функции:

createMnemonic(entropy, wordlist) -> mnemonic
getSeed(mnemonic, passphrase) -> seed
verifyMnemonic(mnemonic, wordlist) -> validity

Это идеальный след микробиблиотеки. Как оказалось, функция getSeed не имеет ничего общего с двумя другими (за исключением некоторых общих тестовых векторов), и это могут быть две микробиблиотеки, но я не хочу разделять BIP.

createMnemonic (энтропия, список слов) - ›мнемоника

Сначала в спецификации предусмотрены предварительные проверки; длина битов в энтропии должна делиться на 32 и находиться в пределах включающего диапазона 128–256 бит.

final int ent = entropyByteCount * 8;
if (ent < 128)
    throw new RuntimeException("Entropy too low, 128-256 bits allowed");
if (ent > 256)
    throw new RuntimeException("Entropy too high, 128-256 bits allowed");
if (ent % 32 > 0)
    throw new RuntimeException("Number of entropy bits must be divisible by 32");

Затем описывается метод получения первых cs бит хеша.

//checksum length (bits)
final int cs = ent / 32;
//mnemonic length (words)
final int ms = (ent + cs) / 11;

Нам нужно добавить первые cs бит хеша в наш байтовый массив энтропии.

//make a copy with space for one more
final byte[] entropyWithChecksum = Arrays.copyOf(entropy, entropy.length + 1);
//hash the original
MessageDigest digest = MessageDigest.getInstance("SHA-256");
final byte[] hash = digest.digest(entropy);
//append the first byte of the hash to the copy
entropyWithChecksum[entropy.length] = hash[0];

Но обратите внимание, я не собираюсь сокращать контрольную сумму, я просто добавляю первый байт целиком. Это потому, что мы собираемся брать 11 байтов за раз, а оставшаяся часть байта в конце все равно будет игнорироваться.

Теперь нам просто нужно обрабатывать этот массив байтов по 11 байтов за раз, что является довольно пугающей перспективой.

Для этого я представил движущееся окно битов по массиву байтов. Он будет иметь смещение до начала окна и длину 11 бит. Окно может занимать 2 или 3 байта из массива байтов в зависимости от смещения.

static int next11Bits(byte[] bytes, int offset) {
    //what's the index of the first byte
    final int skip = offset / 8;

    //how many bits will we need to drop from
    // the end of a 3 byte word?
    final int lowerBitsToRemove = (3 * 8 - 11) - (offset % 8);

    //get the first byte, the 0xff trick is
    // due to Java not having unsigned types
    final int b1 = (int) bytes[skip] & 0xff;

    //second byte
    final int b2 = (int) bytes[skip + 1] & 0xff;

    //third byte, but only if we need it,
    // or we might go out of bounds
    final int b3 = lowerBitsToRemove < 8
            ? ((int) bytes[skip + 2] & 0xff)
            : 0;

    //build up a 3 byte word from the three bytes
    final int firstThreeBytes = b1 << 16 | b2 << 8 | b3;

    //this mask is fixed, it's to keep the last 11 bits
    final int mask = (1 << 11) - 1;

    //drop the last n bits and apply the
    // mask to loose the upper bits
    return firstThreeBytes >> lowerBitsToRemove & mask;
}

Удаление комментариев и небольшое вложение выглядит так:

static int next11Bits(byte[] bytes, int offset) {
    final int skip = offset / 8;
    final int lowerBitsToRemove = (3 * 8 - 11) - (offset % 8);
    return (((int) bytes[skip] & 0xff) << 16 |
            ((int) bytes[skip + 1] & 0xff) << 8 |
            (lowerBitsToRemove < 8
                    ? ((int) bytes[skip + 2] & 0xff)
                    : 0)) >> lowerBitsToRemove & (1 << 11) - 1;
}

Это уродливо, но у него хорошо названный метод, и он хорошо покрыт тестами, так что я могу безопасно провести рефакторинг еще немного позже, если я чувствую, что это нужно.

Итак, теперь у нас есть entropyWithChecksum и способ чтения по 11 бит за раз, все, что осталось, - это прочитать его из списка слов и построить нашу мнемонику.

final StringBuilder sb = new StringBuilder();

for (int i = 0; i < ent + cs; i += 11) {
    final int wordIndex = next11Bits(entropyWithChecksum, i);
    sb.append(wordList.getWord(wordIndex));
    sb.append(" ");
}

//drop the last space
sb.setLength(sb.length() - 1);

return sb.toString();

В разных языках используются разные символы пробела, поэтому нам также необходимо передать их, давайте представим интерфейс для WordList:

public interface WordList {
    String getWord(final int index);
    char getSpace();
}

Всего:

public static String createMnemonic(
        final byte[] entropy,
        final WordList wordList) throws NoSuchAlgorithmException {
    //prechecks
    final int ent = entropy.length * 8;
    if (ent < 128)
        throw new RuntimeException("Entropy too low, 128-256 bits allowed");
    if (ent > 256)
        throw new RuntimeException("Entropy too high, 128-256 bits allowed");
    if (ent % 32 > 0)
        throw new RuntimeException("Number of entropy bits must be divisible by 32");

    //checksum length (bits)
    final int cs = ent / 32;
    //mnemonic length (words)
    final int ms = (ent + cs) / 11;

    //make a copy with space for one more
    final byte[] entropyWithChecksum = Arrays.copyOf(entropy, entropy.length + 1);
    //hash the original
    MessageDigest digest = MessageDigest.getInstance("SHA-256");
    final byte[] hash = digest.digest(entropy);
    //append the first byte of the hash to the copy
    entropyWithChecksum[entropy.length] = hash[0];

    final StringBuilder sb = new StringBuilder();

    for (int i = 0; i < ent + cs; i += 11) {
        final int wordIndex = next11Bits(entropyWithChecksum, i);
        sb.append(wordList.getWord(wordIndex));
        sb.append(wordList.getSpace());
    }
    //drop the last space
    sb.setLength(sb.length() - 1);

    return sb.toString();
}

Это работает для всех английских и японских тестовых векторов, на которые есть ссылки в документе BIP39.

getSeed (мнемоника, кодовая фраза) - ›seed

Теперь мы переходим к поиску семени из мнемоники и ключевой фразы. Вы можете быть удивлены, увидев заголовок этого раздела, не увидев список слов в качестве входных данных для этой функции. Это потому, что мы не идем назад, чтобы найти энтропию, а вместо этого хешируем мнемонику с необязательной парольной фразой для соли.

Чтобы создать двоичное начальное число из мнемоники, мы используем функцию PBKDF2 с мнемоническим предложением (в UTF-8 NFKD), используемым в качестве пароля, и строкой «мнемоника» + парольная фраза (снова в UTF-8 NFKD) в качестве соли. Счетчик итераций установлен на 2048, а HMAC-SHA512 используется как псевдослучайная функция. Длина производного ключа составляет 512 бит (= 64 байта).

Вот и все, что нужно сделать на этот раз.

Первый шаг - нормализовать обе строки.

mnemonic = Normalizer.normalize(mnemonic, Normalizer.Form.NFKD);
passphrase = Normalizer.normalize(passphrase, Normalizer.Form.NFKD);

NFKD - это разложение совместимости, грубо говоря, это означает, что мы упрощаем глифы с целью добраться до чего-то, что мы можем приблизить в UTF-8, без необходимости сохранять точные символы. Например, этому японскому Ka ｶ половинной ширины соответствует обычная ширина カ.

Теперь нам нужно получить байты UTF-8 для соли с префиксом string"mnemonic".

byte[] salt = ("mnemonic" + passphrase).getBytes("UTF-8");

Для самой мнемоники я оставлю UTF-16

char[] chars = mnemonic.toCharArray();

Теперь нам нужно передать их через функцию PBKDF2 с алгоритмом хеширования HMAC-SHA512, с 2048 итерациями и длиной ключа 512 бит.

PBEKeySpec spec = new PBEKeySpec(chars, salt, 2048, 512);
SecretKeyFactory secretKeyFactory =
    SecretKeyFactory.getInstance("PBKDF2WithHmacSHA512");
byte[] seed = secretKeyFactory.generateSecret(spec).getEncoded();

В целом, это очень короткая функция.

public static byte[] getSeed(String mnemonic, String passphrase) throws Exception {
    mnemonic = Normalizer.normalize(mnemonic, Normalizer.Form.NFKD);
    passphrase = Normalizer.normalize(passphrase, Normalizer.Form.NFKD);

    final char[] chars = mnemonic.toCharArray();
    final byte[] salt = ("mnemonic" + passphrase).getBytes("UTF-8");
    final PBEKeySpec spec = new PBEKeySpec(chars, salt, 2048, 512);
    final SecretKeyFactory secretKeyFactory = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA512");
    return secretKeyFactory.generateSecret(spec).getEncoded();
}

Теперь это работает со всеми тестовыми векторами английского и японского языков, на которые есть ссылки в документе BIP39.

Мы оставили мнемонику в собственном формате Java UTF-16, но я думаю, что функция PBKDF2 должна обрабатывать ее как UTF-8, иначе она просто не будет работать. Просто поменяв соль на UTF-16, даже английские векторы не работают.

verifyMnemonic (мнемоника, список слов) - ›validity

Хотя использование мнемоники, не созданной алгоритмом, описанным в разделе «Создание мнемоники», возможно, это не рекомендуется, и программное обеспечение должно вычислять контрольную сумму для мнемонического предложения, используя список слов, и выдавать предупреждение, если оно недействительно.

Итак, в качестве последнего шага, чтобы завершить эту библиотеку, я собираюсь предоставить функцию, которая будет проверять правильность мнемоники по списку слов.

Это отображение слов обратно в entropyWithChecksum, удаление последнего байта и пересчет контрольной суммы. И сравнивая от 4 до 8 бит последнего байта, в зависимости от длины.

private boolean validate(String mnemonic, WordList wordList) {
    //build a map to look up word indexes
    Map<String, Integer> map = new HashMap<>(1 << 11);
    for (int i = 0; i < 1 << 11; i++) {
        map.put(wordList.getWord(i), i);
    }

    //split the mnemonic
    String[] words = mnemonic.split(String.valueOf(wordList.getSpace()));

    //reverse calculate some of the variables from mnemonic generation, ms, ent, cs
    final int ms = words.length;

    final int entPlusCs = ms * 11;
    final int ent = (entPlusCs * 32) / 33;
    final int cs = ent / 32;
    if (entPlusCs != ent + cs)
        throw new RuntimeException("Not a correct number of words");
    byte[] entropyWithChecksum = new byte[(entPlusCs + 7) / 8];

    //look up the words
    int[] wordIndexes = new int[ms];
    for (int i = 0; i < ms; i++) {
        String word = words[i];
        Integer index = map.get(word);
        if (index == null) throw new RuntimeException("Word not found in word list \"" + word + "\"");
        wordIndexes[i] = index;
    }

    //build
    for (int i = 0, bi = 0; i < ms; i++, bi += 11) {
        writeNext11(entropyWithChecksum, wordIndexes[i], bi);
    }

    //strip the last byte
    byte[] entropy = Arrays.copyOf(entropyWithChecksum, entropyWithChecksum.length - 1);
    byte lastByte = entropyWithChecksum[entropyWithChecksum.length - 1];

    //recalculate hash
    byte sha = firstByteOfSha256(entropy);

    //we only want to compare the first cs bits
    byte mask = (byte) ~((1 << (8 - cs)) - 1);

    //if the first cs bits are the same, it's valid
    return ((sha ^ lastByte) & mask) == 0;
}

private void writeNext11(byte[] bytes, int value, int offset) {
    int skip = offset / 8;
    int bitSkip = offset % 8;
    {//byte 0
        byte firstValue = bytes[skip];
        byte toWrite = (byte) (value >> (3 + bitSkip));
        bytes[skip] = (byte) (firstValue | toWrite);
    }

    {//byte 1
        byte valueInByte = bytes[skip + 1];
        final int i = 5 - bitSkip;
        byte toWrite = (byte) (i > 0 ? (value << i) : (value >> -i));
        bytes[skip + 1] = (byte) (valueInByte | toWrite);
    }

    if (bitSkip >= 6) {//byte 2
        byte valueInByte = bytes[skip + 2];
        byte toWrite = (byte) (value << 13 - bitSkip);
        bytes[skip + 2] = (byte) (valueInByte | toWrite);
    }
}

Все это доступно под GPL-3.0 в репозитории здесь https://github.com/NovaCrypto/BIP39

Все это тщательно протестировано и усовершенствовано на предмет безопасности памяти.