1.1.4Алгоритм безопасного хэширования (Secure Hash Algorithm, sha)

NIST, вместе с NSA, для Стандарта цифровой подписи (Digital Signature Standard) разработал Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA). (Сам стандарт называется Стандарт безопасного хэширования ( Secure Hash Standard, SHS), a SHA - это алгоритм, используемый в стандарте.) В соответствии с Federal Register:

Описание SHA

Во - первых, сообщение дополняется, чтобы его длина была кратной 512 битам. Используется то же дополне­ние, что и в MD5: сначала добавляется 1, а затем нули так, чтобы длина полученного сообщения была на 64 бита меньше числа, кратного 512, а затем добавляется 64-битовое представление длины оригинального сообщения.

Инициализируются пять 32-битовых переменных (в MD5 используется четыре переменных, но рассматриваемый алгоритм должен выдавать 160-битовое хэш-значение ):

А = 0×67452301

В = 0×efcdab89

С = 0×98badcfe

D = 0×10325476

E = 0×c3d2e1f0

Затем начинается главный цикл алгоритма. Он обрабатывает сообщение 512-битовыми блоками и продол­жается, пока не исчерпаются все блоки сообщения.

Сначала пять переменных копируются в другие переменные : А в а, В в b, С в с, D в d и Е в е.

Главный цикл состоит из четырех этапов по 20 операций в каждом (в MD5 четыре этапа по 16 операций в каждом). Каждая операция представляет собой нелинейную функцию над тремя из а ,b, с, d и е, а затем выполняет сдвиг и сложение аналогично MD5. В SHA используется следующий набор нелинейных функций :

f_t (X, Y, Z) = (Х  Y)  ((X)  Z) , для t=0 до 19

f_t (X, Y, Z) = Х  Y  Z , для t=20 до 39

f_t (X, Y, Z) = (Х  Y)  (Х  Z)  (Y  Z) , для t=40 до 59

f_t (X, Y, Z) = Х  Y Z , для t=60 до 79

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

К_t = 0×5а827999, для t=0 до 19

К_t = 0×6ed9eba1 , для t=20 до 39

К_t = 0×sf1bbcdc, для t=40 до 59

К_t = 0×ca62cld6, для t=60 до 79

(Если интересно, как получены эти числа, то: 0×5а827999 = 2^1/2/4, 0×6ed9ebal = 3^1/2/4, 0×sflbbcdc = 5^1/2/4, 0×ca62cld6 = 10^1/2/4.)

Блок сообщения превращается из 16 32-битовых слов (М₀ по М₁₅) в 80 32-битовых слов (W_o no 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 no 79

Если t - это номер операции (от 1 до 80), W_t, представляет собой t-ый подблок расширенного сообщения, а <<< s - это циклический сдвиг влево на s битов, то главный цикл выглядит следующим образом:

FOR t = 0 to 79

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

e = d

d=c

b = a

c = b<<<30

a = TEMP

Сдвиг переменных выполняет ту же функцию, которую в MD5 выполняет использование в различных местах различных переменных.

Рисунок 22 — Одна операция SHA.

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

1.1.5Хэш-функция гост

Эта хэш-функция появилась в России и определена в стандарте ГОСТ Р 34.11.94. В ней используется блочный алгоритм ГОСТ, хотя теоретически может использоваться любой блочный алгоритм с 64-битовым блоком и 256-битовым ключом. Функция выдает 256-битовое хэш-значение.

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

Описать работу алгоритма можно следующим образом: H_i = f(M_i, H_i-1), где M_i – входная последовательность, не подвергшаяся обработке, H_i-1 – значение хэш – кода предыдущей итерации, (оба операнда - 256-битовые величины).

Процедура вычисления функции f состоит из последовательности шагов:

Шаг 1:

• Инициализируются переменные L (текущее значение длины обработанной части входной последовательности) и I (значение контрольной суммы);

• Если длина входной необработанной последовательности больше 256 (|M|>256), алгоритм переходит к шагу 3, в противном случае производятся следующие действия:

Шаг 2.

• L = (L + |M|) mod 256;

• I = (I + (0^256-|M| || M) mod 256, где 0^256-|M| — последовательность битовых нулей длиной 256-|M|, || - конкатенация битовых строк. Таким образом, на этом этапе вычисляется текущее значение контрольной суммы.

• H =  ((0^256-|M| || M), H) — вычисляется значение функции хэширования  от аргументов, представляющих собой хэшируемый блок и начальный вектор хэширования (Н);

• H =  (I, H) — результат данного вычисления и является окончательным результатм хэш – функции;

• конец работы алгоритма.

Из входной последовательности выбирается очередной блок длиной 256 бит (M = M0 || M1) и производятся следующие действия:

Шаг 3:

• H =  (M0, H);

• L = (L + |M|) mod 256;

• I = (I + M0) mod 256;

• M = M0;

• Переход к шагу 2.

Вычисление функции  состоит из следующих этапов:

1. При помощи линейного смешивания M_i, H_i-1 и некоторых констант генерируется четыре ключа шифрования ГОСТ;

2. осуществляется зашифрование четырех подблоков (составляющих начальный вектор хэширования Н) по 64 бита каждый в соответствии с алгоритмом ГОСТ 28147 – 89 в режиме простой замены;

3. перемешивающая функция применяется к результату зашифрования.

Генерация секретных ключей.

При генерации секретных ключей используются данные Н и М (входная последовательность, представленная в двоичном виде) и инициализируются следующие константы:

С₂ = С₄ = 0²⁵⁶ и С₃ = 1⁸0⁸1¹⁶0²⁴1¹⁶0⁸(0⁸1⁸)²1⁸0⁸×(0⁸1⁸)⁴(1⁸0⁸)⁴, где a^k – двоичная последовательность из k бинарных знаков а – {0, 1}. После чего выполняется алгоритм:

I = 1; U = H; V = M;

W = U  V;

K1 = P(W);

For i=2 to 4

U = A(U)  C_i

V = A(A(V))

W = U  V

K_i = P(W)

Функции P представляет собой перестановку s(i+1+4(k-1)) = 8_i+k, i = 03, k = 18 над подблоками длиной 8 бит исходной двоичной последовательности длиной 256 бит. Таким образом, последовательность x₃₂ || … || x₁ преобразуется в последовательность x_s(32) || … || x_s(1). Функцией А(Х) обозначают следующее преобразование последовательности, разделенной на 4 подблока по 64 бита каждый: A(X) = (x₁  x₂) || x₄ || x₃ || x_2.

Шифрующее преобразование.

Начальный вектор Н разбивается на 4 подблока h_i длиной 64 бита, и каждый подблок зашифровывается на своем ключе K_i, то есть s_i = Ek_i(h_i) (i=1,2,3,4). В результате получается последовательность S = s₁ || s₂ || s₃ || s₄.

Перемешивающая функция.

Сначала исходная последовательность разбивается на шестнадцать 16-битных подблоков ni i=116 и при помощи регистра сдвига с обратной связью преобразуется в последовательность следующего вида:

n₁  n₂  n₃  n₄  n₁₃  n₁₆ || n₁₆ || … || n₂.

Если обозначить данную функцию через , то исходная функция хэширования -  (M, H) = ⁶¹ ((H   (M  ¹²(S))), где степень функции  обозначает, сколько раз она применяется к битовой последовательности.