Разбираем хеш-функцию SHA-256 алгоритма SHA-2

Разбираем хеш-функцию SHA-256 алгоритма SHA-2

  • 12 месяцев назад
  • 10287 Просмотров
  • 1 0

Если вы интересуетесь технической стороной криптовалют, то эта статья вам точно будет интересна. В ней мы рассмотрим классический алгоритм 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.

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

Оставить комментарий

Ваш e-mail не будет опубликован.

List Mag WP Menu
Join our feeds to automatically receive the latest headlines, news, and information formatted for your club's website or news reader.