MD5: различия между версиями

4 байта добавлено ,  10 лет назад
Нет описания правки
 
=== Шаг 1. Выравнивание потока ===
Входные данные выравниваются так, чтобы их новый размер L' был [[Сравнение по модулю натурального числа|сравним]] с 448 по модулю 512 (L’ = 512 × N + 448). Сначала дописывают единичный бит в конец потока, затем необходимое число нулевых бит (выравнивание происходит, даже если длина уже сравнима с 448).
 
=== Шаг 2. Добавление длины сообщения ===
Метод позволяет для заданного инициализирующего вектора найти две пары <math>M,M'</math> и <math>N,N'</math>, такие что <math>f(f(s,M),M')=f(f(s,N),N')</math>. Важно отметить, что этот метод работает для любого инициализирующего вектора, а не только для вектора используемого по стандарту.
 
Эта атака является разновидностью [[Дифференциальный криптоанализ|''дифференциальной'']] атаки, которая, в отличие от других атак этого типа, использует целочисленное вычитание а не [[Сложение по модулю 2|XOR]] в качестве меры разности. При поиске коллизий используется метод модификации сообщений: сначала выбирается произвольное сообщение ''M''<sub>''0''</sub>, далее оно модифицируется по некоторым правилам, сформулированным в статье, после чего вычисляется дифференциал хеш-функции, причём <math>M'_0=M_0+dM_0</math> с вероятностью 2<sup>-37−37</sup>. К <math>M_0</math> и <math>M'_0</math> применяется функция сжатия для проверки условий коллизии; далее выбирается произвольное <math>M_1</math>, модифицируется, вычисляется новый дифференциал, равный нулю с вероятностью 2<sup>-30−30</sup>, а равенство нулю дифференциала хеш-функции как раз означает наличие коллизии. Оказалось, что найдя одну пару <math>M_0</math> и <math>M'_0</math>, можно менять лишь два последних слова в <math>M_0</math>, тогда для нахождения новой пары <math>M_1</math> и <math>M'_1</math> требуется всего около 2<sup>39</sup> операций хеширования.
 
Применение этой атаки к [[MD4]] позволяет найти коллизию меньше чем за секунду. Она также применима к другим хеш-функциям, таким как [[RIPEMD-160|RIPEMD]] и [[HAVAL]].
* [[Perl]] : [http://perldoc.perl.org/Digest/MD5.html Digest::MD5]
* [[PHP]]: [http://ru2.php.net/manual/en/function.md5.php md5() function]
 
{{Хеш-алгоритмы}}
 
Анонимный участник