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

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

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

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

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

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

E_A(M_n)

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

E_В(E_A(M_n))

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

E_A(M_n)

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

E_С(E_A(M_n))

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

D_A(E_В(E_A(M_n)))= E_В(M_n)

D_A(E_С(E_A(M_n)))= E_С(M_n)

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

D_В(E_В(M_n))

D_C(E_C(M_n))

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

E_A(M_n)

7. Алиса расшифровывает сообщения, чтобы узнать свои карты.

D_A(E_A(M_n))

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

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

В идеале, этап (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].

Анонимное распределение ключей

Хотя непохоже, чтобы кто-нибудь собирался использовать этот протокол для игры в покер по модему, Чарльз Пфлегер (Charles Pfleeger) рассматривает ситуацию, в которой этот тип протокола может оказаться полезным [1244].

Рассмотрим проблему распределения ключей. Если предположить, что люди не могут сами генерировать свои ключи(ключи должны иметь определенную форму, или должны быть подписаны некоторой организацией, или еще что-нибудь подобное), то для генерации и рассылки ключей придется создать Центр распределения ключей (Key Distribution Center, KDC). Проблема в том, что нужно найти такой способ распределения ключей, что никто, включая сервер, не сможет понять, кому какой ключ достался. Следующий протокол решает эту проблему:

1. Алиса создает пару открытый ключ/закрытый ключ. В этом протоколе она сохраняет в секрете оба ключа.

2. KDC генерирует непрерывный поток ключей.

3. KDC шифрует ключи, один за другим, своим открытым ключом.

4. KDC передает зашифрованные ключи, один за другим, по сети.

5. Алиса случайным образом выбирает ключ.

6. Алиса шифрует выбранный ключ своим открытым ключом.

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

8. KDC расшифровывает дважды зашифрованный ключ с помощью своего закрытого ключа, получая ключ, зашифрованный открытым ключом Алисы.

9. Сервер посылает шифрованный ключ обратно Алисе.

10. Алиса расшифровывает ключ с помощью своего закрытого ключа.

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

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

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