Алгоритм безопасного хеширования SHA. Главный цикл алгоритма SHA.

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

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

Такой же дайджест сообщения должен вычисляться пользователем, проверяющим полученную подпись, при этом в качестве входа в алгоритм SНА используется полученное сообщение М.

Алгоритм хэширования SНА назван безопасным, потому что он спроектирован таким образом, чтобы было вычислительно невозможно восстановить сообщение, соответствующее данному дайджесту, а также найти два различных сообщения, которые дадут одинаковый дайджест. Любое изменение сообщения при передаче с очень большой вероятностью вызовет изменение дайджеста, и принятая цифровая подпись не пройдет проверку.

Рассмотрим подробнее работу алгоритма хэширования SНА. Прежде всего исходное сообщение М дополняют так, чтобы оно стало кратным 512 битам. Дополнительная набивка сообщения выполняется следующим образом: сначала добавляется единица, затем следуют столько нулей, сколько необходимо для получения сообщения, которое на 64 бита короче, чем кратное 512, и наконец добавляют 64-битовое представление длины исходного сообщения.

Инициализируется пять 32-битовых переменных в виде:

А = 0х67452301

В = 0хЕFСDАВ89

С = 0х98ВАDСFЕ

D = 0x10325476

Е = 0хС3D2Е1F0

Затем начинается главный цикл алгоритма. В нем обрабатывается по 512 бит сообщения поочередно для всех 512-битовых блоков, имеющихся в сообщении. Первые пять переменных А, В, С, D, Е копируются в другие переменные a, b, с, d, е:

а = А, b = В, с = С, d = D, е = Е

Главный цикл содержит четыре цикла по 20 операций каждый. Каждая операция реализует нелинейную функцию от трех из пяти переменных а, b, с, d, е, а затем производит сдвиг и сложение.

Алгоритм SНА имеет следующий набор нелинейных функций:

f_t (Х, Y, Z) = (X ^Ù Y) Ú ((Ø X) ^Ù Z) для t = 0...19,

f_t (Х, Y, Z) =Х Å Y Å Z для t = 20...39,

f_t (Х, Y, Z) = (X ^Ù Y) Ú (X ^Ù Z) Ú (Y ^Ù Z) для t = 40...59,

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

где t - номер операции.

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

К_t = 0х5А827999 для t = 0...19,

К_t = 0х6ЕD9ЕВА1 для t = 20...39,

К_t = 0х8F1ВВСDС для t = 40...59,

К_t = 0хСА62С1D6 для t = 60...79.

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

W_t = М_t для t = 0...15,

W_t = (W_t-3 Å W_t-8 Å W_t-14 Å W_t-16) <<< 1 для t = 16...79,

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

С учетом введенных обозначений главный цикл из восьмидесяти операций можно описать так:

цикл по t от 0 до 79

ТЕМР = (а <<< 5) + f_t (b, c, d) + е + W_t + К_t

е = d

d = с

с = (b <<< 30)

b = а

а = ТЕМР

конец_цикла

Схема выполнения одной операции показана на рис.5.

Рис.5. Схема выполнения одной операции алгоритма SHA

После окончания главного цикла значения а, b, с, d, е складываются с А, В, С, D, Е соответственно, и алгоритм приступает к обработке следующего 512-битового блока данных. Окончательный выход формируется в виде конкатенации значений А, В, С, D, Е.

Отличия SHA от MD5 состоят в следующем:

• SНА выдает 160-битовое хэш-значение, поэтому он более устойчив к атакам полного перебора и атакам "дня рождения", чем MD5, формирующий 128-битовые хэш-значения.
• Сжимающая функция SHA состоит из 80 шагов, а не из 64 как в MD5.
• Расширение входных данных производится не простым их повторение в другом порядке, а рекуррентной формулой.
• Усложнен процесс перемешивания