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

| " 8 U.R THEN
OR
?PRINT IF DUP SPACE ." = " 8 U.R THEN
;
: D-FG-BC ( b c -- x )
?PRINT IF 2DUP CR ." X & Y = " SWAP 8 U.R SPACE ." & " 8 U.R THEN
AND
?PRINT IF DUP SPACE ." = " 8 U.R THEN
;
: D-FG-vBC ( x1 bc -- x2 )
?PRINT IF 2DUP CR ." . | XY = " SWAP 8 U.R SPACE ." | " 8 U.R THEN
OR
?PRINT IF DUP SPACE ." = " 8 U.R THEN
;
: D-FG ( b-addr c-addr d-addr -- g )
@ ROT @ ROT @ ROT
3DUP
(bcdbcd)
D-FG-CD ( b c d b xi )
-ROT
( b c xi d b )
D-FG-BD ( b c xi xii )

D-FG-CDvBD ( b c xiii )
-ROT
( xiii b c )
D-FG-BC ( xiii xiv )
D-FG-vBC ( g )
;

Приведенный код может показаться достаточно длинным и запутанным, но он
производит вывод большого количества информации. Кроме того, его можно
существенно упростить (оставим это в качестве упражнения для читателя). А также
хочу обратить внимание читателя на то, что все слова в этом коде начинаются с
префикса "D-", то есть "DEBUG" – ОТЛАДОЧНЫЙ. Вот для сравнения код, из которого
были удалены все операторы отладочной печати:

: FF ( b-addr c-addr d-addr -- f ) @ ROT @ ROT @ OVER AND SWAP INVERT ROT AND OR ;
: FG ( b-addr c-addr d-addr -- g ) @ ROT @ ROT @ ROT 3DUP AND -ROT AND OR -ROT AND OR ;
: FH ( b-addr c-addr d-addr -- h ) @ ROT @ ROT @ XOR XOR ;

Не правда ли, гораздо проще!
Процессор также выполняет три базовые операции преобразования. Эти операции
используют определенные выше функции F, G и H и выражаются следующими
формулами:
a = (a + F(b,c,d) + X[k]) >2;
/* слов для копирования */
ec=len&0x03;
for (; ew; ew--,p++)
{

HOST_c2l(data,l); *p=l;
}
HOST_c2l_p(data,l,ec);
*p=l;
}
}

- обработка последнего блока и получение цифрового дайджеста

void MD4_Final(unsigned char *md, MD4_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));
*/
}

На мой критический взгляд, очень длинно и очень запутано. Я постараюсь объяснить
это тем, что библиотека OpenSSL создавалась как переносимая многоплатформенная
библиотека, но... Пример реализации этих же самых примитивов приведенный в
документе RFC 1320 намного проще, но не эффективнее.

Теперь мы готовы привести код для построения цифрового дайджеста строки:

MD4_CTX context;
unsigned char digest[16];
unsigned char string = "abc";
unsigned int len = strlen (string);
MD4_Init(&context);
MD4_Update(&context, string, len);
MD4_Final(digest, &context);

Просто, правда? Зато теперь мы знаем как это все работает внутри!
Ну и конечно же пример:
MD4("abc") = a448017aaf21d8525fc10ae87aa6729d

8. Построение цифрового дайджеста файла
Для того, чтобы построить цифровой дайджест любого файла, мы тоже можем
использовать приведенные выше примитивы. Единственное отличие при обработке
файла от обработки строки состоит в том, что большой файл мы не сможем
представить в виде одной строки байт (символов) и поэтому его нужно будет
обрабатывать частями, например вот так:

FILE *file;
MD4_CTX context;
int len;
unsigned char buffer[1024], digest[16];
file = fopen(filename, "rb");

MD4_Init(&context);
while (len = fread (buffer, 1, 1024, file))
{
MD4_Update(&context, buffer, len);
}
MD4_Final(digest, &context);
fclose(file);

С помощью вот такого кусочка кода и был построен цифровой дайджест для файла
WinWord.EXE, приведенный в начале статьи.
В связи с операцией построения цифрового дайджеста для файла возник один
интересный вопрос, который я исследовал. Вопрос такой: а как влияет размер буфера
данных на скорость работы алгоритма? Есть ли разница в том, какого размера буфер
лучше использовать – размером в 1 байт или размером в 1000 байт?
Для этого я написал маленькую программку, которая измеряет скорость работы
алгоритма для буфера различных размеров, начиная от размера в 1 байт и заканчивая
размером в 128 байт. Результат работы программы я свел в следующие два графика –
график скорости работы реализации и график пропускной способности реализации
алгоритма. В измерениях я использовал две реализации алгоритма построения

цифрового дайджеста MD4 – реализацию, предложенную в документе RFC 1320 и
реализацию из библиотеки OpenSSL.

Время работы алгоритма в зависимоати от
размера буфера
16
14

Время, сек

12
10
RFC

8

OpenSSL

6
4
2

Размер буфера, байт

Рисунок 9. Скорость --">