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

Входные данные выравниваются так, чтобы их новый размер L' был [[Сравнение по модулю натурального числа|сравним]] с 448 по модулю 512 (L’ = 512 × N + 448). Сначала дописывают единичный бит в конец потока, затем необходимое число нулевых бит (выравнивание происходит, даже если длина уже сравнима с 448).

Эта атака является разновидностью [[Дифференциальный криптоанализ|''дифференциальной'']] атаки, которая, в отличие от других атак этого типа, использует целочисленное вычитание а не [[Сложение по модулю 2|XOR]] в качестве меры разности. При поиске коллизий используется метод модификации сообщений: сначала выбирается произвольное сообщение ''M''_''0'', далее оно модифицируется по некоторым правилам, сформулированным в статье, после чего вычисляется дифференциал хеш-функции, причём <math>M'_0=M_0+dM_0</math> с вероятностью 2^-37−37. К <math>M_0</math> и <math>M'_0</math> применяется функция сжатия для проверки условий коллизии; далее выбирается произвольное <math>M_1</math>, модифицируется, вычисляется новый дифференциал, равный нулю с вероятностью 2^-30−30, а равенство нулю дифференциала хеш-функции как раз означает наличие коллизии. Оказалось, что найдя одну пару <math>M_0</math> и <math>M'_0</math>, можно менять лишь два последних слова в <math>M_0</math>, тогда для нахождения новой пары <math>M_1</math> и <math>M'_1</math> требуется всего около 2³⁹ операций хеширования.