Парадокс дней рождений и его роль в задачах криптоанализа

Это очень важный вероятностный парадокс с неперечислимым количеством применений в современной криптографии: от алгоритмов блочного шифрования до систем с открытым ключом.

Предпосылкой возникновения «парадокса дней рождений» явился вопрос: как много учеников должно собраться в одном классе, чтобы как минимум двое из них имели день рождения в один и тот же день? С помощью простых вычислений можно выяснить, что если в классе будет находиться 23 ученика, то вероятность того, что у двух из них день рождения в один день, будет больше, чем /г.

Итак, пронумеруем учеников в классе от 1 до к и обозначим день рождения i-ro ученика как dj (которое может принимать значение от 1 до п, а п=365). Учитывая, что дни рождения не зависят друг от друга, получаем, что вероятность того, что ученики i и j имеют одинаковый день рождения, равна

Таким образом, вероятность того, что у учеников i и j день рождения в один день равна вероятности того, что один из них родился в определенный день года. Теперь найдем вероятность того, что как минимум двое из к учеников родились в один день. Вероятность того, что все к учеников имеют разные дни рождения, равна.

Ясно, что для двух человек — обозначим их как 1 и 2 — ве;

1 .

роятность того, что они родились в один день, равна —. А зна;

п

чит, вероятность того, что у них разные дни рождения, равна 1 _ _. Так как известна вероятность того, что двое имеют раЗ;

ные дни рождения, рассматривая трех учеников, скажем 1, 2 и 3, можно определить вероятность того, что ученик 3 родился с учениками 1 и 2 в разные дни. Эта вероятность равна 1—.

п

Таким образом, увеличивая число учеников до к, получим, что вероятность того, что ученик к не рожден в один день с ученн ую -1.

нами 1,2,…, к-1, равна 1—.

п

В том случае, когда вероятность того, что все к учеников родились в разные дни ниже '/г, получается, что вероятность того, что как минимум двое из них родились в один день больше или равна Уг. Пользуясь неравенством (1-п) <�е'^п, можем заменить в формуле (14) значение (1-п) на е'^п, тогда получаем:

Значит, вероятность того, что, по крайней мере, у двух учеников дни рождения будут совпадать, равна

Решая неравенство.

получаем.

Если п достаточно большое, то можно записать:

Если предположить, что п=365, тогда к=22,54, что близко к правильному значению 23.

Применение «парадокса дней рождений» на практике очень распространено. Предположим, что для атаки на алгоритм шифрования, оперирующий 64-битными блоками данных, противник должен получить две пары открытый — закрытый текст, которые отличаются только младшим значащим битом (типичная задача для дифференциального криптоанализа). Согласно «парадоксу дней рождений», только массив, состоящий примерно из 2³² открытых текстов, будет содержать требуемые пары с высокой вероятностью. Рассмотрим другой пример для одного раунда 64-битного шифра Фейстеля. Предположим, что в шифре используется произвольная функция F. Злоумышленник может захотеть узнать, как много открытых текстов ему нужно получить для того, чтобы на выходе встретилось два одинаковых шифр-текста F-функции. Согласно «парадоксу дней рождений», можно определить, что в этом случае требуется только 2¹⁶ текстов.