How to become an author
Search
Write a publication
Pull to refresh

Что связывает парадокс дней рождения и уязвимости электронных подписей?

Reading time7 min
Views17K
Cryptography*Mathematics*
Translation
Original author: Math for Computer Science

Введение


Допустим, я спрошу вас, сколько человек должно быть в комнате, чтобы у двух из них день рождения с вероятностью 50% приходился на один день. Каким будет ответ? Именно это и называется парадоксом дней рождения.

Парадокс гласит:

Если в комнате есть 23 человека, то с вероятностью 50% двое из них родились в один день.

В некоторых версиях парадокса делаются ещё более сильные заявления:

Если в комнате 70 человек, то с вероятностью 99% двое из них родились в один день.

Поначалу это казалось мне удивительным и контринтуитивным. Давайте выясним, почему же это правда. Чтобы упростить задачу, мы сделаем следующие допущения:

  1. Будем считать, что все люди в комнате родились не в високосный год. Мы делаем это допущение, чтобы нам не пришлось анализировать два разных случая.
  2. В комнате нет близнецов. При наличии пары близнецов решение будет тривиальным.
  3. Мы предполагаем, что люди рождаются равномерно и случайно. Что это значит? Люди с равной вероятностью могут рождаться в любой день года. Если немного это формализовать, то вероятность рождения в любой выбранный день равна $\frac{1}{365}$.
  4. Люди рождаются независимо друг от друга. Это значит, что дата рождения любого человека не влияет на дату рождения другого.

Стоит заметить, что эти условия необязательно соблюдаются в реальном мире. В частности, в реальном мире люди не рождаются с равномерной случайностью. По этой ссылке есть статистика по дням, в которые рождаются люди. Хотя наша модель не является точным отражением реального мира, её простота позволяет значительно облегчить анализ задачи.

Нужно сказать, что если в комнате находится 366 или более людей, то в ней гарантированно есть два человека с одинаковым днём рождения. Это следует из принципа Дирихле («принципа голубей и ящиков»): если есть 366 человека и 365 дней, то по крайней мере два человека обязательно имеют одинаковый день рождения.

Представим, что в комнате один человек, тогда вероятность его общего дня рождения с кем-то ещё равна 0. Пусть $(A_n)$ будет исходом, при котором среди $n$ людей ни один день рождения не совпадает. Пусть $\Pr[A_n]$ — вероятность того, что среди $n$ людей в комнате каждый имеет день рождения в свой день. Аналогично, пусть $\overline{A_n}$ будет дополнением $A_n$, т.е. исходом, при котором среди $n$ людей два человека имеют одинаковый день рождения.

$\Pr[A_n] + \Pr[\overline{A_n}] = 1$


$\Pr[A_1] = 1 \text{ because there is only one person in the room}$


Допустим, в комнате два человека, A и B. Без утери обобщения просто представим, что человек A родился 1 января. Чтобы у B и A были разные дни рождения, нужно, чтобы B родился в любой день, кроме 1 января. У человека B будет 364 варианта дня рождения.

$\Pr[A_2] = \Pr[\text{B is different from A}] = \frac{364}{365}$


Представим, что в комнате три человека, A, B и C. Допустим, что человек A родился 1 января, тогда чтобы все они родились в разные дни, человеку B остаётся только 364 дней, как и в предыдущем примере. Так как A и B занимают два дня, человек C может родиться только в 365 — 2 = 363 дня.

$\Pr[A_3] = \Pr[\text{B is different A and C is different from B,A}] = \frac{364}{365} \times \frac{363}{365}$


Здесь происходит нечто более интересное: предположим, что в комнате уже есть $k - 1$ людей. Когда в комнату заходит $k$-тый человек, то чтобы все $k$ человек имели разные дни рождения, должны быть истинными два исхода

  1. Все $k - 1$ людей, вошедших в комнату до него, должны иметь разные дни рождения. Какова вероятность этого? $\Pr[A_{k-1}]$.
  2. $k$-тому человеку нужно иметь отличающийся день рождения от всех других $k - 1$ людей в комнате. Какова вероятность этого? $\frac{365 - (k-1)}{365}$.

Также нужно заметить, что два представленных выше исхода независимы друг от друга, потому что по допущению (4), сделанному в начале поста, $k$-тый человек родился независимо от всех других.

$\begin{equation*} \begin{split} \Pr[A_k] & = \Pr [ k - 1 \text{ people in the room have different birthdays} \textbf{ AND } \\ & \ \ \ \ \ \ \ \text{person k has a different birthday from the } k - 1 \text{ people } ] \\ & = \Pr [ k - 1 \text{ people in the room have different birthdays}] \\ & \ \ \ \ \times \Pr [\text{person k has a different birthday from the } k - 1 \text{ people } ] \\ & = \Pr[A_{k-1}] \times \frac{365 - (k-1)}{365} \end{split} \end{equation*}$


Теперь вычислим вероятности:

$\begin{equation*} \begin{split} \Pr[A_1] & = 1 \\ \Pr[A_2] & = \Pr[A_1] \times \frac{364}{365} = \frac{364}{365} \approx 0.997 \\ \Pr[A_3] & = \Pr[A_2] \times \frac{363}{365} = \frac{364}{365} \times \frac{363}{365} \approx 0.991 \\ \Pr[A_4] & = \Pr[A_3] \times \frac{362}{365} \approx 0.983 \\ & \vdots \\ \Pr[A_{22}] & = \Pr[A_{21}] \times \frac{344}{365} \approx 0.525 \\ \Pr[A_{23}] & = \Pr[A_{22}] \times \frac{343}{365} \approx 0.493 \\ \end{split} \end{equation*}$


Поскольку мы получили $\Pr[A_{23}] = 0.493 < 0.5$, это будет означать, что вероятность общего дня рождения для двух людей равна

$\Pr[\overline{A_{23}} ] = 1 - \Pr[A_{23}] = 1 - 0.493 = 0.507 > 0.5$


При увеличении $n$ вероятность стремится к 1 и достигает её.

Более сложная задача


Допустим, мы хотим обобщить эту задачу до случая, когда есть $n$ людей и $m$ возможных дней рождения. Имея $n,m$, можем ли мы определить вероятность того, что два человека будут иметь общий день рождения?

Можно использовать такую же систему: у нас будет исход $A_n$, обозначающий все $n$ людей, родившихся в разные дни. В случае с одним человеком ничего не меняется

$\Pr[A_1] = 1$


В случае, когда есть два человека, обозначим их как A и B. Чтобы человек B родился в другой день, человек B должен иметь день рождения среди $m - 1$ других вариантов.

$\Pr[A_2] = \frac{m-1}{m}$


В случае с тремя людьми человек B должен иметь день рождения, отличающийся от дня рождения A. У человека C должен быть день, отличающийся от дней рождения A и B.

$\Pr[A_3] = \frac{m-1}{m} \times \frac{m-2}{m}$


В общем случае для любого $n$ мы можем использовать ту же рекурсивную формулу, что и в предыдущем разделе:

$\Pr[A_n] = \Pr[A_{n-1}] \times \frac{m - (n-1)}{m}$


Допустим, если мы хотим найти выражение в замкнутой форме для $\Pr[A_n]$, то мы разложим выражение

$\begin{equation*} \begin{split} \Pr[A_n] & = \Pr[A_{n-1}] \times \frac{m - (n-1)}{m} \\ & = \Pr[A_{n-2}] \times \frac{m - (n-2)}{m} \times \frac{m - (n-1)}{m} \\ & = \Pr[A_{n-3}] \times \frac{m - (n-3)}{m} \times \frac{m - (n-2)}{m} \times \frac{m - (n-1)}{m} \\ & \ \vdots \\ & = \Pr[A_2] \times \frac{m-2}{m} \times \frac{m-3}{m} \times \cdots \times \frac{m - (n-3)}{m} \times \frac{m - (n-2)}{m} \times \frac{m - (n-1)}{m} \\ & = \prod_{i = 1}^{n-1} \frac{m-i}{m} = \prod_{i = 1}^{n-1} 1 - \frac{i}{m} \\ & \approx \prod_{i = 1}^{n-1} e^{\frac{-i}{m}} \text{ using the identity } 1 - x \approx e^{-x} \\ & = e^{-\sum_{i = 1}^{n-1} \frac{i}{m}} \\ & = e^{\frac{-n(n-1)}{2m}} \approx e^{\frac{-n^2}{2m}} \end{split} \end{equation*}$


Аппроксимацией этого результата является $\Pr[A_n] \approx e^{\frac{-n^2}{2m}}$. Хотя мы и можем найти более приближенные границы, это даёт нам достаточную аппроксимацию. Единственное тождество, которое мы использовали в этой аппроксимации:

$1 - x \approx e^{-x}$


В абстрактном виде парадокс дней рождения имеет множество применений в компьютерных вычислениях. В частности, он используется в хэшировании, которое само по себе имеет множество применений. Выводы, сделанные в этой задаче, являются ключевыми для анализа вероятности хэширования двух элементов в один ключ. Эту задачу можно ещё более обобщить до вероятностной задачи мячей и корзин (balls and bins problem), которую мы оставим для другого поста.

Применение


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

Для начала определим, что такое хэш-функция. Хэш-функция $h : U \rightarrow [0,m-1]$ — это функция, выполняющая отображение из множества $U$ в число в интервале $[0,m-1]$. Функция $h$, определяемая как $h(x) = x \mod m$ — пример хэш-функции из $\mathbb{N} \rightarrow [0,m-1]$. Хэш-функции имеют множество применений, особенно в сочетании с популярной структурой данных «хэш-таблица». Также она используется в криптографии, где применяется специфический тип хэш-функции под названием «крипторафическая хэш-функция».

Одно из множества свойств, которыми должна обладать крипторафическая хэш-функция — стойкость к коллизиям. Должно быть сложно найти два таких $u_1, u_2 \in U$, чтобы они образовывали коллизию, т.е. $h(u_1) = h(u_2)$.

Именно на стойкости к коллизиям мы и сосредоточимся. Во-первых, я объясню, почему она является желательным свойством. Для этого мы сначала рассмотрим цифровые подписи.

В прошлом для «подписания» документов люди и организации пользовались подписями и печатями. В последнее время происходит переход к электронным или цифровым подписям. Цифровая подпись должна удовлетворять трём основным свойствам.

  1. При подписании документа нужна возможность проверить, кто подписал документ.
  2. После подписания документа никто не должен иметь возможности его подделать.
  3. Лицо, подписавшее документ, не может в дальнейшем опровергнуть подписание документа.

Цифровая подпись — это способ доказуемого подтверждения истинности документа или сообщения. Цифровая подпись гарантирует, что полученное сообщение было создано известным отправителем и не изменялось.

Допустим, у нас есть документ $m$. Как нам его подписать?

Каждый пользователь/организация имеет уникальный закрытый ключ $p_k$ и открытый ключ $pub_k$. Они используют функцию подписания для подписи документа собственным закрытым ключом. Однако цифровая подпись может подписать только небольшое количество документов. Область определения функции подписи мала. Один из способов решения этой проблемы — создание меньшего документа, представляющего исходный документ, но в гораздо меньшем размере. Чаще всего для этого к большому документу применяется хэш-функция. Хэш-функция используется для отображения его из большого пространства в меньшее, и результат такой операции называется «отпечатком». Подпись использует отпечаток и закрытый ключ для создания подписи. Процедуру можно описать так:

  1. Получаем закрытый ключ $p_k$.
  2. Хэшируем документ $m$ и получаем $h(m)$.
  3. Подписываем $h(m)$ при помощи закрытого ключа $p_k$.
  4. Отправляем $sign(h(m), p_k)$ и открытый ключ $pub_k$ всем, кто желает подтвердить документ.

Любой, у кого есть $sign(h(m), p_k))$ и открытый ключ, может проверить, действительно ли документ $m$ подписан нужным лицом.

Проблема: предположим, что злоумышленник Ева нашла два документа $m, m'$, где $m$ — это настоящий договор, а $m'$ — мошеннический документ, такой, что $h(m) = h(m')$. Предположим, что Ева заранее знает, что Алиса подпишет только $m$, но не $m'$. Перед подписанием к документу применяется криптографическая хэш-функция $h$. Ева подходит к Алисе и просит её подписать документ $m$, воспользовавшись описанной выше последовательностью. Теперь Ева может заявить, что Алиса подписала мошеннический документ $m'$, потому что $h(m) = h(m')$. Алиса никаким образом не сможет доказать, что она не подписывала $m'$.

В приведённом выше примере $h$ оказалась нестойкой к коллизиям функцией, поэтому Ева смогла найти два входящих набора данных, хэширующихся в то же значение. Ева смогла заявить, что Алиса подписала $m'$, хотя на самом деле она подписала только $m$. Это подчёркивает важность стойкости к коллизиям и показывает, почему цифровые подписи уязвимы, если хэш-функция оказывается нестойкой.

Пусть $h : U \rightarrow [0,m-1]$ будет хэш-функцией. Допустим, что входные данные случайным образом однородно и независимо хэширутся в любой из элементов $m$.

Задача атаки «дней рождения» — найти наименьшее количество элементов $n$, которое можно хэшировать при помощи $h$, чтобы мы могли найти два элемента $x, y \in U$, при которых $h(x) = h(y)$.

При атаке «дней рождения» злоумышленник будет случайным образом подбирать $x \in U$ и сохранять пары $(x, h(x))$. Злоумышленник многократно будет выбирать и сохранять эти пары, пока не найдёт двух значений $x, y$, при которых $h(x) = h(y)$. Нам нужно определить, сколько раз атакующему нужно повторить эту операцию, пока он не найдёт коллизию.

Для анализа атаки «дней рождения» можно использовать те же принципы, которые мы применяли для парадокса дней рождения. В атаке «дней рождения» $m$ обозначает количество дней в году, а $U$ аналогична людям, входящим в комнату. Люди хэшируются в их дни рождения, которые могут быть одним из значений $m$. Допустим, нам нужно найти коллизию с вероятностью 99%. Мы должны знать, каково наименьшее $n$, при котором хэш двух значений будет одним днём рождения (в мире хэш-функций это означает, что два входных набора данных хэшируются в одинаковое значение).

Ранее мы показали, что $\Pr[A_n] \approx e^{\frac{-n^2}{2m}}$

Мы хотим задать $\Pr[\overline{A}_n] \approx e^{\frac{-n^2}{2m}} = \frac{99}{100}$, то есть $\Pr[A_n] \approx e^{\frac{-n^2}{2m}} = \frac{1}{100}$.

$\begin{equation*} \begin{split} e^{\frac{-n^2}{2m}} & = \frac{1}{100} \\ \frac{n^2}{2m} & = \ln 100 \\ n^2 & = 2 m \ln 100 \\ n & = \sqrt{2 m\ln 100 } \end{split} \end{equation*}$


Показанный выше анализ говорит нам, что для получения коллизии в хэш-функции с интервалом размера $m$ злоумышленнику нужно однородно и независимо хэшировать приблизительно $\sqrt{2 m\ln 100 } = O(\sqrt{m})$ для почти полной гарантии (вероятности 99%) того, что два элемента хэшируются в одинаковое значение.

Допустим, что мы хотим получать коллизию с вероятностью 50%; тогда нам нужно $n = \sqrt{2 m \ln 2 }$. Важный вывод здесь заключается в том, что для получения коллизии с вероятностью больше 0,5 нам придётся хэшировать порядка $\sqrt{m}$ элементов. Это согласуется с нашим предыдущим анализом при $m = 365$, потому что $\sqrt{2 \ln 2 \cdot 365}$ приблизительно равен 23.

Дополнительные задачи


  1. Имея $n$ людей, $m$ дней и некое число $k$, найти вероятность того, что ровно $k$ людей имеют одинаковый день рождения.
  2. Давайте немного преобразуем приведённую выше задачу. Допустим, у нас есть $m$ дней и некое число $k$. Каким будет наименьшее значение $n$, при котором не менее $k$ людей будет иметь одинаковый день рождения с вероятностью не менее 0,5? Сможете ли вы обобщить эту задачу для любой вероятности $p > 0$?
  3. Допустим, у нас есть 100 чисел от 1 до 100, а также машина, угадывающая случайное число от 1 до 100 в однородном и случайном порядке. Сколько раз нам нужно будет воспользоваться машиной по математическому ожиданию, чтобы машина угадала все числа о 1 до 100?
  4. Сможете ли вы обобщить эту задачу до любых $n$?
  5. Допустим, у нас есть хэш-функция, случайным однородным образом отображающая элементы в области памяти. Пусть всего областей $m$. Сколько элементов $n$ нужно добавить в нашу структуру данных по математическому ожиданию, чтобы в каждую область были хэшированы по крайней мере два элемента?
Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
Total votes 16: ↑13 and ↓3+10
Comments29
1885
Karma
525.3
Rating
@PatientZero

Переводчик-фрилансер

Send message

Articles

Your account

Sections

Information

Services

Support
© 2006–2025, Habr