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

2 files changed, 170 insertions, 1 deletions

diff --git a/cryptography/lectures/lecture11.tex b/cryptography/lectures/lecture11.tex
index d125e20..ec957ce 100644
--- a/cryptography/lectures/lecture11.tex
+++ b/cryptography/lectures/lecture11.tex
@@ -1,4 +1,4 @@
-% Лекция 10 (14.11.22)
+% Лекция 11 (14.11.22)
 
 Пусть $K(y) = \set{k \in K : \exists x \in X,\, E_k(x) = y}$ --- множество
 ключей, для каждого из которых $y$ является результатом зашифрования некоторого
@@ -178,3 +178,5 @@ $p_\text{н} = \max \set{p_\text{им}, p_\text{подм}}$.
 
 Обозначим через $I(Y, K)$ \emph{взаимную информацию} между $Y$ и $K$, то есть
 величину, определяемую формулой $I(Y, K) = H(Y) - H(Y/K)$.
+
+% TODO: Дописать
diff --git a/cryptography/lectures/lecture12.tex b/cryptography/lectures/lecture12.tex
new file mode 100644
index 0000000..e4a0e7a
--- /dev/null
+++ b/cryptography/lectures/lecture12.tex
@@ -0,0 +1,167 @@
+% Лекция 12 (21.11.22)
+
+\subsection{Шифры, не распространяющие искажений}
+
+Помимо целенаправленных искажений передаваемой шифрованной информации
+возможны также искажения, происходящие за счёт наличия помех в канале связи.
+
+Такие помехи могут привести к искажениям или потере отдельных знаков
+используемого алфавита.
+
+Рассмотрим вопрос о свойствах шифра, позволяющих не распространять искажений при
+расшифровании.
+
+Ограничения рассмотрением эндотрофных шифров и искажений, которые либо заменяют
+знаки знаками того же алфавита (искажения типа <<замена знаков>>) либо приводят
+к потере знаков или появлению дополнительных знаков алфавита (искажения типа
+<<пропуск-вставка знаков>>).
+
+\subsubsection{Шифры, не распространяющие искажений типа <<замена знаков>>}
+
+Рассмотрим шифры, описываемые моделью $\Sigma_A = \set{X, K, Y, E, D}$, в
+которой $X = Y = \bigcup_{l = 1}^L A^l$, причём для любых $x \in X, k \in K$
+длина $y = E_k(x)$ совпадает с длиной $x$.
+
+В данном случае искажения в канале связи --- это искажения типа <<замены>>:
+слово $(a_1, \dots, a_\lambda)$ искажается, то есть каждая буква $a_i$ может
+замениться на другую букву $a'_i$, где $a_i, a'_i \in A, i \in \overline{1,
+\lambda}$.
+
+Единственной мерой значительности последствий искажений типа <<замена знаков>>
+является метрика на множестве сообщений $X = Y$.
+
+Простейшей является \emph{метрика Хэмминга} $\mu$, определяемая формулой:
+\begin{equation*}
+  \mu(x, y) = \sum_{i = 1}^\lambda \delta(x_i, y_i),
+\end{equation*}
+где $x = (x_1, \dots, x_\lambda),\, y = (y_1, \dots, y_\lambda) \in X,\,
+\delta(x_i, y_i) = \begin{cases}
+  1, &x_i \neq y_i \\
+  0, &x_i = y_i \\
+\end{cases}$
+
+Говорят, что подстановочный шифр $\Sigma_\text{п} = (X, E)$ \emph{не
+распространяет искажений типа замены знаков}, если для любых $x, y \in
+A^\lambda, 1 \leq \lambda \leq L$, и любой подстановки $e \in E, e : X \to X$,
+выполняется неравенство $$\mu(e^{-1} x, e^{-1} y) \leq \mu(x, y).$$
+
+Данное неравенство означает, что число искажений в расшифрованном тексте не
+превышает числа искажений в передаваемой криптограмме.
+
+% TODO: Перенумеровать выражение и утверждение
+% Утверждение 4
+\begin{statement}
+  Шифр $\Sigma_\text{в}$ не распространяет искажений типа замены знаков тогда и
+  только тогда, когда для любого $\lambda \in \overline{1, L}$, любых $x, y \in
+  A^\lambda$ и любого $e \in E$ выполняется равенство
+  \begin{equation*}
+    \mu(e^{-1} x, e^{-1} y) \mu(x, y)    \quad (9)
+  \end{equation*}
+\end{statement}
+
+Подстановки $e \in E$, удовлетворяющие условию (9), называются
+\emph{изометриями} на $X$.
+
+Утверждение 4 показывает, что для шифров, не распространяющих искажений типа
+замены знаков множество $E$ состоит изометрией.
+
+% TODO: Перенумеровать
+Введём два преобразования множества $X$:
+\begin{align*}
+  &\prod_{f_1, \dots, f_\lambda} (a_1, \dots, a_\lambda) = (a_{j_1}, \dots a_{j_\lambda}), \quad (10) \\
+  &R(a_1, \dots, a_\lambda) = (R_1(a_1), \dots, R_\lambda(a_\lambda)), \quad (11)
+\end{align*}
+где $(j_1, \dots, j_\lambda)$ --- перестановка чисел $1, 2, \dots, \lambda$;
+$R_i \in S(A)$ --- некоторые фиксированные подстановки множества $A, a_i \in
+A,\, \lambda \in \overline{1, l}, i \in \overline{1, \lambda}$.
+
+% Теорема 3
+\begin{theorem}[Марков А. А.]
+  Биекция $e \in E$ является изометрией на $X$ тогда и только тогда, когда
+  $e = R \cdot \prod_{f_1, \dots, f_\lambda}$ для подходящих преобразований,
+  определённых формулами (10)--(11).
+\end{theorem}
+
+Согласно теореме Маркова А. А. в классе эндоморфных шифров, не изменяющих длины
+сообщений, не распространяют искажений типа замены знаков, например, шифры
+перестановки, поточные шифры однозначной замены, а также из композиции типа шифр
+замены --- шифр перестановки.
+
+
+\subsubsection{Шифры, не распространяющие искажений типа <<пропуск-вставка>>
+знаков}
+
+Рассмотрим также эндоморфные шифры. Рассмотрим искажения типа <<пропуск
+знаков>>, при этом исследование вопроса об искажениях типа <<вставка знаков>>
+производится аналогично.
+
+Искажение типа <<пропуск>> приводит к тому, что искажённый текст принадлежит
+$Y = X$ (при естественном условии, что искажение не приводит к полному
+<<уничтожению>> слова).
+
+Пусть $\varepsilon$ --- бинарное отношение на множестве $X$, определённое
+следующим образом. 
+
+Пусть $a, a' \in X$, тогда $a \varepsilon a' \iff \exists j \in \overline{1,
+\lambda}: a = (a_1, \dots, a_\lambda), a\ = (a_1 , \dots, a_{j - 1}, a_{j + 1},
+\dots, a_\lambda)$.
+
+Таким образом, слово $a$ находится в отношении $\varepsilon$ со словом $a'$,
+если $a'$ получается из $a$ вычёркиванием (пропаданием) одного какого-то знака
+(то есть одним искажением).
+
+Через $\varepsilon^k$ обозначим \emph{<<степень>>} отношения $\varepsilon$:
+\begin{equation*}
+  a \varepsilon^k a' \iff \exists a_1, \dots a_{k - 1} \in X, a \varepsilon a_1,
+  \dots, a_{k - 1} \varepsilon a'.
+\end{equation*}
+
+Таким образом, запись $a \varepsilon^k a'$ означает, что слово $a'$ получается
+из $a$ вычёркиванием $k$ букв, то есть $k$ искажениями.
+
+Говорят, что шифр $\Sigma_\text{п} = (X, E)$ \emph{не распространяет искажений}
+типа <<пропуск знаков>>, если для любых $x, y \in X$, любого $k$, меньшего длины
+слова $x$, а также любого $e \in E$ из условия $x \varepsilon^k y$ следует,
+что $(e^{-1} x) \varepsilon^k (e^{-1} y)$.
+
+Обозначим через $\pi_L: X \to X$, определённое для любого $a \in (a_1, \dots,
+a_\lambda) \in X$ формулой $$\pi_L(a_1, \dots, a_\lambda) = (\pi(a_1), \dots,
+\pi(a_\lambda)),$$ где $\pi$ --- некоторая подстановка множества $A$, а $f :
+X \to X$, меняющее порядок следования букв любого слова на противоположный:
+$f(a_1, \dots, a_\lambda) = (a_\lambda, \dots, a_1)$.
+
+% Теорема 4
+\begin{theorem}
+  Если $\Sigma_\text{п} = (X, E)$ --- шифр, не распространяющий искажений
+  типа <<пропуск знаков>>, то для любого $e \in E$, либо $e = \pi_L$, либо
+  $e = \pi_L \cdot f$ (при подходящем $\pi \in S(A)$).
+\end{theorem}
+
+Примерами шифров, не распространяющих искажений типа <<пропуск-вставка знаков>>
+являются, например, шифры простой замены или шифры простой замены, усложнённые
+перестановкой, осуществляющей изменение порядка следования знаков любого слова
+на противоположный.
+
+
+\section{Поточные шифры}
+
+\subsection{Принципы построения}
+
+\emph{Шифр} называется \emph{поточным}, если он осуществляет шифрование под
+одним блоком (открытого текста) с ключом, длина которого равна длине открытого
+текста.
+
+Наибольшее распространение получили шифры, осуществляющие побуквенное
+зашифрование с помощью некоторого множества подстановочных преобразований
+алфавита открытых сообщений, другими словами, эндоморфные поточные
+многоалфавитные шифры замены с множествами шифрвеличин и шифрообозначений,
+совпадающих с алфавитом открытых сообщений. Рассмотрим такие шифры.
+
+Пусть $A$ --- алфавит открытых сообщений, совпадающих с множествами шифрвеличин
+и шифробозначений, $\set{\varphi_\alpha : A \to A}$ --- совокупность из $r$
+биекций множества $A$, $x = a_1 a_2 \dots a_l$ --- произвольный открытый текст,
+$k \in K$ --- выбранный ключ шифрования. Тогда правило шифрования $E_k(x)$
+определяется формулой $E_k(x) = y$, где $y = b_1 b_2 \dots b_l$ и
+\begin{equation*} % TODO: Перенумеровать
+  b_j = \varphi_{\alpha_j^{(k)}} (a_j),\, j \in \overline{1, l}, \quad (12)
+\end{equation*}