Как дни рождения влияют на безопасность в интернете?

Это парадокс из теории вероятностей. Гласит так: Если собрать группу из 23 случайных людей, то вероятность совпадения дня рождения хотя бы у двух человек превышает 50%. Но как это может быть? Возьмем для примера группу из 3 человек: Алиса, Боб и Чарли. И рассчитаем вероятность того что в этой группе НЕсовпадают дни рождения: 1. Алиса может родиться в любой день года из 365, эта вероятность 365/365 2. Боб может родиться в любой день года кроме дня рождения Алисы, это 364/365 3. Чарли может родиться в любой день года кроме дня рождения Алисы и Боба, это 363/365 Вероятность того что все дни рождения будут разными это произведение вероятностей:

P(н) = (365/365) * (364/365) * (363/365) ≈ 0.9918 или 99.18%

Следовательно вероятность совпадения хотя бы у двух человек, это обратное значение и равняется оно как

P(с) = 100 - 99.18 = 0.82%

Теперь если взять группу для 23 человек, то вероятность НЕсовпадения дней рождения будет равна:

P(н) = 365/365 * 364/365 * 363/365 * ... * 343/365 ≈ 49.27%

А обратное значение составит

P(с) = 100 -  49.27 = 50.73%

Этот парадокс нашел широкое применение в области информационной безопасности и криптографии, так как он демонстрирует вероятностные атаки на хэш-функции и другие совпадения на больших наборах данных. Примерами таких атак можно назвать: 1. Подбор разных вводных данных для получения одного хэша. 2. Создание коллизий в цифровых сертификатах, так как они также используют хэш-функции. Далее следует вопрос, а какая вероятность того что 2 разных ввода сгенерируют один хэш? То есть, какая вероятность коллизии у хэш-функции? Для примера возьмем размер хэша размером 128 бит, то кол-во возможных хэшей составит 2^128. Но из-за парадокса дней рождения, коллизии возможны уже на 2^64 случайных вводов. Однако современные криптографические хэш-функции, такие как SHA-256 или SHA-3 разработаны так, что вероятность коллизии близка к невозможной. А об этом уже в следующих постах.