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

Алгоритм безопасного хэширования 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 используется следующий набор нелинейных функций:

f_t (X,Y,Z) = (X Ù Y) Ú ((Ø X) Ù Z), для t = 0 до 19;

f_t (X,Y,Z) = X Å Y Å Z, для t = 20 до 39;

f_t (X,Y,Z) = (X Ù Y) Ú(X Ù Z) Ú (Y Ù Z), для t = 40 до 59;

f_t (X,Y,Z) = X Å Y Å Z, для t = 60 до 79.

В алгоритме используются также четыре константы:

K_t = 0x5A827999, для t = 0 до 19;

K_t = 0x6ED9EBA1, для t = 20 до 39;

K_t = 0x8FlBBCDC, для t = 40 до 59;

K_t = 0xCA62C1D6, для t = 60 до 79.

Блок сообщения превращается из шестнадцати 32-разрядных слов (M ₀ … M ₁₅) в восемьдесят 32-разрядных слов (W ₀ … W ₇₉) с помощью следующего алгоритма:

W_t = M_t, для t = 0 по 15;

W_t =(W_{t –3} Å W_{t –8} Å W_{t –14} Å W_{t –16}) <<< 1, для t = 16 по 79,

где t – номер операции (для t = 0…79), W_t – t -й субблок расширенного сообщения, <<< S – циклический сдвиг влево на S бит.

С учетом приведенных обозначений главный цикл хэш-преобразования содержит 80 итераций (t = 0…79), каждая из которых описывается следующей последовательностью действий:

TEMP = (a <<< 5) + f_t (b, c, d)+ e + W_t + K_t

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.