Алгоритм безопасного хэширования
Алгоритм безопасного хэширования SHA (Secure Hash Algorithm) разработан НИСТ и АНБ США в рамках стандарта безопасного хэширования SHS (Secure Hash Standard) в 1992 г. Алгоритм хэширования SHA предназначен для использования совместно с алгоритмом цифровой подписи DSA.
При вводе сообщения М произвольной длины алгоритм SHA вырабатывает 160-битовое выходное сообщение, называемое дайджестом сообщения. Алгоритм SHA назван безопасным, потому что он спроектирован таким образом, чтобы было вычислительно невозможно восстановить сообщение, соответствующее данному дайджесту, а также найти два различных сообщения, которые дадут одинаковый дайджест. Любое изменение сообщения при передаче с очень большой вероятностью вызовет изменение дайджеста.
Рассмотрим подробнее работу алгоритма хэширования SHA. Прежде всего исходное сообщение М дополняют так, чтобы оно стало кратным 512 битам. Дополнительная набивка сообщения выполняется следующим образом: сначала добавляется единица, затем следуют столько нулей, сколько необходимо для получения сообщения, которое на 64 бита короче, чем кратное 512, и наконец добавляют 64-битовое представление длины исходного сообщения.
Инициализируется пять 32-битовых переменных в шестнадцатеричном виде:
А = 0х67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476
E = 0xC3D2E1F0
Затем начинается главный цикл алгоритма. Он обрабатывает сообщение 512-битовыми блоками и продолжается, пока не исчерпаются все блоки сообщения.
Сначала пять переменных копируются в другие переменные: A в a, B в b, C в c, D в d и E в e.
Главный цикл состоит из четырех этапов по 20 операций в каждом. Каждая операция представляет собой нелинейную функцию от трех из пяти переменных a, b, c, d и e, а затем выполняет сдвиг и сложение. В SHA используется следующий набор нелинейных функций:
ft(X,Y,Z) = (X Ù Y) Ú ((ØX) Ù Z), для t = 0 до 19;
ft(X,Y,Z) = X Å Y Å Z, для t = 20 до 39;
ft(X,Y,Z) = (X Ù Y) Ú(X Ù Z) Ú (Y Ù Z), для t = 40 до 59;
ft(X,Y,Z) = X Å Y Å Z, для t = 60 до 79.
В алгоритме используются также четыре константы:
Kt = 0x5A827999, для t = 0 до 19;
Kt = 0x6ED9EBA1 , для t = 20 до 39;
Kt = 0x8FlBBCDC, для t = 40 до 59;
Kt = 0xCA62C1D6, для t = 60 до 79.
Блок сообщения превращается из шестнадцати 32-разрядных слов (M0 … M15) в восемьдесят 32-разрядных слов (W0 … W79) с помощью следующего алгоритма:
Wt = Mt , для t = 0 по 15;
Wt =(Wt–3 Å Wt–8 Å Wt–14 Å Wt–16) <<<1, для t = 16 по 79,
где t – номер операции (для t = 0…79), Wt – t-й субблок расширенного сообщения, <<< S – циклический сдвиг влево на S бит.
С учетом приведенных обозначений главный цикл хэш-преобразования содержит 80 итераций (t = 0…79), каждая из которых описывается следующей последовательностью действий:
TEMP = (a <<<5) + ft(b, c, d)+ e + Wt + Kt
e = d
d =c
c = b <<<30
b = a
a = TEMP
На рис. 4.4 приведена схема одной итерации.
|
| Рис. 4.4. Схема выполнения одной итерации алгоритма SHA. |
После окончания главного цикла значения a, b, c, d и e складываются с A, B, C, D и E, соответственно, и алгоритм приступает к обработке следующего 512-разрядного блока данных. Окончательным результатом служит конкатенация значений A, B, C, D и E.