Парадокс дней рождения
Вчера сдал очередную контрольну и довольно успешно. Сам иногда удивляюсь, настолько там для меня все как-то вывернуто и противоестественно. Хотя, я думаю - это дело привычки. Среди прочего, был довольно любопытный материал об атаках на основе "парадокса дней рождения".
Сама постановка звучит так: В группе, состоящей из 23 или более человек, вероятность совпадения дней рождения (число и месяц) хотя бы у двух людей превышает 50 %. Например, если в классе 23 ученика или более, то более вероятно то, что у кого-то из одноклассников дни рождения придутся на один день, чем то, что у каждого будет свой неповторимый день рождения.
Для 60 и более человек вероятность такого совпадения превышает 99 %, хотя 100 % она достигает, согласно принципу Дирихле, только тогда, когда в группе не менее 367 человек (ровно на 1 больше, чем число дней в високосном году; с учётом високосных лет).
Такое утверждение может показаться неочевидным, так как вероятность совпадения дней рождения двух человек с любым днём в году (1/365 = 0.27 %), умноженная на число человек в группе (23), даёт лишь (1/365)×23 = 6.3 %. Это рассуждение неверно, так как число возможных пар (( 23 × 22 )/2 = 253) значительно превышает число человек в группе (253 > 23). Таким образом, утверждение не является парадоксом в строгом научном смысле: логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.
Этот парадокс имеет прямое отношение к т.н. атакам "дней рождения" в криптологии. Для этого вычисляются значения f для случайно выбранных блоков входных данных до тех пор, пока не будут найдены два блока, имеющие один и тот же хеш-код. Таким образом, если f имеет N различных равновероятных выходных значений и N является достаточно большим, то из парадокса дней рождения следует, что в среднем после перебора 1.25*N^0.5 различных входных значений будет найдена искомая коллизия.
Для этой атаки, например, может быть уязвима электронная цифровая подпись. Допустим, что 2 человека - A и Б - хотят подписать контракт, но А хочет подсунуть Б поддельный вариант контракта. Тогда А составляет подлинный контракт и поддельный контракт. Далее посредством внесения допустимых изменений, не меняющих смысла текста (расстановкой запятых, переносов, отступов), А добивается, чтобы оба контракта имели одинаковый хеш. После этого А посылает Б подлинный контракт, Б его подписывает, а его подпись также показывает, что он подписал и поддельный контракт, так как оба контракта имеют одинаковый хеш. Для избежания уязвимости такого рода достаточно увеличить длину хеш-кода настолько, чтобы стало сложно посредством вычислений найти 2 контракта с одинаковыми хеш-кодами.
Сама постановка звучит так: В группе, состоящей из 23 или более человек, вероятность совпадения дней рождения (число и месяц) хотя бы у двух людей превышает 50 %. Например, если в классе 23 ученика или более, то более вероятно то, что у кого-то из одноклассников дни рождения придутся на один день, чем то, что у каждого будет свой неповторимый день рождения.
Для 60 и более человек вероятность такого совпадения превышает 99 %, хотя 100 % она достигает, согласно принципу Дирихле, только тогда, когда в группе не менее 367 человек (ровно на 1 больше, чем число дней в високосном году; с учётом високосных лет).
Такое утверждение может показаться неочевидным, так как вероятность совпадения дней рождения двух человек с любым днём в году (1/365 = 0.27 %), умноженная на число человек в группе (23), даёт лишь (1/365)×23 = 6.3 %. Это рассуждение неверно, так как число возможных пар (( 23 × 22 )/2 = 253) значительно превышает число человек в группе (253 > 23). Таким образом, утверждение не является парадоксом в строгом научном смысле: логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.
Этот парадокс имеет прямое отношение к т.н. атакам "дней рождения" в криптологии. Для этого вычисляются значения f для случайно выбранных блоков входных данных до тех пор, пока не будут найдены два блока, имеющие один и тот же хеш-код. Таким образом, если f имеет N различных равновероятных выходных значений и N является достаточно большим, то из парадокса дней рождения следует, что в среднем после перебора 1.25*N^0.5 различных входных значений будет найдена искомая коллизия.
Для этой атаки, например, может быть уязвима электронная цифровая подпись. Допустим, что 2 человека - A и Б - хотят подписать контракт, но А хочет подсунуть Б поддельный вариант контракта. Тогда А составляет подлинный контракт и поддельный контракт. Далее посредством внесения допустимых изменений, не меняющих смысла текста (расстановкой запятых, переносов, отступов), А добивается, чтобы оба контракта имели одинаковый хеш. После этого А посылает Б подлинный контракт, Б его подписывает, а его подпись также показывает, что он подписал и поддельный контракт, так как оба контракта имеют одинаковый хеш. Для избежания уязвимости такого рода достаточно увеличить длину хеш-кода настолько, чтобы стало сложно посредством вычислений найти 2 контракта с одинаковыми хеш-кодами.