(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, у Боба будет преимущество. (Иногда наименьший значащий бит не является лучшим выбором для использования в приложении, потому что его вычисление может оказаться слишком простым .)

Бросок монеты с помощью криптографии с открытыми ключами

Этот протокол работает как с криптографией с открытыми ключами, так и с симметричной криптографией . Единственное условие - переключение алгоритма. То есть :

DKi( EKi( EKi( M))) = EKi( M)

В общем случае это свойство не выполняется для симметричных алгоритмов, но справедливо для некоторых алгоритмов с открытыми ключами (например, RSA с идентичными модулями). Этот протокол:

(1)И Алиса, и Боб создают пары открытый ключ/закрытый ключ.

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

EA(Mi), EA(M2)

(3)Боб, которые не может прочитать не одно сообщение, случайным образом выбирает одно из них. (Он м о-жет посчитать их с помощью "Эники-беники ели вареники", воспользоваться компьютером для взлома протоколы или обратиться к цыганке.) Он шифрует выбранное сообщение своим открытым ключом и п о-сылает его обратно Алисе.

Eb(Ea(M)

где M - Mi или M2.

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

Da(Eb(Ea(M)))= Eb(M1), если M = Mi, или Eb(M2), если M = M2.

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

Db(EbMi)) или Db(Eb(M2))

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

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

Этот протокол самодостаточен. Любая сторона может немедленно обнаружить мошенничество другой, и не требуется третья сторона ни для участия в протоколе, ни в качестве арбитра после завершения протокола . Чтобы посмотреть, как это работает, давайте попытаемся смошенничать .

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

Если Боб захочет мошеннически выиграть, его положение ничуть не лучше. Он может неправильно заши ф-ровать сообщение на этапе (3), но Алиса обнаружит обман, взглянув на заключительное сообщение на этапе (6).

Он может заявить, что неправильно выполнил этап (5) из-за какого-то мошенничества со стороны Алисы, но эта форма жульничества вскроется на этапе (7). Наконец, он может послать Алиса сообщение о "решке" на этапе (5), независимо от расшифрованного сообщения, но Алиса сможет немедленно проверить достоверность соо б-щения на этапе (6).

Бросок монеты в колодец

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

Генерация ключей с помощью броска монеты

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

4.11 Мысленный покер

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

Мысленный покер с тремя игроками

Покер интереснее, если в игре участвуют несколько человек. Базовый протокол мысленного покера легко может быть распространен на трех и более игроков . В этом случае криптографический алгоритм также должен быть коммутативным.

(1)Алиса, Боб и и Кэрол создают пары открытый ключ/закрытый ключ.

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

(3)Боб, который не может прочитать не одно сообщение, случайным образом выбирает пять из них. Он ши ф-рует их своим открытым ключом и посылает обратно Алисе.

Eb(Ea(M„))

(4)Боб отправляет Кэрол оставшиеся 47 сообщений.

(5)Кэрол, которая не может прочитать не одно сообщение, случайным образом выбирает пять из них. Она шифрует их своим открытым ключом и посылает Алисе.

Ec(Ea(M„))

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

Da(Eb(Ea(M„)))= Eb(M„)

Da(Ec(Ea(M„)))= Ec(M„)

(7)Боб и Кэрол расшифровывают сообщения своими ключами, чтобы узнать свои карты Db(Eb(M„))

Dc(Ec(M„))

(8)Кэрол случайным образом выбирает пять из оставшихся 42 сообщений и п осылает Алисе. Ea(M„)

(9)Алиса расшифровывает сообщения, чтобы узнать свои карты. Da(Ea(M„))

(10)В конце игры Алиса, Боб и Кэрол раскрывают свои карты и пары ключей, чтобы каждый мог убедиться в отсутствии мошенничества.

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

В идеале, этап (10) является обязательным. Свои "руки" в конце протокола должны открывать не все игроки, а только те, которые не спасовали. Так как этап (10) в протокол только для контроля мошенничества, возможны какие-нибудь улучшения.

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

Если выигрывает Алиса, она раскрывает свою "руку" и свои ключи. Боб может использовать закрытый ключ Алисы для проверки правильности действий Алисы на этапе (2), то есть проверить, что каждое из 52 сообщений соответствует отдельной карте. Кэрол может проверить, что Алиса не лжет о своей "руке", шифруя карты открытым ключом Алисы и проверяя, что они соответствуют шифрованным сообщениям, которые она послала Алисе на этапе (8).

Если выигрывают Боб или Кэрол, победитель раскрывает свои карты и ключи. Алиса может убедиться в правильности карт, проверив свои случайные строки . Она может также убедиться, что сданы были именно эти карты, шифруя их открытым ключом победителя и проверяя, что они совпадают с зашифрованными сообщ е-ниями, полученными на этапах (3) или (5).

Этот протокол не защищен от сговора игроков-мошенников. Алиса и другой игрок могут объединиться и безнаказанно вместе надувать третьего игрока. Следовательно, важно проверять все ключи и случайные строки каждый раз, когда игроки раскрывают свои карты . И если вы сидите за виртуальным столом с двумя игроками, которые никогда одновременно не раскрывают свои карты, причем один из них сдает (в предыдущем протоколе это Алиса) кончайте игру.

Все это красиво в теории, но реализовать все это на компьютере весьма непросто. В реализации для трех и г-роков на трех различных Sparc-станциях восемь часов требуется только для тасования колоды, так что лучше поиграть в настоящий покер [513].

Вскрытия мысленного покера

Криптографы показали, что при использовании этими протоколами покера алгоритма с открытыми ключами RSA происходит небольшая утечка информации [453, 573]. Конкретно, если двоичное представление карт является квадратичным остатком (см раздел 11.3), то зашифрованные карты также являются квадратичным остатком. Это свойство может быть использовано для "крапления" некоторых карт - например, всех тузов . Это даст не много информации о сдачах, но в такой игре как покер даже чуть-чуть информации даст преимущество при длительной игре.

Шафи Голдвассер (Shafi Goldwasser) и Сильвия Микали (Silvia Micali) [624] разработали протокол умственного покера для двух игроков, который решает эту проблему, хотя из-за своей сложности он скорее имеет тол ь-ко теоретическое значение. Обобщенный протокол покера для n игроков, устраняющий проблему утечки информации, был разработан в [389].

Результаты других исследований протоколов игры в покер можно найти в [573, 1634, 389]. Усложненный протокол, позволяющий игрокам не раскрывать своих "рук", приведен в [390]. Дон Копперсмит (Don Coppersmith) рассматривает два способа мошенничества в умственном покере, использующем алгоритм RSA [370].