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

требуемых для их вычисления:

#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 --">