Ментальный покер — система криптографических задач, касающихся честных игр на расстоянии (через телефонную связь или Интернет). Термин происходит от названия карточной игры покер. С аналогичной проблемой связана задача подбрасывания монеты на расстоянии.
История
Поскольку с середины XX века многие сделки, денежные операции стали совершаться в удалённом режиме, появилась необходимость в создании криптографического протокола, способного решать такие задачи. Такой протокол должен был обеспечить не только удобство для пользователя, но и надёжность. Подобную задачу можно сформулировать в игровой форме, опуская некоторые технические детали — таким образом появился термин «ментальный покер».
Впервые в покер без карт пытались сыграть Нильс Бор, его сын и друзья в 1933 году, но попытка оказалась безуспешной. Позже проблемой занялся Роберт Флойд. Его исследования подтолкнули создателей протокола RSA-шифрования Ади Шамира, Рона Ривеста и Лена Адлемана к публикации научного доклада, в котором были предложены протоколы, позволяющие решить проблему ментального покера.
Формулировка задачи
Шамир, Ривест и Адлеман сформулировали задачу так: «Могут ли два нечестных друг к другу игрока сыграть в честный покер без использования карт, а, например, по телефону?»
В покере это звучит так: «Как мы можем убедиться, что ни один игрок не подглядывает в карты других игроков, пока мы перетасовываем колоду?». В реальной карточной игре ответить на такой вопрос просто, так как игроки сидят напротив и наблюдают друг за другом (рассматриваем случай, когда исключена возможность обычного мошенничества). Однако если игроки сидят не рядом, а в отдельных комнатах, и могут передавать колоду друг другу целиком (например, с помощью почты), задача становится весьма трудной. Для электронных карточных игр, таких как онлайн-покер, где сам процесс игры скрыт от пользователя, решить проблему и вовсе невозможно, если используемый метод позволяет одному игроку обманывать другого.
Игра должна удовлетворять определенным требованиям:
Перетасовки карт, использующие коммутативное шифрование
Одним из возможных алгоритмов перетасовки карт является использование коммутативной схемы шифрования. Коммутативная схема означает, что если некоторые данные зашифровывают более чем один раз, порядок, в котором их расшифровывают, не имеет значения.
Пример: Алиса шифрует открытый текст, создавая искаженный шифротекст, который она передает Бобу. Боб шифрует шифротекст снова, используя ту же схему, что и Алиса, но с другим ключом. Если схема шифрования является коммутативной, при расшифровке сообщения не будет иметь значения, кто расшифровывает первым.
Функция шифрования, как и в RSA, должна быть односторонней — зная x, легко можно вычислить f(x), но в обратном направлении для вычисления необходимо знать «секрет». Криптостойкость протокола основана на сложности обращения таких функций. Однако это не исключает возможность частичного вычисления x из f(x).
Алгоритм
Алгоритм перетасовки карт с использованием коммутативного шифрования выглядит следующим образом:
Теперь колода перемешана.
Во время игры Алиса и Боб будут забирать карты из колоды, для которых известен порядок в перемешанной колоде. Когда кто-либо из игроков захочет увидеть свои карты, он будет запрашивать соответствующие ключи от другого игрока. Этот игрок (после проверки того, что игрок действительно имеет право смотреть на карты) передает индивидуальные ключи для этих карт другому игроку. Также необходимо проверить, что игрок не пытался запросить ключ к картам, которые ему не принадлежат.
Пример
Алиса и Боб раздают три карты a , b , c {displaystyle a,b,c} . Далее используется алгоритм:
1) Они выбирают простое число p = 23 {displaystyle p=23} , Алиса выбирает простое число c 1 = 7 {displaystyle c_{1}=7} , взаимно простое с p − 1 {displaystyle p-1} , и вычисляет число d 1 {displaystyle d_{1}} по обобщенному алгоритму Евклида, то есть: ( c 1 ∗ d 1 ) mod ( p − 1 ) = 1 {displaystyle (c_{1}*d_{1})mod (p-1)=1} , отсюда d 1 = 19 {displaystyle d_{1}=19} .
2) Аналогично Боб определяет свою пару чисел: c 2 = 9 {displaystyle c_{2}=9} и d 2 = 5 {displaystyle d_{2}=5} .
3) Далее Алиса выбирает три различных числа в промежутке [ 1 , p − 1 ] {displaystyle [1,p-1]} , например a 0 = 2 , b 0 = 5 , c 0 = 3 {displaystyle a_{0}=2,b_{0}=5,c_{0}=3} , и ставит их в соответствие своим картам. Она передает их Бобу в открытом виде.
4) Затем Алиса вычисляет числа: u 1 = 2 7 mod 23 = 13 ; u 2 = 5 7 mod 23 = 17 ; u 3 = 3 7 mod 23 = 2 ; {displaystyle u_{1}=2^{7}mod 23=13;u_{2}=5^{7}mod 23=17;u_{3}=3^{7}mod 23=2;} , перемешивает их и посылает Бобу.
5) Пусть Боб выбирает любое число, например 17 {displaystyle 17} , пересылает Алисе, и это число — её карта (в данном случае b {displaystyle b} ).
6) Теперь Боб вычисляет: v 1 = 13 9 mod 23 = 3 ; v 2 = 2 9 mod 23 = 6 {displaystyle v_{1}=13^{9}mod 23=3;v_{2}=2^{9}mod 23=6} .
7) Он посылает числа Алисе, она выбирает, например, 3 {displaystyle 3} и вычисляет w 1 = 3 19 mod 23 = 6 {displaystyle w_{1}=3^{19}mod 23=6} .
8) Алиса отправляет число Бобу, он вычисляет z = 6 5 mod 23 = 2 {displaystyle z=6^{5}mod 23=2} , таким образом он получает свою карту a 0 {displaystyle a_{0}} , то есть карта a {displaystyle a} . Карта c {displaystyle c} остается в прикупе, при этом Алиса и Боб об этом не знают.
Недостатки
Данный алгоритм имеет недостатки. При шифровании данных некоторые свойства этих данных могут быть сохранены из открытого текста в шифротекст. Это может быть использовано для пометок определенных карт. Таким образом, стороны должны договориться об использовании колоды, где нет карт со свойствами, которые сохраняются во время шифрования.
Кроме того, используемая схема шифрования должна быть защищена от атак на основе открытого текста: Боб не может определить первоначальный ключ Алисы.
Инструментарий для ментальных карточных игр
Описание сложных протоколов для выполнения и проверки большого количества операций с картами и колодами карт приводится в статье Кристиана Шиндельхауэра. Данная работа связана с операциями «общего назначения» (перетасовка, вставка карты в колоду), которые создают протоколы, применимые к любой карточной игре.
Библиотека libtmcg (C++) обеспечивает реализацию инструментария (неопр.). Шиндельхауэра. Она была использована для реализации немецкой карточной игры скат. В этой игре 3 игрока и колода из 32 карт, поэтому вычислений значительно меньше, чем в покере, в котором от пяти до восьми игроков и используется полная колода из 52 карт.
Протокол «покер без перетасовки»
На сегодняшний день алгоритм ментального покера, основанный на стандартном протоколе «Алиса-Боб», не может обеспечить высокую производительность в онлайн-играх. Требование, что каждый игрок шифрует каждую карту по отдельности, накладывает существенные ограничения. Статья Голле описывает протокол ментального покера, при котором достигается наибольшая эффективность за счет использования свойств игры в покер и ухода от модели «зашифровать-перемешать». Вместо перетасовки карт игроки генерируют (в зашифрованном виде) случайные числа, которые используются для выбора следующей карты. Каждую новую карту необходимо сравнить с остальными, которые уже были розданы, для обнаружения дубликатов. Таким образом, этот метод наиболее эффективен в играх типа «покер», в которых количество карт, раздаваемых игрокам, очень мало по сравнению с размером всей колоды.
Алгоритм генерации карт требует организовать криптосистему с двумя ключевыми свойствами. Шифрование Е должно быть аддитивно гомоморфным, то есть таким что: E(c1)E(c2) = E(c1 + c2). Во-вторых, коллизии должны быть обнаружены без раскрытия открытого текста. Другими словами, задавая E(c1) и E(c2), мы можем определить, выполняется ли равенство c1 и c2. Одним из примеров системы с такими свойствами является схема шифрования Эль-Гамаля.
Алгоритм работает следующим образом:
Таким образом, игроки должны только определить способ шифрования карт, который используется в игре, а также некоторые ограничения на коллизии, которые так же малы, как и количество необходимых карт.