SECURE HASH Алгоритмы (SHA-1, SHA-2)

Источники:
1. описание стандарта NIST FIPS PUB 180-4, "Secure Hash Standard (SHS)", U.S. Department of Commerce, март 2012

Термины:
FIPS Federal Information Processing Standard (Федеральный стандарт обработки информации).
SHA Secure Hash Algorithm (алгоритм стойкого хэширования).
Слово – беззнаковая переменная длиной 32 бита (4 байта), либо 64 бита (8 байт), зависит от выбранного SHA-алгоритма.

SECURE HASH STANDARD (семейство криптографических функций SHA-1 и SHA-2)


Семейство криптографических функций SHA делят на два подмножества: непосредственно алгоритм SHA-1 (опубликован в 1995 году – FIPS PUB 180-1) и ряд алгоритмов под общим названием SHA-2 (опубликован в 2002 году – FIPS PUB 180-2, обновлен в 2008 году - FIPS PUB 180-3): SHA-224, SHA-256, SHA-384, SHA-512; в 2012 году в FIPS PUB 180-4 добавлены алгоритмы SHA-512/224 и SHA-512/256. Мы рассмотрим стандарт FIPS PUB 180-4, объединяющий все семейство хэш-функций SHA-1 и SHA-2.


Этот стандарт определяет следующие хэш-алгоритмы: SHA-1, SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 и SHA-512/256, вычисляющие сжатое представление цифровых данных (сообщений). Если на вход хэш-алгоритма подать сообщение любой длины, но меньшее, чем 264 бит (для SHA-1, SHA-224 и SHA-256) или меньше, чем 2128 бита (для SHA-384, SHA-512, SHA-512/224 и SHA-512/256), то результатом будут данные, называемые дайджестом или хэш-значением сообщения. Размер хэш-значения сообщения лежит в диапазоне от 160 до 512 бит (или от 20 до 64 байт), зависит от выбранного алгоритма. SHA алгоритмы обычно используются совместно с другими криптографическими алгоритмами, например, с алгоритмами цифровой подписи или при хешировании с ключом для аутентификации сообщений (HMAC), или при создании случайных чисел (бит).

Хэш-алгоритмы, указанные в этом стандарте называются безопасными потому, что по заданному алгоритму невозможно вычислить следующее: 1) восстановить сообщение по конкретному дайджесту сообщения, или 2) найти два различных сообщения, у которых один и тот же дайджест сообщения (найти коллизию). Любые изменения в сообщении, с очень высокой вероятностью, приводят к различным хэш-значениям. Это свойство полезно при создании и проверке цифровых подписей, при аутентификации сообщений, при создании случайных чисел.

Каждый алгоритм состоит из двух этапов: предварительная обработка и вычисление хэша. Предварительная обработка включает в себя дополнение сообщения, разбиение дополненного сообщения на M-битные блоки, и установка инициализирующих значений, используемые при вычислении хэша. Вычисление хэша проходит итерационно, обрабатывая каждый M-битный блок дополненного сообщения, и использует функции, константы и операции над словами, чтобы получить хэш-значение. Результатом работы процедуры вычисление хэша является дайджест сообщения.

Алгоритмы различаются по размеру блоков и слов хэшируемых данных и хэш-значений – см. таблицу 1.

Алгоритм Размер сообщения (в битах) Размер блока (в битах) Размер слова (в битах) Размер дайджеста сообщения (в битах)
SHA-1 < 264 512 32 160
SHA-224 < 264 512 32 224
SHA-256 < 264 512 32 256
SHA-384 < 2128 1024 64 384
SHA-512 < 2128 1024 64 512
SHA-512/224 < 2128 1024 64 224
SHA-512/256 < 2128 1024 64 256
Функции

SHA-1 использует последовательность нелинейных функций f0 , f1 ,…, f79. Каждая функция ft, где 0 ≤ t < 79, оперирует тремя 32-битными переменными: x, y, и z, в результате возвращая одно 32-битное слово. В алгоритме SHA-1 используется следующий набор нелинейных функций ft (x, y, z):
00 ≤ t ≤ 19     Ch(x, y, z) = (x AND y) XOR ( NOT x AND z)
20 ≤ t ≤ 39     Parity(x, y, z) = x XOR y XOR z
40 ≤ t ≤ 59     Maj(x, y, z) = (x AND y) XOR (x AND z) XOR (y AND z)
60 ≤ t ≤ 79     Parity(x, y, z) = x XOR y XOR z

Булева алгебра.
Обратите внимание, что, например, функцию Ch может выразить по-другому:
z XOR (x AND (y XOR z))
Результат не изменится. В различных реализациях алгоритма такие варианты можно встретить.

Константы

Константы Kt
00 ≤ t ≤ 19     0x5a827999
20 ≤ t ≤ 39     0x6ed9eba1
40 ≤ t ≤ 59     0x8f1bbcdc
60 ≤ t ≤ 79     0xca62c1d6

(Если вас заинтересовал вопрос, откуда взялись эти числа, то укажем их источник:
0x5A827999 = $\sqrt{2} / 4$, 0x6ED9EBA1 = $\sqrt{3} / 4$, 0x8F1BBCDC = $\sqrt{5} / 4$, 0xCA62C1D6 = $\sqrt{10} / 4$; все умножено на 232).

Предварительная обработка
1. Дополнение сообщения

Цель – сделать сообщение кратным 512 или 1024 бит, зависит от выбранного алгоритма SHA. Дополнение может быть выполнено перед процедурой вычисления хэша, или в ходе выполнения хэша, но до обработки блока(ов), который (ые) будут содержать дополнение.

Предположим, что длина сообщения M равна l бит. Сначала в конец сообщения добавляется «1», а затем нули - в количестве k - так, чтобы размер полученного сообщения был на 64 разряда меньше числа, кратного 512 (l+1+k = 448 mod 512). Далее, к полученному результату добавляется 64-битовое представление размера l исходного сообщения М. Например, (ASCII текст) у нас есть сообщение «abc», длиной 8 * 3 = 24 бита. Добавляем к сообщению «1», затем 448 - (24 +1) = 423 бит «0», и в конце 64-битовое представление размера 24 = 00…011000. В итоге получим 512-битовое сообщение вида:

image00.jpg
2. Разбиение дополненного сообщения на M-битные блоки.

Дополненное сообщение разбивается на N M-битных блоков.

Дополненное сообщение разбивается на N 512-битовых блоков: M(1), M(2) … M(N). Т.к. 512 бит можно выразить как 16 (шестнадцать) 32-битных слов, то первые 32 бита i-го блока сообщения обозначим M0(i), следующие 32 бита M1(i), и так дойдем до M15(i).

3. Установка инициализирующих значений

Перед процедурой вычисления хэша алгоритм устанавливает начальные значения H. Размер и количество слов H зависит от выбранного алгоритма.

Четыре 32-битных слова.
H0 = 0x67452301
H1 = 0xefcdab89
H2 = 0x98badcfe
H3 = 0x10325476
H4 = 0xc3d2e1f0

Вычисление хэша

В алгоритме сложение "+" происходит по модулю 232.

For i = 1 to N:
{
     1. i-й блок сообщения с помощью приведенного далее алгоритма
     преобразуется из 16 слов размером в 32 разряда (с М0(i) по М15(i))
     в 80 слов размером 32 разряда (с W0 по W79):
     Wt = Mt, для t = 0..15
     Wt = ROTL(Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16, 1), для t = 16..79
     (Интересно, что в первоначальном варианте спецификации SHA (алгоритм SHA-0) не было
     циклического сдвига влево ROTL(x, 1))

     2. Инициализируем переменные a,b,c,d,e.
     a = H0(i-1)
     b = H1(i-1)
     c = H2(i-1)
     d = H3(i-1)
     e = H4(i-1)

     3. Главный цикл функции сжатия
     For t = 0 to 79
          TEMP = ROTL(a, 5) + ft(b,c,d) + e + Wt + Kt
          e = d
          d = c
          c = ROTL(b, 30)
          b = a
          a = TEMP

     4. Считаем промежуточное хэш-значение
     H0(i) = (H0(i-1) + a)
     H1(i) = (H1(i-1) + b)
     H2(i) = (H2(i-1) + c)
     H3(i) = (H3(i-1) + d)
     H4(i) = (H4(i-1) + e)
}

Результирующее хэш-значение – 160-битный дайджест сообщения:
H0(N) || H1(N) || H2(N) || H3(N) || H4(N) (5 слов * 32 бита = 160 бит)
Внимание: порядок байт в каждом слове "big-endian"

Операции над словами (32-битными).
ROTL - циклический сдвиг влево на n бит:
ROTL(x, n) = (x « n) | (x » (32-n))

Смотрите Python-реализацию алгоритмов. SHA-1,SHA-224,SHA-256,SHA-384,SHA-512,SHA-512/224,SHA-512/256

Криптографические примитивы
Алгоритмы с открытым ключом RSA DSA
Поточные шифры RC4
Хэш-функции RIPEMD-160 SHA-1/2
Пока не указано иное, содержимое этой страницы распространяется по лицензии Creative Commons Attribution-ShareAlike 3.0 License