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

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

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

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

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

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

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

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

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

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

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

Еа(Мп)

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

Ев(Еа(Мп))

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

Еа(Мп)

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

Ес(Еа(Мп))

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

Ва(Ев(Еа(М.п)))= Ев(Мп)

Ва(Ес(Еа(Мп)))= Ec(Mn)

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

Dc(Ec(M„))

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

(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].

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

Хотя непохоже, чтобы кто-нибудь собирался использовать этот протокол для игры в покер по модему , Чарльз Пфлегер (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 существует ряд действий, которые может предпринять Алиса, чтобы получить больше информации, чем ей удалось бы при другом методе шифрования. В нашем сценарии эта проблема не существенна, но при других обстоятельс т-вах она может стать важной.

4.12 Однонаправленные сумматоры

Алиса является членом организации "Заговорщики" . Иногда ей приходится встречаться с другими членами в плохо освещенных ресторанах и шептать секреты налево и направо . Беда в том, что рестораны настолько плохо освещены, что она не может быть уверена, что человек, сидящий напротив нее за столом, тоже член организ а-ции.

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

Новым решением является использование однонаправленного сумматора [116]. Это что-то похожее на од-