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
The MD4 Message-Digest Algorithm
Статус документа
Этот документ содержит информацию для сообщества Internet. Документ не задает каких-либо стандартов. Разрешается свободное распространение документа.
Благодарности
Автор благодарит Don Coppersmith, Burt Kaliski, Ralph Merkle и Noam Nisan за множество полезных комментариев и предложений.
Оглавление
1. Введение ................................................................................................................................................................................ ...... .................... 1
2. Термины и обозначения ........................................................................................................................................................................... ..2...
3. Описание алгоритма MD4 .................................................................................................................................................... ..... ... ................. 2
3.1 Этап 1. Добавление битов заполнения ............................................................................................................................ .................. 2
3.2 Этап 2. Добавление размера сообщения ............................................................................................................................. .............. 2
3.3 Этап 3. Инициализация буфера MD .................................................................................................................................................. 2...
3.4 Этап 4. Обработка сообщения блоками по 16 слов ......................................................................................................................... 2...
3.5 Этап 5. Вывод .................................................................................................................................................................................... ....4...
4. Заключение ............................................................................................................................................................................................... ...4...
Литература ....................................................................................................................................................................................................... 4...
Приложение A – Пример реализации ..................................................................................................................................................... ...... 4
A.1 global.h ........................................................................................................................................................................... ..... .... ................ 4
A.2 md4.h ..................................................................................................................................................................................... .. ............... 5
A.3 md4c.c ................................................................................................................................................................................................ ..5...
A.4 mddriver.c ..................................................................................................................................................................................... .. ....... 9
A.5 Тестовый набор .............................................................................................................................................................................. ..1..2...
Security Considerations ........................................................................................................................................................ ....... ....................... 12
Адрес автора ...................................................................................................................................................................................... ............. 12
1. Введение
В этом документе описывается алгоритм цифровых подписей1 MD4. Этот алгоритм принимает на входе сообщение произвольного размера и выдает в результате 128-битовый “отпечаток” ("fingerprint") или цифровую подпись ("message digest"). Предполагается, что потребуется нереальный объем вычислений для создания двух сообщений, цифровые подписи которых совпадут, или подбора сообщения по имеющейся цифровой подписи. Алгоритм MD4 предназначен для создания цифровой подписи (сигнатуры), когда требуется безопасно “сжать” большой файл перед тем, как шифровать его с использованием закрытого (секретного) ключа в системах с открытыми ключами типа RSA.
Алгоритм MD4 разработан для обеспечения достаточной скорости на 32-битовых машинах. В дополнение к этому MD4 не требует использования больших таблиц подстановки; кодирование алгоритма может быть достаточно компактным.
Алгоритм MD4 открыт для обозрения (public domain) и возможно будет адаптирован в качестве стандартного.
Данный документ заменяет выпущенный в октябре 1990 документ RFC 1186 [2]. Основное отличие между документами заключается в том, что представленный здесь вариант реализации MD4 является более переносимым.
Для приложений OSI идентификатор объекта MD4 имеет форму
md4 OBJECT IDENTIFIER ::= {iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2)
4}
В идентификаторе типа X.509 (AlgorithmIdentifier [3]) параметры для MD4 должны иметь тип NULL.
2. Термины и обозначения
В этом документе термин “слово” (word) используется для 32-битовых значений, а “байт” - для восьмибитовых. Последовательности битов могут интерпретироваться естественным путем как последовательность байтов, в которой каждая группа из 8 последовательных битов интерпретируется как байт, в котором старший (наиболее значимый) бит располагается
1message-digest algorithm
rfc.com.ru
rfc.com.ru
Перевод RFC 1320
первым. Подобно этому последовательность байтов может интерпретироваться как последовательность 32-битовых слов, в которой каждая группа из 4 последовательных байтов интерпретируется как слово, где младший (наименее значимый) указывается первым.
Запись x_i означает x i-ое (x[i]). Если индекс представляет собой выражение, оно будет заключаться в фигурные скобки x_{i+1}. Символ ^ используется для обозначения степени (экспонента) - x^i означает x в степени i.
Символ "+" обозначает сложение слов (т. е., сложение с использованием модуля 2^32). Запись X <<< s означает 32-битовое слово, полученное циклическим сдвигом X влево на s позиций. not(X) означает побитовое дополнение X, а X v Y побитовую операцию X OR Y (X ИЛИ Y). Запись X xor Y означает побитовую операцию X XOR Y (исключающее ИЛИ), а XY побитовую операцию X AND Y (X И Y).
3. Описание алгоритма MD4
Начнем с допущения о наличии на входе сообщения размером b битов, для которого нужно создать цифровую подпись. Здесь b означает неотрицательное целое число; b может принимать нулевое значение и не обязано быть кратным 8; это значение может быть неограниченно большим. Биты исходного сообщения будем представлять следующим образом:
m_0 m_1 ... m_{b-1}
Для создания цифровой подписи выполняется процесс из 5 описанных ниже этапов.
3.1 Этап 1. Добавление битов заполнения
Сообщение дополняется (padded) до размера, конгруэнтного 448 по модулю 512. Т. е., размер сообщения устанавливается таким, чтобы после добавления 64 битов размер был кратен 512. Заполнение производится во всех случаях, даже если размер исходного сообщения конгруэнтен 448 по модулю 512.
Заполнение происходит следующим образом: сначала в конце сообщения добавляется один бит, имеющий значение "1", а потом добавляются биты, имеющие значение "0" до размера, конгруэнтного 448 по модулю 512. В любом случае число добавляемых битов не может быть меньше 1 м больше 512.
3.2 Этап 2. Добавление размера сообщения
64-битовое представление b (размер исходного сообщения в битах) добавляется в конец результата предыдущего этапа. В редких случаях, когда b больше 2^64, используются только младшие 64 бита значения b. Биты добавляются в конце как два 32-битовых слова, в которых младший байт размещается в начале, как было условлено выше).
После этого размер полученного сообщения (исходное сообщение + заполнение + размер) будет кратен 512 битам. Следовательно,результирующее сообщение будет содержать целое число блоков по 16 слов (32 бита в каждом слове). Пусть M [0 ... N-1] обозначает слова полученного в результате сообщения; значение N кратно 16.
3.3 Этап 3. Инициализация буфера MD
Для расчета цифровой подписи используется буфер на 4 слова (A,B,C,D). каждое из слов A, B, C, D представляет собой 32-битовый регистр. Эти регистры инициализируются приведенными ниже значениями (шестнадцатеричное представление, сначала младший байт):
слово A слово B слово C слово D
01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 10
3.4 Этап 4. Обработка сообщения блоками по 16 слов
Сначала определим три дополнительных функции, каждая из которых принимает три 32-битовых слова в качестве аргументов и возвращает одно 32-битовое слово.
F(X,Y,Z) = XY v not(X) Z G(X,Y,Z) = XZ v Y not(Z) H(X,Y,Z) = X xor Y xor Z
Для каждого бита функция F работает как условие – если X, то Y, иначе Z. Функцию F можно определить с использованием сложения (+) вместо операции ИЛИ (v), поскольку XY и not(X)Z никогда не будут давать 1 в одной битовой позиции. Для каждой битовой позиции G работает как мажоритарная функция – если хотя бы один из битов X, Y, Z имеет значение 1, G будет устанавливать значение 1 для соответствующего бита результата, в противном случая G будет устанавливать 0. Интересно отметить, что при условии, когда биты X, Y и Z независимы и не образованы смещением (unbiased), каждый бит функции G (X,Y,Z) будет независимым и не будет образован смещением. Функция H представляет собой побитовую операцию “исключающее ИЛИ” (xor) или функцию “четности” (parity) переданных ей аргументов; свойства этой функции подобны свойствам F и G.
Ниже показана обработка блоков сообщения.
/* обработать каждый блок из 16 слов. */ For i = 0 to N/16-1 do
/* скопировать блок i в X. */ For j = 0 to 15 do
Set X[j] to M[i*16+j]. end /* цикл по j */
/* сохранить A как AA, B как BB, C как CC, D как DD. */ AA = A BB = B CC = C DD = D
rfc.com.ru                                                                                     2                                                            rfc.com.ru
Перевод RFC 1320
/* Круг 1. */
/* [abcd k s] обозначает операцию a = (a + F(b,c,d) + X[k]) <<< s. */
/* Выполним следующие 16 операций. */
[ABCD 0 3] [DABC 1 7]
[ABCD 4 3] [DABC 5 7]
[ABCD 8 3] [DABC 9 7]
[ABCD 12 3] [DABC 13 7]
[CDAB
2
11]
[BCDA
3
19]
[CDAB
6
11]
[BCDA
7
19]
[CDAB
10
11]
[BCDA
11
19]
[CDAB
14
11]
[BCDA
15
19]
/* Круг 2. */
/* [abcd k s] обозначает операцию a = (a + G(b,c,d) + X[k] + 5A827999) <<< s). */
/* Выполним следующие 16 операций.
[ABCD 0 3] [DABC 4 5] [CDAB
[ABCD 1 3] [DABC 5 5] [CDAB
[ABCD 2 3] [DABC 6 5] [CDAB 10
[ABCD 3 3] [DABC 7 5] [CDAB 11
*/
8
9]
[BCDA
12
13]
9
9]
[BCDA
13
13]
0
9]
[BCDA
14
13]
1
9]
[BCDA
15
13]
/* Круг 3. */
/* [abcd k s] обозначает операцию a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s). */
/* Выполним следующие 16 операций. */
[ABCD 0 3] [DABC 8 9] [CDAB
[ABCD 2 3] [DABC 10 9] [CDAB
[ABCD 1 3] [DABC 9 9] [CDAB
[ABCD 3 3] [DABC 11 9] [CDAB
4
11]
[BCDA
12
15]
6
11]
[BCDA
14
15]
5
11]
[BCDA
13
15]
7
11]
[BCDA
15
15]
/* После этого добавим к каждому из 4 регистров значение, которое этот регистр имел до
начала выполнения этого блока. */ A = A + AA B = B + BB C = C + CC D = D + DD end /* цикл по i */
Примечание. Значение 5A..99 является шестнадцатеричной 32-битовой константой, записанной начиная со старшего бита. Эта константа представляет собой квадратный корень и 2. Восьмеричное значение этой константы равно 013240474631.
Значение 6E..A1 является шестнадцатеричной 32-битовой константой, записанной начиная со старшего бита. Эта константа представляет собой квадратный корень и 3. Восьмеричное значение этой константы равно 015666365641.
См. книгу Knuth, The Art of Programming, Volume 2 (Seminumerical Algorithms), Second Edition (1981), Addison-Wesley. Table 2, page 660.
Ниже показана обработка блоков сообщения.
/* обработать каждый блок из 16 слов. */ For i = 0 to N/16-1 do
/* скопировать блок i в X. */ For j = 0 to 15 do
Set X[j] to M[i*16+j]. end /* цикл по j */
/* сохранить A как AA, B как BB, C как CC, D как DD. */ AA = A BB = B CC = C DD = D
/* Круг 1. */
/* [abcd k s i] обозначает операцию a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Выполним следующие 16 операций. */
[ABCD
0
7
1]
[DABC
1
12
2]
[ABCD
4
7
5]
[DABC
5
12
6]
[ABCD
8
7
9]
[DABC
9
12
10]
[ABCD
12
7
13]
[DABC
13
12
14]
[CDAB 2
[CDAB 6
17
3]
[BCDA
3
22
4]
17
7]
[BCDA
7
22
8]
17
11]
[BCDA
11
22
12]
17
15]
[BCDA
15
22
16]
/* Круг 2. */
/* [abcd k s i] обозначает операцию a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Выполним следующие 16 операций. */
[ABCD
1
5 17]
[DABC 6
9 18]
[ABCD
5
5 21]
[DABC 10
9 22]
[ABCD
9
5 25]
[DABC 14
9 26]
[ABCD
13
5 29]
[DABC 2
9 30]
[CDAB 11 14
[CDAB 15 14
[CDAB 3
14
19]
[BCDA
0
20
20]
14
23]
[BCDA
4
20
24]
14
27]
[BCDA
8
20
28]
[CDAB 7 14 31] [BCDA 12 20 32]
/* Круг 3. */
/* [abcd k s t] обозначает операцию a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Выполним следующие 16 операций. */
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
rfc.com.ru
3
rfc.com.ru
Перевод RFC 1320
[ABCD 13 4 41] [DABC 0 11 42] [ABCD 9 4 45] [DABC 12 11 46]
/* Круг 4. */
/* [abcd k s t]  обозначает операцию
/* Выполним следующие 16 операций.
[ABCD 0 6 49]    [DABC 7 10 50]
[ABCD 12 6 53]    [DABC 3 10 54]
[ABCD 8 6 57]    [DABC 15 10 58]
[ABCD 4 6 61]    [DABC 11 10 62]
[CDAB 3 16 43]
[BCDA 6 23 44]
[CDAB 15 16 47]
[BCDA 2 23 48]
ю a = b + ((a + */ [CDAB 14 15 51]
I(b,c,d) + X[k] + T[i]) <<< s) .
[BCDA 5 21 52]
[CDAB 10 15 55]
[BCDA 1 21 56]
[CDAB 6 15 59]
[BCDA 13 21 60]
[CDAB 2 15 63]
[BCDA 9 21 64]
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* После этого добавим к каждому из 4 регистров значение, которое этот регистр имел до
начала выполнения этого блока. */ A = A + AA B = B + BB C = C + CC D = D + DD end /* цикл по i */
3.5 Этап 5. Вывод
Сигнатура сообщения выводится как A, B, C, D (т. е., мы начинаем вывод с младшего байта A и закачиваем старшим байтом D). На этом описание алгоритма MD4 завершается. Пример реализации на языке C дан в приложении.
4. Заключение
Алгоритм цифровых подписей MD4 прост в реализации и создает “отпечатки” (fingerprint) или цифровые подписи для сообщений произвольной длины. Предполагается, что для создания двух сообщений с одинаковыми сигнатурами потребуется порядка 2^64 операций, а для подбора сообщения по имеющейся сигнатуре – порядка 2^128 операция. Алгоритм MD4 был тщательно исследован на предмет поиска слабых мест. Однако алгоритм является достаточно новым и требуется дополнительный анализ, как и для всех новинок этого типа.
Литература
[1] Rivest, R., "The MD4 message digest algorithm", in A.J. Menezes and S.A. Vanstone, editors, Advances in Cryptology - CRYPTO '90 Proceedings, pages 303-311, Springer-Verlag, 1991.
[2] Rivest, R., "The MD4 Message Digest Algorithm", RFC 1186, MIT, October 1990.
[3] CCITT Recommendation X.509 (1988), "The Directory - Authentication Framework".