Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Project: Mental Poker
Views: 58
from random import randint import copy import hashlib
#Итак, это прототип системы для p2p покера. #Протоколы, исполняемые совместо игроками выделены в глобальные функции. #Алгоритмы, выполняемые лично игроком засунуты в класс Player. Вся крипта в классе Encryptor. #Некоторые криптографические моменты пока что немного упрощены (например, не приводится генерация простого числа для шифра), т.к. не имеют отношения к ментальному покеру. #Некоторые комментарии могут показаться изишними в плане математических/криптографических объясений. Это я оставил для себя. #Моделирование игры (техасский холдем) внизу искать. # # Введем следующие обозначения для большей ясности: # O-Card (open card, открытая карта) - число (или битовая строка, с числами удобнее работать), которая однозначно определяет некоторую карту из колоды. # M-Card (masked card, замаскированная карта) - карта с наложенной маской. Карта, которая была зашифрованна последовательно группой игроков. Причем для маскировки карт (наложения маски) игроки используют один и тот же ключ для всех карт (у каждого игрока свой уникальный ключ). M-Card - результат шифрования O-Card на маскировочном ключе. # L-Card (locked card, закрытая карта) - закрытая карта. Карта, которая была зашифрованна последовательно группой игроков. Причем для шифрования игроки используют уникальный ключ для каждой карты (у каждого игрока свой уникальный ключ для каждой карты). L-Card - результат шифрования O-Card на ключе запирания. # ML-Card - карта, на которую была наложена маска (M-Card), после чего ее закрыли (зашифровали) (L-Card). # F-Card (free card, свободная карта) - карта, которая была раздана на руки игроку (или на стол, но ее значение неизвестно)
#Криптографические функции, используемые игроками. Для протокола монут использоваться различные криптосистемы. Довольно простым вариантом является шифр Полига-Хеллмана, он и реализован здесь. #Шифр Полига-Хеллмана - это что-то вроде RSA, но модуль выглядит не как N = p*q, (p, q - простые) а как N = p = 2*q + 1 (p, q - простые) class Encryptor(object): def __init__(self): self.q = 0 #Простое число для получения модуля self.p = 0 #Модуль игрока, простое число вида 2*q + 1 (a.k.a. сильно простое) self.set_modulus() #генерация модуля. Модуль является общим для ВСЕХ игроков за столом. #Шифрование при помощи шифра Полига-Хеллмана #card - число, которое представляет собой карту для зашифрования #key - ключ шифрования def encrypt(self, card, key): enc_card = pow(card, key[0], self.p) return enc_card #Дешифрования при помощи шифра Полига-Хеллмана #card - число, которое представляет собой карту для расшифрования #key - ключ расшифрования def decrypt(self, card, key): dec_card = pow(card, key[1], self.p) return dec_card #Перемножение двух ключей для получения общего ключа #Для коммутативных шифров (PH шифр таким и является) выполянется свойство, что encrypt(message, k1*k2) = encrypt(encrypt(message, k1), k2). Это используется в протоколе def key_mul(self, key1, key2): return Mod(key1 * key2, self.p - 1) #locking card. Закрытие карты, ничем не отличается от шифрования карты. Ввел просто для того, чтобы было более очевидно в протоколах, где карты закрываются, а где маскируются def lock_card(self, card, key): l_card = self.encrypt(card, key) return l_card #masking card. Маскировка карты, ничем не отличается от шифрования карты. Ввел просто для того, чтобы было более очевидно в протоколах, где карты закрываются, а где маскируются def mask_card(self, card, key): m_card = self.encrypt(card, key) return m_card #Получение open_card из ml_card. Ничем не отличается от дешифрования карты. Также введено для большей наглядности def open_card(self, card, key): m_card = self.decrypt(card, key) return m_card #Шифровка сразу целого списка карт X ключами из списка K. Если K состоит только из одного элемента, то все карты шифруются одним ключом def encrypt_cards(self, X, K): Y = [0]*len(X) if len(K) == 1: for i in range(0, len(X)): Y[i] = self.encrypt(X[i], K[0]) else: for i in range(0, len(X)): Y[i] = self.encrypt(X[i], K[i]) return Y #Закрытие (locking) сразу целого списка карт X. Каждая карта шифруется своим ключом из списка K. По факту ничем не отличается от encrypt_cards, введено для большей ясности def lock_cards(self, X, K): return self.encrypt_cards(X, K) #Перемешивание + маскировка списка карт X на ключе m с перестановкой F def shuffle_mask_cards(self, X, m, F): m_cards = [0]*len(X) sm_cards = [0]*len(X) #Сначала маскируем карты, шифруя их одним ключом for i in range(0, len(X)): m_cards[i] = self.encrypt(X[i], m) #Теперь тасуем их for i in range(0, len(X)): sm_cards[F[i]] = m_cards[i] return sm_cards #Установка модуля шифра Полига-Хеллмана, #Пока что для упрощения это фиксированое число def set_modulus(self): self.q = 509 self.p = 2*self.q+1 #Генерация пары (ключ шифрования, ключ дешифрования). Внимание: хоть ключи и разные, они оба держутся игроком в секрете def generate_key(self): e = randint(2, self.p-1) #Наибольший общий делитель (gcd) e и p-1 должен быть равен 1 (т.е. эти два числа должны быть взаимно простыми). Ищем такой ключ, который подошел бы под требование. while(gcd(e, 2*self.q) > 1): e = randint(2, self.p-1) #Находим ключ дешифрования как e^(-1) mod (p-1) d = pow(e, -1, 2*self.q) return (e, d) ###### #Случайная перестановка массива из N элементов. Необходим криптостойкий генератор случайных чисел, пока что для упрощения это просто randint def random_permutation(self, N): #Тривиальная перестановка (оставльяет каждый элемент на своем месте). Нужна для проверки: так как подобная перестановка нежелательна, будем исключать такой результат identity = [i for i in range (N)] #Будущая перестановка (если F[2] = 5, значит, при применении перестановки 2 элемент массива встанет на 5 место) F = [i for i in range (N)] #Генерируем перестановку, пока она не будет отличной от тривиальной while (F == identity): #Оставшиеся свободные позиции, которые надо расположить в перестановке positions = [i for i in range (len(F))] #для всех элементов перестановки F for i in range(0, len(F)): #Выбираем случайный элемент из positions idx = randint(0, len(positions) - 1) #Записываем в перестановку F[i] = positions[idx] #Удаляем выбранный элемент из positions del positions[idx] #Возращаем полученную перестановку return F #Тождественная перестановка (каждый элемент остается на своем месте) из N элементов def identity_permutation(self, N): return [i for i in range(N)] #Переставляет элементы массива X согласно перестановке F def permute(self, X, F): Y = [0]*len(X) for i in range(0, len(X)): Y[F[i]] = X[i] return Y
class Player(object): def __init__(self, number): #Номер игрока за столом. Однозначно определяет игрока за столом self.number = number #Ключ для демаскировки карты (снятия маски с M-card). Будем называть его также маскировочным ключом. Позволяет получить O-Card из M-Card self.mask_key = 0 #Словарь, сопоставляющей каждой закрытой карте (L-Card) ее ключ для дешифрования (ключ запирания). Позволяет получить O-Card из L-Card self.lock_keys = {} #Словарь, сопостовляющий каждой F-Card на руке игрока ее мастер-ключ для дешифрования (позволяет узнать значение карты), составленный из комбинации ключей ВСЕХ игроков. #Позволяет получить O-Card из ML-Card self.master_keys = {} #Словарь, сопостовляющей каждой F-card ее ключ дешифрования в виде комбинации (произведения) всех mask-key и lock-key, наложенных ЭТИМ игроком на эту карту. self.card_keys = {} #Поле для хранения состояния основной колоды игры. self.main_deck = None #Поле для хранения состояния основной колоды, подготовленной к раздаче self.prepared_main_deck = None #Поле для хранения всех открытых карт (O-card), которые составляют колоду (список карт, которые используются в игре). self.open_deck = None #Словарь, который определяет соответсвие каждой открытой карты (O-card) ее значение self.cards_value = {} #Колода, испльзуемая для промежуточных вычислений self.temp_deck = None #Представление ключей после закрытия карт. Представление ключа - это просто пара (p, c), где p - открытая карта, с = encrypt(p, c). Используется для верификации self.lock_representative = {} #Аналогично lock_representative но для раунда маскировки карт self.mask_representative = {} #Список подготовленных к раздаче карт колоды self.prepared_cards = {} #Словарь, поторый опредлеяет, какого игрок на руке держит карту - ключ словаря self.card_holder = {} #Карты на руках игроков. Эту информацию можно вытащить из card_holder, но такой вариант был бы менее удобен. self.hand_cards = [] #Известные карты (карты, которые были открыты + карты на руке игрока). Необходимы для проверки валидности открываемых карт self.showed_cards = [] #Карты на столе (в открытом виде) self.table = [] #Карта, которую сейчас положат на стол (для верификации дилера) self.table_card = 0 #Шифровальщик игрока. Все криптографические функции (а также ключи игрока) собраны в нем self.encryptor = Encryptor() #Множество карт, которое используется при восстановлении колоды после того, как один из игроков покинул игру self.recovery_set = [] #Ключ, используемый при создании наборов для восстановления self.recovery_set_key = 0 #Представление для восстановления self.recovery_mask_representative = [] #Количество выданных из колоды карт self.dealed_cards = 0 #Создает строку случайной карты (число в пределах модуля криптосистемы). Необходим криптостойкий генератор чисел def create_random_card(self): return randint(2, self.encryptor.p) #Создает карту в виде числа N. Если N > p, то оно приводится по модулю def create_card(self, N): return N % self.encryptor.p #Просто заглушка для симуляции. Символизирует собой рассылку некоторого значения value всем игрокам (или, иногда, какому-то конкретному игроку) def broadcast(self, value): return 0
def broadcast(a): return 0
def create_deck(N, players_list): #Протокол выполняется игроками по порядку возрастания их номера players = sorted(players_list, key=lambda x: x.number) #Каждый игрок подготавливает список hand_cards для будущей игры for player in players: player.hand_cards = [[] for i in range(len(players))] #Нулевой игрок (будет считать его дилером) генерирует начальную карту. Для шифра Полига-Хеллмана число p-4 всегда будет являться генератором QNR-группы, используем его gen_card = players[0].encryptor.p - 4 #Дублируем ее N раз, получаем колоду одинаковых карт X = [gen_card]*N #Далее эта колода рассылается всем игрокам players[0].broadcast(X) #Происходит процесс зашифровки карт игроками. Каждая карта шифруется своим ключом. По той же логике, что и в Signidice получаются псевдослучайные непредсказуемые числа. #Эти числа и будут являться идентификаторами карт в колоде locking_round(X, 1, True, players) #Далее каждый игрок в порядке возрастания его номера for i in range(len(players)): #Полученную колоду запоминает как основную players[i].main_deck = copy.copy(players[i].temp_deck) #Ключи для расшифрования и представления, полученные в результате locking_round выше игрокам не понадобятся, так как нет необходимости возвращаться к первому случайному числу. #Эти ключи и представления удаляются и буду заполнены реальными игровыми ключами. players[i].lock_keys = {} players[i].lock_representative = {} #Маркировка полученной колоды, присваиваем каждому идентификатору некоторое игровое значение (например, 7 черви, король пик et cetera). set_open_deck(players)
def locking_round(card_list, lock_round, verified, players_list): #Протокол выполняется игроками по порядку возрастания их номера players = sorted(players_list, key=lambda x: x.number) #Каждый X[i], Y[i] символизирует две копии колоды, которые лежат у игрока. Т.е. каждый игрок обладает своими X, Y и в реальной системе они не объединяются в список X = [card_list for i in range(len(players))] #Это будет списками карт, которые игроки получают на вход для шифрования Y = [card_list for i in range(len(players))] #Представляет собой уже колоду, состоящую из lock-cards (карты, каждая из которых зашифрована своим собственным ключом) #Каждый игрок по очереди выполняет это на своей машине, после чего рассылает результат (Y[i]) всем остальным for i in range(0, len(players)): #Первый игрок просто берет входную колоду для протокола и шифрует ее (то есть изначальный card_list) if i == 0: X[i] = card_list #В данной реализации эти значения стоят по дефолту, но в других может быть иначе, в таком случае надо будет приравнять else: X[i] = Y[i-1] #Если игрок не первый по списку, то он берет результат шифрования предыдущенго игрока, который тот должен был разослать всем #Шифрование может оказаться неудачным с первого раза (привести к появлению повторных карт), потому будем запускать в цикле его is_card_properly_encrypted = False while not is_card_properly_encrypted: #Создаем ключи шифрования для каждой карты в колоде keys = [] for j in range(0, len(card_list)): #Каждый ключ должен быть уникальным, потому ищем ключи, которые еще не были сгенерированы new_key = players[i].encryptor.generate_key() while (new_key in keys): new_key = players[i].encryptor.generate_key() keys.append(new_key) #Теперь строим список locking-cards (зашифрованных карт, каждая из которых шифруется на собственном ключе) Y[i] = players[i].encryptor.lock_cards(X[i], keys) #Далее проверяем, что в колоде не появилось двух одинаковых карт (любым способом проверки списка на это, я сделал так на скорую руку, наверняка есть способ умнее) sorted_cards = sorted(Y[i]) #Теперь карты отсортированы по возрастанию. Если есть две одинаковых карты, то они будут рядом is_card_properly_encrypted = True for j in range(len(sorted_cards) - 1): if (sorted_cards[j] == sorted_cards[j + 1]): is_card_properly_encrypted = False #Здесь игрок должен разослать всем остальным игрокам полученное Y[i]: players[i].broadcast(Y[i]) #В случае необходимости, верифицируем результаты шифрования i-го игрока. if verified: S_LVP(keys, X[i], Y[i], i, players_list) if lock_round > 0: for j in range (len(keys)): #Игрок запоминает использованные ключи: Lock_keys[lock_round, j] = k[j]. #Индекс словаря задается через два значения, потому для однозначной идентификации я использовал приведение в строку (repr(число) = его строчное представление). #Можно иначе это делать как-нибудь, не принципиально. Главное получить хеш-таблицу, которая по номеру раунда и номеру ключа в этом раунде однозначно определяет ключ. players[i].lock_keys[repr(lock_round) + ":" + repr(j)] = copy.copy(keys[j]) #Далее все игроки записывают как изменилась каждая карта в lock_representative for p in range(len(players)): for j in range(len(X[i])): if lock_round > 0: #Как и ранее через строку получаю уникальные ключи для словаря players[p].lock_representative[repr(lock_round) + ":" + repr(i) + ":" + repr(j)] = [X[i][j], Y[i][j]] #Все представления (representative) состоят из пары элементов: карты и ее зашифрованного значения. Это можно вынести в отдельную структуру, да. for j in range(0, len(players)): players[j].temp_deck = copy.copy(Y[len(players) - 1]) #результат "закрытия" - это колода, полученная при шифровании последним игроком
#Протокол приваивания значений полученной колоде карт из псевдослучайных чисел. #В нем каждому числу присваивается некоторое игроков значение (туз пик, 7 буби и прочее) #players_list - список игроков, здесь используется для большего удобства. def set_open_deck(players_list): #Каждый игрок проделывает это for player in players_list: #Предполагается, что в момент вызова протокола в переменной temp_deck лежит открытая колода player.open_deck = copy.copy(player.temp_deck) #Далее cards_value заполняется некоторым определенным образомю #Например, нулевой карте будет соответствовать 6 черви. Первой карте - 7 черви и т.д. #Здесь, в качестве примера, я использую деку из 20 карт со значениям от 6 до 10 всех четырех мастей player.cards_value[player.open_deck[0]] = "6H" #6черви player.cards_value[player.open_deck[1]] = "7H" player.cards_value[player.open_deck[2]] = "8H" player.cards_value[player.open_deck[3]] = "9H" player.cards_value[player.open_deck[4]] = "10H" player.cards_value[player.open_deck[5]] = "6S"#6 пик player.cards_value[player.open_deck[6]] = "7S" player.cards_value[player.open_deck[7]] = "8S" player.cards_value[player.open_deck[8]] = "9S" player.cards_value[player.open_deck[9]] = "10S" player.cards_value[player.open_deck[10]] = "6D"#6 буби player.cards_value[player.open_deck[11]] = "7D" player.cards_value[player.open_deck[12]] = "8D" player.cards_value[player.open_deck[13]] = "9D" player.cards_value[player.open_deck[14]] = "10D" player.cards_value[player.open_deck[15]] = "6C"#6 треф player.cards_value[player.open_deck[16]] = "7C" player.cards_value[player.open_deck[17]] = "8C" player.cards_value[player.open_deck[18]] = "9C" player.cards_value[player.open_deck[19]] = "10C"
def verified_shuffle_masking_round(in_deck, players_list): #Протокол выполняется игроками по порядку возрастания их номера players = sorted(players_list, key=lambda x: x.number) #Каждый X[i], Y[i] символизирует две копии колоды, которые лежат у игрока. Т.е. каждый игрок обладает своими X, Y и в реальной системе они не объединяются в список X = [in_deck for i in range(len(players))] #Колода, которую игрок получает на вход (через broadcast для всех, кроме 0 игрока) и шифрует Y = [in_deck for i in range(len(players))] #Представляет собой уже колоду, состоящую из masking-cards (карты, зашифрованные общим ключом) #Все игроки в порядке возрастания их номера for i in range(len(players)): #Первый игрок в качестве входной колоды берет колоду, которую необходимо замешать if i == 0: X[i] = in_deck #Остальные игроки берут результат перемешивания предыдущего игрока else: X[i] = Y[i-1] #Игрок генерирует некоторую случайную перестановку колоды F = players[i].encryptor.random_permutation(len(X[i])) #Также генерируется ключ для маскировки карт m = players[i].encryptor.generate_key() #Далее игрок перемешивает и маскирует колоду Y[i] = players[i].encryptor.shuffle_mask_cards(X[i], m, F) #Полученная колода рассылается всем players[i].broadcast(Y[i]) #Игрок созддает представление для верификации p = players[i].create_random_card() c = players[i].encryptor.mask_card(p, m) R = [p, c] #Рассылает его остальным игрокам players[i].broadcast(R) #Верификация HMVP(m, F, X[i], Y[i], i, [R[0]], [R[1]], players_list) players[i].mask_key = m #Все игроки добавляют представление игрока i for player in players: player.mask_representative[i] = R #Все игроки устанавливают в качестве результата работы протокола полученную последним игроком колоду for player in players: player.temp_deck = copy.copy(Y[len(players)-1])
#Протокол перемешивания колоды in_deck #in_deck - колода, которую необходимо замешать #players_list - список игроков, здесь используется для большего удобства. def shuffle_deck(in_deck, player_list): #Собственно, перемешивание колоды + наложение маски на карты verified_shuffle_masking_round(in_deck, player_list) #Каждый игрок определяет основную колоду как колоду, полученную на предыдущем шаге (результат verified_shuffle_masking_round записывается в temp_deck каждого игрока) for player in player_list: player.main_deck = copy.copy(player.temp_deck)
def prepare_cards_to_deal(v, player_list): #У всех игроков main_deck находится в одном и том же состоянии. Они берут из нее первые v карт и запускают с ними протокол locking_round #Здесь это сделано на примере 0 игрока cards_for_preparing = [] for i in range(v): cards_for_preparing.append(player_list[0].main_deck[i]) #далее у всех игроков получается одна и так же cards_for_preparing. С ней и запускается locking_round locking_round(cards_for_preparing, 1, False, player_list) #Каждый игрок записывает данные о подготовленных картах for player in player_list: #В temp_deck находится резлуьтат шифрования после locking_round Y = copy.copy(player.temp_deck) for j in range(v): #Получаем ключ, составляющий комбинацию ключа маскировки и ключа закрытия. Он способен расшифровать ML-карту #Ключ состоит из двух подключей: e - шифрования, d - дешифрования k_e = player.mask_key[0] * player.lock_keys["1:" + repr(j)][0] k_d = player.mask_key[1] * player.lock_keys["1:" + repr(j)][1] k = [k_e, k_d] #Добавляем ссылку на полученый ключ для данной карты: player.card_keys[Y[j]] = k #Добавляем ссылку на подготовленную к радаче карту (по карте из main_deck определяет ее подготовленный вариант) player.prepared_cards[cards_for_preparing[j]] = Y[j]
def single_card_deal(player_number, players_list, table_card = False): #Инициатор протокола - игрок, который хочет получить карту initiator = players_list[player_number] #Игрок player_number хочет получить карту. Он собщает об этом другим игрокам, публикуя свой номер initiator.broadcast(player_number) #Каждый игрок берет копию подготовленной карты, которая лежит сверху колоды. Здесь это на примере 0 игрока x = players_list[0].prepared_cards[players_list[0].main_deck[0]] #Опубликованные ключи, хранятся у игрока под номером player_number q = [] #Протокол выполняется игроками по порядку возрастания их номера players = sorted(players_list, key=lambda x: x.number) #Все игроки, кроме того, который получает карту, публикуют свои ключи от нее for i in range(len(players)): if i != player_number: if i == 1 and player_number == 2: q.append(Mod(2, players[i].encryptor.p-1)) else: q_i = players[i].card_keys[x][1] players[i].broadcast(q_i) q.append(q_i) #Для удобства использования на место player_number добавляется 0. Таким образом каждый открытый ключ в списке находится по индексу, совпадающему с номером его владельца else: q.append(0) #Следующие вычисления проводит игрок player_number, он же initiator: #Находит ключ для дешифровки карты x #Для этого он перемножает опубликованные ключи w = 1 for i in range(len(q)): if i != player_number: w = initiator.encryptor.key_mul(w, q[i]) #И к полученному ключу домножает еще и свой w = initiator.encryptor.key_mul(w, initiator.card_keys[x][1]) #Все операции шифрования/дешифрования предполагают, что ключ имеет структуру [e, d], так что приводим ключ к нужной структуре decrypt_key = [0, w] o_card = initiator.encryptor.open_card(x, decrypt_key) #Теперь игрок проверяет, что полученная карта o_card - валидная. Для этого он ищет ее в списке open_deck или ищет ее значение в cards_value. Я тут использую второй вариант #Также карта не должна лежать в списке уже известных карт is_valid = (o_card in initiator.cards_value) and (o_card not in initiator.showed_cards) #Если карта оказываетсяы невалидной, игрок обрывает протокол и начинает проверку if not is_valid: print("card is not valid " + repr(o_card) + " " + repr(x)) card_key_verification(player_number, initiator.dealed_cards + 1, q, players_list) if o_card not in initiator.cards_value: print("value of card don't exist") else: print("card already showed") #Иначе карта считается валидной, протокол продолжается else: #Игрок player_number добавляет карту в список известных карт initiator.showed_cards.append(o_card) #Игрок player_number добавляет мастер-ключ для дешифрования карты x initiator.master_keys[x] = w #Игрок сообщает, что карта валидна initiator.broadcast(True) #Далее все игроки for player in players_list: #Изменяют счетчик сданных карт player.dealed_cards = player.dealed_cards + 1 #В том случае, если карта кладется на стол, игроки помечают ее у себя. Следующая карта, которая открывается на столе должна быть x if table_card: player.table_card = x #Иначе помечают player_number как держателя карты x else: player.card_holder[x] = player_number player.hand_cards[player_number].append(x) #и удаляют x из колоды del player.main_deck[0]
#Игрок player_number открывает карты из card_list всем игрокам и доказывает, что получил их легально #Это быстрый протокол, доказательство в нем представляет собой предъявление мастер-ключа, расшифровывающего карту #player_number - номер игрока, который хочет открыть карты (он и вызывает протокол) #card_list - список карт, которые хочет открыть игрок #players_list - список игроков, здесь используется для большего удобства. #table_card - карта предназначается для дальнейшего ее расположения на столе (в таком случае ее открывает диллер) def show_card(player_number, card_list, players_list, table_card = False): #Инициатор протокола - игрок, который хочет показать карты initiator = players_list[player_number] #Сначала игрок player_number предъявляет карты и ключи к ним broadcast(player_number) #Списки публикуемых ключей и карт. Их составляют остальные игроки по мере публикации keys = [] showed_cards = [] for i in range(len(card_list)): #Игрок публикует карту и ключ к ней broadcast([card_list[i], initiator.master_keys[card_list[i]]]) #Игроки пополняют списки опубликованных карт и ключей keys.append(initiator.master_keys[card_list[i]]) showed_cards.append(card_list[i]) #Теперь игроки проверяют валидность полученных карт for player in players_list: #инициатор протокола не участвует в проверке, очевидно if player != initiator: for i in range(len(showed_cards)): #Если карта кладется на стол, она должна совпадать с картой, которую сдали для этой цели if table_card: if player.table_card != showed_cards[0]: print("Dealer trying to cheat (not table card)") return 0 #Иначе она должна быть помечена, что сдана именно тому игроку, который ее открывает else: if player.card_holder[showed_cards[i]] != player_number: print("Player " + repr(player_number) + " trying to cheat (not card holder)") return 0 c = player.encryptor.open_card(showed_cards[i], [0, keys[i]]) #Теперь игрок проверяет, что полученная карта c - валидная. Для этого он ищет ее в списке open_deck или ищет ее значение в cards_value. Я тут использую второй вариант #Также карта не должна лежать в списке уже известных карт is_valid = (c in player.cards_value) and (c not in player.showed_cards) if not is_valid: print("Player " + repr(player_number) + " trying to cheat (not valid card)") if o_card not in initiator.cards_value: print("value of card don't exist") else: print("card already showed") return 0 #Для большей наглядности печатает, какую карту увидели игроки print(player.cards_value[c])
#Выкладывание карты с колоды на стол (значение становится всем известным) def card_on_table(dealer_number, players_list): #карта сдается дилеру single_card_deal(dealer_number, players_list, True) #затем он открывает карту show_card(dealer_number, [players_list[dealer_number].table_card], players_list, True)
#Протокол позволяет игроку player определить, кто из остальных игроков попытался сжульничать и выдал неправильный ключ для дешифровки карты при раздаче #initiator - номер игрока, получившего при дешифровке невалидную карту и выщвавшего протокол проверки #card_index - индес карты в колоде #key_list - полученный список ключей def card_key_verification(initiator, card_index, key_list, players_list): #Проверяется каждый игрок, кроме инициатора for p in range(len(players_list)): if p != initiator: #Вообще говоря, свои MR, LR создает каждый игрок у себя на машине, но они будут совпадать MR = players_list[0].mask_representative[p] LR = players_list[0].lock_representative["1:" + repr(p) + ":" + repr(card_index)] #MR сейчас - это представление маскирующего ключа. Необходимо же получить представление общего ключа для карты (комбинация mask_key и lock_key). Объединяем представления MR и LR #Игрок p не публикует свой ключ, просто использует его в алгоритме build_representative R = build_representative(p, MR, LR, players_list[p].lock_keys["1:"+repr(card_index)], players_list) #Теперь каждый игрок проверяет полученное представление for i in range(len(players_list)): if i != p: #Собственно проверка if players_list[i].encryptor.encrypt(R[0], [key_list[p], 0]) != [R[1]]: #Если зашифрованная на опубликованном ключе первая часть представления не совпала со второй, значит опубликованный ключ неверный print("Player " + repr(p) + " is cheating: wrong key. Detected by " + repr(i)) return False return True
#Построение нового представления R из представлений A и B для игрока player. B -предсталвение ключа key def build_representative(player, A, B, key, players_list): #Игрок p шфирует вторую часть представления A секретным ключом x = players_list[player].encryptor.lock_card(A[1], key) #Все игроки проверяют полученную карту RLVP(key, A[1], x, player, B[0], B[1], players_list) R = [A[0], x] return R
#Унифицированный протокол верификации. Так как игроки проводят приватные преобразования над картами, то эти преобразования надо верифицировать, чтобы не было возможности жульничества #Все остальные стандартные протоколы верификации могут быть представлены как вызовы унифицированного протокола с различными параметрами #key_list - список ключей шифрования. Каждый ключ с индексом i используется для шифрования карты из in_card_list с индексом i. Если ключ всего один, то он используется для шифрования всех карт. Известен только доказывающему (prover) игроку. #permutation - перестановка, которая применялась к in_card_list для получения out_card_list. Известна только доказывающему (prover) игроку. #in_card_list - список карт, который игрок получил на вход для преобразования #out_card_list - список карт, который получился у игрока на выходе после преобрахования #prover - номер игрока, который проводил преобразования. Именно он будет доказывать остальным корректность проведенных им операций. #is_permuted - использовалась ли перестановка карт (если да, то необходимо проверить ее корректнсоть) #is_same_key - использовались ли уникальные ключи для каждой карты или один для всех #rep_in - список открытых текстов, используемый для входных или выходных представлений при проведении протокола. Если пуст, значит предсталвение не используется в данном протоколе верификации. #Для is_same_key = false список открытых текстов rep_in должен быть пуст #rep_out - соответствующие rep_in шифртексты def UniVP(key_list, permutation, in_card_list, out_card_list, prover, is_permuted, same_key, rep_in, rep_out, players_list): #Каждый из игроков проверяет доказывающего for verifier in range(len(players_list)): #Получает объединение входного списка крт с представлением in_cards = in_card_list + rep_in #Аналогично для выходного out_cards = out_card_list + rep_out #Вызывает протокол верификации UniVP_TP(key_list, permutation, in_cards, out_cards, prover, verifier, is_permuted, same_key, players_list)
#Унифицированный протокол верификации между двумя пользователями s = 2^(20) #граница безопасности для интерактивных доказательств (s - вероятность жульничества) def UniVP_TP(key_list, permutation, in_card_list, out_card_list, prover, verifier, is_permuted, same_key, players_list): #В случае, если используется один и тот же ключ для шифрования всех карт, переходим к интерактивному доказательству с границей безопасности s (s - вероятность жульничества) if (same_key): f = 1.0 while (f < s): #За каждый шаг вероятность обмана будет уменьшаетсья на 1/(размер списка in_card_list) f = f * len(in_card_list) #Заускаем главную часть протокола верификации UniVP_Core(key_list, permutation, in_card_list, out_card_list, prover, verifier, is_permuted, same_key, players_list) #Иначем нам достаточно неинтерактивного доказательства (1 запуск алгоритма верификации) else: UniVP_Core(key_list, permutation, in_card_list, out_card_list, prover, verifier, is_permuted, same_key, players_list)
#В процессе протокола применяются перестановки U, S, R, которые зависят от входных аргументов def UniVP_Core(key_list, permutation, in_card_list, out_card_list, prover, verifier, is_permuted, same_key, players_list): U = S = R = 0 #Игрок verifier выполняет следующие действия: #Генерирует случайный ключ r = players_list[verifier].encryptor.generate_key() #Шифрует карты на полученном ключе _Z = players_list[verifier].encryptor.encrypt_cards(in_card_list, [r]) #В зависимости от того, использовался ли один ключ или много, определяем перестановку U if (same_key): U = players_list[verifier].encryptor.random_permutation(len(in_card_list)) else: U = players_list[verifier].encryptor.identity_permutation(len(in_card_list)) #В зависимсоти от того, перемешивались ли карты, определяем перестановку S if is_permuted: #Будем так обозначать перестановку, сортирующую список, к которому она применяется, по возрастанию S = "sort" else: S = U #Переставляем элеметы в зашифрованной последовательности, чтобы их невозможно было отследить Z = players_list[verifier].encryptor.permute(_Z, U) #Отправляем полученное Z доказывающему broadcast(Z) #Теперь шифруем выходную последовательность карт _W = players_list[verifier].encryptor.encrypt_cards(out_card_list, [r]) #И переставляем ее элементы при помощи S W = _W if S == "sort": W = sorted(_W) else: W = players_list[verifier].encryptor.permute(_W, S) #Хешируем идентификатор доказывающего и полученную последовательность #Вместо prover стоит использовать некоторый идентификатор доказывающего h_w = hashlib.sha512(str(prover) + str(W)).hexdigest() #Дальнейшие действия выполняет уже доказывающий, т.е. игрок players_list[prover] _Q = players_list[prover].encryptor.encrypt_cards(Z, key_list) Q = _Q if is_permuted: Q = sorted(_Q) #Вместо prover стоит использовать некоторый идентификатор доказывающего h_q = hashlib.sha512(str(prover) + str(Q)).hexdigest() #Выбирается некоторая случайная строка заранее заданной длины. Для примера рассмотрим длину l = 30 d = "" l = 30 for i in range(l): d = d + str(randint(0, 9)) h_s = hashlib.sha512(str(h_q) + str(d)).hexdigest() #Полученный хеш h_s - это обязательство доказываюшего. Он публикует его broadcast(h_s) #Далее проверяющий prover публикует вызов broadcast(r) #Доказывающий prover должен ответить на запрос. Для этого он предпринимает следующие шаги: #Если r помечено вотермаркой, проверяет идентификатор отправителя. Если проверка проваливается, то обрывает протокол #Рассчитываем G = _Z G = players_list[prover].encryptor.encrypt_cards(in_card_list, [r]) #Если используются разные ключи, то _Z = Z, а значит, G должно быть равно Z if not same_key: if G != Z: #Прерываем протокол print("Player " + repr(verifier) + " is cheating: trying to do a chosen plaintext attack") return 0 else: #Проверяем, что G есть перестановка Z (в таком случае в отсортированном виде они совпадут) if sorted(G) != sorted(Z): #Прерываем протокол print("Player " + repr(verifier) + " is cheating: trying to do a chosen plaintext attack") return 0 #После проверок он раскрывает значения, связанные обязательством broadcast(h_q) broadcast(d) #Следующие действия выполняет verifier для проверки честности доказывающего: if h_w != h_q or h_s != hashlib.sha512(str(h_q) + str(d)).hexdigest(): #Прерываем протокол print("Player " + repr(prover) + " is cheating! Report by " + repr(verifier)) return 0
#Locking Verification Protocol. Позволяет игроку (prover) доказать остальным игрокам, что out_card_list - это список зашифрованных элементов из in_card_list, при этом ключи не раскрываются. #key_list - список ключей шифрования, используемый во время locking раунда. Каждый ключ с индексом i используется для шифрования карты из in_card_list с индексом i. Если ключ всего один, то он используется для шифрования всех карт. Известен только доказывающему (prover) игроку. #in_card_list - список карт, который игрок получил на вход для преобразования #out_card_list - список карт, который получился у игрока на выходе после преобрахования #prover - номер игрока, который доказывает остальным свою честность. def LVP(key_list, in_card_list, out_card_list, prover, players_list): #Тривиальная перестановка, по факту ничего не переставляет identity_permutation = [i for i in range(len(in_card_list))] return UniVP(L, identity_permutation, in_card_list, out_card_list, prover, False, False, [], [], players_list)
#Shuffle-Masking Verification Protocol. Позволяет доказать игроку (prover) остальным игрокам, что out_card_list - это список зашифрованных на одном ключе и переставленых элементов из in_card_list, при этом ключ не раскрывается. #В процессе протокола генерируется представление - пара (открытый текст, шифртекст), котоая публикуется во время протокола и на которую ссылаются в будущем. #key - ключ, которым шифровались все карты во время Shuffle-Masking раунда #permutation - используемая игроком перестановка во время Shuffle-Masking раунда #in_card_list - список карт, который игрок получил на вход для преобразования #out_card_list - список карт, который получился у игрока на выходе после преобрахования #prover - номер игрока, который доказывает остальным свою честность. #rep_in - список открытых текстов, используемый для входных или выходных представлений при проведении протокола. #rep_out - соответствующие rep_in шифртексты def SMVP(key, permutation, in_card_list, out_card_list, prover, rep_in, rep_out, players_list): return UniVP([key], permutation, in_card_list, out_card_list, prover, True, True, rep_in, rep_out, players_list)
#Re-Locking Verification Protocol. Протокол доказательства игроком prover шифрования одной единственной карты на одном единственном ключе с одним единственным представлением. def RLVP(key, in_card, out_card, prover, rep_in, rep_out, players_list): return UniVP([key], players_list[0].encryptor.identity_permutation, [in_card], [out_card], prover, False, False, [rep_in], [rep_out], players_list)
#Протокол верификации отдельной карты из колоды, полученной в раунде закрытия #Построен по классической схеме доказательства запрос-ответ, в три шага: заявка-вызов-ответ def T_S_LVP(key, in_card, out_card, prover, verifier, players_list): #Для удобства сразу переобозначим модули p, q системы. Они одинаковы для доказывающего (players_list[prover]) и проверяющего (players_list[verifier]) p = players_list[prover].encryptor.p q = players_list[prover].encryptor.q #Заявка #Доказывающий (players_list[prover]) проделывает следующие действия: r = randint(2, q) #должен быть криптостойкий генератор псевдослучайных чисел x = players_list[prover].encryptor.encrypt(in_card, [r, 0]) #Далее он отсылает r проверяющему (players_list[verifier]) players_list[prover].broadcast(r) #Вызов #Теперь проверяющий (players_list[verifier]) делает следующее: e = randint(2, p) #должен быть криптостойкий генератор псевдослучайных чисел #И отсылает сгенерированное число доказывающему players_list[verifier].broadcast(e) #Ответ #доказывающий вычисляет y = Mod(r + key[0]*e, p - 1) #и отправляет полученное значение проверяющему broadcast(y) #Теперь доказывающий проверяет полученное значение res = Mod(pow(in_card, y, p) * pow(out_card, -e, p), p) if x != res: #Если проверка не прошла, значит доказыающий попытался сжульничать print("T_S_LVP error. Prover: " + repr(prover) + ", Verifier: " + repr(verifier)) #Протокол прерывается, players_list[prover] наказывается return False return True
#Shnorr's Id Protocol Based Locking Verification Protocol #Протокол верификации раунда закрытия (locking_round), подходит именно для шифра Полига-Хеллмана #keys - ключи, используемые игроком для закрытия карт. ИГРОК ИХ НЕ ПУБЛИКУЕТ. Просто для удобства в прототипе этом так сделал #in_cards - карты, которые игрок закрывал #out_cards - карты, полученные после закрытия #prover - номер игрока, которые доказывает свою честность #players_list - как обычно, список игроков def S_LVP(keys, in_cards, out_cards, prover, players_list): #Протокол выполняется игроками по порядку возрастания их номера players = sorted(players_list, key=lambda x: x.number) #Все игроки, кроме доказываюшего выполняют for i in range(len(players)): if i != prover: #Для каждой карты протокол T_S_LVP for j in range(len(in_cards)): if not T_S_LVP(keys[j], in_cards[j], out_cards[j], prover, i, players_list): return False return True
#HMVP - Homomorphic Shuffle Masking Verification Protocol #Более подходящий для шифра Полига-Хеллмана, чем классический SMVP т.к. предотварщаяет использование гомоморфных свойств шифра. #Проводит некоторую подготовку, после чего запускает классический SMVP def HMVP(key, permutation, in_card_list, out_card_list, prover, rep_in, rep_out, players_list): #Проверяющие (все остальные игроки) создают случайное число для доказывающего s = 0 for i in range(len(players_list)): #Каждый игрок получает на вход s (первый получает 0) и производит над ним дейтсвие. #На самом деле не важно, в каком интервале брать числа, так как далее полученная сумма хешируется. Но для примера я взял в интервале (2, p) s = s + randint(2, players_list[i].encryptor.p) #Далее сообщает полученное число следующему игроку broadcast(s) #Последний игрок отослал s доказывающему (players_list[prover]) #Теперь доказывающий составляет представление R = [] #Доказывающий находит хеш-сумму от сгенерированного другими игроками сида и приводит ее к виду карты (т.е. числу в нашем случае) hashsum = int(hashlib.sha512(str(s)).hexdigest(), 16) #Теперь он создает карту и добавляет ее к представлению R.append(players_list[prover].create_card(hashsum)) #Добавляет к представлению зашифрованный вариант этой карты. Теперь это представление ключа key R.append(players_list[prover].encryptor.encrypt(R[0], key)) #И далее рассылает его всем broadcast(R) #Теперь игроки проверяют полученные блоки на валидность for player in players_list: #Сначала идет какая-нибудь проверка типов, что R[0], R[1] - числа #потом проверяем, что эти числа меньше p: if (R[0] > player.encryptor.p - 1) or (R[1] > player.encryptor.p - 1): print("Error: representation fail, HMVP: repr > p") return 0 #Также проверяем, что R[0] - хеш-значение от сида real_hash = int(hashlib.sha512(str(s)).hexdigest(), 16) if player.create_card(real_hash) != R[0]: print("Error: representation fail, HMVP: R.p != hash(s)") return 0 #Проверяем правильность составленного представления S_LVP([key], [R[0]], [R[1]], prover, players_list) #Запускаем основной протокол верификации rep_in.append(R[0]) rep_out.append(R[1]) return SMVP(key, permutation, in_card_list, out_card_list, prover, rep_in, rep_out, players_list)
def drop_out_recovery(do_player, players_list): #Для начала все записи перестраиваются так, словно ушедшего игрока и не было в игре, а именно: #контракту, отвественному за данный стол, посылается сообщение об исключении вышедшего игрока из списка #каждый игрок исключает ушедшего игрока из списка #Нумерация игроков перестраивается: чтобы не было пробелов в номерах игроков, номера всех игроков после do_player сдвигаются на 1. В итоге вместо номеров 1..n имеем номера 1..n-1 player_list.delete(player_list[do_player]) #Создаются наборы для восстановления колоды create_recovery_sets(players_list) for j in range(len(players_list)): players_list[j].mask_key = players_list[j].recovery_set_key players_list[j].mask_representative = players_list[j].recovery_mask_representative #У каждого игрока создается свой X, здесь я их обозначил просто как список X = [[]]*len(players_list) for card in players_list[j].hand: #Для каждой карты с руки игрока находим ее аналог в recovery_set #Для этого сначала расшифровываем карту и шифруем ее ключом из сета для восстановления open_card = players_list[j].encryptor.decrypt(card, players_list[j].master_keys(card)) recovery_card = players_list[j].encryptor.ecnrypt(open_card, players_list[j].mask_key) #А затем находим его индекс в recovery_set s = players_list[j].recovery_set[j].index(recovery_card) #Рассылаем всем игрокам индексы для нахождения нужной карты players_list[j].broadcast(card, s) #Теперь все игроки проверяют эту карту for i in range(len(players_list)): if (i != j): q = players_list[i].recovery_set[j][s] #Если проверка карты прошла, она добавляется в список if S_LVP([z], [q], j, players_list): X[i].append(q) #Все X[i] у игроков одинаковые. Запускается протокол добавления маски к полученным картам и их перемешивания всеми игроками, кроме j. verified_shuffle_remasking_round(X[0], j, players_list) #Каждый игрок временно
def create_recovery_sets(players_list): return 0
def verified_shuffle_remasking_round(in_card_list, masking_player, players_list): return 0
##################################################### #Моделирование игры, собственно ##################################################### #Игроки садятся за стол players_list = [Player(0), Player(1), Player(2)]
#Создается колода из 20 карт create_deck(20, players_list)
players_list[0].main_deck
[746, 649, 362, 431, 764, 559, 583, 792, 700, 992, 826, 752, 643, 159, 918, 299, 839, 674, 939, 716]
#Колода замешивается shuffle_deck(players_list[0].main_deck, players_list)
#Опять же таки, исключительно для дебага посмотрим на получившуюся колоду после замешивания players_list[0].main_deck
[897, 950, 330, 150, 514, 486, 299, 815, 186, 213, 58, 138, 438, 674, 37, 851, 476, 264, 103, 407]
#К раздаче подготавливается 11 карт (6 картсдается на руки трем игрокам + 5 на сто) prepare_cards_to_deal(11, players_list)
#Можно посомтреть, какие карты подготовлены и как вылядит основная колода players_list[0].prepared_cards players_list[0].main_deck
{897: 236, 514: 399, 950: 422, 486: 102, 330: 739, 299: 665, 815: 822, 213: 651, 150: 152, 186: 851, 58: 560} [897, 950, 330, 150, 514, 486, 299, 815, 186, 213, 58, 138, 438, 674, 37, 851, 476, 264, 103, 407]
#Сдается по две карты каждому из игроков single_card_deal(0, players_list) single_card_deal(0, players_list) #На этом этапе результаты подписываются и записываюстя в IPFS/SWARM #Показано, что лежит на руке у игрока (зашифрованные карты) print("Player 0 hand:") print(players_list[0].hand_cards[0]) single_card_deal(1, players_list) single_card_deal(1, players_list) #На этом этапе результаты подписываются и записываюстя в IPFS/SWARM #Показано, что лежит на руке у игрока (зашифрованные карты) print("Player 1 hand:") print(players_list[1].hand_cards[1]) single_card_deal(2, players_list) single_card_deal(2, players_list) #На этом этапе результаты подписываются и записываюстя в IPFS/SWARM #Показано, что лежит на руке у игрока (зашифрованные карты) print("Player 2 hand:") print(players_list[2].hand_cards[2]) #Что осталось в деке после раздачи print("Deck after deal:") print(players_list[1].main_deck)
Player 0 hand: [236, 422] Player 1 hand: [739, 152] card is not valid 755 399
*** WARNING: Code contains non-ascii characters *** Error in lines 9-9 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1013, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "", line 27, in single_card_deal File "", line 9, in card_key_verification File "", line 7, in encrypt TypeError: Argument 'self' has incorrect type (expected sage.rings.finite_rings.integer_mod.IntegerMod_int, got int)
#Что осталось в деке после раздачи players_list[1].main_deck
[514, 486, 299, 815, 186, 213, 58, 138, 438, 674, 37, 851, 476, 264, 103, 407]
#Флоп card_on_table(0, players_list) card_on_table(0, players_list) card_on_table(0, players_list)
8C 8C 7H 7H 9S 9S
#Терн card_on_table(0, players_list)
7C 7C
#Ривер card_on_table(0, players_list)
8D 8D
#0 игрок вскрывается show_card(0, players_list[0].hand_cards[0], players_list)
7S 10C 7S 10C
#1 игрок вскрывается show_card(1, players_list[1].hand_cards[1], players_list)
9D 10S 9D 10S
#2 игрок вскрывается show_card(2, players_list[2].hand_cards[2], players_list)
6C 10D 6C 10D