Теперь перейдем к основному циклу алгоритма. Этот цикл продолжается, пока не исчерпаются 512-битовые блоки сообщения.

Четыре переменных копируются в другие переменные : A в a, B в b, C в c и D в d.

Главный цикл состоит из четырех очень похожих этапов (у MD4 было только три этапа). На каждом этапе 16 раз используются различные операции. Каждая операция представляет собой нелинейную функцию над тр е-мя из a, b, c и d. Затем она добавляет этот результат к четвертой переменной, подблоку текста и константе. Д алее результат циклически сдвигается вправо на переменное число битов и добавляет результат к одной из пер е-менных a, b, c и d. Наконец результат заменяет одну из переменных a, b, c и d. См. 13-й и 12-й. Существуют четыре нелинейных функции, используемые по одной в каждой операции (для каждого этапа - другая фун кция).

Рис. 18-5. Главный цикл MD5.

Нелинейнаяч функция у~

Рис. 18-6. Одна операция MD5.

F(X,F,Z) = (X л Y) V ((-X) л Z)

G(X,Y,Z) = (Xл Z) V (Yл (-Z))

H(X,Y,Z) = X © Y © Z

I(X,Y,Z) = Y © (X V (-Z))

(© - это XOR, л - AND, v - OR, а - - NOT.)

Эти функции спроектированы так, чтобы, если соответствующие биты X, Y и Z независимы и несмещены, каждый бит результата также был бы независимым и несмещенным . Функция F - это побитовое условие: если X, то Y, иначе Z. Функция H - побитовая операция четности.

Если Mj обозначает j-ый подблок сообщения (от 0 до 15), а «<s обозначает циклический сдвиг влево на

битов, то используются следующие четыре операции :

FF(a,b,c,d,Mj,s,ti) означает a = b + ((a + F(b,c,d) + Mj + t,) «<s) GG(a,b,c,d,Mj,s,ti) означает a = b + ((a + G(b,c,d) + Mj + t,) «<s) HH(a,b,c,d,MJ,s,t,-) означает a = b + ((a + H(b,c,d) + Mj + t,) «<s) II(a,b,c,d,MJ,s,t,-) означает a = b + ((a + I(b,c,d) + Mj + t,) «<s) Четыре этапа (64 действия выглядят следующим образом):

Этап 1:

FF(a, b, c, d, М0, 7, 0xd76aa478) FF(d, a, b, c, M1, 12, 0xe8c7b756) FF(c, d, a, b, M2, 17, 0x242070db) FF(b, c, d, a, M3, 22, 0xc1bdceee) FF(a, b, c, d, M4, 7, 0xf57c0faf) FF(d, a, b, c, M5, 12, 0x4787c62a) FF(c, d, a, b, M6, 17, 0xa8304613) FF(b, c, d, a, M7, 22, 0xfd469501) FF(a, b, c, d, Ms, 7, 0x698098d8) FF(d, a, b, c, M9, 12, 0x8b44f7af) FF(c, d, a, b, M10, 17, 0xffff5bb1)

FF(b, c, d, a, M11, 22, 0x895cd7be) FF(a, b, c, d, M12, 7, 0x6b901122)

FF(d, a, b, c, M13, 12, 0xfd987193) FF(c, d, a, b, M14, 17, 0xa679438e) FF(b, c, d, a, M15, 22, 0x49b40821)

Этап 2:

GG(a, b, c, d, M1, 5, 0xf61e2562) GG(d, a, b, c, M6, 9, 0xc040b340) GG(c, d, a, b, M11, 14, 0x265e5a51) GG(b, c, d, a, Mo, 20, 0xe9b6c7aa) GG(a, b, c, d, M5, 5, 0xd62fl05d) GG(d, a, b, c, Mi0, 9, 0x02441453) GG(c, d, a, b, M15, 14, 0xd8ale681) GG(b, c, d, a, M4, 20, 0xe7d3fbc8) GG(a, b, c, d, M9, 5, 0x2,lelcde6) GG(d, a, b, c, Mi4, 9, 0xc33707d6) GG(c, d, a, b, M3, 14, 0xf4d50d87) GG(b, c, d, a, Ms, 20, 0x455al4ed) GG(a, b, c, d, Mi3, 5, 0xa9e3e905) GG(d, a, b, c, M2, 9, 0xfcefa3f8)

GG(c, d, a, b, M7, 14, 0x676f02d9)

GG(b, c, d, a, M12, 20, 0x8d2a4c8a)

Этап 3:

HH(a, b, c, d, M5, 4, 0xfffa3942) HH(d, a, b, c, M8, 11, 0x8771f681) HH(c, d, a, b, M11, 16, 0x6d9d6122) HH(b, c, d, a, M14, 23, 0xfde5380c) HH(a, b, c, d, M1, 4, 0xa4beea44) HH(d, a, b, c, M4, 11, 0x4bdecfa9) HH(c, d, a, b, M7, 16, 0xf6bb4b60) HH(b, c, d, a, M10, 23, 0xbebfbc70) HH(a, b, c, d, M13, 4, 0x289b7ec6) HH(d, a, b, c, M0, 11, 0xeaa127fa) HH(c, d, a, b, M3, 16, 0xd4ef3085) HH(b, c, d, a, M6, 23, 0x04881d05) HH(a, b, c, d, M9, 4, 0xd9d4d039) HH(d, a, b, c, M12, 11, 0xe6db99e5) HH(c, d, a, b, M15, 16, 0x1fa27cf8) HH(b, c, d, a, M2, 23, 0xc4ac5665)

Этап 4:

II(a, b, c, d, M0, 6, 0xf4292244)

II(d, a, b, c, M7, 10, 0x432aff97) II(c, d, a, b, M14, 15, 0xab9423a7) II(b, c, d, a, M5, 21, 0xfc93a039) II(a, b, c, d, M12, 6, 0x655b59c3) II(d, a, b, c, M3, 10, 0x8f0ccc92) II(c, d, a, b, M10, 15, 0xffeff47d) II(b, c, d, a, M1, 21, 0x85845ddl) II(a, b, c, d, Ms, 6, 0x6fa87e4f) II(d, a, b, c, M15, 10, 0xfe2ce6e0) II(c, d, a, b, M6, 15, 0xa3014314) II(b, c, d, a, M13, 21, 0x4e081lal)

II(a, b, c, d, M4, 6, 0xf7537e82)

II(d, a, b, c, M11, 10, 0xbd3af235)

II(c, d, a, b, M2, 15, 0x2ad7d2bb)

II(b, c, d, a, M9, 21, 0xeb86d391)

Эти константы, t,-, выбирались следующим образом:

На ,-ом этапе it является целой частью 232*abs(sin(,)), где , измеряется в радианах.

После всего этого a, b, c и d добавляются к A, B, C и D, соответственно, и алгоритм продолжается для следующего блока данных. Окончательным результатом служит объединение A, B, C и D.

Безопасность MD5

Рон Ривест привел следующие улучшения MD5 в сравнении с MD4 [1322]:

1. Добавился четвертый этап.

2. Теперь в каждом действии используется уникальная прибавляемая константа .