Алгоритм безопасного хэширования SHA

Алгоритм безопасного хэширования SHA (Secure Hash Algorithm) разработан НИСТ и АНБ США в рамках стандарта безопасного хэши­ова­ния SHS (Secure Hash Standard) в 1992 г. Он разработан для использования со­вместно с алгоритмом цифровой подписи DSA.

При вводе сообщения M произвольной длины менее 2⁶⁴ бит алгоритм SHA вырабатывает 160-битовое выходное сообще­ние, называемое дайд­же­стом сообщения M D (Message Digest). Затем этот дайджест сообщения ис­пользуется в качестве входа алгоритма DSA, который вычисляет цифро­вую подпись сообщения M. Формирование цифровой подписи для дайд­жеста сообщения, а не для самого сообщения повышает эффектив­ность процесса подписания, поскольку дайджест сообщения обычно намного ко­роче самого сообщения. Такой же дайджест сообщения должен вычислять­ся поль­зователем, проверяющим полученную подпись, при этом в качест­ве входа в алгоритм SHA используется полученное сообщение M.

Алгоритм SHA построен на основе конечных автома­тов Мили и описан, например, в [9]. Главный цикл алгоритма обраба­тыва­ет по 512 бит сообщения поочередно для всех блоков, имеющихся в сооб­щении. Он содержит четыре цикла по 20 операций ка­ждый. Каждая опе­ра­ция реализует нелинейную функцию, а затем производит сдвиг и сложе­ние.

Алгоритм хэширования SHA назван безопасным, потому что его создатели утверждают, что вычислительно невозможно восстановить сообщение, соответствующее данному дайджесту, а также найти два различных сообщения, которые дадут одинаковый дайджест. Любое изменение сообщения при пе­редаче с очень большой вероятностью вызовет изменение дай­джеста, и принятая цифровая подпись не пройдет проверку. Также считается, что алгоритм SHA более устойчив к атакам полного перебора и атакам "дня рождения", поскольку выдает 160-битовое хэш-значение, тогда как большинство других алгоритмов хэширова­ния формируют 128-битовые хэш-значения.

Отечественный стандарт хэш-функции

Российский стандарт ГОСТ Р 34.11-94 определяет алго­ритм и про­цедуру вычисления хэш-функции для любых последо­вательностей двоич­ных символов, применяемых в криптографиче­ских методах обработки и защиты информации. определенная им хэш-функция формирует 256-би­товое хэш-значение.

Этот стандарт базируется на блочном алгоритме шифрования ГОСТ 28147-89, хотя в принципе позволяет использовать и другой блочный алго­ритм шифрования с 64-битовым блоком и 256-битовым ключом.

Функция сжатия H_i = f (M_i, H_{i -1}) (оба операнда M_i, и H_{i -1} являются 256-битовыми величинами) определяется следующим образом:

1. Генерируются 4 ключа шифрования k_j, j = 1...4, путем линейного смешивания операндов M_i, H_{i -1} и некоторых констант c _j, j = 1...4.

2. Каждый ключ k_j используют для шифрования 64-битовых подслов h_i слова H_{i -1} в режиме простой замены: S _j =E _kj  (h_j).

Результирующая последовательность S₄, S₃, S₂, S₁ длиной 256 бит запоминается во временной переменной S.

3. Значение H_i является сложной, хотя и линейной функци­ей смешивания S, M_i и H_{i -1}.

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

- H_n - хэш-значения последнего блока сообщения;

- Z - значения контрольной суммы, получаемой при сложении по модулю два всех блоков сообщения;

- L-длины сообщения.

Эти три переменные и дополненный последний блок M ' сообщения объединяются в окончательное хэш-значение сле­дующим образом:

h (M)= f (Z Å M', f (L, f (M', H_n))).

Данная хэш-функция определена стандартом ГОСТ Р 34.11-94 для использования совместно с российским стандартом электронной цифровой подписи.