19.5.Алгоритм sha-1.
Алгоритм SHA (Secure Hash Algorithm) является частью стандарта SHS, принятого АНБ и Национальным институтом стандартов и технологий США (NIST) в 1993г. В версии SHA-1 длина хэш-кода H равна 160 битам.
В конец исходного сообщения М, которое рассматривается как битовая строка, дописывается 1. Затем к концу сообщения, при необходимости, дописываются нули, так, чтобы длина полученного сообщения, увеличенная на 64, была кратна 512. Таким образом формируется сообщение, состоящее из N блоков длиной 512 битов, которого в последнем блоке которого зарезервировано поле в б4 бита. В это поле помещается число, равное длине исходного сообщения М.
Обработка расширенного сообщения ведется блоками по 512 битов. При этом каждый блок рассматривается как массив, состоящий их 16 тридцатидвухбитовых слов.
Одношаговая
функция сжатия используется в виде
,
,
,
где блок V
является
конкатенацией начальных значений пяти
зарезервированных тридцатидвухбитовых
переменных V=A,B,C,D,E
следующего вида (в 16-ричной системе):
A= 67452301, B=EFCDAB89, C=98BADCFE, D=10325476, E=C3D2E1F0.
В
результате обработки очередного блока
сообщения значения переменных A,B,C,D,E
изменяются. Результатом работы каждого
цикла
является конкатенция новых состояний
переменных A,B,C,D,E.
Выход последнего цикла дает значение хэш-кода.
Каждый
цикл состоит из восьмидесяти шагов. В
каждом шаге j
цикла с номером i
обрабатывается
слово
,
состоящее из 32-х разрядов.
В начале каждого цикла создаются копии переменных A,B,C,D,E: A1=A, B1= B, C1= C, D1= D, E1= E.
Слова,
обрабатываемые на цикле i
формируются
из блока сообщения
следующим образом.
1.
Блок
рассматривается как последовательность
шестнадцати слов
,
j=1,…,16,
исходя из которых, по рекуррентному
закону формируются остальные 64 слова.
Рекуррентное соотношение имеет вид
,
j=17,…,80.
Здесь функция Sft[t] означает циклический сдвиг слова на t разрядов влево, операция - поразрядную сумму слов по модулю два.
2.
Обработка восьмидесяти слов производится
последовательно, группами по 20 слов в
каждой. Каждой из четырех групп
соответствуют 20 шагов цикла (раунд):
j=1,…,20,
j=21,…,40,
j=41,…,60,
j=61,…,80.
Кроме того, с каждым раундом
,
k=1,…,4,
связана своя тридцатидвухбитовая
константа
и функция
от трех переменных, каждая из которых
является словом. При обработке слова
применяются константа и функция,
связанные с соответствующей группой.
3. Обработка очередного слова приводит к изменению переменных A,B,C,D,E и заключается следующем:
,
E=D,
D=C,
C=Sft[30]B,
A=T.
Здесь
Т
– вспомогательная переменная, а сложение
производится по модулю
.
4. После 80 шагов обработки блока сообщения, цикл завершается модификацией переменных A,B,C,D,E: A=A+A1, B=B+B1, C=C+C1, D=D+D1, E=E+E1.