Описание MD5

После некоторой первоначальной обработки MD5 обрабатывает входной текст 512-битовыми блоками, раз­битыми на 16 32-битовых подблоков. Выходом алгоритма является набор из четырех 32-битовых блоков, кото­рые объединяются в единое 128-битовое хэш-значение.

Во первых, сообщение дополняется так, чтобы его длина была на 64 бита короче числа, кратного 512. Этим дополнением является 1, за которой вплоть до конца сообщения следует столько нулей, сколько нужно. Затем, к результату добавляется 64-битовое представление длины сообщения (истинной, до дополнения). Эти два дейст­вия служат для того, чтобы длина сообщения была кратна 512 битам (что требуется для оставшейся части алго­ритма), и чтобы гарантировать, что разные сообщения не будут выглядеть одинаково после дополнения. Ини­циализируются четыре переменных:

А = 0x01234567

В = 0x89abcdef

С = 0xfedcba98

D = 0x76543210

Они называются переменными сцепления.

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

Четыре переменных копируются в другие переменные: Ав а, В в Ь, Св сиОв d.

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

Этап 1

Этап 2

-ш-

п

#

A B С-D

ЭтапЗ

Этап 4

►с

Ш------ ►D

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

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

F(X,Y,Z) = (1л Y) v ((­X) л Z)

G(X,Y,Z) = (XaZ)v(Ya (­Z))

R(X,Y,Z) = X® Y® Z

l(X,Y,Z) = Y®(Xv(­Z))

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

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

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

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

W(a,b,c,d,Mj,s,ti) означает а = Ъ + ((а + ¥(b,c,d) + М, + г,) <«s)

GG(a,b,c,d,Mj,s,ti) означает а = Ъ + ((а + G(ft,c,J) + Mj + г,) <«s)

mHa,b,c,dMjJ,ti) означает а = ft + ((а + Н(й,с,</) + Mj + г,) <«s)

И^ЛсДМ,,^,) означает а = й + ((а + I(ft,c,J) + М, + f,-) <«s)

Четыре этапа (64 действия выглядят следующим образом):

Этап 1:

FF(a, Ъ, с, d, Mo, 7, 0xd76aa478)

FF(a?, a, b, с, М_ь 12, 0xe8c7b756)

FF(c, d, a, b, M₂, 17, 0x242070db)

FF(i, c, d, a, M₃, 22, Oxclbdceee)

FF(a, b, c, d, M₄, 7, 0xf57c0faf)

FF(a?, a, b, c, M₅, 12, 0x4787c62a)

FF(c, d, a, b, M₆, 17, 0xa8304613)

FF(i, c, d, a, M₇, 22, 0xfd469501)

FF(a, b, c, d, М_г, 1, 0x698098d8)

FF(a?, a, b, c, M₉, 12, 0x8b44f7af)

FF(c, d, a, b, M_w, 17, 0xffff5bbl)

FF(ft, c, d, a, M„, 22, 0x895cd7be)

FF(a, b, c, d, M_u, 1, 0x6b901122)

FF(a?, a, b, c, M₁₃, 12, 0xfd987193)

FF(c, d, a, b, M_u, 17, 0xa679438e)

FF(i, c, d, a, M₁₅, 22, 0x49b40821)

Этап 2:

GG(a, b, c, d, M_b 5, 0xf61e2562)

GG(a?, a, b, c, M₆, 9, 0xc040b340)

GG(c, d, a, b, M_n, 14, 0x265e5a51)

GG(i, c, d, a, M₀, 20, 0xe9b6c7aa)

GG(a, b, c, d, M₅, 5, 0xd62fl05d)

GG(a?, a, b, c, M₁₀, 9, 0x02441453)

GG(c, d, a, b, M₁₅, 14, 0xd8ale681)

GG(i, c, d, a, M₄, 20, 0xe7d3fbc8)

GG(a, b, c, d, M₉, 5, 0x2,lelcde6)

GG(d, a, b, c, M₁₄, 9, 0xc33707d6)

GG(c, d, a, b, M₃, 14, 0xf4d50d87)

GG{b, c, d, a, M_s, 20, 0x455al4ed)

GG(a, b, c, d, M₁₃, 5, 0xa9e3e905)

GG(a?, a, b, c, M₂, 9, Oxfcefa3f8)

GG(c, d, a, b, M₇, 14, 0x676f02d9)

GG{b, c, d, a, M_n, 20, 0x8d2a4c8a)

ЭтапЗ:

НН(д, b, с, d, M₅, 4, 0xfffa3942)

HH(W, a, b, c, M_g, И, 0x877lf681)

HH(c, a?, a, b, M_u, 16, 0x6d9d6122)

HH(ft, c, a?, a, M₁₄, 23, 0xfde5380c)

HH(a, ft, c, d, M_b 4, 0ха4Ьееа44)

HH(W, a, b, c, M₄, 11, 0x4bdecfa9)

HH(c, а?, а, ft, M₇, 16, 0xf6bb4b60)

HH(ft, c, d, a, M_w, 23, 0xbebfbc70)

HH(a, b, c, d, M₁₃, 4, 0x289b7ec6)

HH(rf, a, й, с, M₀, 11, 0xeaal27fa)

HH(c, d, a, b, M₃, 16, 0xd4eG085)

HH(i, c, a?, a, M₆, 23, 0x0488Ы05)

HH(a, й, с, d, M₉, 4, 0xd9d4d039)

Н1ОД a, 6, c, M₁₂, 11, 0xe6db99e5)

HH(c, rf, a, b, M₁₅, 16, 0xlfa27cf8)

HH(i, c, d, a, M₂, 23, 0xc4ac5665)

Этап 4:

П(д, й, с, d, M₀, 6, 0xf4292244)

II(W, а, й, с, M₇, 10, 0x432aff97)

II(c, d, a, b, M_u, 15, 0xab9423a7)

ЩЬ, с, d, a, M₅, 21, 0xfc93a039)

Ща, b, c, d, M_u, 6, 0x655b59c3)

II(d, a, b, c, M₃, 10, 0x8fflccc92)

II(c, d, a, b, M_w, 15, 0xffeff47d)

ЩЬ, с, d, a, M_b21, 0x85845ddl)

Ща, b, c, d, М_г, 6, 0x6fa87e4f)

II(d, a, b, c, M₁₅, 10, 0xfe2ce6e0)

II(c, d, a, b, M₆, 15, 0xa3014314)

ЩЬ, с, d, a, M₁₃, 21, 0x4e0811al)

Ща, b, c, d, M₄, 6, 0xf7537e82)

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

Щс, d, a, b, M₂, 15, 0x2ad7d2bb)

ЩЬ, с, d, a, M₉, 21, 0xeb86d391)

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

На i-ou этапе U является целой частью 2³²*abs(sin(0), где i измеряется в радианах.

После всего этого а, Ъ, с и d добавляются к А, В, С и D, соответственно, и алгоритм продолжается для сле­дующего блока данных. Окончательным результатом служит объединение А, В, С и D.