Русская Википедия:Ментальный покер
Ментальный покер — система криптографических задач, касающихся честных игр на расстоянии (через телефонную связь или Интернет)Шаблон:SfnШаблон:Sfn. Термин происходит от названия карточной игры покер. С аналогичной проблемой связана задача подбрасывания монеты на расстоянииШаблон:Sfn.
История
Поскольку с середины XX века многие сделки, денежные операции стали совершаться в удалённом режиме, появилась необходимость в создании криптографического протокола, способного решать такие задачи. Такой протокол должен был обеспечить не только удобство для пользователя, но и надёжность. Подобную задачу можно сформулировать в игровой форме, опуская некоторые технические детали — таким образом появился термин «ментальный покер»Шаблон:Sfn.
Впервые в покер без карт пытались сыграть Нильс Бор, его сын и друзья в 1933 году, но попытка оказалась безуспешнойШаблон:Sfn. Позже проблемой занялся Роберт Флойд. Его исследования подтолкнули создателей протокола RSA-шифрования Ади Шамира, Рона Ривеста и Лена Адлемана к публикации научного доклада, в котором были предложены протоколы, позволяющие решить проблему ментального покераШаблон:Sfn.
Формулировка задачи
Шамир, Ривест и Адлеман сформулировали задачу так: «Могут ли два нечестных друг к другу игрока сыграть в честный покер без использования карт, а, например, по телефону?»Шаблон:SfnШаблон:Sfn
В покере это звучит так: «Как мы можем убедиться, что ни один игрок не подглядывает в карты других игроков, пока мы перетасовываем колоду?». В реальной карточной игре ответить на такой вопрос просто, так как игроки сидят напротив и наблюдают друг за другом (рассматриваем случай, когда исключена возможность обычного мошенничества). Однако если игроки сидят не рядом, а в отдельных комнатах, и могут передавать колоду друг другу целиком (например, с помощью почты), задача становится весьма трудной. Для электронных карточных игр, таких как Шаблон:Не переведено 4, где сам процесс игры скрыт от пользователя, решить проблему и вовсе невозможно, если используемый метод позволяет одному игроку обманывать другого.
Игра должна удовлетворять определенным требованиямШаблон:Sfn:
- Игрок не знает даже частичной информации о картах своего противника.
- Все возможные исходы равновероятны для обоих игроков.
- В конце игры игрок может удостовериться, что игра была честной и обмана не произошло.
Перетасовки карт, использующие коммутативное шифрование
Одним из возможных алгоритмов перетасовки карт является использование коммутативной схемы шифрования. Коммутативная схема означает, что если некоторые данные зашифровывают более чем один раз, порядок, в котором их расшифровывают, не имеет значения.
Пример: Алиса шифрует открытый текст, создавая искаженный шифротекст, который она передает Бобу. Боб шифрует шифротекст снова, используя ту же схему, что и Алиса, но с другим ключом. Если схема шифрования является коммутативной, при расшифровке сообщения не будет иметь значения, кто расшифровывает первым.
Функция шифрования, как и в RSA, должна быть односторонней — зная x, легко можно вычислить f(x), но в обратном направлении для вычисления необходимо знать «секрет». Криптостойкость протокола основана на сложности обращения таких функций. Однако это не исключает возможность частичного вычисления x из f(x)Шаблон:Sfn.
Алгоритм
Алгоритм перетасовки карт с использованием коммутативного шифрования выглядит следующим образомШаблон:Sfn:
- Алиса и Боб соглашаются использовать определенную «колоду» карт. На практике это означает, что они согласны использовать множество чисел или других данных таких, что каждый элемент множества представляет собой карту.
- Алиса шифрует каждую карту колоды, используя ключ А.
- Алиса тасует карты.
- Алиса передает зашифрованную и перемешанную колоду Бобу. Он не знает, где какие карты.
- Боб выбирает шифрование ключа B и использует его для шифрования каждой карты из уже зашифрованной и перетасованной колоды.
- Боб тасует колоду.
- Боб передает дважды зашифрованную и перетасованную колоду обратно Алисе.
- Алиса расшифровывает каждую карту, используя её ключ А. Но шифрование Боба все ещё остается, то есть она не знает, где какие карты.
- Алиса выбирает ключ шифрования каждой карты (А1, А2 и т. д.) и шифрует их по отдельности.
- Алиса передает колоду Бобу.
- Боб расшифровывает каждую карту, используя его ключ В. Индивидуальное шифрование Алисы все ещё остается, то есть он не знает, где какие карты.
- Боб выбирает ключ для шифрования каждой карты (B1, B2 и т. д.) и шифрует их по отдельности.
- Боб передает колоду обратно Алисе.
- Алиса показывает колоду всем игрокам (в данном случае игроки — Алиса и Боб).
Теперь колода перемешана.
Во время игры Алиса и Боб будут забирать карты из колоды, для которых известен порядок в перемешанной колоде. Когда кто-либо из игроков захочет увидеть свои карты, он будет запрашивать соответствующие ключи от другого игрока. Этот игрок (после проверки того, что игрок действительно имеет право смотреть на карты) передает индивидуальные ключи для этих карт другому игроку. Также необходимо проверить, что игрок не пытался запросить ключ к картам, которые ему не принадлежат.
Пример
Алиса и Боб раздают три карты <math> a, b, c </math>. Далее используется алгоритм:
1) Они выбирают простое число <math> p = 23 </math>, Алиса выбирает простое число <math> c_{1} = 7 </math>, взаимно простое с <math> p-1 </math>, и вычисляет число <math> d_1 </math> по обобщенному алгоритму Евклида, то есть: <math> (c_1*d_1) \mod (p-1) = 1 </math> , отсюда <math> d_1 = 19 </math>.
2) Аналогично Боб определяет свою пару чисел: <math> c_2 = 9 </math> и <math> d_2 = 5 </math>.
3) Далее Алиса выбирает три различных числа в промежутке <math> [1, p-1] </math> , например <math> a_0 = 2, b_0 = 5, c_0 = 3 </math> , и ставит их в соответствие своим картам. Она передает их Бобу в открытом виде.
4) Затем Алиса вычисляет числа: <math>u_1 = 2^7\mod 23 = 13; u_2 = 5^7\mod 23 =17; u_3 = 3^7\mod 23 = 2; </math>, перемешивает их и посылает Бобу.
5) Пусть Боб выбирает любое число, например <math> 17 </math>, пересылает Алисе, и это число — её карта (в данном случае <math> b </math>).
6) Теперь Боб вычисляет: <math> v_1 = 13^9\mod 23 = 3 ; v_2 = 2^9\mod 23 = 6 </math> .
7) Он посылает числа Алисе, она выбирает, например, <math> 3 </math> и вычисляет <math> w_1 = 3^{19}\mod 23 = 6 </math> .
8) Алиса отправляет число Бобу, он вычисляет <math> z = 6^5\mod 23 = 2 </math> , таким образом он получает свою карту <math> a_0 </math>, то есть карта <math> a </math>. Карта <math> c </math> остается в прикупе, при этом Алиса и Боб об этом не знаютШаблон:Sfn.
Недостатки
Данный алгоритм имеет недостатки. При шифровании данных некоторые свойства этих данных могут быть сохранены из открытого текста в шифротекст. Это может быть использовано для пометок определенных карт. Таким образом, стороны должны договориться об использовании колоды, где нет карт со свойствами, которые сохраняются во время шифрования.
Кроме того, используемая схема шифрования должна быть защищена от атак на основе открытого текста: Боб не может определить первоначальный ключ АлисыШаблон:Sfn.
Инструментарий для ментальных карточных игр
Описание сложных протоколов для выполнения и проверки большого количества операций с картами и колодами карт приводится в статье Кристиана Шиндельхауэра. Данная работа связана с операциями «общего назначения» (перетасовка, вставка карты в колоду), которые создают протоколы, применимые к любой карточной игреШаблон:Sfn.
Библиотека libtmcg (C++) обеспечивает реализацию Шаблон:Cite web Шиндельхауэра. Она была использована для реализации немецкой карточной игры скат. В этой игре 3 игрока и колода из 32 карт, поэтому вычислений значительно меньше, чем в покере, в котором от пяти до восьми игроков и используется полная колода из 52 картШаблон:Sfn.
Протокол «покер без перетасовки»
На сегодняшний день алгоритм ментального покера, основанный на стандартном протоколе «Алиса-Боб», не может обеспечить высокую производительность в онлайн-играх. Требование, что каждый игрок шифрует каждую карту по отдельности, накладывает существенные ограничения. Статья Голле описывает протокол ментального покера, при котором достигается наибольшая эффективность за счет использования свойств игры в покер и ухода от модели «зашифровать-перемешать»Шаблон:Sfn. Вместо перетасовки карт игроки генерируют (в зашифрованном виде) случайные числа, которые используются для выбора следующей карты. Каждую новую карту необходимо сравнить с остальными, которые уже были розданы, для обнаружения дубликатовШаблон:Sfn. Таким образом, этот метод наиболее эффективен в играх типа «покер», в которых количество карт, раздаваемых игрокам, очень мало по сравнению с размером всей колодыШаблон:Sfn.
Алгоритм генерации карт требует организовать криптосистему с двумя ключевыми свойствами. Шифрование Е должно быть аддитивно гомоморфным, то есть таким что: E(c1)E(c2) = E(c1 + c2). Во-вторых, коллизии должны быть обнаружены без раскрытия открытого текста. Другими словами, задавая E(c1) и E(c2), мы можем определить, выполняется ли равенство c1 и c2. Одним из примеров системы с такими свойствами является схема шифрования Эль-ГамаляШаблон:Sfn.
Алгоритм работает следующим образомШаблон:Sfn:
- Игроки создают пустой список L, который фиксирует используемые карты.
- Чтобы взять карту, каждый игрок вычисляет случайное число ri в {0, …, 51}, вычисляет E(ri) и публикует схему обязательства E(ri).
- Затем игроки показывают их значение E(ri) и можно убедиться, что каждый игрок честен с остальными.
- Игроки вычисляют значение <math>\Pi E(r_i) = E(\Sigma r_i) </math>, которое образует новую зашифрованную карту E(r*) : <math>r* = \Sigma r_i</math>
- Игроки проверяют, есть ли E(r*) в L. Если нет, E(r*) раздается соответствующим игроком и добавляется к L. Когда карты раскрыты, они могут быть совместно расшифрованы.
Таким образом, игроки должны только определить способ шифрования карт, который используется в игре, а также некоторые ограничения на коллизии, которые так же малы, как и количество необходимых карт.
См. также
Примечания
Литература
- Шаблон:Source
- Шаблон:Книга
- Шаблон:Source
- Шаблон:Книга
- Шаблон:Source
- Шаблон:Source
- Шаблон:Статья
- Шаблон:Статья
