SHA-1

tiger@ibd.lv

🕛 02.11.2006, 16:38

Алгоритм SHA-1 (Secure Hash Algorithm) используется в алгоритмах электронно-цифровых подписей (DSA - Digital Signature Algorithm). Для сообщения (потока данных) длиной меньше 2^64 бита, данный алгоритм вычисляет 160-битный хэш. Полученный хэш используется для генерации "подписи" к сообщению, а также для ее проверки. Любые изменения в исходном сообщении приведут к измению хэша с очень большой вероятностью.
SHA-1 разрабатывался с целью иметь следующие свойства: не представляется возможным с использованием комьютера найти исходное сообщение, зная хэш, или найти два различных сообщения дающее одинаковый хэш.
В данном алгоритме под "словом" понимается количество информации в 32 бита, "байт" - 8 бит. Целое число в промежутке от 0 до 2^32 - 1 включительно может быть представлено как слово, в котором старший байт записан первым, младший - последним. Целое z (0 <= z < 2^64) представляется в виде z = (2^32)x + y, где x и y - целые в промежутке от 0 до 2^32 - 1. Таким образом, z можно представить парой слов x и y. Блок из 512 бит может быть представлен последовательностью из 16 слов.
В алгоритме используются следуюсчие опреации:

x & y
- побитовое "И"
x | y
- побитовое "ИЛИ"
x ^ y
- побитовое "исключающее ИЛИ"
~x
- побитовое отрицание
x <<< y
- циклический сдвиг x влево на y бит
x + y
= (x + y) mod 2^32, т.е. рассматриваются младшие 32 бита результат

Выравнивание сообщения.
Длина сообщения принимается как количество бит во входном потоке (возможно пустое сообщение длиной 0 бит). Цель выравнивания: сделать длину сообщения кратной 512, т.к. алгоритм SHA-1 обрабатывает входной поток блоками по 512 бит. Выравнивание проиходит следующим образом: добавляется один бит '1' (a), затем следуют биты '0' (b), после чего записывается длина сообщения до выравнивания (c). В результате получаем длину потока равную n*512.

Пример: допустим входной поток бит имел следующий вид:
01100001 01100010 01100011 01100100 01100101 (40 бит)
после шага (a) cообщение принимает вид:
01100001 01100010 01100011 01100100 01100101 1 (41 бит)
на шаге (b) добавляются 407 '0', что в шестнадцатиричном виде выглядит так:
61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000
на шаге (c) добавляем длину до выравнивания: 40 - 00000000 00000028 (hex); и получаем выравненное сообщение:
61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000028

Далее будем рассматривать входной поток как массив M[0 ... N-1] слов длиной N.

Логические функции.
SHA-1 использует последовательность логических функций f(0), f(1), ... , f(79), каждая из которых принимает 3 32-битных слова и вычисляет результат - слово. Функция f(t; B, C, D) определена следующим видом:

f(t; B, C, D) = (B & C) | (~B & D)
0 <= t <= 19
f(t; B, C, D) = B ^ C ^ D
20 <= t <= 39
f(t; B, C, D) = (B & C) | (B & D) | (C & D)
40 <= t <= 59
f(t; B, C, D) = B ^ C ^ D
60 <= t <= 79

Константы.
В данном алгоритме используется последовательность константных слов K(0), K(1), ... , K(79):

K(t) = 5A827999
0 <= t <= 19
K(t) = 6ED9EBA1
20 <= t <= 39
K(t) = 8F1BBCDC
40 <= t <= 59
K(t) = CA62C1D6
60 <= t <= 79

Вычисление.
Для вычисления SHA-1 хэш функции используется буфер из 5 слов {H0, H1, H2, H3, H4}, который перед началом вычислений инициализируется следующими значениями:

H0 = 67452301
H1 = EFCDAB89
H2 = 98BADCFE
H3 = 10325476
H4 = C3D2E1F0

Для каждого блока M<i> выполняются следующие вычисления (MASK = 0x0F):

a. разложить M<i> на 16 слов W[0], ... , W[15], где W[0] - крайнее слева слово в M<i>

b. сохранить H0, H1, H2, H3, H4
A = H0, B = H1, C = H2, D = H3, E = H4

c.
for t = 0 to 79 do
{
s = t & MASK;
if (t >= 16)
W = (W[(s + 13) & MASK] ^ W[(s + 8) & MASK] ^
W[(s + 2) & MASK] ^ w) <<< 1;
temp = (A <<< 5) + f(t; B, C, D) + E + W + K(t);
E = D; D = C; C = B <<< 30; B = A; A = temp;
}

d. H0 += A; H1 += B; H2 += C; H3 += D; H4 += E;

Вывод SHA-1.
Результат вычислений записывается пятью словами в порядке H0, H1, H2, H3, H4. Вычисленный хэш имеет длину 160 бит.

Примеры:
"a" - 86f7e437faa5a7fce15d1ddcb9eaeaea377667b8
"abc" - a9993e36476816aba3e25717850c26c9cd0d89d
"abrakadabra" - 79fb86e161e6bee2f1474099c4bee8247926999

Подробнее об алгоритме MD5 можно прочитать в FIPS180-1.