Описание МD5

Алгоритм MD5

Алгоритм MD4

Алгоритм MD4 (Message Digest) был разработан Ривестом. Размер вырабатываемого хэш-кода -- 128 битов. По заявлениям самого разработчика при создании алгоритма он стремился достичь следующих целей:

• Безопасность. Для построения коллизий не существует алгоритма эффективнее метода "грубой силы" (т. е. метода, основанного на "парадоксе дня рождения").
• Алгоритм построен без использования каких-либо предположительно трудных задач, т. е. его стойкость должна, подобно шифраторам, обеспечиваться его собственной конструкцией.
• Скорость. Алгоритм допускает эффективную программную реализацию на 32-разрядном процессоре.
• Простота и компактность. Алгоритм MD4 не использует сложных структур данных и подпрограмм.
• Алгоритм оптимизирован с точки зрения его реализации на микропроцессорах типа Intel.

Алгоритм MD4 предусматривает:

· дополнение текста до длины, равной 448 бит по модулю 512;

· добавляется длина текста в 64-битном представлении;

· 512-битные блоки подвергаются процедуре Damgard-Merkle[1], причем каждый блок участвует в трех разных циклах.

MD5 является доработанной версией алгоритма MD4. Аналогично MD4, в алгоритме MD5 размер хэш-кода равен 128 битам.

После ряда начальных действий MD5 разбивает текст на блоки длиной 512 битов, которые, в свою очередь, делятся на 16 подблоков по 32 бита. Выходом алгоритма являются 4 блока по 32 бита, конкатенация которых образует 128-битовый хэш-код.

Сначала текст дополняется таким образом, чтобы длина получаемого текста, выраженная в битах, стала на 64 меньше числа, кратного 512. Дополнение осуществляется приписыванием к концу сообщения единицы и затем необходимого числа нулей (в бинарном представлении). Затем к тексту приписывается 64-битовое представление длины исходного сообщения. Таким образом получается текст, длина которого кратна 512 битам.

После некоторой первоначальной обработки МD5 обрабатывает входной текст 512-битовыми блоками, разбитыми на 16 32-битовых подблоков. Выходом алгоритма является набор из четырех 32-битовых блоков, кото­рые объединяются в единое 128-битовое хэш-значение.

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

А = 0x01234567

В = Оx89abcdef

С = Оxfedcba98

D = 0x76543210

Они называются переменными сцепления.

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

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

Главный цикл состоит из четырех очень похожих этапов (у МD4 было только три этапа). На каждом этапе 16 раз используются различные операции. Каждая операция представляет собой нелинейную функцию над тре­мя из а, b, с и d. Затем она добавляет этот результат к четвертой переменной, подблоку текста и константе. Далее результат циклически сдвигается вправо на переменное число битов и добавляет результат к одной из переменных а, b, с и d. Наконец результат заменяет одну из переменных а, b, с и d. См. 13-й и 12-й. Существуют четыре нелинейных функции, используемые по одной в каждой операции (для каждого этапа - другая функция).

Каждый основной цикл состоит из 4 раундов (в MD4 было всего 3 раунда). В свою очередь, каждый раунд состоит из 16 операторов. Все операторы однотипны и имеют вид: . Здесь:

, , и суть , , и в зависимости от номера раунда и номера оператора в раунде (в оригинале эта подстановка записана в явном виде).

обозначает -тый подблок обрабатываемого блока. В каждом раунде порядок обработки очередным оператором подблоков определяется задаваемой в явном виде подстановкой на множестве всех подблоков (их, также как и операторов, 16).

обозначают зафиксированные случайные константы, зависящие от номера раунда и номера оператора в раунде (Ривест положил для -того () оператора в -том () раунде константу равной целой части от .

обозначает левый циклический сдвиг аргумента на битов. Величины сдвигов также зависят от номера раунда и номера оператора в раунде.

-- некоторая функция (фиксированная для каждого раунда), действующая покоординатно на биты своих трех аргументов.

Рис. Основной цикл алгоритма MD5.

Рис. Одна операция МD5

На первом этапе действует функция .

На втором этапе действует функция .

На третьем этапе действует функция .

На четвертом этапе действует функция .

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

Дата добавления: 2014-01-20