Атака «Дней рождения» Подготовил: Самойленко Илья 4 курс 9 группа

Базовая атака

Алгоритм

Среднее время атаки

Вероятностная модель: Хэш-значения можно интерпретировать как частицы, которые случайно независимо друг от друга размещаются в ячеек. Пусть ν номер первой частицы, которая попадает в уже занятую ячейку. Попадание означает, что () = () для некоторых случайных, X. При этом ν время ожидания коллизии, или время атаки «дней рождения», выраженное в количестве обращений к алгоритму

Среднее время атаки

Парадокс дней рождения Название атаки объясняется известным парадоксом дней рождения: в группе, состоящей из 23 или более человек, вероятность совпадения дней рождения (число и месяц) хотя бы у двух людей превышает 50 %

Парадокс дней рождения Такое утверждение может показаться неочевидным, так как вероятность совпадения дней рождения двух человек с любым днём в году (1/365 = 0.27 %), умноженная на число человек в группе (23), даёт лишь (1/365)×23 = 6.3 %. Это рассуждение неверно, так как число возможных пар (( 23 × 22 )/2 = 253) значительно превышает число человек в группе. Таким образом, утверждение не является парадоксом в строгом научном смысле: логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием и результатами математического расчёта.

Модифицированная атака Атака «дней рождения» обладает двумя серьезными недостатками. Во-первых, она имеет низкую криптографическую мотивацию. Действительно, Виктора интересуют коллизионные пары (, ), в которых слово семантически близко к истинному сообщению, а слово к поддельному, в то время как атака позволяет найти среди элементов X случайную коллизионную пару. Во-вторых, для атаки требуются большие ресурсы памяти ( ячеек). Известны модернизации атаки «дней рождения», лишенные указанных недостатков. Приведем описание одной из них.

Модифицированная атака

Алгоритм Брента

Спасибо за просмотр