Ло Шу - Алгоритм построения цифрового дайджеста MD4
Название: | Алгоритм построения цифрового дайджеста MD4 | |
Автор: | Ло Шу | |
Жанр: | Статьи и рефераты, Самиздат, сетевая литература, Литература ХXI века (эпоха Глобализации экономики), Алгоритмы и структуры данных, Программирование: прочее | |
Изадано в серии: | неизвестно | |
Издательство: | СИ | |
Год издания: | 2002 | |
ISBN: | неизвестно | |
Отзывы: | Комментировать | |
Рейтинг: | ||
Поделись книгой с друзьями! Помощь сайту: донат на оплату сервера |
Краткое содержание книги "Алгоритм построения цифрового дайджеста MD4"
Данная статья предлагает детальный анализ алгоритма построения цифрового дайджеста сообщения MD4. Теория, рассматриваемая в деталях, подкреплена весьма качественными примерами, реализованными на языках Си и Форт.
Читаем онлайн "Алгоритм построения цифрового дайджеста MD4". [Страница - 2]
- 1
- 2
- 3
- 4
- . . .
- последняя (5) »
алгоритм MD4 считается взломанным.
В 1994 году Ван Ооршот и Вейнер оценили стоимость машины для поиска двух
сообщений, приводящих к коллизии, то есть таких, которые генерируют одинаковый
цифровой дайджест методом "грязной силы" для алгоритма MD5 – последователя
алгоритма MD4. Эта оценка показала, что стоимость такой машины составляет 10
миллионов долларов (на 1994 год) и для нахождения коллизирующих сообщений в
среднем требуется 24 дня работы.
4. MD4 процессор
В основе работы алгоритма MD4 лежит преобразование блока данных с
использованием определенных формул. Но для начала посмотрим на внутреннюю
структуру алгоритма как на специализированный процессор, который имеет свои
регистры и операции. Начнем с регистров. На Рисунке 2 представлена внутренняя
структура такого процессора.
MESSAGE POINTER
a
61
MESSAGE LENGTH
3
REGISTER A
REGISTER B
REGISTER C
REGISTER D
NUMBER OF BITS
BLOCK BUFFER
DATA LENGTH
MD4 PROCESSOR
Рисунок 2. Структура MD4 процессора.
b
62
c
63
Два регистра "УКАЗАТЕЛЬ ДАННЫХ" и "РАЗМЕР ДАННЫХ" содержат, соответственно,
указатель на буфер, где находится строка, подлежащая обработке и ее размер в
байтах. На рисунке приведена строка, состоящая из трех символов, поэтому регистр
"РАЗМЕР ДАННЫХ" содержит величину 3.
Регистры A, B, C и D содержат текущий дайджест обрабатываемого блока, а в конце
обработки – цифровой дайджест сообщения. Каждый регистр содержит 32-разрядную
беззнаковую величину, поэтому размер цифрового дайджеста будет равен 32*4=128
бит.
Регистр "РАЗМЕР СООБЩЕНИЯ" хранит размер обрабатываемого сообщения в битах.
Эта величина понадобиться нам на последнем этапе работы алгоритма. Регистр хранит
64-разрядную величину.
Регистровая группа "БЛОЧНЫЙ БУФЕР" предназначена для хранения очередного
блока, подлежащего обработке. Эта группа состоит из 16 регистров с номерами от 0 до
15.
Регистр "БАЙТ В БУФЕРЕ" хранит величину указывающую заполнение регистровой
группы "БЛОЧНЫЙ БУФЕР".
4.1 Базовые операции MD4 процессора
Я начну с рассмотрения трех базовых функций, затем мы рассмотрим три базовых
преобразования, которые выполняет процессор. И в конце мы объединим все это в
операцию преобразования блока данных.
MD4 процессор реализует три базовых логических функции:
1
F(x,y,x) = (x AND y) OR (NOT x AND z)
G(x,y,z) = (x AND y) OR (x AND z) OR (y AND z)
H(x,y,z) = x XOR y XOR z
Таблицы истинности этих логических функций выглядят следующим образом:
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
F
0
1
0
1
0
0
1
1
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
G
0
0
0
1
0
1
1
1
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
H
0
1
1
0
1
0
0
1
Каждая из функций получает на вход три 32-разрядные величины и формирует один
32-разрядный результат.
Здесь подошло время обратиться к исходному коду. В качестве иллюстрации мы будем
использовать исходный код библиотеки OpenSSL (HTTP://www.OpenSSL.ORG). Вот как
реализованы эти функции в этой библиотеке:
#define F(b,c,d) (((b) & (c)) | ((~(b)) & (d)))
#define G(b,c,d) (((b) & (c)) | ((b) & (d)) | ((c) & (d)))
#define H(b,c,d) ((b) ^ (c) ^ (d))
С целью изучения работы этих функций ниже приведен код на языке Форт. Его можно
использовать для того, чтобы посмотреть какой результат получится после применения
1
NOT x AND z = (NOT x) AND z
этих функций к каким-либо данным. (Примечание: если хотите увидеть результат в
двоичном виде, то замените слово HEX на слово BINARY.)
: D-FF-BC ( c b -- x )
?PRINT IF 2DUP CR ." X & Y = " 8 HEX U.R SPACE ." & " 8 HEX U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 HEX U.R THEN
;
: D-FF-~B ( b -- ~b )
?PRINT IF DUP CR ." ~X = ~" 8 HEX U.R THEN
INVERT
?PRINT IF DUP SPACE ." = " 8 HEX U.R THEN
;
: D-FF-~BD ( ~b d -- x )
?PRINT IF 2DUP SWAP CR ." ~X & Z = " 8 HEX U.R SPACE ." & " 8 HEX U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 HEX U.R THEN
;
: D-FF-F ( x1 x2 -- x3 )
?PRINT IF 2DUP SWAP CR ." . | .. = " 8 HEX U.R SPACE ." | " 8 HEX U.R THEN
OR
?PRINT IF DUP SPACE ." = " 8 HEX U.R THEN
;
: D-FF ( b-addr c-addr d-addr -- f )
@ ROT @ ROT @ ( d b c )
OVER ( d b c b )
D-FF-BC ( d b xi )
SWAP ( d xi b )
D-FF-~B ( d xi ~b )
ROT
( xi ~b d )
D-FF-~BD ( xi xii )
D-FF-F ( f )
;
: D-FG-CD ( c d -- x )
?PRINT IF 2DUP CR ." Y & Z = " SWAP 8 U.R SPACE ." & " 8 U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 U.R THEN
;
: D-FG-BD ( d b -- x )
?PRINT IF 2DUP CR ." X & Z = " SWAP 8 U.R SPACE ." & " 8 U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 U.R THEN
;
: D-FG-CDvBD ( cd bd -- x )
?PRINT IF 2DUP CR ." YZ | XZ = " SWAP 8 U.R SPACE ." --">
В 1994 году Ван Ооршот и Вейнер оценили стоимость машины для поиска двух
сообщений, приводящих к коллизии, то есть таких, которые генерируют одинаковый
цифровой дайджест методом "грязной силы" для алгоритма MD5 – последователя
алгоритма MD4. Эта оценка показала, что стоимость такой машины составляет 10
миллионов долларов (на 1994 год) и для нахождения коллизирующих сообщений в
среднем требуется 24 дня работы.
4. MD4 процессор
В основе работы алгоритма MD4 лежит преобразование блока данных с
использованием определенных формул. Но для начала посмотрим на внутреннюю
структуру алгоритма как на специализированный процессор, который имеет свои
регистры и операции. Начнем с регистров. На Рисунке 2 представлена внутренняя
структура такого процессора.
MESSAGE POINTER
a
61
MESSAGE LENGTH
3
REGISTER A
REGISTER B
REGISTER C
REGISTER D
NUMBER OF BITS
BLOCK BUFFER
DATA LENGTH
MD4 PROCESSOR
Рисунок 2. Структура MD4 процессора.
b
62
c
63
Два регистра "УКАЗАТЕЛЬ ДАННЫХ" и "РАЗМЕР ДАННЫХ" содержат, соответственно,
указатель на буфер, где находится строка, подлежащая обработке и ее размер в
байтах. На рисунке приведена строка, состоящая из трех символов, поэтому регистр
"РАЗМЕР ДАННЫХ" содержит величину 3.
Регистры A, B, C и D содержат текущий дайджест обрабатываемого блока, а в конце
обработки – цифровой дайджест сообщения. Каждый регистр содержит 32-разрядную
беззнаковую величину, поэтому размер цифрового дайджеста будет равен 32*4=128
бит.
Регистр "РАЗМЕР СООБЩЕНИЯ" хранит размер обрабатываемого сообщения в битах.
Эта величина понадобиться нам на последнем этапе работы алгоритма. Регистр хранит
64-разрядную величину.
Регистровая группа "БЛОЧНЫЙ БУФЕР" предназначена для хранения очередного
блока, подлежащего обработке. Эта группа состоит из 16 регистров с номерами от 0 до
15.
Регистр "БАЙТ В БУФЕРЕ" хранит величину указывающую заполнение регистровой
группы "БЛОЧНЫЙ БУФЕР".
4.1 Базовые операции MD4 процессора
Я начну с рассмотрения трех базовых функций, затем мы рассмотрим три базовых
преобразования, которые выполняет процессор. И в конце мы объединим все это в
операцию преобразования блока данных.
MD4 процессор реализует три базовых логических функции:
1
F(x,y,x) = (x AND y) OR (NOT x AND z)
G(x,y,z) = (x AND y) OR (x AND z) OR (y AND z)
H(x,y,z) = x XOR y XOR z
Таблицы истинности этих логических функций выглядят следующим образом:
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
F
0
1
0
1
0
0
1
1
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
G
0
0
0
1
0
1
1
1
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
H
0
1
1
0
1
0
0
1
Каждая из функций получает на вход три 32-разрядные величины и формирует один
32-разрядный результат.
Здесь подошло время обратиться к исходному коду. В качестве иллюстрации мы будем
использовать исходный код библиотеки OpenSSL (HTTP://www.OpenSSL.ORG). Вот как
реализованы эти функции в этой библиотеке:
#define F(b,c,d) (((b) & (c)) | ((~(b)) & (d)))
#define G(b,c,d) (((b) & (c)) | ((b) & (d)) | ((c) & (d)))
#define H(b,c,d) ((b) ^ (c) ^ (d))
С целью изучения работы этих функций ниже приведен код на языке Форт. Его можно
использовать для того, чтобы посмотреть какой результат получится после применения
1
NOT x AND z = (NOT x) AND z
этих функций к каким-либо данным. (Примечание: если хотите увидеть результат в
двоичном виде, то замените слово HEX на слово BINARY.)
: D-FF-BC ( c b -- x )
?PRINT IF 2DUP CR ." X & Y = " 8 HEX U.R SPACE ." & " 8 HEX U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 HEX U.R THEN
;
: D-FF-~B ( b -- ~b )
?PRINT IF DUP CR ." ~X = ~" 8 HEX U.R THEN
INVERT
?PRINT IF DUP SPACE ." = " 8 HEX U.R THEN
;
: D-FF-~BD ( ~b d -- x )
?PRINT IF 2DUP SWAP CR ." ~X & Z = " 8 HEX U.R SPACE ." & " 8 HEX U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 HEX U.R THEN
;
: D-FF-F ( x1 x2 -- x3 )
?PRINT IF 2DUP SWAP CR ." . | .. = " 8 HEX U.R SPACE ." | " 8 HEX U.R THEN
OR
?PRINT IF DUP SPACE ." = " 8 HEX U.R THEN
;
: D-FF ( b-addr c-addr d-addr -- f )
@ ROT @ ROT @ ( d b c )
OVER ( d b c b )
D-FF-BC ( d b xi )
SWAP ( d xi b )
D-FF-~B ( d xi ~b )
ROT
( xi ~b d )
D-FF-~BD ( xi xii )
D-FF-F ( f )
;
: D-FG-CD ( c d -- x )
?PRINT IF 2DUP CR ." Y & Z = " SWAP 8 U.R SPACE ." & " 8 U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 U.R THEN
;
: D-FG-BD ( d b -- x )
?PRINT IF 2DUP CR ." X & Z = " SWAP 8 U.R SPACE ." & " 8 U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 U.R THEN
;
: D-FG-CDvBD ( cd bd -- x )
?PRINT IF 2DUP CR ." YZ | XZ = " SWAP 8 U.R SPACE ." --">
- 1
- 2
- 3
- 4
- . . .
- последняя (5) »
Книги схожие с «Алгоритм построения цифрового дайджеста MD4» по жанру, серии, автору или названию:
Автор неизвестен - Адаптивный генетический алгоритм, для распределенных систем с произвольной топологией Жанр: Алгоритмы и структуры данных Год издания: 2021 |
Ло Шу - Алгоритм построения цифрового дайджеста MD5 Жанр: Алгоритмы и структуры данных Год издания: 2003 |