Подбрасывание монеты по телефону

Подбрасывание монеты по телефону (англ. Coin flipping by telephone) — это криптографический протокол, с помощью которого решается задача передачи информации между двумя участниками, находящимися на удалении друг от друга и при этом не доверяющим друг другу. Описание протокола было предложено американским ученым Мануэлем Блюмом в 1981 году, которое он опубликовал в своей статье «Подбрасывание монеты по телефону: протокол для решения нерешаемых задач».

Описание

Приведем схематическое описание работы протокола. Алиса и Боб хотят подбросить монету по телефону, но они находятся на расстоянии друг от друга и могут общаться только по каналу связи. Боб выбирает случайную последовательность бит $b$, записывает его на листе бумаги, запирает этот лист в ящике, оставляя ключ от замка у себя, и посылает ящик Алисе. Предполагается, что, не имея ключа, Алиса не может добраться до содержимого ящика. Получив ящик, Алиса выбирает случайный бит $c$ и посылает его Бобу. В ответ Боб посылает Алисе ключ от ящика. Исходом подбрасывания монеты будет бит $d=b\oplus c$.

Для данного протокола справедливо одновременное выполнение следующих условий:

1. Алиса должна "бросить монету", до того, как Боб загадает свой бит.
2. Алиса не должна иметь возможности изменить результаты своего броска, узнав бит Боба.
3. У Боба не должно быть возможности узнать результат броска перед тем, как он сделает свое предположение.

Алгоритмы подбрасывания монеты

Подбрасывание монеты с помощью однонаправленных функций

Представим, что Алиса и Боб договорились об однонаправленной функции.

Шаг 1. Алиса выбирает случайное число $x$.Далее вычисляет $y=f(x)$, где $f(x)$ - однонаправленная функция.

Шаг 2. Алиса посылает $y$ Бобу.

Шаг 3. Боб пытается угадать четность $x$ и посылает свое предположение Алисе (подбрасывает монету).

Шаг 4. Алиса объявляет результат броска, посылая $x$ Бобу. Если Боб угадал, то результат броска - "орел", если не угадал, то "решка".

Шаг 5. Боб проверяет, не обманула ли его Алиса, подставляя $y=f(x)$

К сожалению данный алгоритм легко поддается обману как со стороны Алисы, так и со стороны Боба. Если Алиса сможет найти $x$ и $x'$, такие что $x$ - четно, а $x'$ - нечетно, и $y=f(x)=f(x')$, то она каждый раз сможет обманывать Боба, так как Боб никак не сможет узнать, какой бит загадала Алиса. Алиса всегда сможет раскрыть тот бит, который ей удобен. Кроме того, наименьший значащий бит $f(x)$ должен быть некоррелирован с $x$. В противном случае Боб сможет обманывать Алису, по крайней мере иногда. Например, если $f(x)$ в 75 процентах случаев четна, когда четен $x$, то у Боба будет преимущество, так как он сможет угадывать значения $x$.

Подбрасывание монеты с помощью криптографии с открытыми ключами

Шаг 1. Алиса и Боб создают пары открытый/закрытый ключ.

Шаг 2. Алиса создает два сообщения, одно для "орла", второе - для "решки". Сообщения должны включать некоторую случайную строку, чтобы она могла подтвердить их подлинность на последующих этапах протокола. Алиса шифрует оба сообщения своим открытым ключом и посылает их Бобу в произвольном порядке.

$E_{A}(M_{1}),E_{A}(M_{2})$

Шаг 3. Боб случайным образом выбирает одно сообщение, шифрует его своим открытым ключом и посылает обратно Алисе.

$E_{B}(E_{A}(M))$, где $M=M_{1}$ или $M=M_{2}$

Шаг 4. Алиса расшифровывает сообщение своим закрытым ключом и посылает обратно Бобу.

$D_{A}(E_{B}(E_{A}(M)))=E_{B}(M_{1})$, если $M=M_{1}$, или $E_{B}(M_{2})$, если $M=M_{2}$

Шаг 5. Боб расшифровывает сообщение своим закрытым ключом, раскрывая результат броска монеты, и посылает расшифрованное сообщение Алисе.

$D_{B}(E_{B}(M_{1}))$ или $D_{B}(E_{B}(M_{2}))$

Шаг 6. Алиса читает результат броска монеты и проверяет, что случайная строка правильная.

Шаг 7. Алиса и Боб раскрывают пары своих ключей, чтобы каждая из сторон могла убедиться в отсутствии мошенничества.

Этот же алгоритм самодостаточен. Любая сторона может немедленно обнаружить мошенничество другой, и не требуется третья сторона ни для участия в протоколе, ни в качестве арбитра после завершения протокола. Покажем справедливость этого утверждения.
У Алисы есть три возможности смошенничать. Во-первых, она может зашифровать два сообщения для "орла" на шаге 2. Боб обнаружит это, когда Алиса раскроет свои ключи на шаге 7.Во-вторых, она может использовать другой ключ для расшифрования сообщения на шаге 4. Но Боб поймет это на шаге 5. И наконец, она может объявить неправильным сообщение на шаге 6. Боб также обнаружит это на 7-ом шаге.
У Боба также есть 3 пути для обмана. Во-первых, он может неправильно зашифровать сообщение на шаге 3, но Алиса обнаружит мошенничество на шаге 6.Во-вторых, он может сказать, что неправильно выполнил шаг 5 из-за жульничества Алисы, но это вскроется на шаге 7. В-третьих, он может послать Алисе сообщение о "решке" на шаге 5, независимо от расшифрованного сообщения, но Алиса может немедленно проверить достоверность сообщения на шаге 6.

Выводы

Рассмотренные выше алгоритмы являются различными реализациями описанного протокола. Первый алгоритм прост в реализации, но достаточно уязвим. Второй же гораздо более надежен в использовании, но и в том числе более сложен. На практике использование алгоритма с однонаправленными функциями более целесообразно, так как по определению однонаправленной функции вычисление обратной к ней является трудоемкой и длительной по времени задачей. Из этого следует, что обман, который совершает Алиса практически невозможно осуществить за приемлемое время. То есть пока Алиса пытается обмануть Боба, Боб может прервать соединение из-за слишком большого времени ожидания.

Применение

Ментальный покер

Протокол подбрасывания монеты позволяет Алисе и Бобу играть друг с другом в покер по электронной почте. Алиса вместо создания и шифрования двух сообщений для "орла" и "решки", создает 52 сообщения по числу карт в колоде. Боб случайным образом выбирает пять из них, шифрует своим открытым ключом и посылает обратно Алисе. Алиса расшифровывает сообщения и посылает их обратно Бобу, который расшифровывает их для определения своей "руки".Затем он случайным образом выбирает еще 5 сообщений и, не изменяя их, посылает Алисе.Она расшифровывает их, и эти соответствующие карты становятся ее "рукой". В течение игры эта же процедура применяется для сдачи игрокам дополнительных карт. В конце игры Алиса и Боб раскрывают свои карты и пары ключей, чтобы каждый мог убедиться в отсутствии мошенничества.

Обмен секретами

Обмен секретами — это общепринятое в литературе название типа криптографических протоколов, в которых у участников, вообще говоря, нет никакой конфиденциальной информации, но у каждого из них есть данные, представляющие для него определенную ценность, и он готов отдать их, но только в обмен на равноценную информацию.
Рассмотрим протокол с двумя участниками Алисой и Бобом.
У Алисы есть секрет $S_{A}$, у Боба $S_{B}$, которые будем считать двоичными строками. Участники согласны обменяться секретами. Проблема в том, что если первый шаг делает Алиса и посылает Бобу значение $S_{A}$, то в ответ она может не дождаться ничего. Если первый Боб, ситуация аналогична. Протокол подбрасывания монеты по телефону исключает такую возможность. Для понимания, каким образом это происходит, необходимо просто заменить в протоколе действие по подбрасыванию монеты, действием по передаче секрета.

Электронная почта с уведомлением

Электронная почта с уведомлением — электронный аналог хорошо известной службы доставки заказной почтовой корреспонденции. В этом случае Алиса — служба доставки, у которой есть файл, адресованный Бобу. Файл должен быть передан Бобу только в обмен на расписку в получении.
В этом сценарии есть одно существенное отличие от общего случая обмена секретами: защищаться нужно от главным образом от нечестных действий получателя.
В качестве примера рассмотрим протокол из работы Атеньезе и Нита-Ротару.

Шаг 1. Алиса выбирает случайное число $r$, вычисляет $y=r^{e}h(M)$, подписывает $y$ и посылает Бобу.Здесь $M$ - сообщение для Боба, $h$ - хеш-функция.

Шаг 2. Боб вычисляет $VE(y^{d})$, подписывает это сообщение и посылает Алисе. $VE$ - функция шифрования криптосистемы с проверяемым шифрованием.Открытый ключ этой криптосистемы общедоступен, секретный ключ доступен известен центру доверия. Криптосистема с проверяемым шифрованием - специальный вид шифра, обладающий следующим свойством. Алиса, получив криптограмму, может проверить, что она содержит подпись для $rh(M)$.Но извлечь эту подпись, не зная секретный ключ, невозможно.

Шаг 3. Алиса посылает Бобу сообщение $M$.

Шаг 4. Боб передает Алисе квитанцию $h(M)^{d}$.

Если в ответ на сообщение Алиса не получила квитанцию, она обращается к центру доверия, передавая ему все отправленные и полученные сообщения, а также $M$ и $r$.
Центр доверия проверяет все подписи, расшифровывает криптограмму и посылает Алисе $h(M)^{d}$, а Бобу $M$.
Данный пример является частным случаем обмена секретами. Протокол подбрасывания монеты по телефону используется здесь для одновременного получения обеими сторонами желаемого: Бобом письма, Алисой расписки.