# Криптография без односторонних функций
<div style="text-align: right; font-style: italic; white-space: pre;"> Подготовили студенты группы 0372:
Жуков Владимир
Пахаревская Элина</div>

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

## Протоколы
### Вычисление суммы
**Постановка задачи:** вычисление суммы элементов $n_1,n_2, \dots,n_k$, хранимых узлами $P_1, P_2, \dots,P_k$ соответственно, не раскрывая этих значений.

#### Протокол 1
1. Узел $P_1$ начинает алгоритм, отправляя сумму $n_1 + n_{01}$ узлу $P_2$, где $n_{01}$ - случайное число, сгенерированное $P_1$.
2. Каждый узел от $P_2$ до $P_{k-1}$ включительно делают то же самое. $P_i$ при получении элемента $m$ от $P_{i-1}$ прибавляет к нему свою сумму $n_i+n_{0i}$ и передает результат $P_{i+1}$.
3. $P_k$ также прибавляет к полученному от $P_{k-1}$ свою сумму $n_k+n_{0k}$ и отправляет ее $P_1$.
4. $P_1$ вычитает $n_{01}$ из полученного значения. Теперь результат - это сумма всех элементов и случайных чисел (кроме первого) узлов. После этого $S$ становится известен всем. *
5. Теперь все участники, кроме первого, раскрывают свои $n_{0i}$ и происходит вычисление суммы этих значений. После этого вычисляется результат: из $S$ вычитается сумма случайных чисел.

\*передаем по защищенному каналу, чтобы всем узлам не стало известно сгенерированное $P_1$ число и $P_2$ не смог вычислить хранимое $P_1$ значение.

> **Замечание**
> Проблемой протокола 1 является его избыточность. Если оставить способность генерации случайных чисел только первому узлу, не возникнет изменений ни в конечной сумме, ни в соблюдении секретности на всех шагах выполнения протокола. Можно предложить другой вариант, в котором сократится количество арифметических операций и снизится нагрузка на каналы связи.

#### Протокол 2
1. Узел $P_1$ начинает алгоритм, отправляя случайное сгенерированное число $n_{01}$ узлу $P_2$.
2. Каждый узел $P_i$ при получении элемента $m$ от $P_{i-1}$ прибавляет к нему свое число $n_i$ и передает результат $P_{i+1}$.
3. $P_k$ также прибавляет к полученному от $P_{k-1}$ свое число $n_k$ и отправляет ее $P_1$.
4. $P_1$ прибавляет свое число $n_1$ к полученному значению и вычитает из него $n_{01}$. Теперь результат - это сумма $S$ элементов всех узлов.
5. Узел $P_1$ сообщает $S$ остальным узлам по порядку, начиная со второго.

\*После получения от $P_k$ суммы $S$ узел $P_1$ сравнивает ее с той, которая была отправлена узлу $P_2$. Если они отличаются, то в сети есть узел, который изменил сумму, то есть сообщил ложную информацию. Простыми способами его не вычислить, поэтому данный алгоритм так же требует доработки.

### Вычисление произведения
**Постановка задачи:** вычисление произведения элементов $n_1,n_2, \dots,n_k$, хранимых узлами $P_1, P_2, \dots,P_k$ соответственно, не раскрывая этих значений.

#### Протокол 1
1. Узел $P_1$ начинает алгоритм, отправляя произведение $n_1 \cdot n_{01}$ узлу $P_2$, где $n_{01}$ - случайное число (не равное нулю), сгенерированное $P_1$.
2. Каждый узел от $P_2$ до $P_{k-1}$ включительно производят ту же операцию. $P_i$ умножает полученный от $P_{i-1}$ $m$ на произведение своих $n_i \cdot n_{0i}$ и отправляет результат $P_{i+1}$
3. $P_k$ также умножает полученный $m$ на свое произведение $n_k \cdot n_{0k}$ и отправляет его $P_1$
4. $P_1$ делит полученное число на свое сгенерированное $n_{01}$. Таким образом наш нынешний результат P - произведение всех элементов и случайных чисел (кроме первого) узлов. После этого $P$ становится известен всем. *
5. Теперь все участники, кроме первого, раскрывают свои $n_{0i}$ и происходит вычисление произведения этих значений. После этого вычисляется результат: $P$ делится на произведение случайных чисел.

> **Замечание**
> Протокол для вычисления произведения обладает тем же недочетом, что и протокол для вычисления суммы. Поэтому здесь также будет приведен модифицированный протокол.

#### Протокол 2
1. Узел $P_1$ начинает алгоритм, отправляя случайное сгенерированное число $n_{01}$ узлу $P_2$.
2. Каждый узел $P_i$ при получении элемента $m$ от $P_{i-1}$ умножает на него свое число $n_i$ и передает результат $P_{i+1}$.
3. $P_k$ также умножает полученное от $P_{k-1}$ на свое число $n_k$ и отправляет его $P_1$.
4. $P_1$ умножает полученное значение на свое число $n_1$ и делит его на $n_{01}$. Теперь результат - это произведение $P$ элементов всех узлов.
5. Узел $P_1$ сообщает $P$ остальным узлам по порядку, начиная со второго.

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

### Сравнениие двух чисел
**Постановка задачи:** сравнить два числа $n_1$ и $n_2$, принадлежащие $P_1$ и $P_2$ соответственно, не раскрывая их значений.

#### Протокол
Для решения нам также понадобится третий участник, назовем его D (dummy), которому запрещено генерировать случайные значения. Он может лишь отвечать на конкретные запросы.
1. $P_1$ раскладывает свое число на разность $n_1=n_{11}-n_{12}$. Затем отправляет $n_{12}$ узлу $P_2$.
2. $P_2$ раскладывает свое число на разность $n_2=n_{21}-n_{22}$. Затем отправляет $n_{22}$ узлу $P_1$.
3. $P_1$ отправляет сумму $n_{11}+n_{22}$ $D$.
4. $P_2$ отправляет сумму $n_{21}+n_{12}$ $D$.
5. $D$ вычитает ($n_{21}+n_{12}$) из ($n_{11}+n_{22}$) чтобы получить $n_1-n_2$ и выяснить результат.

### Вычисление неоднородной функции
**Постановка задачи:** поиск значения функции вида $f(n_1,n_2,n_3)=n_1 \cdot n_2+g(n_3)$, где g - любая вычислимая функция.
**Протокол:**
1. Узел $P_1$ начинает процесс с отправки случайного значения $a_0$ узлу $P_2$
2. $P_2$ умножает $a_0$ на свое $n_2$ и отправляет результат $P_3$
3. $P_3$ умножает $a_0 \cdot n_2$ на случайный элемент $c_0$ и отправляет результат $P_1$
4. $P_1$ умножает $a_0 \cdot n_2 \cdot c_0$ на свой $n_1$, делит его на $a_0$ и отправляет результат обратно $P_3$
5. $P_3$ делит $n_1 \cdot n_2 \cdot c_0$ на $c_0$, прибавляет $g(n_3)$ и получает искомый результат $n_1 \cdot n_2+g(n_3)$

### Битовая схема обязательств

**Постановка задачи:** организовать такой обмен значениями между узлами, при котором гарантируется
* секретность (концу commitment phase ни одна из сторон не владеет полной информацией о другой стороне)
* однозначность (к концу decommitment phase отправленные и опубликованные узлами значения не должны отличаться).

#### Протокол:
Рассмотрим случай, когда участников трое.
1. Каждый узел раскладывает свое число на два случайных: $n_i = r_i + s_i$. Если участники хотят работать с битами, то "0" они раскладывают или на $0+0$ или на $1+1$, а "1" на $0+1$ или $1+0$
2. **(Фаза передачи)** $P_1$ отправляет $r_1$ $P_2$, затем $P_2$ отправляет $r_1+r_2$ $P_3$, $P_3$ отправляет $r_1+r_2+r_3$ $P_1$. После этого в обратную сторону, $P_3$ отправляет $s_3$ $P_2$, затем $P_2$ отправляет $s_2+s_3$ $P_1$, $P_1$ отправляет $s_1+s_2+s_3$ $P_3$. \*
3. **(Фаза раскрытия)** $P_3$ отправляет $n_1+n_2$ $P_1$ и $P_2$. Сейчас $P_1$ знает $n_2$, а $P_2$ знает $n_1$.
4. $P_2$ отправляет $r_1$ $P_3$. Сейчас $P_3$ может восстановить $r_2$ с помощью $r_1$ и $r_1+r_2$.
5. $P_1$ отправляет $s_2+s_3$ $P_3$. Сейчас $P_3$ сможет узнать $s_2$ из полученной суммы, зная $r_2$, восстановить $n_2$, а также $n_1$ зная сумму $n_1+n_2$.
6. $P_1$ отправляет $r_1+r_2+r_3$ $P_2$. Теперь $P_2$ может узнать $r_3$ и восстановть $n_3=r_3+s_3$

\*На этом этапе ни один из участников не может восстановить какую-либо информацию о другом участнике. Имеющейся информации недостаточно. Но можно исключить факт мошенничества, так как каждый фрагмент переданной узлу информации может быть подтвержден двумя другими.
$P_1$ знает: $s_1$, $r_1$, $s_2+s_3$, $r_1+r_2+r_3$
$P_2$ знает: $s_2$, $r_2$, $r_1$, $s_3$
$P_3$ знает: $s_3$, $r_3$, $r_1+r_2$, $s_1+s_2+s_3$

Этот протокол можно применить на $3m$ участников (где $m \ge 1$), разделив игроков на тройки.

**Частный случай.** Частным случаем этой задачи является ситуация, когда участников двое. Для этого алгоритма необходимо ввести третий узел, которым будет являться Dummy.

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

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

#### Протокол 1
Будем рассматривать ситуацию, когда участников трое.
Перед началом все игроки договариваются о едином параметре $N$, который будет означать максимальное количество полных циклов.
Пусть $N=10$.
1. Каждый участник генерирует себе счетчик $c_i$ между 1 и $N$ и держит его в секрете.
2. Узел $P_1$ начинает алгоритм с "лишнего" значения 0 и отправляет его $P_2$.*
3. $P_i$ отправляет $P_{i+1}$ одно из двух значений: $m$ или $m+1$ по следующей схеме:
* если узел $P_i$ встречает число впервые, то он отправляет $m$ узлу $P_{i+1}$ и обновляет свой счетчик $c_i$, запоминая факт получения $m$;
* если узел $P_i$ встречает число меньшее или равное количество раз счетчику $c_i$, то он передает $m$ узлу $P_{i+1}$;
* если узел $P_i$ встречает число большее количество раз, чем значение счетчика $c_i$, то он забирает себе число $m$, передает $m+1$ узлу $P_i$ и обновляет свой счетчик $c_i$.
4. Описанный в пункте 3 алгоритм повторяет каждый узел до тех пор, пока у каждого участника не будет $s$ значений (не считая 0). Если у узла уже имеется $s$ чисел, то он "пропускает ход", просто передавая полученное значение следующему узлу, пока остальные участники не доберут $s$ чисел.
5. Когда один из игроков забирает себе последнее значение из $3s$ возможных, он передает его далее, как будто он не забирал его себе.
6. Алгоритм прекращает свою работу, когда последнее значение из возможных $3s$ проходит $N+1$ циклов.**

\*0 отправляется для того, чтобы ни один участник не смог догадаться, кто забрал единицу.

\*\*N+1 цикл нужен, чтобы узел, получивший впервые число $3s$, обновив счетчик до максимально возможного N, смог получить это число после $N+1$ циклов.

> **Замечание**
> Данный протокол имеет избыточные шаги:
> * первичная генерация счетчика
> * обновление счетчика и при первой встрече числа, и при отправке следующего числа следующему узлу

Учитывая данные замечания, можно предложить обновленный протокол 1.2.

#### Протокол 1.2
1. Узел $P_1$ начинает алгоритм с "лишнего" значения 0 и отправляет его $P_2$.
2. $P_2$ отправляет $P_3$ одно из двух значений: $m$ или $m+1$ по следующей схеме:
* если узел $P_i$ встречает число впервые, то он отправляет $m$ узлу $P_{i+1}$ и генерирует новое значение счетчика $c_i$, запоминая факт получения $m$;
* если узел $P_i$ встречает число меньшее или равное количество раз счетчику $c_i$, то он передает $m$ узлу $P_{i+1}$;
* если узел $P_i$ встречает число большее количество раз, чем значение счетчика $c_i$, то он забирает себе число $m$, передает $m+1$ узлу $P_i$.
3. Описанный в пункте 3 алгоритм повторяет каждый узел до тех пор, пока у каждого участника не будет $s$ значений (не считая 0). Если у узла уже имеется $s$ чисел, то он "пропускает ход", просто передавая полученное значение следующему узлу, пока остальные участники не доберут $s$ чисел.
4. Когда один из игроков забирает себе последнее значение из $3s$ возможных, он передает его далее, как будто он не забирал его себе.
5. Алгоритм прекращает свою работу, когда последнее значение из возможных $3s$ проходит $N+1$ циклов.

*Цель протокола 2:* сгенерировать каждому участнику число, которое будет использовано в дальнейшем при непосредственной "раздаче карт".

#### Протокол 2
Положим количество участников равным $3s,\ s \in \mathbb{Z}$, тогда второй протокол состоит из следующих этапов:
1. $P_{i-1}$ и $P_{i+1}$ тайно и независимо генерируют значение $n_{i-1}$ и $n_{i+1}$ соответственно по модулю числа $M$.
2. $P_2$ и $P_3$ передают свои $n_2$ и $n_3$ узлу $P_1$.
3. $P_1$ складывает полученные числа и сохраняет себе модуль этой суммы $n_1 = n_2 + n_3$ по $M$.

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

Сгенерировать случайную перестановку также можно выбирая случайные значения в промежутке $[0, M]$. Однако, такой грубый метод требует много времени на обработку повторений, поэтому эффективнее использовать, например, тасование Кнута или любой другой алгоритм, не предполагающий перебор. После реализации этого алгоритма мы имеем последовательность из чисел, которые равномерно и случайным образом будут распределяться между узлами в соответствии с числами из протокола 1.

> **Принцип тасования Кнута**
> Алгоритм начинается с исходной перестановки. Затем происходит последовательный обход всех позиций, для каждой из которой меняется местами текущий элемент на произвольно выбранный. В случае протокола 2 этим случайным элементом будет сгенерированное число $n_i$.

### Решение квадратного уравнения
**Постановка задачи:** необходимо найти корни квадратного уравнения и сообщить их всем узлам $P_1$, $P_2$ и $P_3$, которые хранят параметры соответственно $a$, $b$ и $c$ в секретном виде.
#### Протокол
1. Узел $P_1$ умножает соответствующий ему параметр $a$ на случайное число $m_1$ и отправляет произведение $am_1$ узлу $P_3$
2. Узел $P_3$ умножает полученное значение на соответствующий ему параментр $c$ и отправляет произведение $am_1c$ узлу $P_2$
3. Узел $P_1$ передает сгенерированное значение $m_1$ узлу $P_2$
4. Узел $P_2$ в свою очередь делит полученное от узла $P_3$ $am_1c$ на $m_1$, благодаря чему получает произведение $ac$, которое позволяет ему вычислить $x_{01,02}=\left( -b \pm \sqrt{b^2 - 4ac} \over 2 \right)$. $P_2$ умножает $x_{01}$ и $x_{02}$ на случайное $m_2$ и передает узлу $P_3$.
5. Узел $P_3$ умножает полученное значение на $m_3$ и передает $x_{01,02}m_2m_3$ узлу $P_1$
6. Узел $P_1$ делит $x_{01,02}$ на параметр $a$ и передает результат $P_2$.
7. Узел $P_2$ делит полученные значения на $m_2$ и передает $x_{01,02}m_3$ узлу $P_3$.
8. Узел $P_3$ делит результат на $m_3$, вычисляет корни уравнения $x_1$ и $x_2$, которые передает узлам $P_1$ и $P_2$.

> **Замечание**
> Предполагается, что после выполнения протокола узлы не будут совершать никаких арифметических операций, иначе, очевидно, зная корни уравнения и один из параметров можно без проблем вывести и остальные параметры, из-за чего рушится секретность. Можно также привести более логичную модификацию данного протокола, введя секретный для уже всех узлов параметр $n$, который является общим делителем всех параметров квадратного уравнения. В таком случае исходное уравнение выглядит как $n(ax^2 + bx + c)$, тогда, зная корни и, например, параметр $a$, определить величину $n$ невозможно (даже если $n = 1$, узлы об этом вряд ли узнают, если это число не задействуется в последующих вычислениях).

### Вычисление определителя матрицы
**Постановка задачи:** необходимо найти определитель матрицы $n\times n$, строки $n_i$ которой распределены между $n$ участниками сверху вниз.
#### Протокол
1. Узел $P_1$ умножает $n_1$ на случайное сгенерированное число $m_1$, и передает результат $P_2$
2. Узел $P_i$ делает то же, объединяет полученное $n_{i - 1}$ с $n_i$ так, чтобы получилась матрица $i \times n$, а $n_i$ оказалась нижней строкой, и передает результат $P_{i+1}$
3. Последний узел передает $P_1$ матрицу $n \times n$, который находит ее определитель и посылает его $P_i$
4. $P_i$ делит определитель на $m_i$ и передает следующему узлу
5. Первый узел делит принятое число на $m_1$, получая определитель исходной матрицы, который сообщает остальным участникам, начиная со второго

### Определение узла с наибольшим числом
**Постановка задачи:** необходимо найти узел, который хранит наибольшее число.
#### Протокол 1
Алгоритм начинается с первого узла и не требует уникальности секретных чисел. Общее количество узлов будем обозначать $M$.
1. Находится среднее значение с помощью протокола поиска суммы
2. Первый узел запоминает значение счетчика ($c_1 = c$) и посылает второму кортеж $(N, c)$, где $N$ - среднее (сравниваемое) число, $c$ - счетчик вершин, числа которых больше числа $N$ (изначально $c = 0$)
3. (Цикл до $i = 1\ mod\ M$) Узел $i$ сравнивает счетчик $c$ со своим сохраненным $c_i$ (изначально $c_i = -1$).
**Если они равны**, то текущий узел имеет наибольшее число, о чем он сообщает всем остальным узлам широковещательной рассылкой.
**Иначе** он проверяет условие $N \lt n_i$. Если оно справедливо, то узел инкрементирует счетчик $c$.
**Далее** он запоминает счетчик до следующего получения кортежа ($c_i = c$) и отправляет его узлу $i + 1$
4. Первый узел получает кортеж и проверяет выражение $c = c_1$.
**Если оно справедливо** и **цикл был первый**, то у всех узлов одинаковые числа, о чем он сообщает всем широковещательной рассылкой. _**(STOP)**_
**Если не был получен ни один широковещательный ответ**
4.1. **Если оно справедливо** и , то $N = N - N_{inc} + 1$, где $N_{inc} = 2^q$, где $q$ - количество раз, когда первый узел получил один и тот же счетчик $c$ (изначально и после выполнения пункта 4.1. $q = 0$).
4.2. **Иначе** $N = N + N_{inc}$ и $q = q + 1$
**Иначе** _**(STOP)**_
**Далее** выполняется шаг 3.

#### Протокол 2
1. Первый узел генерирует случайное число $N$ в промежутке $[0, n_1]$, после чего посылает его второму узлу
2. Узел $i$ сравнивает секретное число $n_i$ с $N$:
**Если \($n_i = N$\)**, то наибольшее число среди всех узлов у текущего, о чем он рассказывает остальным
**Иначе если $n_i \gt N$**, то узел $i$ запоминает текущее $N$ и посылает узлу $i + 1$ число $\lceil\frac{N + n_i}{2}\rceil$
**Иначе** узел $i$ посылает узлу $i + 1$ число $N$

### Определение наибольшего значения узла
**Постановка задачи:** необходимо найти наибольшее число, хранимое узлом.
#### Протокол
Введем следующие обозначения:
* $n_i$ - секретное число $i$-го узла
* $N$ - текущее среднее арифметическое
* $c$ - счетчик чисел, больших текущего среднего
* $P$ - сумма чисел, больших текущего среднего.

Алгоритм начинается с первого узла.

1. Первый узел генерирует случайные числа для среднего арифметического $N$, находящегося в промежутке $[0, n_1]$, cчетчика $c$, который должен быть больше $1$, и суммы $P$.
2. Каждый узел, начиная с первого, сравнивает свое секретное значение с $N$:
**Если $n_i \lt N$**, то текущий узел передает кортеж следующему
**Если $n_i \ge N$**, то текущий узел инкрементирует счетчик и прибавляет к $P$ свое секретное значение. После этого передает кортеж следующему узлу.
3. Первый узел получает кортеж от последнего узла. После этого он вычитает свои сгенерированные числа из значений счетчика $c$ и суммы $P$ соответственно.
**Если $c = 1$**, то $P$ - наибольшее число и первый узел передает результат всем узлам, начиная со второго
**Если $c \gt 1$**, то $N =$ $P \over c$, сбрасываются значения $c$ и $P$ и генерируются новые. Алгоритм повторяется, начиная с 2 шага.

## Реализация карточных игр
## Вспомогательные протоколы
### Протокол N0
**Цель:** Распределить числа от 1 до $n*s$ между $n$ игроками так, чтобы у каждого было $m$ карт, причем никто другой не знал какие.

**Обозначения:**
- $P_i$ - Игрок с индексом $i$
- $m$ - Текущее число
- $s$ - Количество чисел, которые получит каждый игрок
- $c_i$ - Максимальное число раз, когда игрок получает текущее число $m$ ($1 \le c_i \le N, c_i \in Z$)
- $n$ - Количество игроков

**Алгоритм**
1. Узел $P_1$ начинает алгоритм с "лишнего" значения $m = 0$ и отправляет его $P_2$.
2. $P_2$ отправляет $P_3$ одно из двух значений: $m$ или $m+1$ по следующей схеме:
* если узел $P_i$ встречает число впервые, то он отправляет $m$ узлу $P_{i+1}$ и генерирует новое значение счетчика $c_i$, запоминая факт получения $m$;
* если узел $P_i$ встречает число меньшее или равное количество раз счетчику $c_i$, то он передает $m$ узлу $P_{i+1}$;
* если узел $P_i$ встречает число большее количество раз, чем значение счетчика $c_i$, то он забирает себе число $m$, передает $m+1$ узлу $P_i$.
3. Описанный в пункте 2 алгоритм повторяет каждый узел до тех пор, пока у каждого участника не будет $s$ значений (не считая 0). Если у узла уже имеется $s$ чисел, то он "пропускает ход", просто передавая полученное значение следующему узлу, пока остальные участники не доберут $s$ чисел.
4. Когда один из игроков забирает себе последнее значение из $s$ возможных, он передает его далее, как будто он не забирал его себе.
5. Алгоритм прекращает свою работу, когда последнее значение из возможных $n*s$ проходит $N+1$ циклов.

### Протокол N1
**Цель:** Перетасовать карты методом Кнута.

**Обозначения:**
- $\tilde K$ - Количество карт в колоде
- $q$ - Счетчик

**Алгоритм**
1. $P_i$ начинает выполнение протокола, сообщая об этом остальным
2. Все игроки заводят счетчик $q = 1$ и начинают проверять общий канал связи на наличие чисел
3. $P_i$ выполняет протокол $N2.1$, получая позицию карты, которую все узлы меняют с картой на позиции $q$, увеличивая $q$ на 1.
4. Шаг 3 выполняется игроком $P_{i+1}$, пока $q \neq \tilde K$.

### Протокол N2
**Цель:** Секретно сгенерировать случайное число с помощью смежных узлов.

**Обозначения:**
- $M$ - Количество карт в колоде
- $P_i$ - Узел под номером $i$, $i \in [1, n]$
- $n$ - Количество узлов
- $n_i$ - Случайно сгенерированное число узлом $i$

**Алгоритм:**
1. $P_{i-1}$ и $P_{i+1}$ тайно и независимо генерируют значения $n_{i-1}$ и $n_{i+1}$ по модулю числа $M$.
2. $P_{i-1}$ и $P_{i+1}$ передают свои $n_{i-1}$ и $n_{i+1}$ узлу $P_i$.
3. $P_i$ складывает полученные числа и сохраняет себе сумму $n_i = (n_{i-1} + n_{i+1}) \mod M$.

### Протокол N2.1
**Цель:** Сгенерировать случайное число с помощью смежных узлов так, чтобы узел не мог сделать это нечестным образом (например, заменить его на свое).

**Обозначения:**
- $n_i$ - Случайно сгенерированное число узла $i$
- $n$ - Количество узлов
- $M$ - Количество карт в колоде

**Алгоритм:**
1. $P_{i-1}$ и $P_{i+1}$ независимо генерируют значения $n_{i-1}$ и $n_{i+1}$ по модулю числа $M$.
2. $P_{i-1}$ и $P_{i+1}$ передают свои $n_{i-1}$ и $n_{i+1}$ всем узлам.
3. $P_i$ складывает полученные числа и сохраняет себе сумму $n_i = (n_{i-1} + n_{i+1}) \mod M$.
4. $P_i$ передает число $n_i$ всем узлам, которые выполняют проверку.

### Протокол N2.2
**Цель:** Коллективно сгенерировать случайное число.

**Обозначения:**
- $n_i$ - Случайно сгенерированное число узла $i$
- $n$ - Количество узлов
- $\tilde n$ - Результирующее коллективно случайно сгенерированное число
- $M$ - Количество карт в колоде

**Алгоритм:**
1. Все узлы независимо генерируют значения $n_{i}$ по модулю числа $M$.
2. Все узлы отправляют свои $n_{i}$ в общий канал связи.
3. Узлы складывают полученные числа и сохраняют себе сумму $\tilde n_i = (\sum_1^n n_{i}) \mod M$.
4. Узлы обмениваются числами $\tilde n_i$ и выполняют проверку корректности которые выполняют проверку.

### Протокол N3
**Цель:** Секретно взять $k$ карт из колоды.

**Обозначения**
- $K$ - Множество карт выбора
- $N$ - Множество карт сброса
- $\tilde K$ - Количество карт во множестве $K$
- $n$ - Количество игроков
- $m$ - Начальное число карт на руках у игрока

**Алгоритм**
1. Добрать $k$ карт из множества $K$, соответствующие свободным индексам
2. Если индексы закончились, то
* Собрать свободные индексы у всех игроков
* Составить новое множество $K$ из карт, находящихся на позициях полученных индексов
* Если индексов достаточно мало, то смешать $K$ с $N$ $^*$
* Выполнить протокол \(N0\) для $s = \tilde K/n$
3. Добрать оставшиеся карты

$*$ Если правила игры это позволяют

**Примечание**
Свободные индексы - индексы карт, которые игрок может взять в процессе игры из множества $K$. Получаются после выполнения протокола $N0$ для $s$ большим, чем минимальное количество карт на руках у игроков.

### Взрывные котята
### Правила
Начальные условия:
- Количество игроков от двух до пяти.
- В колоде 56 карт, среди которых 6 зеленых, 4 черных, а остальные - нейтральные.

Процесс игры:
1. В начале игры каждый игрок получает по 1 зеленой карте, $(6-n)$ оставшихся вмешиваются в колоду (если игроков не более 3, то вмешиваются 2, остальные удаляются из игры);
2. Черных карт вмешивается в колоду на единицу меньше, чем игроков;
3. Каждый игрок в начале хода тянет одну карту из колоды
3.1. если вытянул НЕЙТРАЛЬНУЮ: помещает в колоду сброса;
3.2. если вытянул ЗЕЛЕНУЮ: забирает себе;
3.3. если вытянул ЧЕРНУЮ: проверяет наличие зеленой карты
3.3.1. если зеленая есть: черную вмешивает в колоду, а зеленую сбрасывает;
3.3.2. если зеленой нет: игрок проиграл.

### Протокол
**Обозначения:**
- n - количество игроков $(2 \le n \le 5)$
- M - количество карт в колоде $(M = 56)$
- K - множество карт новой колоды.
- N - множество карт колоды сброса.

**Алгоритм**
1. Игрок-инициатор начинает игру, сообщая об этом остальным.
2. Все игроки собирают новую колоду $K$ в зависимости от значения $n$:
1. Если $n \ge 4$: $M = 46 + (6 - n) + (n - 1) = 51$
2. Если $n \le 3$: $M = 46 + 2 + (n - 1) = 47 + n\ (M \in [49, 50])$
> Карты в колоде $K$ располагаются в порядке: нейтральные, черные, зеленые.
3. Каждый игрок забирает одну зеленую карту без удаления ее из колоды (это выполнимо, так как в шаге 2 зеленых карт в колоде 6 - n).
4. Выполняется тасование (протокол $N1$).
5. Игроки выбирают участника, который сделает первый ход, выбирая случайную карту с помощью протокола $N2.1$ (карта же удаляется из $K$), после чего делает проверку:
5.1. Если карта нейтральная, он помещает ее во множество $N$
5.2. Если карта зеленая, он забирает ее
5.3. Если карта черная, он проверяет наличие у себя зеленой карты:
5.3.1. Если она есть, то она помещается в $N$, а черная возвращается на исходное место (для больше случайности можно выполнить протокол $N1$, но это не обязательно)
5.3.2. Если ее нет, то игрок выбывает

**Примечание**
Ввиду открытости протокола $N2.1$ все действия игрока $i$ видны остальным, поэтому дополнительных проверок на честность выполнять не требуется.
Также важно понимать, что шаг 5 выполняется синхронно на всех узлах ввиду отсутствия секретности.

### Уно
#### Правила
Есть две колоды "прикуп" и "сброс". Из первой игроки выбирают карты, а во вторую - сбрасывают.

В колоде "прикуп" изначально имеется 108 карт, среди которых
1. цифровые карты от 1 до 9 в двойном количестве и по одной с цифрой 0
2. активные карты "пропусти ход", "возьми две" и "наоборот" в двойном количестве
3. черные активный карты "закажи цвет" и "закажи цвет и возьми 4 карты" по одной
Каждая карта представлена в 4 цветах: красный, синий, желтый и зеленый.

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

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

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

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

**Правило "Уно!"**
Если после выкидывания карты у игрока остается одна и кто-то раньше него говорит "Уно", то он берет одну карту из колоды "прикуп".

#### Обозначения
$n$ - количество игроков
$m$ - начальное число карт на руках у игрока ($m = 7$)
$K$ - множество карт в колоде "прикуп" ($\tilde K = 108$)
$N$ - множество карт в колоде "сброс"
$Q_i$ - множество карт, имеющиеся на руках игроков
$L_i$ - множество карт, которые игрок взять не может

#### Алгоритм
1. Игрок $P_i$ начинает игру, о чем сообщает остальным
2. Выполняются протоколы $N0$ и $N1$ для $s = \tilde K/n$
3. Выбирается игрок $P_i$, который делает первый ход и передает его следующему $P_{i+1}$
4. Игрок $P_i$ проверяет возможность выполнения хода:
4.1. Если такая возможность есть, то он выкидывает карту, а ход передается следующему
4.2. Иначе выполняется протокол $N3$ для $k = 1$:
4.2.1. Если после взятия карты ход возможен, он ее выкидывает
4.2.1. Иначе передает ход игроку $P_{i+1}$

**Примечания**
- Каждая выброшенная карта игроком $P_i$ заносится во множество $L_i$.

### Покер
#### Правила
В игре может участвовать от 2 до 10 человек.

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

Перечислим все возможные комбинации в порядке возрастания:
1. Самая младшая комбинация *«Старшая карта»* – это 1 карта. Чем она выше по рангу, тем вероятнее ее победа.
2. *«Пара»* – это 2 одинаковые карты.
3. *«Две пары»* – 4 карты, среди которых собраны по 2 одинаковых по рангу.
4. *«Сет» или «Тройка»* – 3 карты одного ранга.
5. *«Стрит»* – 5 собранных по порядку карт любой масти.
6. *«Флеш»* – 5 одномастных карт.
7. *«Фулл Хаус»* – комбинация, включающая в себя «Пару» и «Тройку» одновременно.
8. *«Каре»* – 4 карты одного ранга.
9. *«Стрит Флеш»* – 5 карт одной масти по порядку.
10. *«Роял Стрит Флеш»* – 5 самых старших одномастных карт.


В колоде 52 карты, среди которых 4 масти (пики, червы, бубны и крести), численные карты от 2 до 10, валет, дама, король и туз.

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

Участники могут совершать следующие действия во время торговли:
- увеличить ставку - поставить выше, чем соперники;
- поставить столько же, сколько поставил соперник - уравнять;
- в ситуациях, когда ставка уже была сделана или ставки не были сделаны соперниками – не добавлять ничего в банк, оставить «как есть»;
- отказаться от дальнейшего участия в игре и сбросить карты.

Круг торговли заканчивается тогда, когда все игроки сделали одинаковые ставки (кроме тех, кто сбросил карты).

После первого круга торговли (если в круге остается больше одного человека) на стол выкладываются три открытые общие карты. Используя их игроки пытаются составить комбинации и оценить свои шансы. Начинается новый круг торговли.

Если после этого раунда в раздаче остается больше одного игрока, то кладут еще одну общую карту. Проводится еще один круг торговли.

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

#### Алгоритм

1. Игрок $P_1$ начинает игру, сообщая об этом остальным игрокам
2. Выполняются протоколы N1 и N0, после чего все делают первую ставку, которые сохраняются в общем для всех игроков банке
> [name=Elina Paxarevskaya] А здесь $s = 2$
3. Все игроки коллективно выбирают три карты из колоды с помощью протокола N2.2
4.