Алгоритмы защиты информации / RFC+1320+Алгоритм+хэш-функции+MD4

Хэширование и эл подпись

1

Request for Comments: 1320 The MD4 Message-Digest Algorithm

Разработан для быстрых вычислений на 32-битных машинах. Он не требует больших таблиц замещений. Очень компактный алгоритм

Мы имеем b-битовое сообщение на входе m0 m1 ... mb-1

1. Добавление Padding Bits

Сообщение всегда расширяется чтобы его длина (в битах) составляла остаток 448 по модулю 512, даже если она уже этому равна

Расширение выполняется следующим образом добавляется единственный единичный бит за которым следуют нулевые биты

2. К результату предварительного шага добавляется 64 битное представление длины b до расширения. В нежелательном случае если длина превышает 264 используются только младшие 64 бита. Результирующее сообщение имеет длину кратную 512 битам или 16 (32bit) словам. Обозначим его M0 ... МN-1 , где N -кратно 16.

3. Инициализация MD буфера. Для вычисления дайджеста сообщения используется 4 словный буфер из 32 битных регистров A, B, C, D. Эти регистры инициализируются следующими шестнадцатиричными величинами, младший байт вначале:

4. Обработка сообщения в 16 словных блоках(то есть блок имеет длину 512 бит) 512битные блоки подвеpгаются пpоцедуpе Damgard-Merkle [16], пpичем каждый блок участвует в тpех pазных циклах.

Определим 3 функции, имеющие на входах и выходах 32-битные слова

F(X,Y,Z) = XY v not(X) Z G(X,Y,Z) = XY v XZ v YZ H(X,Y,Z) = X xor Y xor Z, где

"+" - сложение слов т.е. по модулю 232

X <<< s - циклический сдвиг 32-bit влево на S разрядов

not(X) - bit-wise complement of			X,	Y.
X	v Y побитовая операция OR над		X,
X	Y -побитовая	операция исключающего ИЛИ,

XY операция побитового умножения (AND) над X и Y.

В функции F каждый бит Х действует как условие , если установлен берется соответсвующее значение бита из Y, иначе из Z

Функция G -есть функция побитового мажорирования.

Функция H -функция побитовой операции XOR или функции четности

For i = 0 to N/16-1 do	{Process each 16-word block. }
For j = 0	to 15 do {Копируем блок i в X}
end	xj := M I*16+j

ПАЗИ Криптография с ОК

18.04.04

1

Хэширование и эл подпись		2

AA: = A BB: = B CC:= C DD:= D {Сохраняем значения A,B, C,D}

{Проход 1}

{Обозначим [abcd k s] операцию a = (a + F(b,c,d) + X[k]) <<< s }

[ABCD

0

3]

[DABC

1

7]

[CDAB

2

11]

[BCDA

3

19]

[ABCD

4

3]

[DABC

5

7]

[CDAB

6

11]

[BCDA

7

19]

[ABCD

8

3]

[DABC

9

7]

[CDAB 10

11]

[BCDA 11

19]

[ABCD 12

3]

[DABC 13

7]

[CDAB 14

11]

[BCDA 15

19]

{Проход 2}

{Обозначим	[abcd k s] операцию a = (a						+ G(b,c,d) + X[k] + 5A827999) <<< s}
[ABCD	0	3]	[DABC	4	5]	[CDAB	8	9]	[BCDA 12		13]
[ABCD	1	3]	[DABC	5	5]	[CDAB	9	9]	[BCDA 13		13]
[ABCD	2	3]	[DABC	6	5]	[CDAB	10	9]	[BCDA	14	13]
[ABCD	3	3]	[DABC	7	5]	[CDAB	11	9]	[BCDA	15	13]

{Проход 3}

{Обозначим	[abcd k		s] операцию a = (a +				H(b,c,d) + X[k]				+ 6ED9EBA1) <<< s}
[ABCD	0	3]	[DABC	8	9]	[CDAB	4	11]	[BCDA	12	15]
[ABCD	2	3]	[DABC	10	9]	[CDAB	6	11]	[BCDA	14	15]
[ABCD	1	3]	[DABC	9	9]	[CDAB	5	11]	[BCDA	13	15]
[ABCD	3	3]	[DABC	11	9]	[CDAB	7	11]	[BCDA	15	15]
A = A	+ AA {Cкладываем новое значение регистров с первоначальным}
B = B + BB			C = C + CC D = D + DD

end

Величина 5A827999 - 32-битная константа, записанная начиная со старшей цифры. Представляет квадратный корень из 2.

6ED9EBA1 - представляет собой квадратный корень из 3

5. Вывод

Дайджест сообщения находится после окончания алгоритма в регистрах A, B, C, D. Начиная с младшего байта A, и кончая старшим байтом D.

В алгоритме MD4 довольно быстро были найдены дыpы, поэтому он был заменен алгоритмом MD5, в котором каждый блок участвует не в трех, а в четырех различных циклах.

ПАЗИ Криптография с ОК

18.04.04

2