Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
  Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 5.2.4 SECURE HASH ALGORITHM (SHA) Вверх: 5.2 Методы построения криптографических хэш-функций Назад: 5.2.2 MD4   Содержание   Предметный указатель

5.2.3 MD5

MD5 является доработанной версией алгоритма MD4. Аналогично MD4, в алгоритме MD5 размер хэш-кода равен 128 битам.

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

Сначала текст дополняется таким образом, чтобы длина получаемого текста, выраженная в битах, стала на 64 меньше числа, кратного 512. Дополнение осуществляется приписыванием к концу сообщения единицы и затем необходимого числа нулей (в бинарном представлении). Затем к тексту приписывается 64-битовое представление длины исходного сообщения. Таким образом получается текст, длина которого кратна 512 битам.

Инициализируются 4 переменных размером по 32 бита:

    \begin{tabular}{r@{}l}
$A={}$&\texttt{01 23 45 67};\\
$B={}$&\texttt{89 AB CD E...
...\
$C={}$&\texttt{FE DC BA 98};\\
$D={}$&\texttt{76 54 32 10}.\\
\end{tabular}

Далее начинает работу основной цикл алгоритма. Основной цикл повторяется столько раз, сколько блоков по 512 битов присутствует в хэшируемом сообщении.

Создаются копии инициализированных переменных: $ AA$ для $ A$, $ BB$ для $ B$, $ CC$ для $ C$, $ DD$ для $ D$.

Каждый основной цикл состоит из 4 раундов (в MD4 было всего 3 раунда). В свою очередь, каждый раунд состоит из 16 операторов. Все операторы однотипны и имеют вид: $ u=v+((F(v,w,z)+M_j+t_j)\ll s_j)$. Здесь:

$ u$, $ v$, $ w$ и $ z$ суть $ A$, $ B$, $ C$ и $ D$ в зависимости от номера раунда и номера оператора в раунде (в оригинале эта подстановка записана в явном виде).

$ M_j$ обозначает $ j$-тый подблок обрабатываемого блока. В каждом раунде порядок обработки очередным оператором подблоков определяется задаваемой в явном виде подстановкой на множестве всех подблоков (их, также как и операторов, 16).

$ t_i$ обозначают зафиксированные случайные константы, зависящие от номера раунда и номера оператора в раунде (Ривест положил для $ i$-того ($ i\in 0;15$) оператора в $ j$-том ($ j\in 0;3$) раунде константу равной целой части от $ 2^{32}\vert\sin(16j+i)\vert$.

$ \ll s_i$ обозначает левый циклический сдвиг аргумента на $ s_i$ битов. Величины сдвигов также зависят от номера раунда и номера оператора в раунде.

$ F(v,w,z)$ -- некоторая функция (фиксированная для каждого раунда), действующая покоординатно на биты своих трех аргументов.

В первом раунде действует функция $ F(X,Y,Z)=XY\lor(\qopname\relax o{not}X)Z$.

Во втором раунде действует функция $ G(X,Y,Z)=XZ\lor(\qopname\relax o{not}Z)Y$.

В третьем раунде действует функция $ H(X,Y,Z)=X\oplus
Y\oplus Z$.

В четвертом раунде действует функция $ I(X,Y,Z)=Y\oplus(X\lor(\qopname\relax o{not}Z))$.

Функции подобраны таким образом, чтобы при равномерном и независимом распределении битов аргументов выходные биты были бы также распределены равномерно и независимо.

Основной цикл алгоритма завершается суммированием полученных $ A$, $ B$, $ C$ и $ D$ и накапливаемых $ AA$, $ BB$, $ CC$ и $ DD$, после чего алгоритм переходит к обработке нового блока данных. Выходом алгоритма является конкатенация получаемых после последнего цикла $ A$, $ B$, $ C$ и $ D$.


Известные результаты анализа


Ривест внес следующие изменения в MD4 при разработке MD5:

  • добавлен четвертый раунд в основной цикл;

  • в каждом операторе при суммировании используется уникальная константа;

  • изменена функция $ G$ второго раунда (в MD4 было $ XY\lor
XZ\lor YZ$). Это сделано для того, чтобы сделать функцию менее симметричной;

  • результат каждого шага теперь суммируется с результатом предыдущих шагов, что позволяет усилить эффект распространения ошибки;

  • изменен порядок считывания слов во втором и третьем раундах для того, чтобы они меньше походили друг на друга;

  • величина циклического сдвига в каждом раунде оптимизирована с точки зрения усиления эффекта распространения ошибки. Сдвиги от раунда к раунду различаются.

Берсон [Be] пытался применить метод дифференциального анализа к однораундовым преобразованиям алгоритма MD5. Но его подход не дает эффекта для полной четырехраундовой схемы.

Ден Буру и Босселэру [dBB1] удалось построить коллизию для функции сжатия (т. е. элементарной функции, которая на каждом раунде преобразует промежуточное значение, полученное из предыдущего раунда, и текущий блок сообщения в новое промежуточное значение) алгоритма MD5. Пока это не привело к компрометации MD5 в практических приложениях. Тем не менее этот результат означает, что нарушен один из принципов построения MD5, а именно требование, чтобы функция сжатия была свободна от коллизий.


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 5.2.4 SECURE HASH ALGORITHM (SHA) Вверх: 5.2 Методы построения криптографических хэш-функций Назад: 5.2.2 MD4   Содержание   Предметный указатель


Проект осуществляется при поддержке:
Геологического факультета МГУ,
РФФИ
   
TopList Rambler's Top100