Криптографическая хэш-функция CryptoNight

CryptoNight - криптографическая хэш-функция, по умолчанию применяемое для доказательства выполнения работы (Proof-of-Work, PoW) в протоколе CryptoNote.

Описание алгоритма:

1. Инициализация ОЗУ.

1.1. Для входного сообщения вычисляется конечное состояние хэш-функции Keccak с параметрами b=1600 и c=512 (длина строки состояния 1600 бит).

1.2. 0-ой, 1-ый, ..., 31-ый байты вычисленного конечного состояния (256 бит) интерпретируются как 256-битный ключ алгоритма AES-256, из которого генерируются 10 раундовых ключей (алгоритма AES-256).

1.3. Выделяются 2097152 байт (2Мб) ОЗУ.

1.4. 64-ый, ..., 191-ый байты вычисленного конечного состояния (128 байтов) делятся на 8 блоков по 16 байтов каждый.

1.5. Каждый из этих 8 блоков зашифровывается с помощью следующих преобразований:

       for i = 1..10 do:

             block = aes_round(block, round_keys[i]),

       где block - 16-байтный блок, aes_round - раунд алгоритма AES-256 (SubBytes, ShiftRows, MixColumns, AddRoundKey), i - номер раунда, round_keys[i] - раундовый ключ i-го раунда.

1.6. Полученные в результате 8 зашифрованных 16-байтных блоков записываются в первые 128 байтов ОЗУ.

1.7. Далее эти же 8 блоков снова зашифровываются как в шаге 1.5.

1.8. Полученные в результате 8 зашифрованных 16-байтных блоков записываются в следующие 128 байтов ОЗУ.

1.9. Каждый следующий раз в ОЗУ записываются 128 байтов, представляющие собой результат шифрования ранее записанных 128 байт. Этот процесс повторяется до тех пор, пока ОЗУ не будет полностью инициализирован.

2. Memory-Hard Цикл (Memory-Hard Loop).

2.1. 0-ой, 1-ый, ..., 31-ый байты складываются по модулю 2 (XOR) с 32-ым, 33-им, ..., 63-им байтами вычисленного конечного состояния хэш-функции Keccak.

2.2. Полученные в результате 32 байта используются для инициализации двух переменных a и b, каждая по 16 байтов.

Следующая последовательность шагов (2.3- 2.11) повторяется 524288 раз

2.3. С помощью значения переменной а вычисляется адрес 16 байтов в ОЗУ.  Для этого 16 байтовое значение переменной а интерпретируется как бинарное представление целого числа, записанное в порядке от младшего к старшему, и первые 21 младших бит используются как индекс байта в ОЗУ, при этом первые 4 младших бита очищаются для их полного перебора и последовательного получения индексов 16 байтов в ОЗУ.

2.4. 16 байтов (128 бит), записанные в ОЗУ по вычисленному адресу, зашифровываются одним раундом алгоритма AES-256, используюя качестве раундового ключа 16 байтов (128 бит) переменной а.

2.5. Полученные зашифрованные 16 байтов складываются по модулю 2 (XOR) с 16 байтами переменной b, и также эти зашифрованные 16 байтов становятся новым значением переменной b.

2.6. Полученные в результате сложения 16 байтов обратно записываются в ОЗУ по вычисленному адресу.

2.7. С помощью уже нового значения переменной b вычисляется новый адрес 16 байтов в ОЗУ (как в шаге 2.3).

2.8. Первые 8 байтов  из 16 байтов, записанных в ОЗУ по вычисленному адресу, интерпретируются как бинарное представление 64-битового беззнакового целого числа, записанное в порядке от младшего к старшему. Первые 8 байтов значения переменной b также интерпретируются как бинарное представление 64-битового беззнакового целого числа, записанное в порядке от младшего к старшему. К этой паре 8-мибайтовых значений применяется покомпонентное умножение по модулю 2^64. Результат преобразуется в 16 байт, и, наконец, две 8-байтовые части результата меняются местами.

2.9. Полученный результат интерпретируется как бинарное представление пары 64-битовых беззнаковых целых чисел, записанных в порядке от младшего к старшему. Значение переменной а также интерпретируется как бинарное представление пары 64-битовых беззнаковых целых чисел, записанных в порядке от младшего к старшему. К этим 4-м 8-мибайтовым значениям применяется покомпонентное умножение по модулю 2^64. Результат преобразуется в 16 байт и становится новым значением переменной а.

2.10. Также полученный результат обратно записывается в ОЗУ по вычисленному адресу. При этом 16 байтов,  ранее записанных в ОЗУ по вычисленному адресу, складываются по модулю 2 (XOR) с новым значением 16 байтов переменной а.

2.11. Результат сложения становится новым значением переменной а.

3. Вычисление результата хеширования.

3.1. 32-ой, 33-ий, ..., 63-ий байты вычисленного конечного состояния хэш-функции Keccak интерпретируются как 256-битный ключ алгоритма AES-256, из которого генерируются 10 раундовых ключей (алгоритма AES-256) (как в шаге 1.2).

3.2. 64-ый, 65-ый, ..., 191-ый байты вычисленного конечного состояния хэш-функции Keccak складываются по модулю 2 (XOR) с первыми 128 байтами ОЗУ.

3.3. Полученные в результате сложения 128 байтов зашифровываются как в шагах 1.4, 1.5 с использованием раундовых ключей, полученных в шаге 3.1.

3.4. Полученные в результате 128 байтов складываются по модулю 2 (XOR) с вторыми 128 байтами ОЗУ.

3.5. Полученные в результате сложения 128 байтов снова зашифровываются как в шагах 1.4, 1.5 с использованием раундовых ключей, полученных в шаге 3.1, и затем складываются по модулю 2 (XOR) со следующими 128 байтами ОЗУ, и так далее.

3.6. После сложения с последними 128 байтами ОЗУ результат последний раз зашифровывается.

3.7. 64-ый, 65-ый, ..., 191-ый байты конечного состояния хэш-функции Keccak заменяются полученными в результате зашифрования 128 байтами.

3.8. Затем к измененному состоянию хэш-функции Keccak применяется функция Keccak-f (с параметром b=1600).

3.9. Затем 2 младших бита первого байта состояния используются для выбора хеш-функции:

0 = BLAKE-256 [BLAKE],

1 = Groestl-256 [GROESTL],

2 = JH-256 [JH]

и 3 = Skein-256 [SKEIN].

3.10. Выбранная хеш-функция затем применяется к состоянию Keccak, и получается результат CryptoNight.