Ментальный покер

Алгоритм перетасовки карт с использованием коммутативного шифрования выглядит следующим образом[3]:

1. Алиса и Боб соглашаются использовать определенную «колоду» карт. На практике это означает, что они согласны использовать множество чисел или других данных таких, что каждый элемент множества представляет собой карту.
2. Алиса шифрует каждую карту колоды, используя ключ А.
3. Алиса тасует карты.
4. Алиса передает зашифрованную и перемешанную колоду Бобу. Он не знает, где какие карты.
5. Боб выбирает шифрование ключа B и использует его для шифрования каждой карты из уже зашифрованной и перетасованной колоды.
6. Боб тасует колоду.
7. Боб передает дважды зашифрованную и перетасованную колоду обратно Алисе.
8. Алиса расшифровывает каждую карту, используя её ключ А. Но шифрование Боба все ещё остается, то есть она не знает, где какие карты.
9. Алиса выбирает ключ шифрования каждой карты (А1, А2 и т. д.) и шифрует их по отдельности.
10. Алиса передает колоду Бобу.
11. Боб расшифровывает каждую карту, используя его ключ В. Индивидуальное шифрование Алисы все ещё остается, то есть он не знает, где какие карты.
12. Боб выбирает ключ для шифрования каждой карты (B1, B2 и т. д.) и шифрует их по отдельности.
13. Боб передает колоду обратно Алисе.
14. Алиса показывает колоду всем игрокам (в данном случае игроки — Алиса и Боб).

Теперь колода перемешана.

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

Алиса и Боб раздают три карты ${\displaystyle a,b,c}$. Далее используется алгоритм:

1) Они выбирают простое число ${\displaystyle p=23}$, Алиса выбирает простое число ${\displaystyle c_{1}=7}$, взаимно простое с ${\displaystyle p-1}$, и вычисляет число ${\displaystyle d_{1}}$ по обобщенному алгоритму Евклида, то есть: ${\displaystyle (c_{1}*d_{1})\mod (p-1)=1}$ , отсюда ${\displaystyle d_{1}=19}$.

2) Аналогично Боб определяет свою пару чисел: ${\displaystyle c_{2}=9}$ и ${\displaystyle d_{2}=5}$.

3) Далее Алиса выбирает три различных числа в промежутке ${\displaystyle [1,p-1]}$ , например ${\displaystyle a_{0}=2,b_{0}=5,c_{0}=3}$ , и ставит их в соответствие своим картам. Она передает их Бобу в открытом виде.

4) Затем Алиса вычисляет числа: ${\displaystyle u_{1}=2^{7}\mod 23=13;u_{2}=5^{7}\mod 23=17;u_{3}=3^{7}\mod 23=2;}$, перемешивает их и посылает Бобу.

5) Пусть Боб выбирает любое число, например ${\displaystyle 17}$, пересылает Алисе, и это число — её карта (в данном случае ${\displaystyle b}$).

6) Теперь Боб вычисляет: ${\displaystyle v_{1}=13^{9}\mod 23=3;v_{2}=2^{9}\mod 23=6}$ .

7) Он посылает числа Алисе, она выбирает, например, ${\displaystyle 3}$ и вычисляет ${\displaystyle w_{1}=3^{19}\mod 23=6}$ .

8) Алиса отправляет число Бобу, он вычисляет ${\displaystyle z=6^{5}\mod 23=2}$ , таким образом он получает свою карту ${\displaystyle a_{0}}$, то есть карта ${\displaystyle a}$. Карта ${\displaystyle c}$ остается в прикупе, при этом Алиса и Боб об этом не знают[1].

Данный алгоритм имеет недостатки. При шифровании данных некоторые свойства этих данных могут быть сохранены из открытого текста в шифротекст. Это может быть использовано для пометок определенных карт. Таким образом, стороны должны договориться об использовании колоды, где нет карт со свойствами, которые сохраняются во время шифрования.

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