Добавлена 10 лекция

2 files changed, 175 insertions, 0 deletions

diff --git a/cryptography/lectures/lecture10.tex b/cryptography/lectures/lecture10.tex
index 7ab1fb8..28d89d2 100644
--- a/cryptography/lectures/lecture10.tex
+++ b/cryptography/lectures/lecture10.tex
@@ -1,2 +1,173 @@
 % Лекция 10 (07.11.22)
 
+\begin{example}
+  \begin{enumerate}
+    \item
+      Любая группа является также и квазигруппой, так как $$a \cdot x = b \iff x
+      = a^{-1} \cdot b,\, y \cdot a = b \iff y = b \cdot a^{-1}$$
+    \item Целые числа $\Z$ с операцией вычитания ($-$) являются квазигруппой.
+  \end{enumerate}
+\end{example}
+
+С алгебраической точки зрения буква $a_k$ есть результат применения к буквам
+$a_i$ и $a_j$ квазигрупповой операции $\cdot$, табличным заданием которой
+является латинский квадрат $L : a_k = a_i \cdot a_j$.
+
+% TODO: Убрать 8.1?
+В случае шифра Виженера квазигруппа $(A, \cdot)$ является группой $(Z_n, +)$.
+При этом уравнение шифрования имеет вид $$b_i = (a_i + \gamma_i) \pmod{n} \quad
+(8.1),$$ а $\gamma_i$ представляет собой периодическую последовательность,
+образованную повторением некоторого ключевого слова.
+
+Наряду со сложением используется и вычитание знаков гаммы. Соответствующие
+уравнения шифрования принимают вид $$b_i = (a_i - \gamma_i) \pmod{n} \quad
+(8.2)$$ или $$b_i = (\gamma_i - a_i) \pmod{n} \quad (8.3)$$
+
+Шифры гаммирования с уравнениями шифрования (8.1)--(8.3) называют \emph{шифрами
+модульного гаммирования}.
+
+\paragraph{О равновероятной гамме.}
+Рассмотрим Основные идеи анализа на примере шифра с уравнением (8.1). Занумеруем
+буквы алфавита $A$ числами от $0$ до $n - 1$. Пусть $p_i, r_i, s_i$ ---
+вероятности появления знака $i$ в открытом тексте, гамме и в криптограмме
+соответственно.
+
+Тогда задание вероятностных распределений на знаках открытого текста и гаммы
+индуцирует распределение вероятностей знаков шифротекста по формуле:
+\begin{equation*}
+  s_j = \sum_{i = 0}^{n - 1} p_{((j - i) \pmod{n})} \cdot r_i \quad (8.4)
+\end{equation*}
+при этом $$\sum_{j = 0}^{n - 1} s_j = 1.$$
+
+Из формулы (8.4) следует, что если $r_i = \frac{1}{n}$ при всех $i =
+\overline{0, n - 1}$, то $s_j = \frac{1}{n}$ при всех $j = \overline{0, n - 1}$.
+
+Это означает, что при зашифровании открытого текста равновероятной гаммой
+получается шифротекст, вероятностные свойства которого не отличаются от самой
+равновероятной гаммы, что не даёт криптоаналитику использовать диаграмму
+повторяемости букв открытого текста.
+
+% TODO: Новая подсекция, а не секция???
+\section{Надёжность шифров}
+
+% TODO: В оригинале оформлено как \paragraph???
+\subsection{Энтропия языка}
+
+Выдающиеся результаты в применении математических методов в криптографии
+принадлежат Клоду Шеннону (1916--2001).
+
+\emph{Энтропия} определяется функцией от вероятностного распределения и
+характеризуется количеством неопределённости или информации в случайном
+эксперименте.
+
+К.~Шеннон предложил формулу <<прирост информации = устранённой
+неопределённости>>, на основании которой неопределённости и информация должны
+измеряется одной и той же мерой.
+
+К такому выводу можно прийти на примере эксперимента с монетой.
+
+Если монета дефектна и всегда выпадает орёл, то нет никакой неопределённости и
+при этом при проведении эксперимента мы не получим никакой информации (мы заранее
+знали о его исходе, количество информации равно нулю).
+
+Максимальные неопределённость и количество получаемой информации будет в случае,
+когда <<орёл>> и <<решка>> равновероятны.
+
+Пусть независимые испытания случайной величины $\xi$ с распределением
+вероятностей $\xi = \begin{pmatrix}
+  a_1 & \cdots & a_n \\
+  p_1 & \cdots & p_n \\
+\end{pmatrix}$, тогда энтропия $H(\xi)$ определяется формулой $$H(\xi) =
+-\sum_{i = 1}^n p_i \cdot \log_2 p_i \quad (9.1)$$
+
+Единицу измерения энтропии вероятностной схемы предлагает так называемая теорема
+кодирования, утверждающая, что любой исход можно закодировать символами 0 и 1
+так, что полученная длина кодового слова будет сколь угодно близка сверху к
+$H(\xi)$.
+
+На основании этого единицей количества информации считают 1 бит. Например,
+количество информации, полученное при бросании монеты равно 1 бит, так как
+орёл можно закодировать единицей, решку --- нулём.
+
+Если $p_i = \frac{1}{n}$ при всех $i = \overline{1, n}$, то $H_0 = H(\xi)
+= \log_2 n$. Под $H_0 = \log_2 n$ понимается абсолютная энтропия языка ---
+величина, равная максимуму информации, которую можно передать единицей данного
+языка (данная величина не учитывает возможную непроизносимость полученных
+<<слов>>).
+
+В общем случае $H(\xi) \geq 0$, причём $H(\xi) = 0$ в том и только том случае,
+когда $p_i = 1$ для некоторого $i$ и $p_j = 0$ для всех $j \neq i$.
+
+Мерой среднего количества информации, приходящейся на одну букву открытого
+текста языка $\Lambda$ служит величина $H_\Lambda$, называемая \emph{энтропией}
+языка $\Lambda$.
+
+Вычисляется она последовательными приближениями: $H_0, H_1$, где $H_1$ ---
+энтропия позначной модели открытого текста, то есть величина (9.1), в которой
+$p_i$ совпадает с вероятностью появления буквы $a_i$ в открытом тексте.
+
+Для английского языка $H_0 \approx 4.70, H_1 = H(\xi) \approx 4.14$.
+
+Энтропия языка $H_\Lambda$ языка $\Lambda$ определяется как $$H_\Lambda =
+\lim_{r \to \infty} \frac{H_r}{r}$$ где $H_r$ --- энтропия вероятностной схемы
+на $r$-граммах (для осмысленных текстов $\frac{H_r}{r}$ --- угадывание $r$-й
+буквы текста при условии, что предшествующие буквы известны).
+
+При этом формула $R_\Lambda = 1 - \frac{H_\Lambda}{\log_2 n}$ определяет
+\emph{избыточность языка $\Lambda$}.
+
+Например, русский язык имеет избыточность 72.6\%, что означает, что при
+оптимальном кодировании текста (например, код Фано) его можно сжать практически
+до четверти длины без потери информации.
+
+\subsection{Расстояние единственности}
+
+Попытки определения истинного ключа шифра по данной криптограмме путём её
+расшифрования на всех возможных ключах могут привести к тому, что критерий на
+открытый текст примет несколько претендентов за открытый текст.
+
+Найдём оценку для числа ложных ключей.
+
+\emph{Условная энтропия} --- это величина, характеризующая степень
+неопределённости в предсказании исхода эксперимента, если известен исход
+некоторого другого эксперимента.
+
+Пусть имеются дискретные величины $\xi$ и $\eta$, заданные вероятностными
+распределениями $P(\xi), P(\eta)$.
+
+Для них можно вычислить совместное распределение $P(\xi, \eta)$ и условные
+распределения $P(\xi/y), P(\eta/x)$ для любых фиксированных значений $x \in \xi,
+y \in \eta$.
+
+Тогда условная энтропия $H(\xi/y)$ определяется формулой:
+\begin{equation*}
+  H(\xi/y) = -\sum_{x \in \xi} p(x/y) \cdot \log_2 p(x/y)
+\end{equation*}
+
+% TODO: Перенумеровать?
+Усреднённая (по всем $y \in \eta$) величина $H(\xi/y)$ называется \emph{условной
+энтропией двух вероятностных определений}:
+\begin{equation*}
+  H(\xi/\eta) = -\sum_{y \in \eta} \sum_{x \in \xi} p(y) \cdot p(x/y) \cdot
+  \log_2 p(x/y) \quad (9.2)
+\end{equation*}
+
+Величина (9.2) измеряет среднее количество информации $\xi$, обнаруживаемое с
+помощью $\eta$.
+
+Известно, что $H(\xi/\eta) \leq H(\xi)$, причём $H(\xi/\eta) = H(\xi) \iff \xi,
+\eta$ --- независимые случайные величины.
+
+% TODO: Какой индекс у \Sigma?
+Условная энтропия $H(K/Y)$ называется \emph{неопределённостью шифра $\Sigma_B$
+по ключу}. Она измеряет среднее количество информации о ключе, которую даёт
+криптограмма. Аналогично вводится \emph{неопределённость шифра по открытому
+тексту $H(X/Y)$}. Эти величины являются мерой теоретической стойкости шифра.
+Идеально является ситуация, когда $H(X/Y) = H(X)$.
+
+В этом случае шифр можно назвать \emph{идеальным} или \emph{совершенным}, то
+есть такой шифр не даёт криптоаналитику никакой дополнительной информации об
+открытом тексте при изучении перехваченной криптограммы.
+
+Связь между энтропиями компонент шифра даёт формула для неопределённости шифра
+по ключу: $$H(K/Y) = H(X) + H(K) - H(Y)$$.
diff --git a/cryptography/lectures/lecture9.tex b/cryptography/lectures/lecture9.tex
index cb430f9..9fc9d8a 100644
--- a/cryptography/lectures/lecture9.tex
+++ b/cryptography/lectures/lecture9.tex
@@ -97,4 +97,8 @@ X_2 \cdot T^{\gamma_2 - \gamma_3} \cdot \dots T^{\gamma_{N - 1} - \gamma_N}
 
 Криптоанализ дисковых шифраторов является весьма сложной задачей.
 
+\subsection{Шифры гаммирования}
 \textbf{TODO: Дописать}
+
+\paragraph{Шифр Виженера.}
+\paragraph{Табличное гаммирование.}