Отредактирована пятая лекция по крипте

1 files changed, 120 insertions, 122 deletions

diff --git a/cryptography/lectures/lecture5.tex b/cryptography/lectures/lecture5.tex
index 8e42a0c..8e8dbe9 100644
--- a/cryptography/lectures/lecture5.tex
+++ b/cryptography/lectures/lecture5.tex
@@ -7,60 +7,54 @@
 меняются друг с другом. Ключи шифра является перестановка номеров букв открытого
 текста.
 
-Множество всех подстановок на множестве \(M\) называют любое биективное
-отображение множества \(M\) в себя. Множество всех подстановок на множестве
-\(M\) обозначают через \(S(M)\). Множество \(S(M)\) относительно операции
-суперпозиции отображения образует группу.
-
-Если \(M\) --- конечное множество мощности \(n\), то говорят, что \(S(M)\) ---
-симметрическая группа подстановок степени \(n\).
-
-Группа \(S(M)\) является коммутативной только в случае \(n \leq 2\).
-
-Перенумеровав элементы множества \(M\) некоторым фиксированным образом \(M = \{
-x_1, x_2, \dots, x_n \}\) и отождествив элементы \(x_i\) с их номерами \(i\),
-вместо группы \(S(M)\) можно рассматривать группу \(S(\Omega)\), где \(\Omega =
-\{ 1, 2, \dots, n \}\). Обычно группа \(S(\Omega)\) обозначают через \(S_n\).
-
-Любая подгруппа \(G\) группы \(S_n\) называется \emph{группой подстановок}
-степени \(n\).
-
-Пусть \(X = Y = A^L\) и пусть \(K \subset S_L\). Для любого ключа \(k\),
-открытого текста \(x = (x_1, \dots, x_L)\) и шифрованного текста \(y = (y_1,
-\dots, y_L)\) правила зашифрования и расшифрования \emph{шифра перестановки}
-определяется формулами $$ E_k(x) = (x_{k(1)}, \dots, x_{k(L)}), \, D_k(y)
-= (y_{k^{-1}(1)}, \dots, y_{k^{-1}(L)}) $$ где \(k^{-1}\) --- подстановка,
-обратная к \(k\).
+Множество всех подстановок на множестве $M$ называют любое биективное
+отображение множества $M$ в себя. Множество всех подстановок на множестве $M$
+обозначают через $S(M)$. Множество $S(M)$ относительно операции суперпозиции
+отображения образует группу. Если $M$ --- конечное множество мощности $n$, то
+говорят, что $S(M)$ --- симметрическая группа подстановок степени $n$. Группа
+$S(M)$ является коммутативной только в случае $n \leq 2$.
+
+Перенумеровав элементы множества $M$ некоторым фиксированным образом $M = \{
+x_1, x_2, \dots, x_n \}$ и отождествив элементы $x_i$ с их номерами $i$, вместо
+группы $S(M)$ можно рассматривать группу $S(\Omega)$, где $\Omega = \{ 1, 2,
+\dots, n \}$. Обычно группа $S(\Omega)$ обозначают через $S_n$.
+
+Любая подгруппа $G$ группы $S_n$ называется \emph{группой подстановок} степени
+$n$. Пусть $X = Y = A^L$ и пусть $K \subset S_L$. Для любого ключа $k$,
+открытого текста $x = (x_1, \dots, x_L)$ и шифрованного текста $y = (y_1,
+\dots, y_L)$ правила зашифрования и расшифрования \emph{шифра перестановки}
+определяется формулами $$E_k(x) = (x_{k(1)}, \dots, x_{k(L)}), \, D_k(y) =
+(y_{k^{-1}(1)}, \dots, y_{k^{-1}(L)})$$ где $k^{-1}$ --- подстановка, обратная
+к $k$.
 
 \subsubsection{(2) Маршрутные перестановки}
 
 Широкое применение получили так называемые \emph{маршрутные перестановки},
-основанные на некоторой геометрической фигуре.
-
-Отрезок открытого текста записывается в такую фигуру на некоторой траектории.
-
-Шифрованным текстом является последовательность, полученная при выписывании по
-другой траектории.
-
-\textbf{Примеры}
-
-\begin{enumerate}
-\item \emph{В учении нельзя останавливаться}, 28 букв
-
-в у ч е н и
-и н е л ь з
-я о с т а н
-а в л и в а
-т ь с я - -
-\begin{itemize}
-\item - - - - -
-\end{itemize}
-
-вуиянчееоатвслниьтльсиазнвяа
-
-\item Вертикальная перестановка.
-В этой системе также используется прямоугольная таблица, в которую сообщение
-записывается построкам слева направо.
+основанные на некоторой геометрической фигуре. Отрезок открытого текста
+записывается в такую фигуру на некоторой траектории. Шифрованным текстом
+является последовательность, полученная при выписывании по другой траектории.
+
+\begin{example}
+\emph{В учении нельзя останавливаться}, 28 букв
+
+\begin{table}[H]
+  \centering
+  \begin{tabular}{cccccc}
+    в & у & ч & е & н & и \\
+    и & н & е & л & ь & з \\
+    я & о & с & т & а & н \\
+    а & в & л & и & в & а \\
+    т & ь & с & я & - & - \\
+    - & - & - & - & - & - \\
+  \end{tabular}
+\end{table}
+
+\textbf{Шифротекст}: вуиянчееоатвслниьтльсиазнвяа
+\end{example}
+
+\begin{example}
+Вертикальная перестановка. В этой системе также используется прямоугольная
+таблица, в которую сообщение записывается по строкам слева направо.
 
 Выписывается сообщение по вертикали (сверху вниз), при этом столбцы
 выбираются в порядке, определяемом числовым ключом (например, в
@@ -68,24 +62,25 @@ x_1, x_2, \dots, x_n \}\) и отождествив элементы \(x_i\) с
 
 \emph{Без примера ничему не выучишься}, 27 букв
 
-\begin{center}
-\begin{tabular}{llllll}
-б & е & з & п & р & и\\
-м & е & р & а & н & и\\
-ч & е & м & у & н & е\\
-в & ы & у & ч & и & ш\\
-ь & с & я & - & - & -\\
-\hline
-ж & ё & л & у & д & ь\\
-\end{tabular}
-\end{center}
-
-рнниеееысбмчвьзрмуяпаучииеш
-\end{enumerate}
+\begin{table}[H]
+  \centering
+  \begin{tabular}{cccccc}
+  б & е & з & п & р & и \\
+  м & е & р & а & н & и \\
+  ч & е & м & у & н & е \\
+  в & ы & у & ч & и & ш \\
+  ь & с & я & - & - & - \\
+  \hline
+  ж & ё & л & у & д & ь \\
+  \end{tabular}
+\end{table}
+
+\textbf{Шифротекст}: рнниеееысбмчвьзрмуяпаучииеш
+\end{example}
 
 Более сложные маршрутные перестановки могут использовать другие геометрические
-фигуры и более "хитрые" маршруты, например, при обходе шахматной доски "ходом
-коня", пути в некотором лабиринте и тому подобное.
+фигуры и более <<хитрые>> маршруты, например, при обходе шахматной доски <<ходом
+коня>>, пути в некотором лабиринте и тому подобное.
 
 \subsubsection{(3) Элементы криптоанализа шифров перестановки}
 
@@ -109,53 +104,61 @@ x_1, x_2, \dots, x_n \}\) и отождествив элементы \(x_i\) с
 стоящих до и после данной буквы И, соединяются в пары, то есть получаются два
 столбца букв, записанные рядом:
 
-\begin{center}
-\begin{tabular}{ll}
-I & II\\
-\ldots{} & \ldots{}\\
-Н & И\\
-\ldots{} & \ldots{}\\
-\end{tabular}
-\end{center}
+\begin{table}[H]
+  \centering
+  \begin{tabular}{cc}
+  I      & II     \\
+  \ldots & \ldots \\
+  Н      & И      \\
+  \ldots & \ldots \\
+  \end{tabular}
+\end{table}
 
 Длина столбцов неизвестна, но используя положение конкретных букв, можно
 получить на них некоторые ограничения:
 \begin{enumerate}
-\item Столбцы должны иметь одинаковые длины или первый столбец может быть
-длиннее второго на одну букву, и тогда эта буква --- последняя буква
-сообщения.
-\begin{center}
-\begin{tabular}{ll}
-\ldots{} & \ldots{}\\
-Р & А\\
-\ldots{} & \ldots{}\\
-У & Ч\\
-Я & -\\
-\end{tabular}
-\end{center}
-\item Если приписываемые друг к другу буквы разделены, например, только четырьмя буквами,
-то можно составить в соседних столбцах не более пяти пар, и длина каждого столбца
-не превышает пяти:
-\begin{center}
-\begin{tabular}{llllll}
-б & е & \emph{з} & п & р & и\\
-м & е & \emph{р} & а & н & и\\
-ч & \emph{е} & \emph{м} & у & н & е\\
-в & \emph{ы} & у & ч & и & ш\\
-ь & \emph{с} & я & - & - & -\\
-\hline
-ж & ё & л & у & д & ь\\
-\end{tabular}
-\end{center}
-\item Ограничением можно послужить появление запретной биграммы
-\begin{center}
-\begin{tabular}{ll}
-\ldots{} & \ldots{}\\
-Н & И\\
-\ldots{} & \ldots{}\\
-И & Ь\\
-\end{tabular}
-\end{center}
+  \item
+    Столбцы должны иметь одинаковые длины или первый столбец может быть
+    длиннее второго на одну букву, и тогда эта буква --- последняя буква
+    сообщения.
+    \begin{table}[H]
+      \centering
+      \begin{tabular}{cc}
+        \ldots & \ldots \\
+        Р      & А      \\
+        \ldots & \ldots \\
+        У      & Ч      \\
+        Я      & -      \\
+      \end{tabular}
+    \end{table}
+
+  \item
+    Если приписываемые друг к другу буквы разделены, например, только четырьмя
+    буквами, то можно составить в соседних столбцах не более пяти пар, и длина
+    каждого столбца не превышает пяти:
+    \begin{table}[H]
+      \centering
+      \begin{tabular}{llllll}
+        б & е      & \bf{з} & п & р & и \\
+        м & е      & \bf{р} & а & н & и \\
+        ч & \bf{е} & \bf{м} & у & н & е \\
+        в & \bf{ы} & у      & ч & и & ш \\
+        ь & \bf{с} & я      & - & - & - \\
+        \hline
+        ж & ё      & л      & у & д & ь \\
+      \end{tabular}
+    \end{table}
+  \item
+    Ограничением можно послужить появление запретной биграммы
+    \begin{table}[H]
+      \centering
+      \begin{tabular}{cc}
+        \ldots & \ldots \\
+        Н      & И      \\
+        \ldots & \ldots \\
+        И      & Ь      \\
+      \end{tabular}
+    \end{table}
 \end{enumerate}
 
 Для выбранного сочетания НИ получается по одной паре столбцов для каждого
@@ -163,12 +166,9 @@ I & II\\
 ту пару, которая содержит наиболее частые биграммы.
 
 При автоматизации этого процесса можно приписать каждой биграмме вес, равный
-частоте её появления в открытом тексте.
-
-Тогда отбирается та пара столбцов, которая имеет наибольший вес.
-
-Появление одной биграммы с низкой частотой может указать на то, что длину
-столбца надо ограничить.
+частоте её появления в открытом тексте. Тогда отбирается та пара столбцов,
+которая имеет наибольший вес. Появление одной биграммы с низкой частотой может
+указать на то, что длину столбца надо ограничить.
 
 Выбрав пару столбцов аналогичным образом подбирается к ним третий (справа или
 слева) и так далее. Описанная процедура значительно упрощается при использовании
@@ -178,10 +178,8 @@ I & II\\
 (б) Рассмотрим метод, применимый к любым шифрам перестановки.
 
 Допустим, что к двум или более сообщениям (или отрезкам сообщений) одинаковой
-длины применяется один и тот же шифр перестановки.
-
-Тогда очевидно, что буквы, которые находились на одинаковых местах в открытых
-текстах, окажутся на одинаковых местах и в криптограммах.
-
-Выпишем криптограммы одну под другой так, что первые буквы всех сообщений
-оказываются в первом столбце, вторых --- во втором и так далее.
+длины применяется один и тот же шифр перестановки. Тогда очевидно, что буквы,
+которые находились на одинаковых местах в открытых текстах, окажутся на
+одинаковых местах и в криптограммах. Выпишем криптограммы одну под другой так,
+что первые буквы всех сообщений оказываются в первом столбце, вторых --- во
+втором и так далее.