Алгоритм MD4

Алгоритм MD4 является более ранней разработкой того же автора Рона Ривеста. Первоначально данный алгоритм был опубликован в октябре 1990 г., незначительно измененная версия была опубликована в RFC 1320 в апреле 1992 г. Кратко рассмотрим основные цели MD4:

1. Безопасность: это обычное требование к хэш-коду, состоящее в том, чтобы было вычислительно невозможно найти два сообщения, имеющие один и тот же дайджест.

2. Скорость: программная реализация алгоритма должна выполняться достаточно быстро. В частности, алгоритм должен быть достаточно быстрым на 32-битной архитектуре. Поэтому алгоритм основан на простом множестве элементарных операций над 32-битными словами.

3. Простота и компактность: алгоритм должен быть простым в описании и простым в программировании, без больших программ или подстановочных таблиц. Эти характеристики не только имеют очевидные программные преимущества, но и желательны с точки зрения безопасности, потому что для анализа возможных слабых мест лучше иметь простой алгоритм.

4. Желательна little- endian архитектура: некоторые архитектуры процессоров (такие как линия Intel 80xxx) хранят левые байты слова в позиции младших адресов байта (little- endian). Другие (такие как SUN Sparcstation) хранят правые байты слова в позиции младших адресов байта (big endian). Это различие важно, когда сообщение трактуется как последовательность 32-битовых слов, потому что эти архитектуры имеют инверсное представление байтов в каждом слове. Ривест выбрал использование схемы little- endian для интерпретации сообщения в качестве последовательности 32-битных слов. Этот выбор сделан потому, что big- endian процессоры обычно являются более быстрыми.

Эти цели преследовались и при разработке MD5. MD5 является более сложным и, следовательно, более медленным при выполнении, чем MD4. Считается, что добавление сложности оправдывается возрастанием уровня безопасности. Главные различия между этими двумя алгоритмами состоят в следующем:

1. MD4 использует три цикла из 16 шагов каждый, в то время как MD5 использует четыре цикла из 16 шагов каждый.

2. В MD4 дополнительная константа в первом цикле не применяется. Аналогичная дополнительная константа используется для каждого из шагов во втором цикле. Другая дополнительная константа используется для каждого из шагов в третьем цикле. В MD5 различные дополнительные константы, Т [i], применяются для каждого из 64 шагов.

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

4. В MD5 на каждом шаге текущий результат складывается с результатом предыдущего шага. Например, результатом первого шага является измененное слово А. Результат второго шага хранится в D и образуется добавлением А к циклически сдвинутому влево на определенное число бит результату элементарной функции. Аналогично, результат третьего шага хранится в С и образуется добавлением D к циклически сдвинутому влево результату элементарной функции. MD4 это последнее сложение не включает.