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

работы реализаций алгоритма MD4

127

118

109

100

91

82

73

64

55

46

37

28

19

10

1

0

Скорость работы в зависимости от размера буфера
140000
120000
100000
80000

RFC
OpenSSL

60000
40000
20000
0

Размер буфера, байт
Рисунок 10. Пропускная способность реализаций алгоритма MD4
Измерения производились на компьютере с процессором Intel Pentium III, работающем
на частоте 750 МГц. Оценка производилась на основании построения цифрового
дайджеста 10000 раз для сообщения размером 10000 байт.
На основании этих двух графиков можно сделать следующие выводы:
- реализация алгоритма в библиотеке OpenSSL более эффективна;
- оптимальными для использования являются буферы с размерами кратными 64,
то есть размеру внутреннего БЛОЧНОГО БУФЕРА;
- существуют некие другие размеры буфера, дающие увеличение пропускной
способности;
- время работы реализации OpenSSL для буфера размером 64 байта составляет
0.891 секунды, для буфера размером 128 байт – 0.781 секунды;
- пропускная способность реализации OpenSSL для буфера размером 64 байта
составляет 109602 килобайта в секунду (= 107 МБ/сек), для буфера размером
128 байт – 125040 килобайта в секунду (= 122 МБ/сек).
При использовании библиотеки OpenSSL выбирайте размер буфера кратный 64!

9. Резюме
Мы рассмотрели работу алгоритма построения цифрового дайджеста MD4. Этот
алгоритм лежит в основе большинства основных методов построения цифровых
дайджестов и теперь читателю будет несложно понять их работу. В следующей статье
мы рассмотрим алгоритм построения цифрового дайджеста MD5, который широко
используется сегодня. Мы коснемся математических вопросов для более глубокого
понимания того, как и почему строится дайджест и почему его сложно "сломать". Также
я постараюсь осветить вопросы криптоанализа и криптографических атак. До
следующей встречи.

Редакция 3 от 24 сентября 2002 года
Ло Шу (LoShu_LoShu@Yahoo.COM, LoShu_LoShu@HotMail.COM).

Приложение А. RFC 1320

Network Working Group
Request for Comments: 1320
Obsoletes: RFC 1186

R. Rivest
MIT Laboratory for Computer Science
and RSA Data Security, Inc.
April 1992

Алгоритм построения цифрового дайджеста
сообщения MD4
Статус данного документа
Данный документ предлагает информацию для рассмотрения сообществом Интернет.
Документ не определяет стандарт Интернет. Распространение данного документа не
ограничено.

Благодарности
Мы хотели бы выразить благодарность Дону Копперсмиту (Don Coppersmith), Бурту
Калиски (Burt Kaliski), Ральфу Мерклу (Ralph Merkle) и Ноаму Нисану (Noam Nisan) за их
многочисленные важные комментарии, замечания и предложения.

1. Краткое содержание
Этот документ описывает алгоритм построения цифрового дайджеста MD4 [1].
Алгоритм получает в качестве исходных данных сообщение произвольной длины и в
результате своей работы формирует 128-битовый "отпечаток" или "цифровой
дайджест" входного сообщения. Предполагается, что вычислительными средствами
невозможно построить два сообщения, которые имеют одинаковые цифровые
дайджесты, или построить сообщение с заданным цифровым дайджестом. Алгоритм
MD4 предназначается для приложений, требующих использования цифровых
подписей, в которых большие файлы должны быть "сжаты" безопасным способом
перед тем как они будут зашифрованы приватным (секретным) ключом с
использованием таких общественных криптосистем, как, например, RSA.
Алгоритм MD4 спроектирован таким образом, чтобы быть достаточно быстрым на 32разрядных машинах. В дополнение к этому, алгоритм MD4 не требует никаких больших
таблиц подстановки; алгоритм может быть достаточно компактно закодирован.
Алгоритм MD4 предложен для обзора общественности и возможной адаптации его в
качестве стандарта.
Этот документ замещает RFC 1186 от октября 1990 года. Основное различие состоит в
том, что реализация алгоритма MD4, приведенная в Приложении В, является более
переносимой.

Для приложений, поддерживающих стандарт OSI, идентификатор объекта MD4 имеет
вид
md4 OBJECT IDENTIFIER ::=
{iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 4}
В типе AlgorithmIdentifier [3] из X.509, параметры для MD4 должны иметь тип NULL.

2. Терминология и нотация
В этом документе "слово" обозначает 32-разрядная величина, а "байт" это 8-разрядная
величина. Последовательность бит может быть интерпретирована естественным
образом как последовательность байт, где каждая последующая группа из восьми бит
интерпретируется как --">