Ло Шу - Алгоритм построения цифрового дайджеста MD4

Алгоритм построения цифрового дайджеста
MD4
Данная статья предлагает детальный анализ алгоритма построения цифрового
дайджеста сообщения MD4. Теория, рассматриваемая в деталях, подкреплена
весьма качественными примерами, реализованными на языках Си и Форт.

1. Введение
Язык программирования Си наиболее распространенный из языков на сегодняшний
день. Но, как оказалось, в процессе написания статьи мне необходимо было выполнять
некие вычисления. Язык Форт оказался здесь незаменимым помощником, он дал
возможность создавать код, глубже вникать в алгоритм во время его реализации и
выполнять этот алгоритм по шагам в интерактивном режиме. Лучше инструмента найти
я не смог. Я использовал WinForth32, который можно бесплатно загрузить с адреса
FTP://FTP.Taygeta.COM/pub/Forth/Compilers/Native/windows/Win32For/W32for42.exe
Для тех, кто хочет познакомиться с Фортом поближе, я рекомендую посетить сайты
HTTP://www.Forth.ORG и HTTP://www.Forth.ORG.RU.
Алгоритм MD4 это один из алгоритмов целого семейства, в этом семействе существует
еще два алгоритма – MD2 и MD5. Но MD2 довольно старый алгоритм и сейчас
практически не используется, а MD5 это следующий шаг после MD4, и в его основе
лежит все тот же MD4. Поэтому я принял решение начать с более простого алгоритма,
чтобы построить фундамент для понимания современных алгоритмов построения
цифровых дайджестов.

2. Цифровой дайджест
Я прелагаю начать знакомство с цифровыми дайджестами с его определения, взятого
из компьютерного словаря. Одно из определений звучит следующим образом:
"Цифровой дайджест – это представление текста в виде строки цифр, построенной с
использованием формулы, называемой односторонней хэш функцией. Шифрование
цифрового дайджеста с помощью закрытого ключа создает цифровую подпись, которая
представляет собой электронный вид аутентификации." И, наверное, будет неплохо
привести пример. Вот цифровой дайджест строки "MD4" и файла WinWord.EXE
построенный с помощью программы, взятой из документа RFC 1320:
MD4(MD4) = 9af4a3d5f2dfb4b6851b265b46fbeff3
MD4(WinWord.EXE) = 595452c1c9c3008273d83ad32cc8de16
Прошу заметить, что цифровой дайджест для файла WinWord.EXE будет отличаться
для различных версий этого файла. Я строил дайджест для WinWord.EXE с
характеристиками, представленными на Рисунке 1.

Рисунок 1. Диалоговое окно со свойствами фала WinWord.EXE.
Для начала освежим в памяти, что такое хэш. Хэш - это численная величина,
полученная из текстовой строки. Эта величина существенно меньше, чем сама
текстовая строка. Хэш строится с помощью одностороннего преобразования, или
односторонней функции. Особенность этого преобразования заключается в том, что
вероятность генерации одинакового хеш-значения для двух различных строк крайне
низка. Процесс получения такой числовой величины из текстовой строки называется
хэшированием. Хэширование играет большую роль в системах безопасности, где оно
используется для того, чтобы удостовериться, что переданное сообщение не было
подделано. Отправитель строит хэш сообщение, шифрует его и отправляет вместе с
сообщением (также зашифрованным). Получатель дешифрует сообщение и хэш,
строит новый хэш для дешифрованного сообщения и сравнивает его с полученным.
Если они одинаковы, то вероятность того, что сообщение пришло без изменений очень
высока. "Односторонняя" обозначает, что практически невозможно воспроизвести
исходную текстовую строку на основании ее хэш значения. "Практически невозможно" в
свою очередь обозначает, что для нахождения такой строки потребуется
вычислительный ресурс недостижимой на данный момент мощности из-за
ограниченности современных технологий, а также то, что время нахождения такой
строки с использованием современных вычислительных ресурсов настолько велико
(может измеряться годами), что даже если такая строка будет найдена, то ее
информационный смысл уже утратит свою значимость.

3. Немного истории
Немного истории, конечно же, не помешает. Алгоритм MD4 был спроектирован
профессором Ривестом из Массачусетского Технологического Института Соединенных
Штатов Америки в 1990 году и является последователем алгоритма MD2. Этот
алгоритм оптимизирован для быстрого построения цифрового дайджеста сообщения на
32-разрядных машинах. Описание алгоритма и пример реализации может быть найден
в документе RFC 1320, перевод которого приведен в Приложении к этой статье. На
сегодняшний день --">