Если вы интересуетесь технической стороной криптовалют, то эта статья вам точно будет интересна. В ней мы рассмотрим классический алгоритм SHA-2 и хеш-функцию SHA-256.

Именно на этом алгоритме построен майнинг самой популярной криптовалюты — биткоина, а так же и других альтернативных валют, называемых альткоинами.

Содержание

• Что такое SHA-256?
• Общее описание алгоритма SHA-2
• Технические характеристики хеш-функции SHA-256
• Псевдокод хеш-функции SHA-256
• Пример хеширования
• Криптоанализ алгоритма SHA-256
• Применение и сертификация хеширования 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
• Максимальная длина сообщения (бит) — 2⁶⁴-1
• Длина слова (бит) — 32
• Количество интераций в цикле — 64
• Скорость (MiB/s) — 139

Псевдокод хеш-функции SHA-256

Для любителей сломать себе мозг и для более глубокого понимания хеш-функции SHA-256 читайте информацию под спойлером.

Пояснения: Все переменные беззнаковые, имеют размер 32 бита и при вычислениях суммируются по модулю 232 message — исходное двоичное сообщение m — преобразованное сообщение

Инициализация переменных (первые 32 бита дробных частей квадратных корней первых восьми простых чисел [от 2 до 19]): h0 := 0×6A09E667 h1 := 0xBB67AE85 h2 := 0×3C6EF372 h3 := 0xA54FF53A h4 := 0×510E527F h5 := 0×9B05688C h6 := 0×1F83D9AB h7 := 0×5BE0CD19

Таблица констант (первые 32 бита дробных частей кубических корней первых 64-х простых чисел [от 2 до 311]): k[0..63] := 0×428A2F98, 0×71374491, 0xB5C0FBCF, 0xE9B5DBA5, 0×3956C25B, 0×59F111F1, 0×923F82A4, 0xAB1C5ED5, 0xD807AA98, 0×12835B01, 0×243185BE, 0×550C7DC3, 0×72BE5D74, 0×80DEB1FE, 0×9BDC06A7, 0xC19BF174, 0xE49B69C1, 0xEFBE4786, 0×0FC19DC6, 0×240CA1CC, 0×2DE92C6F, 0×4A7484AA, 0×5CB0A9DC, 0×76F988DA, 0×983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7, 0xC6E00BF3, 0xD5A79147, 0×06CA6351, 0×14292967, 0×27B70A85, 0×2E1B2138, 0×4D2C6DFC, 0×53380D13, 0×650A7354, 0×766A0ABB, 0×81C2C92E, 0×92722C85, 0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3, 0xD192E819, 0xD6990624, 0xF40E3585, 0×106AA070, 0×19A4C116, 0×1E376C08, 0×2748774C, 0×34B0BCB5, 0×391C0CB3, 0×4ED8AA4A, 0×5B9CCA4F, 0×682E6FF3, 0×748F82EE, 0×78A5636F, 0×84C87814, 0×8CC70208, 0×90BEFFFA, 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]

Инициализация вспомогательных переменных: 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]

Добавить полученные значения к ранее вычисленному результату: 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.

Надеюсь эта информация была полезной и познавательной для вас! Дальше будет еще интереснее!