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, вычисляющие сжатое представление цифровых данных (сообщений). Если на вход хэш-алгоритма подать сообщение любой длины, но меньшее, чем 2⁶⁴ бит (для SHA-1, SHA-224 и SHA-256) или меньше, чем 2¹²⁸ бита (для SHA-384, SHA-512, SHA-512/224 и SHA-512/256), то результатом будут данные, называемые дайджестом или хэш-значением сообщения. Размер хэш-значения сообщения лежит в диапазоне от 160 до 512 бит (или от 20 до 64 байт), зависит от выбранного алгоритма. SHA алгоритмы обычно используются совместно с другими криптографическими алгоритмами, например, с алгоритмами цифровой подписи или при хешировании с ключом для аутентификации сообщений (HMAC), или при создании случайных чисел (бит).

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

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

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

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

Функции

• SHA-1
• SHA-224, SHA-256
• SHA-384, SHA-512, SHA-512/224, SHA-512/384

SHA-1 использует последовательность нелинейных функций f₀, f₁,…, f₇₉. Каждая функция f_t, где 0 ≤ t < 79, оперирует тремя 32-битными переменными: x, y, и z, в результате возвращая одно 32-битное слово. В алгоритме SHA-1 используется следующий набор нелинейных функций f_t (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))
Результат не изменится. В различных реализациях алгоритма такие варианты можно встретить.

Константы

• SHA-1
• SHA-224, SHA-256
• SHA-384, SHA-512, SHA-512/224, SHA-512/384

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

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

Предварительная обработка

Дополнение сообщения

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

• SHA-1, SHA-224, SHA-256
• SHA-384, SHA-512, SHA-512/224, SHA-512/384

Предположим, что длина сообщения 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-битовое сообщение вида:

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

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

• SHA-1, SHA-224, SHA-256
• SHA-384, SHA-512, SHA-512/224, SHA-512/384

Дополненное сообщение разбивается на N 512 -битовых блоков: M⁽¹⁾, M⁽²⁾ … M^(N). Т.к. 512 бит можно выразить как 16 (шестнадцать) 32-битных слов, то первые 32 бита i -го блока сообщения обозначим M₀⁽ⁱ⁾, следующие 32 бита M₁⁽ⁱ⁾, и так дойдем до M₁₅⁽ⁱ⁾.