парадокс дней рождения

Ответ от *@ Екатерина @ *[гуру]
Многие криптоаналитические атаки построены на базе так называемой задачи парадокса дня рождения. Задача состоит в нахождении минимального размера группы людей, такой чтобы, по меньшей мере, двое из них имели общий день рождения с высокой вероятностью. Допустим, что дни рождения r людей образуют случайную выборку размером r из набора всех дней в году. Годы не имеют равную длину, и дни рождения не постоянны на протяжении года. Однако, как приближение, случайная выборка людей принимается эквивалентной случайной выборке дней рождения. Рассмотрим год из 365 дней. Решение находится путем рассмотрения дополнительной задачи? оценки вероятность того, что все r дней рождения будут различны. Как этот парадокс относится к криптографии? Положим для атаки на 64-битный блочный шифр сопернику нужно получить две плайнтекст/шифр-текстовых пары, которые отличаются только в наименее значимом бите. Интерпретация этой задачи в терминах задачи о парадоксе дня рождения приводит к выводу, что пространство из около 2^32 известных открытых текстов с высокой вероятностью будет содержать необходимую пару. Как другой пример рассмотрим цикл 64-битового Фейстелева шифра. Положим, что в шифре использована случайная F-функция (32 в 32 бита) . Нападающий может захотеть узнать, как много ему необходимо получить открытых текстов для того, чтобы наблюдать равенство выходов (столкновение) F-функции. Ответом, предусмотренным парадоксом дня рождения, есть? только O(2^16) текстов. Одним из последствий парадокса дня рождения является то, что для n-битового блочного шифра, повторяемые появления блока шифртекста могут ожидаться с вероятностью около 0.63, если более чем 2n/2 + 1 случайных открытых текстов зашифрованы на одном ключе (Кнудсен) , независимо от размера ключа. Для CBC режима, при совпадении двух блоков шифртекста Ci = Cj соответствующие входные данные (блоки) для функции шифрования Ek( ) также будут равны. Это означает, что в атаке только с шифртекстом есть информация об открытых текстах раскрывается из шифртекстовых блоков.Источник: