КулЛиб - Классная библиотека! Скачать книги бесплатно
Всего книг - 706312 томов
Объем библиотеки - 1349 Гб.
Всего авторов - 272773
Пользователей - 124661

Последние комментарии

Новое на форуме

Новое в блогах

Впечатления

DXBCKT про Калюжный: Страна Тюрягия (Публицистика)

Лет 10 назад, случайно увидев у кого-то на полке данную книгу — прочел не отрываясь... Сейчас же (по дикому стечению обстоятельств) эта книга вновь очутилась у меня в руках... С одной стороны — я не особо много помню, из прошлого прочтения (кроме единственного ощущения что «там» оказывается еще хреновей, чем я предполагал в своих худших размышлениях), с другой — книга порой так сильно перегружена цифрами (статистикой, нормативами,

  подробнее ...

Рейтинг: 0 ( 0 за, 0 против).
DXBCKT про Миронов: Много шума из никогда (Альтернативная история)

Имел тут глупость (впрочем как и прежде) купить том — не уточнив сперва его хронологию... В итоге же (кто бы сомневался) это оказалась естественно ВТОРАЯ часть данного цикла (а первой «в наличии нет и даже не планировалось»). Первую часть я честно пытался купить, но после долгих и безуспешных поисков недостающего - все же «плюнул» и решил прочесть ее «не на бумаге». В конце концов, так ли уж важен носитель, ведь главное - что бы «содержание

  подробнее ...

Рейтинг: 0 ( 0 за, 0 против).
DXBCKT про Москаленко: Малой. Книга 2 (Космическая фантастика)

Часть вторая (как и первая) так же была прослушана в формате аудио-версии буквально «влет»... Продолжение сюжета на сей раз открывает нам новую «локацию» (поселок). Здесь наш ГГ после «недолгих раздумий» и останется «куковать» в качестве младшего помошника подносчика запчастей))

Нет конечно, и здесь есть место «поиску хабара» на свалке и заумным диалогам (ворчливых стариков), и битвой с «контролерской мышью» (и всей крысиной шоблой

  подробнее ...

Рейтинг: 0 ( 0 за, 0 против).
iv4f3dorov про Соловьёв: Барин 2 (Альтернативная история)

Какая то бредятина. Писал "искусственный интеллект" - жертва перестройки, болонского процесса, ЕГЭ.

Рейтинг: 0 ( 0 за, 0 против).
iv4f3dorov про Соловьёв: Барин (Попаданцы)

Какая то бредятина. Писал "искусственный интеллект" - жертва перестройки, болонского процесса, ЕГЭ.

Рейтинг: +1 ( 1 за, 0 против).

Алгоритм построения цифрового дайджеста MD5 [Ло Шу] (pdf) читать онлайн

Книга в формате pdf! Изображения и текст могут не отображаться!


 [Настройки текста]  [Cбросить фильтры]

Алгоритм построения цифрового
дайджеста MD5
Введение
Данная статья продолжает рассмотрение алгоритмов построения цифрового дайджеста
сообщения и содержит информацию об алгоритме MD5. По-прежнему, предполагается,
что читатель знаком с языками программирования Си и Форт. Смотрите статью
"Алгоритм построения цифрового дайджеста MD4" в предыдущем номере журнала.

Цифровой дайджест MD5
В том же 1991 году, когда был создан алгоритм построения цифрового дайджеста MD4,
профессором Ривестом был предложен другой алгоритм – MD5, "старший" и более
сильный брат алгоритма MD4 (почему "старший" мы узнаем чуть позже). Он во многом
похож на своего собрата и поэтому нам будет гораздо легче понять как он работает, так
как мы уже в деталях знаем как работает MD4.
Здесь я тоже начну с примера. Итак, цифровой дайджест строки символов и файла:
MD5("MD5") = 7F138A09169B250E9DCB378140907378
MD5(WinWord.EXE) = B9D86A2E86028000B500B498FE71C299
Длина цифрового дайджеста MD5 составляет 16 байт или 16*8 = 128 бит.

MD5 процессор
MD5 процессор состоит из набора следующих регистров. Прежде всего это регистры A,
B, C и D, которые содержат промежуточный результат вычисления цифрового
дайджеста. "БЛОЧНЫЙ БУФЕР" MD5 процессора содержит 16 32-разрядных слов, в этом
буфере формируется очередной блок для построения очередного промежуточного
результата. Регистр "БАЙТ В БУФЕРЕ" содержит число, определяющее количество байт
в "БЛОЧНОМ БУФЕРЕ" на этапе его формирования, или заполнения. Регистр "РАЗМЕР
СООБЩЕНИЯ" содержит полный размер исходного сообщения, для которого строиться
цифровой дайджест, в битах; эта величина будет добавлена в конец исходного
сообщения на финальном этапе формирования цифрового дайджеста. Регистры
"УКАЗАТЕЛЬ ДАННЫХ" и "РАЗМЕР ДАННЫХ" содержат, соответственно, указатель на
текущий обрабатываемый пакет данных и его размер.
Структура MD5 процессора изображена графически на Рисунке 1.

УКАЗАТЕЛЬ ДАННЫХ
РАЗМЕР ДАННЫХ
РЕГИСТР A
РЕГИСТР B
РЕГИСТР C
РЕГИСТР D
РАЗМЕР СООБЩЕНИЯ

БЛОЧНЫЙ БУФЕР

БАЙТ В БУФЕРЕ

СТРУКТУРА MD5 ПРОЦЕССОРА

Рисунок 1. Структура MD5 процессора.
Операция инициализации процессора приводи его в определенное начальное
состояние, то есть во все регистры помещаются определенные начальные значения.
Эти значения диктуются документом RFC 1321. После инициализации MD5 процессор
выглядит следующим образом:

NULL

УКАЗАТЕЛЬ ДАННЫХ

0

РАЗМЕР ДАННЫХ
РЕГИСТР A

67452301

РЕГИСТР B

EFCDAB89

РЕГИСТР C

98BADCFE

РЕГИСТР D

10325476
00000000 00000000 [0]

РАЗМЕР СООБЩЕНИЯ

00000000
БЛОЧНЫЙ БУФЕР

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

00000000

БАЙТ В БУФЕРЕ

ИНИЦИАЛИЗАЦИЯ MD5 ПРОЦЕССОРА

Рисунок 3. Состояние MD5 процессора после инициализации.
В качестве маленького итога, можно сказать, что MD5 процессор по своей структуре не
отличается от MD4 процессора. Они даже сходны по своей процедуре инициализации.

Базовые операции
Цифровой дайджест MD5 определяет четыре базовые логические функции, которые
используются в операции преобразования блока данных. Вот они:
F(x,y,z) = (x AND y) OR (NOT x AND z)1
G(x,y,z) = (x AND z) OR (y AND NOT z)2
H(x,y,z) = x XOR y XOR z
I(x,y,z) = y XOR (x OR NOT z)3
И таблицы истинности этих функций:
x
0
0
0
0
1
1
2
3

y
0
0
1
1
0

z
0
1
0
1
0

F
0
1
0
1
0

x
0
0
0
0
1

y
0
0
1
1
0

NOT x AND z = (NOT x) AND z
y AND NOT z = y AND (NOT z)
x OR NOT z = x OR (NOT z)

Z
0
1
0
1
0

G
0
0
1
0
0

X
0
0
0
0
1

y
0
0
1
1
0

z
0
1
0
1
0

H
0
1
1
0
1

x
0
0
0
0
1

y
0
0
1
1
0

z
0
1
0
1
0

I
1
0
0
1
1

1
1
1

0
1
1

1
0
1

0
1
1

1
1
1

0
1
1

1
0
1

1
1
1

1
1
1

0
1
1

1
0
1

0
0
1

1
1
1

0
1
1

1
0
1

1
0
0

На языке программирования Си эти логические функции могут быть записаны
следующим образом:

#define
#define
#define
#define

F(x,y,z)
G(x,y,z)
H(x,y,z)
I(x,y,z)

((x & y) | (~x & z))
((x & z) | (y & ~z))
(x ^ y ^ z)
(y ^ (x | ~z))

Библиотека OpenSSL применяет несколько другие обозначения и использует
оптимизацию! Логические функции можно преобразовать и уменьшить количество
операций, требуемых для их вычисления:

#define
#define
#define
#define

F(b,c,d)
G(b,c,d)
H(b,c,d)
I(b,c,d)

((((c) ^ (d)) & (b)) ^ (d))
((((b) ^ (c)) & (d)) ^ (c))
((b) ^ (c) ^ (d))
(((~(d)) | (b)) ^ (c))

Здесь используется тот факт, что (x AND y) OR (NOT x AND z) = ((y XOR z) AND z) XOR z.
То есть мы имеем на одну логическую операцию меньше. Сравните: в первом случае –
AND, OR, NOT, AND, и во втором случае – XOR, AND, XOR. Как увидим дальше, экономия
в одну операцию будет существенной во время преобразования блока данных.
Как и прежде для исследования поведения этих операций я использовал язык FORTH и
его реализацию WinForth32. Вот как выглядят приведенные выше логические операции
на Форте с выводом промежуточных результатов
\
:
\
:

-------------------------------------------------------------------------.= ( x -- x ) ?PRINT IF DUP SPACE ." = " 8 HEX U.R THEN ;
-------------------------------------------------------------------------D-FF-BC ( c b -- x )
?PRINT IF 2DUP CR ." X & Y = " 8 HEX U.R SPACE ." & " 8 HEX U.R THEN
AND .=
;
: D-FF-~B ( b -- ~b )
?PRINT IF DUP CR ." ~X = ~" 8 HEX U.R THEN
INVERT .=
;
: D-FF-~BD ( ~b d -- x )
?PRINT IF 2DUP SWAP CR ." ~X & Z = " 8 HEX U.R SPACE ." & " 8 HEX U.R
THEN
AND .=
;
: D-FF-F ( x1 x2 -- x3 )
?PRINT IF 2DUP SWAP CR ." . | .. = " 8 HEX U.R SPACE ." | " 8 HEX U.R
THEN
OR .=
;
: 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-~D ( d -- ~d )
?PRINT IF DUP CR ." ~Z = ~" 8 HEX U.R THEN
INVERT .=
;
D-FG-~DC ( ~d c -- x )
?PRINT IF 2DUP CR ." Y & ~Z = " 8 U.R SPACE ." & " 8 U.R THEN
AND .=
;
D-FG-BD ( b d -- x )
?PRINT IF 2DUP CR ." X & Z = " SWAP 8 U.R SPACE ." & " 8 U.R THEN
AND .=
;
D-FG-BDv~DC ( bd ~dc -- x )
?PRINT IF 2DUP CR ." XZ | ~ZY = " SWAP 8 U.R SPACE ." | " 8 U.R THEN
OR .=
;
D-FG ( b-addr c-addr d-addr -- g )
@ ROT @ ROT @ ROT ( b c d )
DUP
( b c d d )
D-FG-~D
( b c d xi )
ROT
( b d xi c )
D-FG-~DC
( b d xii )
-ROT
( xii b d )
D-FG-BD
( xii xiii )
D-FG-BDv~DC ( g )
;
-------------------------------------------------------------------------D-FH-B^C ( b c -- x )
?PRINT IF 2DUP CR ." X ^ Y = " SWAP 8 U.R SPACE ." ^ " 8 U.R THEN
XOR .=
;
D-FH-^D ( d x1 -- x2 )
?PRINT IF 2DUP CR ." . ^ Z = " 8 U.R SPACE ." ^ " 8 U.R THEN
XOR .=
;
D-FH ( b-addr c-addr d-addr -- h )
@ ROT @ ROT @ ( d b c )
D-FH-B^C ( d xi )
D-FH-^D ( h )
;
-------------------------------------------------------------------------D-FI-~D ( d -- ~d )
?PRINT IF DUP CR ." ~Z = ~" 8 HEX U.R THEN
INVERT .=
;
D-FI-Bv~D ( ~d b -- x )
?PRINT IF 2DUP CR ." X | ~Z = " 8 HEX U.R SPACE ." | " 8 HEX U.R THEN
OR .=
;
D-FI-^C ( c x1 -- x2 )
?PRINT IF 2DUP SWAP CR ." C ^ . = " 8 U.R SPACE ." ^ " 8 U.R THEN
XOR .=
;
D-FI ( b-addr c-addr d-addr -- i )
@ ROT @ ROT @ ROT ( b c d )
D-FI-~D
( b c xi )
ROT
( c xi b )
D-FI-Bv~D ( c xii )
D-FI-^C
( i )
;
--------------------------------------------------------------------------

И оптимизированная версия
: FF (
AND OR
: FG (
AND OR
: FH (
: FI (

b-addr
;
b-addr
;
b-addr
b-addr

c-addr d-addr -- f ) @ ROT @ ROT @ OVER AND SWAP INVERT ROT
c-addr d-addr -- g ) @ ROT @ ROT @ ROT DUP INVERT ROT AND -ROT
c-addr d-addr -- h ) @ ROT @ ROT @ XOR XOR ;
c-addr d-addr -- i ) @ ROT @ ROT @ ROT INVERT ROT OR XOR ;

В Форте очень удобно проверять как работает та или иная операция, например можно
выполнить в интерактивном режиме такой запрос:
A B C D-FF
И в результате на экране будет выведена полная трассировка операции.
Если вы пожелаете вывести результат не в шестнадцатеричном, а в двоичном виде, то
нужно везде заменить слово HEX на слово BINARY.

Преобразование блока данных
Для преобразования блока данных мы определим четыре базовых команды, которые
будет выполнять MD5 процессор. Эти четыре базовые команды производят обработку и
обновление регистров процессора на основании их предыдущего содержимого и на
основании данных из БЛОЧНОГО БУФЕРА.
Эти операции описываются следующим выражением:
a = b + ((a + F(b,c,d) + X[k] + T[i]) num&0x03);
l=p[sw]; HOST_p_c2l(data,l,sc); p[sw++]=l;
for (; sw < ew; sw++)
{
HOST_c2l(data,l); p[sw]=l;
}
if (ec)
{
HOST_c2l_p(data,l,ec); p[sw]=l;
}
}
return;
}
}
sw=len/HASH_CBLOCK;
if (sw > 0)
{
#if defined(HASH_BLOCK_DATA_ORDER)
{
HASH_BLOCK_DATA_ORDER(c,data,sw);
sw*=HASH_CBLOCK;
data+=sw;

len-=sw;
}
#endif

}
if (len!=0)
{
p = c->data;
c->num = len;
ew=len>>2;
/* слов для копирования */
ec=len&0x03;
for (; ew; ew--,p++)
{
HOST_c2l(data,l); *p=l;
}
HOST_c2l_p(data,l,ec);
*p=l;
}
}

- обработка последнего блока и получение цифрового дайджеста
void MD5_Final(unsigned char *md, MD5_CTX *c)
{
register HASH_LONG *p;
register unsigned long l;
register int i,j;
static const unsigned char end[4]={0x80,0x00,0x00,0x00};
const unsigned char *cp=end;
/* c->num определенно должен иметь место по крайней мере
* еще для одного байта. */
p=c->data;
i=c->num>>2;
j=c->num&0x03;
l = (j==0) ? 0 : p[i];
HOST_p_c2l(cp,l,j); p[i++]=l;
/* i это следующее 'неопределенное слово' */
if (i>(HASH_LBLOCK-2)) /* оставить место для Nl и Nh */
{
if (iNl;
#elif defined(DATA_ORDER_IS_LITTLE_ENDIAN)
p[HASH_LBLOCK-2]=c->Nl;
p[HASH_LBLOCK-1]=c->Nh;
#endif
HASH_BLOCK_HOST_ORDER (c,p,1);
#ifndef HASH_MAKE_STRING
#error "HASH_MAKE_STRING must be defined!"
#else
HASH_MAKE_STRING(c,md);
#endif
c->num=0;

/* очистить все, HASH_BLOCK может оставить некоторую информацию
* на стеке, но меня это не беспокоит
memset((void *)c,0,sizeof(HASH_CTX));
*/
}

А функция преобразования одного 16-байтового блока данных, использующая
рассмотренные выше операции преобразования регистров процессора выглядит так:
void md5_block_host_order(MD5_CTX *c, const void *data, int num)
{
const MD5_LONG *X=data;
register unsigned long A,B,C,D;
A=c->A;
B=c->B;
C=c->C;
D=c->D;
for (;num--;X+=HASH_LBLOCK)
{
/* Раунд 0 */
R0(A,B,C,D,X[ 0], 7,0xd76aa478L);
R0(D,A,B,C,X[ 1],12,0xe8c7b756L);
R0(C,D,A,B,X[ 2],17,0x242070dbL);
R0(B,C,D,A,X[ 3],22,0xc1bdceeeL);
R0(A,B,C,D,X[ 4], 7,0xf57c0fafL);
R0(D,A,B,C,X[ 5],12,0x4787c62aL);
R0(C,D,A,B,X[ 6],17,0xa8304613L);
R0(B,C,D,A,X[ 7],22,0xfd469501L);
R0(A,B,C,D,X[ 8], 7,0x698098d8L);
R0(D,A,B,C,X[ 9],12,0x8b44f7afL);
R0(C,D,A,B,X[10],17,0xffff5bb1L);
R0(B,C,D,A,X[11],22,0x895cd7beL);
R0(A,B,C,D,X[12], 7,0x6b901122L);
R0(D,A,B,C,X[13],12,0xfd987193L);
R0(C,D,A,B,X[14],17,0xa679438eL);
R0(B,C,D,A,X[15],22,0x49b40821L);
/* Раунд 1 */
R1(A,B,C,D,X[ 1], 5,0xf61e2562L);
R1(D,A,B,C,X[ 6], 9,0xc040b340L);
R1(C,D,A,B,X[11],14,0x265e5a51L);
R1(B,C,D,A,X[ 0],20,0xe9b6c7aaL);
R1(A,B,C,D,X[ 5], 5,0xd62f105dL);
R1(D,A,B,C,X[10], 9,0x02441453L);
R1(C,D,A,B,X[15],14,0xd8a1e681L);
R1(B,C,D,A,X[ 4],20,0xe7d3fbc8L);
R1(A,B,C,D,X[ 9], 5,0x21e1cde6L);
R1(D,A,B,C,X[14], 9,0xc33707d6L);
R1(C,D,A,B,X[ 3],14,0xf4d50d87L);
R1(B,C,D,A,X[ 8],20,0x455a14edL);
R1(A,B,C,D,X[13], 5,0xa9e3e905L);
R1(D,A,B,C,X[ 2], 9,0xfcefa3f8L);
R1(C,D,A,B,X[ 7],14,0x676f02d9L);
R1(B,C,D,A,X[12],20,0x8d2a4c8aL);
/* Раунд 2 */
R2(A,B,C,D,X[ 5], 4,0xfffa3942L);
R2(D,A,B,C,X[ 8],11,0x8771f681L);
R2(C,D,A,B,X[11],16,0x6d9d6122L);
R2(B,C,D,A,X[14],23,0xfde5380cL);
R2(A,B,C,D,X[ 1], 4,0xa4beea44L);

R2(D,A,B,C,X[ 4],11,0x4bdecfa9L);
R2(C,D,A,B,X[ 7],16,0xf6bb4b60L);
R2(B,C,D,A,X[10],23,0xbebfbc70L);
R2(A,B,C,D,X[13], 4,0x289b7ec6L);
R2(D,A,B,C,X[ 0],11,0xeaa127faL);
R2(C,D,A,B,X[ 3],16,0xd4ef3085L);
R2(B,C,D,A,X[ 6],23,0x04881d05L);
R2(A,B,C,D,X[ 9], 4,0xd9d4d039L);
R2(D,A,B,C,X[12],11,0xe6db99e5L);
R2(C,D,A,B,X[15],16,0x1fa27cf8L);
R2(B,C,D,A,X[ 2],23,0xc4ac5665L);
/* Раунд 3 */
R3(A,B,C,D,X[ 0], 6,0xf4292244L);
R3(D,A,B,C,X[ 7],10,0x432aff97L);
R3(C,D,A,B,X[14],15,0xab9423a7L);
R3(B,C,D,A,X[ 5],21,0xfc93a039L);
R3(A,B,C,D,X[12], 6,0x655b59c3L);
R3(D,A,B,C,X[ 3],10,0x8f0ccc92L);
R3(C,D,A,B,X[10],15,0xffeff47dL);
R3(B,C,D,A,X[ 1],21,0x85845dd1L);
R3(A,B,C,D,X[ 8], 6,0x6fa87e4fL);
R3(D,A,B,C,X[15],10,0xfe2ce6e0L);
R3(C,D,A,B,X[ 6],15,0xa3014314L);
R3(B,C,D,A,X[13],21,0x4e0811a1L);
R3(A,B,C,D,X[ 4], 6,0xf7537e82L);
R3(D,A,B,C,X[11],10,0xbd3af235L);
R3(C,D,A,B,X[ 2],15,0x2ad7d2bbL);
R3(B,C,D,A,X[ 9],21,0xeb86d391L);
A
B
C
D

=
=
=
=

c->A
c->B
c->C
c->D

+=
+=
+=
+=

A;
B;
C;
D;

}
}

Именно здесь и сокрыто основное отличие в реализации двух алгоритмов.

Как это реализовано в Microsoft Windows
Microsoft Windows прячет от нас детали реализации алгоритма построения цифрового
дайджеста MD5 и предлагает для работы только Crypto API – прикладной программный
интерфейс для работы с криптографической библиотекой.
Crypto API построена по принципу так называемых "провайдеров", или в более
русскоязычном варианте – модулей, обеспечивающих функции криптозащиты. Из этого
следует, что вы можете построить свой собственный модуль, следуя требованиям
библиотеки Crypto API, зарегистрировать его и использовать.
Но мы посмотрим только на ту часть библиотеки, которая позволит нам построить
цифровой дайджест MD5.
Для построения цифрового дайджеста блока данных и для работы с полученным
цифровым дайджестом Crypto API предлагает четыре метода:
• CryptCreateHash – функция используется для инициализации хэширования
блока данных. Она возвращает дескриптор хэш-объекта, который затем можно
использовать для хэширования данных.
• CryptGetHashParam – функция, используемая для извлечения значения хэша.
• CryptHashData – функция, выполняющая хэширование блока данных.



CryptDestroyHash – функция для освобождения дескриптора полученного от
функции создания хэш-объекта CryptCreatehash.

Метод CryptHashData используеься для построения промежуточного цифрового
дайджеста блока дынных. Эта функция может быть вызвана несколько раз для
обработки длинного сообщения, разбитого на блоки различной длины.
В качестве примера мы рассмотрим построение цифрового дайджеста для блока данных
длиной dwBufferLen, которые расположены в памяти по адресу pBuffer. Предполагается,
что данные подлежащие хэшированию полностью расположены в буфере. Поэтому
после извлечения цифрового дайджеста с помощью метода CryptoGetHashParam
дальнейшее хэширование данных с помощью данного хэш-объекта более не возможно.

#include
// определения CryptoAPI
/*
Значение некоторых констант, используемых в данном примере:
#define ALG_CLASS_HASH
(4