# Криптография

:::warning
[Справка по $\LaTeX$](https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference) + [Short Math Guide v2.0](http://ctan.altspu.ru/info/short-math-guide/short-math-guide.pdf)
:::

[Все презентации в pdf](https://yadi.sk/d/VnZuiNQyLloKRg)

## Вопросы

> ✅ — готов
> 🔄 — не совсем готов
> 🔴 — совсем не готов

$$
П =>^I_k Fp <=> E j, I <= j <= k, П => ^j_k p
$$$$
П =>^I_k !p <=> p\not\in L(П(I))
$$$$
П => p \land g <=> П =>^I_k p \land П => ^I_k g
$$$$
П => ^I_k p \lor g <=> П => ^I_k p \lor П => ^I_k g
$$

[TOC]

## 1. ✅ Симметричные криптосистемы. Исторические шифры. Шифр замены, шифр сдвига.

**Криптография** ("kryptos" – тайный + "grapho" – пишу = "тайнопись") – наука о методах обеспечения конфиденциальности, целостности данных, аутентификации.

- **Конфиденциальность** – невозможность прочтения информации для посторонних;
- **Целостность данных** – невозможность незаметного изменения информации;
- **Аутентификациия** – процедура проверки подлинности.

**Шифрование** – процесс преобразования текста с помощью криптографического алгоритма и ключа в зашифрованный текст.

**Конфиденциальность = Шифрование**

**Криптоанализ** (от др.-греч. κρυπτός «скрытый» + «анализ») — наука о методах дешифровки зашифрованной информации без предназначенного для этого ключа, а также сам процесс такой дешифровки.

**Стеганография** (от греч. στεγανός — скрытый + γράφω — пишу; буквально «тайнопись») — наука о скрытой передаче информации путём сохранения в тайне самого факта передачи.

**Процесс шифрования**: $C = E_k(m)$

**Процесс расшифровывания**: $m = D_k(C)$

- $E$ – Encrypt - шифрующая функция
- $D$ – Decrypt - расшифровывающая функция
- $C$ – Cipher - шифротекст
- $m$ – message - открытый текст
- $k$ – key - секретный ключ

**Шифр сдвига (шифр Цезаря)**


**Шифр замены**


Шифры сдвига и замены – **моноалфавитные**. Их можно взломать при помощи частотного анализа.

**Полиалфавитный шифр замены**


hello → QNTKG

**Шифр Виженера**


Можно взломать при помощи **метода Касиски**:
- по повторяющимся биграммам и триграммам находим вероятные длины ключа
- перебираем длины ключа, для каждой буквы ключа выписываем соответствующее ей подмножество сообщения и взламываем частотным анализом (как шифр сдвига)
- выбираем из полученных вариантов лучший вручную или по распределению вероятностей букв, близкому к естественному (см. критерий $\chi^2$)

**Перестановочный шифр**

- Фиксируем перестановку: $[1, 2, 3, 4, 5] \to [2, 4, 1, 3, 5]$
> once upon a time there was a little girl called Snow White
- Разбиваем сообщение на блоки по длине перестановки
> onceu ponat imeth erewa salit tlegi rlcal ledsn owwhi te
- Выполняем перестановку в каждом блоке
> coenu npaot eitmh eewra lsiat etgli crall dlsen wohwi et
- Соединяем блоки в одно сообщение
> coenunpaoteitmheewralsiatetglicralldlsenwohwiet

Метод взлома – **атака с выбором открытого текста**

**Роторные машины**

Роторная машина – набор вращающихся барабанов, позволяющих задавать ключи для шифров замены. Пример: Энигма.

## 2. ✅ Симметричные криптосистемы и криптосистемы с открытым ключом.

**Симметричные криптосистемы** – алгоритмы, которые используют для шифрования и дешифрования один и тот же ключ.

**Асимметричные криптосистемы** – алгоритмы, которые используют для шифрования и дешифрования разные ключи. Как правило, один из ключей является открытым и известен всем, а другой - закрыт и известен только владельцу.

"Теория связи в секретных системах", Клод Шеннон, 1948 г.

**Теоретико-информационная стойкость**

$\mathbb{P}$ – множество возможных сообщений (открытых текстов)
$\mathbb{K}$ – множество возможных ключей
$\mathbb{C}$ – множество возможных криптограмм (шифротекстов)

**Симметричный шифр** над множеством $\left(\mathbb{P}, \mathbb{K}, \mathbb{C}\right)$ – пара алгоритмов $\left(E, D\right)$, таких что

$$E:\ \mathbb{K} \times \mathbb{P} \to \mathbb{C}$$

$$D:\ \mathbb{K} \times \mathbb{C} \to \mathbb{P}$$

и при этом для любого сообщения $m \in \mathbb{P}$ выполнено: $D(k, E(k, m)) = m$

**Определение**. Криптосистема обладает абсолютной стойкостью, если для всех сообщений $m \in \mathbb{P}$ и для всех криптограмм $с \in \mathbb{С}$ выполняется равенство:

$$p(P = m\ |\ C = c) = p(P = m)$$

**Лемма**. Криптосистема является абсолютно стойкой, если для всех $m$ и $c$

$$p(C = c\ |\ P = m) = p(C = c)$$

Доказательство следует из формулы: $p(P = m\ |\ C = c) = \frac{p(P = m)p(C = c\ |\ P = m)}{p(C = c)}$

**Лемма**. Для абсолютно стойкой криптосистемы выполняется неравенство:

$$\left|\mathbb{K}\right| \geq \left|\mathbb{C}\right| \geq \left|\mathbb{P}\right|$$

**Теорема Шеннона**. Пусть набор $\left(\mathbb{P}, \mathbb{C}, \mathbb{K}, E_k, D_k\right)$ обозначает криптосистему, в которой $\left|\mathbb{K}\right| = \left|\mathbb{C}\right| = \left|\mathbb{P}\right|$. Она обладает абсолютной стойкостью тогда и только тогда, когда

- использование всех ключей равновероятно: $\forall k \in \mathbb{K}:\ p(K=k) = \cfrac{1}{|\mathbb{K}|}$

- для каждой пары $m \in \mathbb{P}$ и $c \in \mathbb{C}$ существует единственный ключ $k$, такой что $E_k(m) = c$

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

Симметричные шифры разделяются на **блочные** и **поточные**. В блочном шифре сообщение разбивается на блоки равной длины и каждый блок кодируется ключом. В поточном шифре используется поток ключей, который побайтово XOR'ом кодирует сообщение.


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

## 3. ✅ Блочные шифры. Алгоритм DES.

**Блочный шифр** – разновидность симметричного шифра, оперирующего группами бит фиксированной длины.

Основные принципы шифра по Шеннону: **рассеивание** + **перемешивание**

**SP-сеть** = substitution-permutation network (SPN) – чередующиеся стадии подстановки (Substitution) и перестановки (Permutation)

**S-блок** (substitution box, S-box) – таблица подстановки, которая отвечает за перемешивание данных

**P-блок** (permutation box, P-box) – таблица перестановки, которая отвечает за рассеивание данных

**Сеть Фейстеля**:


**Алгоритм DES**

Начальная перестановка $IP$ $\to$ сеть Фейстеля $\to$ конечная перестановка $IP^{-1}$

* Количество раундов ($S$): 16
* Размер блока ($n$): 64 бита
* Размер ключа ($k$): 56 бит
* Подключи: $k_0,\ \ldots,\ k_{16}$ по 48 бит

1. Разбить текст на блоки $T_1, ..., T_l$ по 64 бита, затем для каждого блока независимо выполнить операции 2-5.
2. Применить к текущему блоку начальную перестановку: $T_i = IP(T_i)$
3. Разбить блок на две части по 32 бита: $L_0 = T_i[0;31]$ и $R_0 = T_i[32;63]$ соответственно
4. Провести 16 раундов шифрования с использованием раундовых подключей
5. Вернуть зашифрованное значение $T_i = IP^{-1}(L_{16}R_{16})$

**Раунд шифрования**:

$\left\{
\begin{array}{l}
L_i = R_{i-1} \\
R_i = L_{i-1} \oplus f(R_{i-1}, k, i) \\
\end{array}
\right.$

где функция $f(R, k, i)$ выглядит следующим образом:

* Применить перестановку с расширением: $R = E(R)$ с 32 до 48 бит
* Сложить по модулю 2 с 48-битным подключом раунда: $R = R \oplus k_i$
* Разбить $R$ на 8 блоков по 6 бит: $R = B_0\ldots B_7$
* Для каждого блока выполнить подстановку через S-блок (8 раз, 6 бит $\to$ 4 бита)
* Сконкатенировать полученные блоки в 32-битный блок: $R = \hat{B_0}..\hat{B_7}$
* Выполнить финальную перестановку: $R = P(R)$
* Вернуть 32-битное значение $R$

**S-box**


**Генерация подключей**:

* Добавление битов чётности на позиции 8, 16, 24, 32, 40, 48, 56, 64 со сдвигом оставшихся битов вправо. Значени бита чётности должно задавать нечётное количество единиц в соответствующем байте.
* Разбить ключ на 2 блока $k = C_0(k) D_0(k)$ по 28 бит, где $C_0$ и $D_0$ -- независимые перестановки
* Для всех значение раундов $i = 1..16$ выполнить независимые циклические сдвиги $C_{i-1}$ и $D_{i-1}$ на 1 или 2 бита вправо (количество опеределяется таблицей)
* Для каждого подключа выполнить операцию сужения до 48 бит $k_i = P(C_iD_i)$
* Вернуть 16 подключей $k_1..k_{16}$

**Модификация: 3DES**, использует 3 ключа по 56 бит (3*56=168)

**Режимы работы DES (и блочных шифров вообще)**:

* **ECB** (Electronic Code Book) -- все блоки шифруются независимо (как один из плюсов -- можно делать параллельно, но при этом есть атака через подмену/удаление/вставку блока)
* **CBC** (Cipher Block Chaining) -- каждый последующий блок сначала выполняет операцию $T_i = T_{i-1}\oplus T_i$, потом шифруется через **DES**. Предотвращает потери при атаке со вставкой и удалением
* **CFB** (Cipher FeedBack) -- есть публичный начальный вектор $T_0$, а само шифрование происходит через **DES** по схеме $T_i = DES(T_{i-1},k)$. Блочный шифр превращается в поточный. Отдельная ошибка в криптограмме при этом влияет как на блок, в котором она допущена, так и на следующей блок
* **OFB** (Output FeedBack) -- есть публичный начальный вектор $A_0$, который дальше прогоняется через **DES** ($A_i = DES(A_{i-1}, k)$), а само шифрование это $T_i = T_i \oplus A_i$. Блочный шифр превращается в поточный. Ошибка в одном бите в шифротексте дает один ошибочный бит в расшифрованном тексте – нет распространения ошибки

## 4. ✅ Блочные шифры. Алгоритм AES (Rijndael).

**Алгоритм AES**:

* Количество раундов: $[10, 12, 14]$ (в зависимости от размера ключа)
* Блок: $n = 128$ бит
* Размер ключа: $k = [128, 192, 256]$ бит
* Подключи: $k_0, ..., k_{16}$ по 48 бит

AddRoundKey(S, K[0]);
for (i=l; i<=9; i++) {
    SubBytes(S);
    ShiftRows(S);
    MixColumns(S) ;
    AddRoundKey(S, K[i]);
}
SubBytes(S);
ShiftRows(S);
AddRoundKey(S,К[10])

1. Разбить текст на блоки по 16, 24, 32 байт (в зависимости от размера ключа) и представить каждые блок в виде матрицы $S_b$ 4x(4|6|8)

(Для упрощения понимания, дальше будет описан алгоритм для ключа 128 бит, матрица состояния 4х4)

2. Посчитать $10 + 1$ подключей по 4 байта и сохранить их массиве $ws$
3. Выполнить операцию $S_b = AddRoundKey(S_b, ws[0])$
4. Выполнить 10 раундов ($i=1..10$) шифрования, которые выглядят так:
4.1. Выполнить преобразование $S_b = SubBytes(S_b)$, котороые выполняет нелинейное преобразование над каждым байтом в матрице: получает байт перестановки из S-box (который задаёт обратный многочлен в поле Голуа ($2^8$) с модулем $r(x) = x^8+x^4+x^3 + x + 1$) и выполняет над ним операцию $B[i] = B[i] \oplus B[(i + 4) \% 8] \oplus B[(i + 5) \% 8] \oplus B[(i + 6) \% 8] \oplus B[(i + 7) \% 8] \oplus 99$, где $B[i]$ -- $i$ бит байта $B$
4.2. Выполнить преобразование $S_b = ShiftRows(S_b)$, которое совершает циклический сдвиг строки матрицы на $t$ раз влево, где $t$ -- номер строки в таблице, начиная с 0
4.3. Выполнить преобразование $S_b = MixColumns(S_b)$ $(\color{red}{за\ исключением\ последнего\ (10)\ раунда})$, которое воспринимает каждую колонку (4 байта), как полином $p(x)$ 3 степени: в поле Голуа ($2^4$) проиведение полиномов $p(x)c(x)$ берётся по модулю $r(x)=x^4+1$, где $c(x)=3 x^3 + x^2 + x + 2$ фиксированные полином
4.4. Выполнить операцию $S_b = AddRoundKey(S_b, ws[i])$
5. Вернуть 16 байт шифротекста из матрицы $S_b$

## 5. ✅ Блочные шифры. ГОСТ 28147-89.

Работает, как и DES, на основе сети Фейстеля:

**Алгоритм**:

* Количество раундов: 32
* Блок: $n = 64$ бита
* Размер ключа: $k = 256$ бит
* Подключи: $k_0, ..., k_{16}$ по 32 бита

1. Разбить текст на блоки $T_1, ..., T_l$ по 64 бита, затем для каждого блока независимо выполнить операции, начиная с 2.
2. Разбить блок на части по 32 бита $L_0 = T_i[0;31]$ и $R_0 = T_i[32;63]$ соответственно
3. Провести 32 раунда ($i = 1..32$) шифрования
4. Вернуть зашифрованное значение $T_i = L_{16}R_{16}$

**Раунд шифрования**:

$\left\{
\begin{array}{l}
L_i = R_{i-1} \oplus f(L_{i-1}, k, i) \\
R_i = L_{i-1} \\
\end{array}
\right.$, где функция $f (L, k, i)$ выглядит следующим образом:

* Сложить числа $L = (L + K_i) \% 2^{32}$, где $K_i$ -- подключ для шага $i$
* Разбить число $L$ на 8 блоков по 4 бита -- $L = a_1..a_8$
* Для каждого блока произвести заммену, согласно S-box: $a_i = bin(S_i[dec(a_i)])$. При этом сами S-box'ы в ГОСТ не приводятся, и предполагается, что они хранятся в секрете (что не очень хорошо).
* Вернуть 32 битное число, полученное конкатенацией частей $L = a_1 a_2 .. a_8$

**Генерация подключей**:

* Исходный ключ $k$ разбивается на 8 частей по 32 бита: $k=k_1 k_2..k_8$
* Подключи $K_i = k_{i\ mod\ 8} \forall i \in [0;23]$, оставшиеся 8 подключей -- исходные подключи $k_i$ в обратном порядке

**Преимущества**
- Криптостойкость (устойчив к линейному и дифференциальному криптоанализу)
- Скорость работы, эффективность реализации
- 4 режима работы, возможность аутентификации (имитовставка)

**Недостатки**
- Не описан способ генерации ключей и таблиц замены – существуют слабые ключи и слабые таблицы замены
- Потихоньку устаревает

## 6. ✅ Криптография с открытым ключом. Математические задачи, на которых она основывается.

**Криптография с открытым ключом, общая схема:**

* Шифрование: $C = E_{ok}(m)$, где $ok$ - открытый ключ
* Дешифрование: $m = D_{pk}(C)$, где $pk$ - приватный ключ

**Односторонняя функция** -- математическое преобразование,
которое тяжело обратить не зная секретной информации, формально:

* Функция $F : X \rightarrow Y$ такая, что существует полиномиальный алгоритм вычисления $F(x),$ и не существует полиномиального алгоритма решения уравнения $F(x)=y$ относительно $x$

**Односторонняя функция с потайным входом (функция-ловушка)** -- односторонняя функция, секретной информацией которой является ключ, формально:

* Функция $F : K \times X \rightarrow Y$ такая, что (1) существует полиномиальный алгоритм генерации пары ключей $(k_1, k_2)$, (2) существует полиномиальный алгоритм вычисления $F_{k_1}(x)$, (3) не существует полиномиального алгоритма решения уравнения $F_{k_1}(x) = y$ при неизвестном $k_2$, (4) существует полиномиальный алгоритм решения уравнения $F_{k_1}(x) = y$ при известном $k2$

**Пример**: факторизация числа (разложение на множетели)

Вычислить $N = p*q$, где $p, q$ -- простые числа, просто, а разложить $N$ на простые множители не зная ни одного из $p, q$ -- сложно. Верно для произведения любого числа множителей $\prod_{i=0}^{n} p_i$, но на практика используются два простых.

Лучший алгоритм факторизации $N$ - общий метод решета числового поля (general number field sieve, GNFS), который имеет асимптотику:
$$L_{N}(\frac{1}{3},\sqrt[3]{\frac{64}{9}}) = exp((\sqrt[3]{\frac{64}{9}} + o(1))(ln\ N)^{\frac{1}{3}}(ln\ ln\ N)^{\frac{2}{3}}),$$

то есть примерно кубический корень от длины $N$.

**Пример**: дискретное логарифмирование

Вычислить $B = A^{n}\ mod\ p$, зная $A$, $p$ и $n$ -- просто, но найти $\hat{n} = n$ при известных $A$, $p$ и $B$ -- сложно.

**Пример**: вычисление дискретного корня

Вычислить $A = n^2\ mod\ p$, зная $n$ и $p$ -- просто, но найти $\hat{n} = n$ при известных $A$ и $p$ -- сложно.

## 7. ✅ Криптография с открытым ключом. Алгоритм RSA.

**Задача RSA**

Задача RSA - функция-ловушка, на которой основана криптосистема RSA. Формулируется следующим образом:

Даны числа $Y, E, N=p*q$, где $$НОД(E, (p-1)*(q-1)) = 1,$$ необходимо найти m такое, что $$ m^E \equiv Y(mod\ N)$$

**Алгоритм**:

1. Сгенерировать 2 простых числа $p, q$ и вычислить их произведение $N = p * q$
2. Вычислить значение функции Эйлера $\phi(n) = (p - 1) * (q - 1)$
3. Выбрать число $0 < e < \phi(n)$ такое, что $GCD (e, \phi(n)) = 1$
4. Найти мультипликативно обратное число $d$ такое, что $d * e \equiv 1 (mod\ \phi(n))$
5. Опубликовать открытый ключ $(e, n)$
6. Запомнить закрытый ключ $(d, n)$

**Шифрование и дешифрование**

Пусть $m$ -- сообщение, которое является числом таким, что $0 \le m \le n$, тогда $C = m^e (mod\ n)$,
а дешифрование $m = C^d (mod\ n)$. Это работает, потому что
$(m^e)^d (mod\ n) = m^{e * d} (mod\ n) = m^{1 + s\phi(n)} (mod\ n) = m\cdot m^{s\phi(n)} (mod\ n) = m (mod\ n)$

$e*d = 1 + s\phi(n)$ по опредению сравнимости:
$e * d \equiv 1 (mod\ \phi(n)) \Leftrightarrow e * d - 1\ \vdots\ \phi(n) \Leftrightarrow e * d - 1 = s\phi(n)$

**Лемма 1**: Задача RSA не сложнее, чем задача факторизации

**Доказательство**:

Если существует алгоритм факторизации, то мы можем найти $p$ и $q$, для которых $p*q=N$, отсюда вычислить $E = \phi(N)$, отсюда найти обратное число $d$, и получить $C^d \equiv m^ed \equiv m^{1\ mod\ \phi(n)} \equiv m (mod\ N)$.

**Лемма 2**: Если задача RSA является трудноразрешимой, то и криптосистема RSA вычислительно защищена от атак с выбором открытого текста (взлом криптосистемы RSA не легче взлома задачи RSA)

**Доказательство**:

Пусть у нас есть оракул, взламывающий криптосистему RSA. Взломаем с его помощью задачу RSA (сведём задачу к криптосистеме).
В задаче RSA даны $Y, E, N$. Для взлома дешифруем сообщение $C=Y$ - мы получим открытый текст $m$, для которого $m^E \equiv C = Y(mod\ N)$. То есть мы нашли $m$ и решили задачу RSA.

**Атаки и прочие факты:**

1. **Если известна расшифровывающая экспонента $d$, соответствующая публичному ключу $(e,n)$, то число $n$ можно эффективно разложить на множители**

$\phi(n)=(p-1)(q-1)=N-(p+q)-1$
Пусть $S = N + 1 - \phi(n) = p + q$

Нам необходимо найти $p$ и $q$, зная их сумму $S$ и произведение $N$.
Рассмотрим многочлен $f(X) = (X - p)(X - q) = X^2 - SX + N$, решив его, мы получим искомые значения:

\begin{array}{ll}
p = \frac{S+\sqrt{S^2 - 4N}}{2} & q = \frac{S - \sqrt{S^2 - 4N}}{2}\\
\end{array}

2. **Общее значение $n$**

Допустим, что нападающий знает 2 шифра $C_1 = m^{e_1} (mod\ n), C_2 = m^{e_2} (mod\ n)$

Тогда он может вычислить $T_1 = e_1^{-1} (mod\ e_2)$ и $T_2 = \frac{T_1 e_1 - 1}{e_2}$

И дальше восстановить сообщение:

$C_1^{T_1} C_2^{-T_2} = m^{e_1 T_1}m^{-e^2 T_2} = m^{1 + e_2 T_2}m^{-e_2 T_2} = m^{1 + e_2 T_2 - e_2 T_2} = m$

3. **Малые шифрующие экспоненты $e$**

Допустим, что нападающий знает 3 шифра $C_1 = m^3 (mod\ n_1), C_2 = m^3 (mod\ n_2), C_3 = m^3 (mod\ n_3)$

Тогда с помощью Китайской Теоремы об Остатках может найти решение системы в виде $X = m^3 (mod\ n_1 n_2 n_3)$

4. **Атака Винера при малых дешифрующих экспонентах**

При $d < \frac{1}{3}N^\frac{1}{4}$ нападающий может найти $d$.
Эта атака основана на том, что существует такое $k$, при котором $ed - k\phi(N) = 1$, то есть $$|\frac{e}{\phi(N)} - \frac{k}{d}| = \frac{1}{d\phi(N)},$$ следовательно $\frac{k}{d} \approx \frac{e}{\phi(N)}$. И мы можем найти $\frac{k}{d}$ в процессе разложения $\frac{e}{\phi(N)}$ на непрерывную дробь.

5. **Атака перебором**

На сегодняшний день максимальная длина подобранного ключа RSA - $\approx 800$ бит. Используемые сейчас значения - от 1024 до 4096 бит (NSA рекомендует хотя бы RSA-3072 для Top Secret данных).

6. **Квантовый перебор**

Алгоритм Шора факторизует число $N$ за $O(\log^3 N)$ времени на квантовом компьютере с $O(\log N)$ кубитов. На сегодняшний день известно о существовании компьютера с 53 кубитами. Так что эта угроза - в будущем.

**TLDR:** не экономьте на качестве ключей.

## 8. ✅ Криптография с открытым ключом. Алгоритм рюкзак.

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

**Алгоритм**:

1. Генерируем сверхвозрасающую последовательность $a_i$ длины $n$, которая будет секретным ключом
2. Генерируются взаимнопростые числа $p, q$
3. Последовательность $a_i$ преобразуется в последовательность $b_i = (a_i * p) \% q$, которая будет открытым ключом

**Шифрование**:

* Текст рабивается на блоки ($T_1..T_l$) по $n$ бит
* Для каждого блока вычисляется сумма: $s_i = \sum_{t=0}^n T_i[t] * b_t$, т.е. суммируются те члены публичной последовательности, на позиции которых в блоке стоит 1
* Публикуется шифротекст $s_1..s_l$

**Дешифрование**:

* Вычисление мультипликативно обратного числа $r$ такого, что $r * p \equiv 1 (mod\ q)$
* Преобразование последовательности шифротекста в последовательность $c_i = (s_i * r) \% q$
* Разложение каждого элемента последовательности $c_i$ на сумму элементов из $a_i$. Например, если $a={2, 3, 6, 13, 27}$, а $c = 9$, то $\hat{s} = 9 = 2 * 0 + 3 * 1 + 6 * 1 + 13 * 0 + 27 * 0$, что соответствует сообщению $01100$
* Конкатенация сумм и восстановление расшифрованного текста

## 9. ✅ Криптография с открытым ключом. Алгоритм Эль-Гамаль.

**Публичные данные**: простое число $P$; число $G$ такое, что $G^{\phi(P)}\equiv 1 (mod\ P)$

**Секретные данные**: ключ $1 < x < p - 1$

**Шифрование**:

1. Генерация сессионного ключа $1 < k < p - 1$
2. Вычисление значений $a = G^k (mod\ P)$ и $b = y^k * m (mod\ P)$, где $y = G^x (mod\ P)$
3. Публикация шифротекста $(a, b)$

**Дешифрование**:

$b * a^{-x} = b * G^{-kx} \equiv (G^{kx} * m) * G^{-kx} (mod\ P) \equiv m (mod\ P)$

В отличие от классической схемы обмена ключами Диффи-Хелмана в данной схеме невозможна атака "Человек посередине" (с прослушиванием), потому что значение $G^x$ адресата является публичным ключом, и в случае его подмены адресат не сможет корректно дешифровать отправленное ему сообщение. В худшем случае атакующий может помешать установлению канала связи между двумя участниками, подменив $G^x$

## 10. ✅ Распределение ключей с помощью криптографии с открытым ключом. Алгоритм Диффи-Хэлмана и использование RSA для передачи ключей.

**Прогрессивно секретная криптосистема** -- криптосистема, у которой компроментация долгосрочного секретного ключа в какой-то момент времени не приводит к вскрытию тайны переписки в прошлом.

**Протокол распределения ключей Диффи-Хелмана**:

1. Оба участника генерируют сессионные секретные ключи $a, b$ соответственно
2. Оба участника вычисляют значения $G_a = G^a (mod\ P), G_b = G^b (mod\ P)$ соответственно
3. Участники обмениваются значениями $G_a$ и $G_b$
4. Имея значение $G_x$ собеседника, оба участника вычисляют значения $G_{ba} = G_b^a (mod\ P) = (G^b)^a (mod\ P)$ и $G_{ab} = G_a^b (mod\ P) = (G^a)^b (mod\ P)$ соответственно
5. В результате у участников есть общее значение $G_{ab}$, которое будет являться секретным ключом

**Проблема алгоритма в чистом виде**: атака "Человек посередине"

Из-за того, что участники никак не идентифицируют себя, значение $G_x$, котрое было получено от собеседника, может оказаться подставным. Идея в том, что атакующий, перехватывает значение $G_a$ и вместо него отправляет свой $G_{fa}$, аналогично со вторым значением. В итоге получается, что участники думают, что они общаются друг с другом, но по факту каждый из них общается с человеком по середине. Причём у участников нет возможности понять это.

**Защита от атаки**: цифровая подпись значений $G_x$.

**Протокол распределения ключей с использованием RSA**:

1. Оба участника генерируют сессионные пары ключей $(e_a, d_a, n_a)$ и $(e_b, d_b, n_b)$ соответственно
2. Оба участника публикуют свои открытые ключи $(e_a, n_a)$ и $(e_b, n_b)$ соответственно
3. Один из участников (допустим А) отправляет В сообщение $E_{e_b}(m)$, где $m$ -- какое-то сообщение
4. Участник В расшифровывает сообщение $m = D_{d_b}(E_{e_b}(m))$ и меняет его заранее определённым способом $m_b = m + \delta$
5. Участник В отправляет сообщение $E_{e_a}(m_b)$ участнику А
6. Участник А расшифровывает сообщение $m_b = D_{d_a}(E_{e_a}(m_b))$ и проверяет, что $m_b - m = \delta$
7. Участник А генерирует сессионный ключ для алгоритма симметричного шифрования $k$ и отправляет B сообщение $E_{e_b}(k)$
8. Участник В расшифровывает сообщение $k = D_{d_b}(E_{e_b}(k))$
9. У обоих участников есть секретный ключ $k$, которые они дальше используют в заранее оговрённом алгоритме симметричного шифрования

## 11. 🔄 Цифровые подписи. Использование симметричной криптографии, криптографии с открытым ключом и хэш-функции для создания цифровой подписи. Digital Signature Algorithm.

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

Как правило, сначала от сообщения берётся хэш, потом он шифруется секретным ключом. Для проверки надо расшифровать хэш открытым и посчитать хэш от сообщения. Если сошлось, то подпись правильная.

Цифровая подпись также применяется для защиты от MITM атак.

**Схема подписи с приложением**
- СООБЩЕНИЕ + секретный ключ Алисы = ПОДПИСЬ
- СООБЩЕНИЕ + ПОДПИСЬ + ОТКРЫТЫЙ КЛЮЧ АЛИСЫ = ДА/НЕТ

**Схема подписи с восстановлением сообщения**
- СООБЩЕНИЕ + секретный ключ Алисы = ПОДПИСЬ
- ПОДПИСЬ + ОТКРЫТЫЙ КЛЮЧ АЛИСЫ = ДА/НЕТ + СООБЩЕНИЕ

**Общая схема цифровой подписи**
- Секретное преобразование подписи $s$
- Открытое преобразование проверки $V$

1. Подпись достоверна. Она убеждает получателя документа в том, что подписавший сознательно подписал документ.
2. Подпись неподдельна. Она доказывает, что именно подписавший, и никто иной, сознательно подписал документ.
3. Подпись не может быть использована повторно. Она является частью документа и её невозможно перенести на другой документ.
4. Подписанный документ нельзя изменить. После того, как документ подписан, любое изменение делает подпись невалидной.
5. От подписи невозможно отречься. Подпись и документ материальны. Подписавший не сможет впоследствии утверждать, что он не подписывал документ.

Алиса: $М$ – сообщение, $S = s(M)$ –цифровая подпись.
Боб: $V(S)$ – проверка подписи, получает на выходе сообщение $M$ и 1 бит $v$ – результат проверки подписи.

Корректная подпись подтверждает:
- Целостность сообщения (не было изменено)
- Оригинальность сообщения (было отправлено Алисой)
- Отсутствие ренегатства (Алиса точно его посылала, даже если не признаётся в этом)

**RSA как алгоритм подписи**
- Алиса – отправитель - возводит сообщение в секретную степень $d$: $S = m^d (mod\ N)$
- Боб – получатель – восстанавливает сообщение: $M = S^E (mod\ N)$

Но такая подпись занимает большой объём памяти и трудно вычисляется


В общем случае к сообщению добавляется установленное дополнение, и при расшифровке проверяется, что дополнение корректно (а значит, и сообщение расшифровали верно)

**DSA – Digital Signature Algorithm**

- I этап
1. Фиксируется 160-битное простое $Q$
2. Выбирается простое $P$: $2^{512} < P < 2^{2048}$, $P - 1$ делится на $Q$
3. Генерируется $H < P$
4. Вычисляется $G = H^{(P - 1)/Q}(mod\ P)$
5. Если $G = 1$, возвращаемся к пункту 3. Так обеспечиваем $G^Q = 1 (mod\ P)$
- II этап
1. Каждый пользователь генерирует свой собственный секретный подписывающий ключ $x$: $0 < x < Q$
2. Открытый ключ $Y$: $Y = G^x(mod\ P)$
- III этап: подпись сообщения
1. Вычисляется хэш $H = h(M)$
2. Выбирается эфемерный ключ $0 < k < Q$
3. Определяется $R = [G^k(mod\ P)](mod\ Q)$
4. Находится $S = (H + xR) / k (mod\ Q)$
5. Подписью сообщения $M$ служит $(R, S)$ – 320 бит
- IV этап: проверка подписи
1. Вычисляется хэш $H=h(M)$
2. Определяется $A = H/S (mod Q)$ и $B = R/S (mod Q)$
3. Находится $V = [\{(G^A)(Y^B)\} (mod\ P)] (mod\ Q)$
$Y$ -- открытый ключ автора сообщений
4. Подпись корректна, если $V = R$

**Подпись Шнорра**

Ключевая пара – секретный ключ $x$, открытый ключ $Y=G^x (mod\ P)$

- Подпись сообщения
1. Выбирается эфемерный ключ $0 < k < Q$
2. Определяется $R = G^k (mod\ P)$
3. Находится $E = h(M || R)$
4. Вычисляется $S = k+xE (mod\ Q)$
5. Подписью является пара $(E, S)$
- Проверка подписи
1. Вычисление $R = G^S * Y^{-E} (mod\ P)$
2. Вычисление $E' = h(M||R)$
3. Подпись корректна, если $E' = E$

Алгоритм подписи Шнорра был предложен к эксплуатации в
процедурах запрос-ответ идентификации кредитных карточек, по­
скольку «отвечающая» часть подписи (значение S) легко проверя­
ется, так как д,ля этого нужно всего лишь одно умножение и одно
сложение в конечном поле. Независимо от того, в какой группе мы
работаем, эта заключительная стадия требует только арифметики
по модулю относительно небольшого простого числа.

TODO:

## 12. 🔄 Хэш-функции. MD5

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

- Необратимость: для заданного значения хеш-функции $m$ должно быть практически невозможно найти блок данных $X$, для которого $H(X)=m$.
- Стойкость к коллизиям первого рода: для заданного сообщения $M$ должно быть практически невозможно подобрать другое сообщение $N$, для которого $H(N)=H(M)$.
- Стойкость к коллизиям второго рода: должно быть практически невозможно подобрать пару сообщений $(M, M′)$, имеющих одинаковый хеш.

**Алгоритм**:

1. Дополнить исходный текст $T$ до длины $l \equiv_{512} 448$ по схеме: $T = T10^*$
2. Дописать в конце текста 64 бита, соответствующие длине хэшируемого текста
3. Инициализировать начальные состояния чисел по 4 байта $A, B, C, D$
4. Определить таблицу констант $C[i] = floor(2^{32} * |sin\ i|)$
5. Разбить дополненный текст на блоки по 512 бит $T = T_1..T_l$
6. Для каждого блока независимо провести:
6.1. Разбить блок на 16 подблоков по 32 бита $T_a = t_{a_1}..t_{a_{16}}$
6.2. К каждому подблоку применить функцию $p(x_1, x_2, x_3, x_4, f, k, i, s) = x_1 := x_2 + ((x_1 + f(x_2, x_3, x_4) + t_{a_k} + C[i]) <<< s)$ 64 раза (16 раз с $f = F$, 16 раз с $f = G$, 16 раз с $f = H$, 16 раз с $f = I$) с определённым значением s для каждого раунда и перестановкой $[A, B, C, D]$ в качестве аргументов $x_1, x_2, x_3, x_4$
7. Вернуть значение $R = ABCD$, которое и будет являться 128 битным хэшом

**Вспомогательные функции**:

* $F(x, y, z) = (x \wedge y) \vee (\neg x \wedge z)$
* $G(x, y, z) = (x \wedge z) \vee (\neg z \wedge y)$
* $H(x, y, z) = x \oplus y \oplus z$
* $I(x, y, z) = y \oplus (\neg z \vee x)$

## 13. ✅ Криптоанализ

**Криптоанализ** -- наука о методах дешифровки информации без предназначенного для такой операции ключа

Криптоанализ предполагает выявление ключа или нахождение уязвимсотей реализации алгоритма

**Криптографическая атака** -- попытка дешифровать конкретную информацию методами криптоанализа

**Взлом** -- криптографическая атака, которая достигла своей цели

**Принципы Керкхоффа + современности (вольная интерпретация)**:

1. Система должна быть физически невскрываемой (только математически)
2. Система не должна храниться в тайне (только ключ), чтобы враг не получал преимущества при физическом захвате системы (чем меньше секретов в системе, тем выше безопасность)
3. Участники общения должны иметь возможность менять ключ по своему усмотрению
4. Система должна быть проста в использовании, и не должна требовать участия нескольких лиц одновременно

**Методы**:

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

**Виды атак**:

* Полный перебор
* Частотный анализ
* Метод Касиски - атака на шифр Вижинера (исторический пример)
* Атака "Дней рождений" -- поиск коллизий (тексты x и y, для которых $h(x) = h(y)$ за $O(2^{n/2})$
* Атака "Человек посередине"

**Линейный криптоанализ**:

1. Строим соотношения между открытым текстом, шифротекстами и ключами. Оцениваем их вароятности.
2. Применяем соотношения с высокой вероятностью к известным шифротекстам

Смог взломать DES

**Дифференциальный криптоанализ**

Выявление закономерностей в шифротекстах в зависимости от изменений в открытых текстах.

Так же можно ещё смотреть на разницу в данных между раундами и делать какие-то выводы отсюда.

На практике слабо применим, потому что требует много времени и объём данных.

**Атаки по сторонним каналам**

Окружаем мобильник всеми возможными датчиками, застваляем что-то шифровать/дешифровать, а дальше кормим всё в нейро-сетку и что-то получается (было лень писать, и ёжикам понятно, что это такое)

* Время выполнения
* Потребляемая мощность
* Электомагнитное излучение
* Издаваемые звуки
* Излучение от экрана

**Криптостойкость** -- способность криптографического алгоритма противостоять криптоанализу

Взлом должен требовать слишком много ресурсов: времени (актуальность информации), открытых текстов, памяти

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

## 14. Симметричное vs асимметричное шифрование

1. Симметричное шифрование использует один и тот же ключ, а в асимметричном применяются два ключа: открытый и закрытый
2. При симметричном шифровании перехват ключа приводит ко взлому зашифрованных сообщений, а при асимметричном передаётся только часть ключа, которая не является секретной.
3. В симметричных системах ключ генерируется случайным образом, а в асимметричном шифровании есть формула генерации пары ключей, что сокращает пространство возможных ключей. Поэтому в симметричных системах длина ключей обычно равна 128-256 бит, тогда как в асимметричных для сравнимой стойкости нужно 2048 бит.
4. Симметричные системы быстрее и требуют меньше вычислительной мощности, чем асимметричные.
5. При помощи асимметричного шифра можно зашифровать ограниченный объём информации, например, 245 байт для RSA. Для шифрования большего объёма данных их нужно разбить на блоки не более 245 байт. На практике вместо этого асимметричным шифром шифруют симметричный ключ, и далее кодируют симметричным шифром.