diff options
| -rw-r--r-- | cryptography/cryptography.pdf | bin | 256867 -> 250756 bytes | |||
| -rw-r--r-- | cryptography/lectures/lecture5.tex | 242 |
2 files changed, 120 insertions, 122 deletions
diff --git a/cryptography/cryptography.pdf b/cryptography/cryptography.pdf Binary files differindex 34180d4..69fcb28 100644 --- a/cryptography/cryptography.pdf +++ b/cryptography/cryptography.pdf 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\\ (б) Рассмотрим метод, применимый к любым шифрам перестановки. Допустим, что к двум или более сообщениям (или отрезкам сообщений) одинаковой -длины применяется один и тот же шифр перестановки. - -Тогда очевидно, что буквы, которые находились на одинаковых местах в открытых -текстах, окажутся на одинаковых местах и в криптограммах. - -Выпишем криптограммы одну под другой так, что первые буквы всех сообщений -оказываются в первом столбце, вторых --- во втором и так далее. +длины применяется один и тот же шифр перестановки. Тогда очевидно, что буквы, +которые находились на одинаковых местах в открытых текстах, окажутся на +одинаковых местах и в криптограммах. Выпишем криптограммы одну под другой так, +что первые буквы всех сообщений оказываются в первом столбце, вторых --- во +втором и так далее. |