Криптография для карточной игры P2P

Question

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

Основная проблема, как я понимаю, заключается в том, чточто у каждого игрока есть несколько стопок карт (колода, текущая рука и колода сброса).Ни один из игроков не должен иметь возможности изменять состав этих стопок, кроме случаев, когда это разрешено правилами игры (т. Е. Вытягивать или сбрасывать карты), и при этом игроки не должны знать, что находится в стопках их или их оппонента.

Я чувствую, что должен быть какой-то способ использовать что-то вроде криптографии с открытым ключом для достижения этой цели, но я продолжаю находить дыры в своих схемах.Может кто-нибудь предложить протокол или указать мне некоторые ресурсы по этой теме?

[Править] Хорошо, так что я думал об этом немного больше, и вот идея, которую я придумал.Если вы можете проделать это, пожалуйста, дайте мне знать.

В случайное время у игрока есть стопка карт, ценность которых ему известна.Они принимают эти значения, объединяют случайную соль для каждого, а затем хешируют их.Они записывают соли и передают хеш-коды своему противнику.

Оппонент собирает собственную соль, снова хэширует, затем перетасовывает хэши и передает колоду обратно первоначальному игроку.

Я полагаю, что в этот момент колода была рандомизирована, и ни один из игроков не может знать значения.Однако, когда карта извлекается, противник может раскрыть свою соль, что позволяет первому игроку определить первоначальное значение, а когда карта разыгрывается, игрок обнаруживает свою собственную соль, что позволяет противнику проверить значение карты.

Answer 1

Ваша проблема - известная проблема Mental Poker в криптографии (это была одна из моих любимых частей крипто-класса в колледже) . Это возможно возможно, и оно было решено (частично, как все крипто, Рон Ривест ) , если вы не возражаете против огромный успех.

Проверьте страницу вики для получения более подробной информации.

Answer 2

Традиционная схема Mental Poker излишня. Ваша ситуация на самом деле намного проще, поскольку нет общей колоды. Вы могли бы сделать что-то вроде этого:

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

Обновлено: если подумать, вот более простое решение: как и выше, игрок A шифрует свои карты и отправляет их B. B. тасует их. Всякий раз, когда A хочет карту, он сообщает B, из какой колоды он берет. B возвращает (зашифрованную) карту из соответствующей стопки.

Answer 3

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

Предположим, у игрока A есть карты A1, A2, A3, ... изнабор, представленный числами 0, 1, ... N-1.Эти карты также могут быть разделены на стопки, но это не изменит следующее.

Вместо обработки этих карт одним списком [A1, A2, A3, ...] вместо них можно использовать две из них [A1_a, A2_a, A3_a, ...] и [A1_b, A2_b, A3_b, ...], где одинс игроком A, а другой с игроком B.Они генерируются таким образом, что каждый из них является случайным (в диапазоне 0...N-1), но оба соотносятся так, что A1_a + A1_b = A1, A2_a + A2_b = A2, ... (все операции по модулю N).

• Таким образом, ни один игрок на самом деле не знает карты без доступа к дополнительной колоде (то есть он не может разумно менять свои карты)
• Всякий раз, когда вам нужно знать карту, оба игрока показывают свою соответствующую ценность, и вы добавляете тепо модулю N
• вы можете легко реализовать такие вещи, как "вытянуть карту", обе стопки нужно обрабатывать одинаково

Answer 4

Хотя центральный сервер, вероятно, будет самым простым способом, если вы хотите избежать его, вы можете использовать распределенную систему, в которой каждый, кто играет в игру, является хранилищем для колод других игроков (не для себя или своего оппонента, нокто-нибудь еще).Я полагаю, что Limewire и Bittorrent работают таким образом, поэтому вы можете получить некоторые идеи, изучив эти источники.

Answer 5

Может быть, игроки смогут обмениваться хэшами своих стопок в начале игры.

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

Единственная проблема заключается в том, как колоды сначала перетасовываются.Вы должны убедиться, что игрок не может просто начать свою колоду в любом порядке, который он выберет.

Возможно, игроки получат свой начальный порядок колоды, получая случайность из какого-то определенного источника ... но таким образом, чтобы другиеигрок не может определить порядок колоды другого игрока до конца игры, но все же может проверить, что игрок не играл на своих колодах.Не уверен, как вы могли бы сделать это.

Редактировать:

Еще одна идея.Возможно, вместо генерации случайных колод в начале игры, они могут генерироваться по ходу игры.

Каждый раз, когда игроку нужно взять новую карту из колоды, его противник посылает ему какую-нибудь случайную комбинацию.seed, который используется для выбора следующей карты.

Таким образом, у пользователя нет возможности узнать, в каком порядке карты будут следовать в своих колодах.

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

Answer 6

это адаптация подхода желудей:

установка:

каждый игрок имеет свою колоду (полностью упорядоченные наборы карт) ... эти колоды являются общедоступными и находятся в естественном порядке

каждому игроку нужна асимметричная (подписывающая) пара ключей, обмен открытыми ключами

Теперь к проблеме случайности:

, поскольку игрок не может заранее видеть, какие карты он вытянет, источником нашей случайности будет противник:

когда нам нужно какое-то случайное значение, мы просим нашего оппонента ... случайные значения сохраняются вместе с ходами, которые будут проверены позже

, поскольку наш оппонент может не иметь возможности манипулировать порядком наших карт, мы берем полученное случайное значение и подписываем его нашим закрытым ключом ... значение этой подписи будет нашим семенем ГСЧ (непредсказуемо для оппонента) и позже оппонент может проверить подпись по случайному числу, которое он / она сгенерировал (поэтому мы также храним подписи и обмениваем их после игры)

, так как мы можем делать этот случайный обмен числами каждый раунд, случайные значения не известны игроку заранее -> не заглядывать в порядок нашего стека

и, поскольку теперь у нас есть засеянный ГСЧ, мы можем получить случайные значения, полученные из этого "общего" случайного значения ... таким образом мы можем вытянуть из нашей колоды «случайные» (полностью детерминированные, с повторяемыми проверяемыми результатами) карты ... колоду / колоду не нужно будет перетасовывать, поскольку мы можем получить случайные позиции из нашего RNG

так как мы все обменялись случайными значениями, подписями, начальными колодами (в общем порядке) и всеми ходами, мы можем потом воспроизвести всю игру и проверить на неровности