Алгоритм построения цифрового дайджеста MD5 [Ло Шу] (pdf) читать постранично

Алгоритм построения цифрового
дайджеста MD5
Введение
Данная статья продолжает рассмотрение алгоритмов построения цифрового дайджеста
сообщения и содержит информацию об алгоритме MD5. По-прежнему, предполагается,
что читатель знаком с языками программирования Си и Форт. Смотрите статью
"Алгоритм построения цифрового дайджеста MD4" в предыдущем номере журнала.

Цифровой дайджест MD5
В том же 1991 году, когда был создан алгоритм построения цифрового дайджеста MD4,
профессором Ривестом был предложен другой алгоритм – MD5, "старший" и более
сильный брат алгоритма MD4 (почему "старший" мы узнаем чуть позже). Он во многом
похож на своего собрата и поэтому нам будет гораздо легче понять как он работает, так
как мы уже в деталях знаем как работает MD4.
Здесь я тоже начну с примера. Итак, цифровой дайджест строки символов и файла:
MD5("MD5") = 7F138A09169B250E9DCB378140907378
MD5(WinWord.EXE) = B9D86A2E86028000B500B498FE71C299
Длина цифрового дайджеста MD5 составляет 16 байт или 16*8 = 128 бит.

MD5 процессор
MD5 процессор состоит из набора следующих регистров. Прежде всего это регистры A,
B, C и D, которые содержат промежуточный результат вычисления цифрового
дайджеста. "БЛОЧНЫЙ БУФЕР" MD5 процессора содержит 16 32-разрядных слов, в этом
буфере формируется очередной блок для построения очередного промежуточного
результата. Регистр "БАЙТ В БУФЕРЕ" содержит число, определяющее количество байт
в "БЛОЧНОМ БУФЕРЕ" на этапе его формирования, или заполнения. Регистр "РАЗМЕР
СООБЩЕНИЯ" содержит полный размер исходного сообщения, для которого строиться
цифровой дайджест, в битах; эта величина будет добавлена в конец исходного
сообщения на финальном этапе формирования цифрового дайджеста. Регистры
"УКАЗАТЕЛЬ ДАННЫХ" и "РАЗМЕР ДАННЫХ" содержат, соответственно, указатель на
текущий обрабатываемый пакет данных и его размер.
Структура MD5 процессора изображена графически на Рисунке 1.

УКАЗАТЕЛЬ ДАННЫХ
РАЗМЕР ДАННЫХ
РЕГИСТР A
РЕГИСТР B
РЕГИСТР C
РЕГИСТР D
РАЗМЕР СООБЩЕНИЯ

БЛОЧНЫЙ БУФЕР

БАЙТ В БУФЕРЕ

СТРУКТУРА MD5 ПРОЦЕССОРА

Рисунок 1. Структура MD5 процессора.
Операция инициализации процессора приводи его в определенное начальное
состояние, то есть во все регистры помещаются определенные начальные значения.
Эти значения диктуются документом RFC 1321. После инициализации MD5 процессор
выглядит следующим образом:

NULL

УКАЗАТЕЛЬ ДАННЫХ

0

РАЗМЕР ДАННЫХ
РЕГИСТР A

67452301

РЕГИСТР B

EFCDAB89

РЕГИСТР C

98BADCFE

РЕГИСТР D

10325476
00000000 00000000 [0]

РАЗМЕР СООБЩЕНИЯ

00000000
БЛОЧНЫЙ БУФЕР

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

БАЙТ В БУФЕРЕ

ИНИЦИАЛИЗАЦИЯ MD5 ПРОЦЕССОРА

Рисунок 3. Состояние MD5 процессора после инициализации.
В качестве маленького итога, можно сказать, что MD5 процессор по своей структуре не
отличается от MD4 процессора. Они даже сходны по своей процедуре инициализации.

Базовые операции
Цифровой дайджест MD5 определяет четыре базовые логические функции, которые
используются в операции преобразования блока данных. Вот они:
F(x,y,z) = (x AND y) OR (NOT x AND z)1
G(x,y,z) = (x AND z) OR (y AND NOT z)2
H(x,y,z) = x XOR y XOR z
I(x,y,z) = y XOR (x OR NOT z)3
И таблицы истинности этих функций:
x
0
0
0
0
1
1
2
3

y
0
0
1
1
0

z
0
1
0
1
0

F
0
1
0
1
0

x
0
0
0
0
1

y
0
0
1
1
0

NOT x AND z = (NOT x) AND z
y AND NOT z = y AND (NOT z)
x OR NOT z = x OR (NOT z)

Z
0
1
0
1
0

G
0
0
1
0
0

X
0
0
0
0
1

y
0
0
1
1
0

z
0
1
0
1
0

H
0
1
1
0
1

x
0
0
0
0
1

y
0
0
1
1
0

z
0
1
0
1
0

I
1
0
0
1
1

1
1
1

0
1
1

1
0
1

0
1
1

1
1
1

0
1
1

1
0
1

1
1
1

1
1
1

0
1
1

1
0
1

0
0
1

1
1
1

0
1
1

1
0
1

1
0
0

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

#define
#define
#define
#define

F(x,y,z)
G(x,y,z)
H(x,y,z)
I(x,y,z)

((x & y) | (~x & z))
((x & z) | (y & ~z))
(x ^ y ^ z)
(y ^ (x | ~z))

Библиотека OpenSSL применяет несколько другие обозначения и использует
оптимизацию! Логические функции можно преобразовать и уменьшить количество
операций, требуемых для их вычисления:

#define
#define
#define
#define

F(b,c,d)
G(b,c,d)
H(b,c,d)
I(b,c,d)

((((c) ^ (d)) & (b)) ^ (d))
((((b) ^ (c)) & (d)) ^ (c))
((b) ^ (c) ^ (d))
(((~(d)) | (b)) ^ (c))

Здесь используется тот факт, что (x AND y) OR (NOT x AND z) = ((y XOR z) AND z) XOR z.
То есть мы имеем на одну логическую операцию меньше. Сравните: в первом случае –
AND, OR, NOT, AND, и во втором случае – XOR, AND, XOR. Как увидим дальше, экономия
в одну операцию будет существенной во время преобразования блока данных.
Как и прежде для исследования поведения этих операций я использовал язык FORTH и
его