Возможен ли алгоритм реализации карточных игр без участия логики на сервере с защитой от читерства?

В любом случае сервер необходим. Даже если его роль выполняет один из клиентов. И от читерства именно на этом клиенте защититься не получится. Хотя по максимуму защититься от него - можно.

Logo, Что значит - `без участия логики на сервере`? Сервер - это тот, кто раздает карты. Проверить честность раздающего без доступа к серверу - нельзя.

Думаю что возможен (по крайней мере для некоторых игр).

В двух словах, протокол примерно следующий.
Раздающий компьтер, делает полный снимок состояния (колоды в момент раздачи и проч.) зашифровывает случайным паролем и отсылает это состояние партнеру в зашифрованном виде.

Пароль же к этим данным, партнер получит только после кона игры.
И сможет проверить что не было шулерства.
Ну, в сыром виде, приблизительно, как-то так...

Угу... вот только кто мешает эту колоду перемешать так, чтобы заведомо поиметь преимущество? ну а потом пошифрить и отправить...
И в любом случае тот, кто сидит за раздающим компом, имеет возможность "подглядеть" расклады.

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




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




Это сообщение отредактировал(а) volatile - 4.9.2015, 19:58

Сначала он это состояние СОЗДАЁТ. Причём в нешифрованном виде. Перехватить - не проблема. Немного подкорректировать - в общем тоже.

Зато может посмотреть результат перемешивания. Я не представляю, как тасовать, и особенно раздавать, колоду, когда её состояние зашифровано. Не говоря уж о том, что можно вести опережающую раздачу в копии памяти процесса.

Вот тут http://habrahabr.ru/post/147241/ предложен алгоритм раздачи, но он работает для количества игроков >= 3 и сговор между двумя игроками против третьего должен быть исключен.

Это сообщение отредактировал(а) Logo - 4.9.2015, 23:09

Akina, Идея, насколько я понял, в том, что игрокам сервер посылает начальное состояние колоды, играющий "перемешивает" колоду собственным случайным "кодом". 

В этом месте надо бы исключить моделирование расклада на стороне клиента. Для этого коды можно складывать в доверенное хранилище с правом "добавить", но не "читать". Право "читать" появляется у всех игроков только после игры.

Права можно обеспечить шифрованием с ключами. Начальное состояние шифруется ключами игроков и ключём сервера. Код перемешивания шифруется ключём игрока.
После игры все ключи вскрываются и все ходы становятся доступны для проверки...

Вроде, получается чисто...

 

Доверенное хранилище не должно быть доступно ни одному игроку. Не вижу реализации этого, если отсутствует недоступный ВСЕМ игрокам сервер. 

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

К тому же недоступное никому хранилище нельзя проверить === отсутствие доверия со стороны параноидальных игроков ;)

Добавлено через 6 минут и 40 секунд
Паранойя распространяется и на сервер.  Так что считать сервер неподсудным нельзя...

Хранилище такое не проблема, каждый игрок может сохранять свои данные у себя, а остальным отправлять подпись, например MD5 хеш от данных. В конце  же он должен открыть хранилище, а остальные сверят подпись с данными. Так можно морской бой реализовать без читерства.
Но с картами сложнее тут раскладка должна быть такой, что бы ни один игрок по отдельности не мог ее расшифровать, и в тоже время все месте они могли это делать, что бы открывать карты (по одной).

Logo, Давай я точнее сформулирую, что у меня пока получается.

• Перед началом игры каждый игрок и сервер сочиняют по паре ключей - публичный/приватный. Публичный отдается серверу+остальным игрокам, для обеспечения приватного чата.
• сервер мешает колоду случайным образом первый раз, упаковывает ее состояние последовательно всеми публичными ключами игроков и выкладывает в доступное всем место (рассылает игрокам в виде черного ящика, для послеигрового контроля).
• "Следующий по порядку" игрок генерирует "сдвиг" - код, по которому колода еще раз перемешивается. Сдвиг складывается в хранилище(рассылается игрокам ).
• Игра идет, карты раздаются, ходы игроков записываются.
• По окончании игры, все приватные ключи открываются и у каждого игрока появляется возможность проверить, что колода в процессе игры не тасовалась, порядок карт в колоде не менялся и все игроки играли своими картами.

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

Игрок шифрует своё расположение, и только отвечает "мимо-ранен-убит" на каждый ход соперника... это очевидно. Но тут всё проще - у каждого своё поле. В отличие от карточной игры, где колода одна на всех.

Изначально задача ставилась так, что сервера НЕТ.

Сервер - тот кто карты раздает в эту игру. Можно это право по очереди клиентам передавать.

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

Akina, Я как-то упустил, что знания о картах, которые выдаются игрокам - тоже должны быть секретны для всех... Мои измышления защищают колоду от явного подтасовывания. От "подглядывания" в колоду - не защищают... :(

Вот так можно обеспечить секретность колоды:
Для колоды каждый игрок придумывает секретый ключ (один) Шифрование должно быть адитивное, тоесть если кодировать ключем А, потом Б, то раскодировать можно, применяя оба ключа в любом порядке А,Б или Б,А.
Крупье мешает карты, кодирует каждую карту своим ключем, передает колоду по кругу всем игрокам. Игроки также кодируют карты своим ключем, перемешивают и передают дальше.
Крупье выдает карту игроку A. Перед этим, карта передается по всем игрокам, кроме А и каждый ее декодирует. Так что последняя операция расшифровки у игрока А. Карта у него.  

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

Собсно в такой постановке как таковой крупье не нужен. Раздача начинается с того, что игроки случайным образом генерируют порядок перемешивания (кто первый, кто второй и так далее - тот же порядок можно оставить и для вскрытия карты, замкнув кольцо, порядок можно генерить как на каждую раздачу, так и на всю партию). Перемешанная всеми колода публикуется и разбирается по порядку.

Это сообщение отредактировал(а) Akina - 7.9.2015, 18:10

Можно и один ключ. Тут кодирование-раскодирование выполняет сам игрок. Ключ можно вскрыть только в конце раунда, если у партнеров появились сомнения в читерстве.

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

Logo, сфига бы?
Первый игрок тасует карты и шифрует их по отдельности, а не всю колоду целиком. Получая 36 шифрованных блоков. Второй тасует эти блоки, шифрует их по отдельности (всё, исходный порядок сдох) и передаёт третьему. И так далее.

Допустим, надо открыть карту #1 в получившейся закрытой колоде для второго игрока. Третий игрок говорит, что положил на место #1 карту #5 от второго игрока. Второй не знает, что за карта у него на позиции #5, только знает что взял ее с позиции допустим #3 от первого игрока. Он вынужден спросить у первого игрока, какую карту он положил на место #3. Он говорит, и таким образом эту карту знают уже 2 игрока, первый и второй, а должен знать только второй.
Так ведь?

Это сообщение отредактировал(а) Logo - 9.9.2015, 13:46

Не так.
После того, как КАЖДЫЙ перемешал колоду и зашифровал её карты своим ключом, колода публикуется. Игроку 2 надо дать карту 1 из этой колоды? Игрок 3 берёт эту карту (и удаляет её из своей копии колоды), дешифрует, результат передаёт игроку 4, тот дешифрует (и удаляет карту 1 из своей копии колоды) и передаёт игроку 1, он дешифрует (и удаляет) и передаёт игроку 2, тот дешифрует (и удаляет), узнаёт, какая это карта, и прикладывает к имеющимся на руках. Все остальные имели дело с картой, зашифрованной как минимум одним игроком (кроме себя), и узнать, что это за карта, не смогут.

Logo, Это точно карточная игра?   

Для примера, игра - "дурак", подкидной, на 4 игрока.

Перемешивание:
- колода 36 незашифрованных карт.
- игрок №1 копирует к себе колоду, перемешивает карты и шифрует каждую карту своим ключем.
- игрок №2 копирует к себе зашиврованную колоду, перемешивает карты и шифрует каждую карту своим ключем.
- все остальные игроки по очереди делают так же
- итого, в колоде лежат 36 зашифроманных всеми 4-мя ключами карт-чисел в неизвестном никому порядке.

Раздача:

Игроки по очереди берут из колоды по 6 карт.
- перед тем, как игрок №1 получит карту с верха колоды, эта карта последовательно передается всем остальным игрокам и они ее расшифровывают. Когда карта попадает к игроку #1, она все равно зашифрована, но уже только его ключем, таким образом,после раскодирования, номинал карты известен только игроку #1.
- каждый игрок по очереди набирает по 6 карт таким же макаром.

Итого, у каждого игрока по 6 карт с известным только игрокам номиналом.

Игра идет "обычным" образом, карты выкладываются на стол в незашифрованом виде.

Финальная проверка нужна от "туза в рукаве" - подмены номинала своей карты игроком. Весь ход игры можно воспроизвести до места шулерства.

Опасно. 
Смотри... идёт игра. Игрок 1 должен взять очередную карту. Ему эту карту передаёт, скажем, игрок 2, и карта зашифрована только ключом игрока 1. Игрок 2 это запоминает. По окончании партии он будет знать, какой картой она НЕ МОЖЕТ быть (он знает, какие карты уже вышли или засветились в неотбитой им взятке - если, например, играют в дурака), и с некоторой долей вероятности предполагать, какой она МОЖЕТ быть (анализируя игру).
Начинается другая раздача. Ключ игрока 1 тот же. Опять он берёт карту, и опять игрок 2 ему её передаёт для окончательной дешифровки. Раз ключ тот же, то и шифрованная карта та же - то есть игрок 2 получает некие сведения о вероятном наличии карты у игрока 1. Это недопустимо.

А зачем тот же? Можно генерировать ключи каждый тур. А в конце тура ключи вскрывать, чтобы автоматически или в ручном режиме проверить честность этого тура. Гарантированное обнаружение шулерства, как бы, будет от него защищать...

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

Кодировать надо 1 байт (4 масти и <16 номиналов). "Солить" этот байт особенно не получится, так как сервера, который бы следил за "солью" у нас нет.

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

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

Мне кажется, что описанная мной последовательность доказывает, что не МОЖНО, а НУЖНО.

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

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

Когда я говорил "пара ключей", я имел в виду, что алгоритм может быть несимметричным. В случае же симметричного формально можно считать, что ключа всё равно два, только они совпадают. Такой подход (уже на стадии программирования) даст более универсальный код.