Если вы интересуетесь технической стороной криптовалют, то эта статья вам точно будет интересна. В ней мы рассмотрим классический алгоритм SHA-2 и хеш-функцию SHA-256.
Именно на этом алгоритме построен майнинг самой популярной криптовалюты — биткоина, а так же и других альтернативных валют, называемых альткоинами.
Что такое SHA-256?
Итак, SHA-256 представляет из себя криптографическую функцию хеширования, которую разработали в Америке сотрудники Агентства Национальной Безопасности (АНБ).
Хеш-функция SHA-256 является однонаправленной функцией алгоритма SHA-2 (Secure Hash Algorithm Version 2). Основное применение — защита информации.
Общее описание алгоритма SHA-2
На рисунке ниже приведена схема 1 итерации алгоритма SHA-2.
В основе хеш-функции лежит структура Меркла-Дамгарда, согласно которой исходное значение после дополнения разбивается на блоки, а каждый блок в свою очередь на 16 слов.
Каждый блок сообщения пропускается алгоритмом через цикл с 80 или 64 интерациями, или раундами. На каждом раунде задается функция преобразования из входящих в состав блока слов. Два слова из сообщения преобразуются этой функцией. Полученные результаты суммируются, а в результате получается значение хеш-функции. Для обработки следующего блока используются результаты обработки предыдущего блока. Независимо друг от друга блоки обрабатывать нельзя.
В работе алгоритма SHA-2 используются битовые операции:
- || — конкатенация — операция склеивания объектов линейной структуры, строк
- + — операция сложение
- and (&, &&) — побитовая операция «И»
- xor — операция, исключающая «ИЛИ»
- shr (shift right) — логический сдвиг вправо
- rots (rotate right) — циклический сдвиг вправо
Технические характеристики хеш-функции SHA-256
- Длина дайджеста сообщения (бит) — 256
- Длина внутреннего состояния (бит) — 256 (8х32)
- Длина блока (бит) — 512
- Максимальная длина сообщения (бит) — 264-1
- Длина слова (бит) — 32
- Количество интераций в цикле — 64
- Скорость (MiB/s) — 139
Псевдокод хеш-функции SHA-256
Для любителей сломать себе мозг и для более глубокого понимания хеш-функции SHA-256 читайте информацию под спойлером.
Пояснения:
Все переменные беззнаковые, имеют размер 32 бита и при вычислениях суммируются по модулю 232
message — исходное двоичное сообщение
m — преобразованное сообщение
Инициализация переменных
(первые 32 бита дробных частей квадратных корней первых восьми простых чисел [от 2 до 19]):
h0 := 0x6A09E667
h1 := 0xBB67AE85
h2 := 0x3C6EF372
h3 := 0xA54FF53A
h4 := 0x510E527F
h5 := 0x9B05688C
h6 := 0x1F83D9AB
h7 := 0x5BE0CD19
Таблица констант
(первые 32 бита дробных частей кубических корней первых 64-х простых чисел [от 2 до 311]):
k[0..63] :=
0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5, 0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5,
0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3, 0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174,
0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC, 0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA,
0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7, 0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967,
0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13, 0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85,
0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3, 0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070,
0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5, 0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3,
0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208, 0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2
Предварительная обработка:
m := message ǁ [единичный бит]
m := m ǁ [k нулевых бит], где k — наименьшее неотрицательное число такое, что битовая длина
итогового сообщения будет ≡ 448 (mod 512) (сравнима по модулю 512 c 448)
m := m ǁ Длина(message) — длина исходного сообщения в битах в виде 64-битного числа
с порядком байтов от старшего к младшему
Далее сообщения обрабатывается последовательными порциями по 512 бит:
разбить сообщение на куски по 512 бит
для каждого куска
разбить кусок на 16 слов длиной 32 бита: w[0..15]
Сгенерировать дополнительные 48 слов:
для i от 16 до 63
s0 := (w[i-15] rotr 7) xor (w[i-15] rotr 18) xor (w[i-15] shr 3)
s1 := (w[i-2] rotr 17) xor (w[i-2] rotr 19) xor (w[i-2] shr 10)
w[i] := w[i-16] + s0 + w[i-7] + s1
Инициализация вспомогательных переменных:
a := h0
b := h1
c := h2
d := h3
e := h4
f := h5
g := h6
h := h7
Основной цикл:
для i от 0 до 63
Σ0 := (a rotr 2) xor (a rotr 13) xor (a rotr 22)
Ma := (a and b) xor (a and c) xor (b and c)
t2 := Σ0 + Ma
Σ1 := (e rotr 6) xor (e rotr 11) xor (e rotr 25)
Ch := (e and f) xor ((not e) and g)
t1 := h + Σ1 + Ch + k[i] + w[i]
h := g
g := f
f := e
e := d + t1
d := c
c := b
b := a
a := t1 + t2
Добавить полученные значения к ранее вычисленному результату:
h0 := h0 + a
h1 := h1 + b
h2 := h2 + c
h3 := h3 + d
h4 := h4 + e
h5 := h5 + f
h6 := h6 + g
h7 := h7 + h
Получить итоговое значения хеша:
digest = hash = h0 ǁ h1 ǁ h2 ǁ h3 ǁ h4 ǁ h5 ǁ h6 ǁ h7
Пример хеширования
Вот пример использования функции хеширования SHA-256. Результатом хеширования фразы «Bitcoin is the most popular cryptocurrency» будет выражение: 6810abc7 27b7e113 c8aa73f6 15bdb2ba adb1aa9c f30e177c 16c4df1a 82caf226
При малейшем изменении текста сообщения, результат хеширования изменяется кардинально. Это являетя следствием «лавинного эффекта» — важного криптографического свойства для шифрования.
Стоит изменить в вышеуказанном примере первую букву «B» на маленькую «b», получим следующий результат:
aa5415b4 cf0808fe 04457075 f5749564 9b45ca3a be9e9d11 bbb9fdae eab233ee
Криптоанализ алгоритма SHA-256
Криптоанализ — наука о способах и методах дешифрования зашифрованных данных без использования специального ключа.
Криптоанализ алгоритма SHA-2 проводился многими исследователями начиная с 2003 года — тогда не были найдены какие-либо уязвимости.
Но уже в 2008 году результатом исследования индийских ученых были опубликованы найденные коллизии для 22 итераций SHA-512 и SHA-256. Чуть позже в сентябре того же года был предоставлен метод создания коллизий для усеченного алгоритма SHA-2 (21 итерация), а позднее для 31 итерации хеш-функции SHA-256 и для 27 итераций SHA-512.
При криптоанализе хеш-функций проверяется устойчивость алгоритма как минимум к двум видам атак:
1. Нахождение коллизий — одинаковый хеш при разных входных параметрах. От устойчивости к этому виду атак зависит безопасность цифровой подписи с применением текущего алгоритма.
2. Нахождение прообраза — расшифровка исходного сообщения по его хешу. Устойчивость к этому виду атак обеспечивает безопасность хранения хешей аутентификационных паролей.
Разработчики алгоритма SHA-2 приняли решение, что новый алгоритм SHA-3 будет работать совершенно по иному принципу. Таким образом в октябре 2012 года в качестве SHA-3 был утвержден алгоритм Keccak.
Применение и сертификация хеширования SHA-256
Законом США допускается применение SHA-256 и других схожих хеш-функций в некоторых федеральных приложениях для защиты информации в рамках других алгоритмов и протоколов, не имеющих грифа «Секретно». Так же допускается применение SHA-2 частными и коммерческими организациями.
Вот мы и добрались до платежной системы Bitcoin, где используется хеш-функция SHA-256 для выпуска новой валюты. В данном случае выпуск новой валюты Биткоинов осуществляется поиском строк по их заданной структуре хеша SHA-256.
Сертификация SHA-2, необходимая для использования в специальных приложениях, проводится в рамках процедуры Cryptographic Module Validation Program (CMVP).
На ноябрь 2008 года сертификации было подвергнуто более 250 вариаций алгоритма SHA-2, в 4 из которых можно производить операции с сообщениями, длиной в битах не кратной 8.
Надеюсь эта информация была полезной и познавательной для вас! Дальше будет еще интереснее!
- Поделиться на Facebook
