diff options
Diffstat (limited to 'cryptography/cryptography.tex')
| -rw-r--r-- | cryptography/cryptography.tex | 1104 |
1 files changed, 8 insertions, 1096 deletions
diff --git a/cryptography/cryptography.tex b/cryptography/cryptography.tex index 6c51c60..c1a8b47 100644 --- a/cryptography/cryptography.tex +++ b/cryptography/cryptography.tex @@ -1,5 +1,4 @@ \documentclass{../Lecture} - \usepackage{../preamble} \title{Криптографические методы защиты информации} @@ -15,1100 +14,13 @@ \subsection{\ldots{}} -\subsection{Алгебраические структуры} - -Множество R с двумя бинарными ассоциативными операциями сложения "+" и умножения -"$\cdot$" называется \textbf{кольцом}, если выполнены следующие условия: -\begin{enumerate} - \item - множество R с бинарной операцией сложения является абелевой группой - (нейтральный элемент кольца называют \emph{нулём} кольца и обозначают через - 0) - \item - операция "*" удовлетворяет условию дистрибутивности относительно операции - "+" то есть \((a + b) * c = a * c + b * c\) и \(a * (b + c) = a * b + a * - c\) -\end{enumerate} - -Если операция умножения коммутативна, то кольцо называется коммутативным. Пример ---- множество \(Z_n\), образующее полную систему вычетов целых чисел по модулю -\(n\) с операциями сложения и умножения по модулю \(n\), причём это кольцо -является коммутативным. - -Кольцо вычетов \(Z_4\): - -\_+4\_| 0 1 2 3 -----+-------- -0 | 0 1 2 3 -1 | 1 2 3 0 -2 | 2 3 0 1 -3 | 3 0 1 2 - -\_*4\_| 0 1 2 3 -----+-------- -0 | 0 1 2 3 -1 | 1 2 3 0 -2 | 2 3 0 1 -3 | 3 0 1 2 - -x | 0 1 2 3 ----+-------- --x | 0 3 2 1 - - -Если в кольце существует элемент 1 такой, что \(g \cdot 1 = 1 \cdot g = -g\) (нейтральный элемент относительно умножения), такое кольцо называется -\emph{кольцом с единицей}. - -\emph{Полем} называется коммутативное кольцо с единицей, отличной от нуля, в -котором любой ненулевой элемент обратим. - -Кольцо вычетов целых чисел по модулю \(Z_n\) является полем в том и только том -случае, когда \(n\) --- простое число. - -Поля вычетов являются конечными полями. Конечные поля называются \emph{полями -Галуа}. - - -\subsection{Открытые сообщения} -\label{sec:orga0e3510} - -\subsubsection{Характеристики} -\label{sec:org72d8f1b} - -\begin{itemize} - \item - Открытый и шифрованные тексты представляют собой последовательности символов, - взятых из конечного набора, называемого \emph{алфавитом}. - \item Элемент алфавита называется \emph{буквой}. - \item Число символов алфавита называется \emph{мощностью} алфавита. -\end{itemize} - -Примеры --- Алфавиты: -\begin{enumerate} - \item \(A_1\) --- алфавит прописных букв, \(|A_1| = 33\) : А, Б, В, \dots{}, Э, Ю, Я - \item - \(A_2\) --- прописные и строчные буквы, целые числа, пробел и знаки - препинания (мощность алфавита примерно равна 84): А, Б, В, \dots{}, Э, Ю, Я, - а, б, в, - \dots{}, э, ю, я, \dots{}, 0, 1, \dots{}, 9, пробел, запятая, точк, :, ;, ", ?, !. - \item \(A_3\) --- элементы множества \(\{0, 1\}\). -\end{enumerate} - -В основном используются производные от \(A_3\) алфавиты, совпадающие с -множеством \(V_n\) двоичных n-мерных векторов. - -Мощность алфавитов равна \(2^n\), и, как правило, \(5 \leq n \leq 8\). - -Часто в процессе шифрования наз символами алфавита производятся вычислительные -действия, поэтому удобно их представлять в виде чисел или двоичных наборов. - -Рассмотрим в качестве алфавита \(Z_m = \{ 0, 1, \dots, m - 1 \}\) - -Всякий текст, записанный в некотором алфавите имеет \emph{длину}, равную числу -букв в соответствующей записи. - -Последовательность \(k\) соседних букв текста, \(k \geq 2\), называется \$k\$-граммой (при -\(k = 2\) --- биграммой и т.д.). - -Помимо алфавита \(Z_m\) могут рассматриваться производные от него алфавиты \(Z_m(t)\) -представляющие собой набор всевозможных $t$-грамм исходного алфавита. - -\subsubsection{Детерминированные модели открытых текстов} - -Каждый источник открытых сообщений порождает тексты в соответствии с правилами -грамматики некоторого языка, что находит отражение и в статистических -характеристиках сообщений. - -Всякий язык и всякий источник открытых сообщений можно характеризовать -разбиением множества всех $k$-грамм, \(k = 2, 3, \dots\), на \emph{допустимые} -(встречающиеся в каких-либо текстах) и \emph{запрещённые} (не встречающиеся -ни в каких текстах), что определяет \emph{детерминированную модель} источника -открытых сообщений. - -В такой модели открытый текст рассматривается как последовательность букв -некоторого алфавита, не содержащая запретных $k$-грамм. - -\subsubsection{Вероятностные модели открытых текстов} - -В вероятностных моделях источник открытых сообщений рассматривается как источник -случайных последовательностей. - -Пусть источник генерирует в алфавите \(Z_m\) текст конечной или бесконечной -длины, в результате чего получается последовательность случайных переменных -\(x_1, x_2, \dots, x_{n - 1}, \dots\), принимающих значения в \(Z_m\). - -\emph{Вероятность случайного сообщения} \((a_0, a_1, \dots, a_{n - 1})\) -определяется как вероятность такой последовательности событий: $$P(a_0, a_1, -\dots, a_{n - 1}) = P(x_0 = a_0, x_1 = a_1, \dots, x_{n - 1} = a_{n - 1})$$ - -Множество случайных сообщений образует вероятностное пространство, если -выполнены условия: -\begin{enumerate} - \item - \(P(a_0, a_1, \dots, a_{n - 1}) \geq 0\) для любого случайного сообщения - \((a_0, a_1, \dots, a_{n - 1})\). - \item - \(\displaystyle\sum_{(a_0, a_1, \dots, a_{n - 1})} P(a_0, a_1, \dots, a_{n - - 1}) = 1\) - \item - для любого случайного сообщения \((a_0, a_1, \dots, a_{n - 1})\), и любого - \(s > n\) \(P(a_0, a_1, \dots, a_{n - 1}) = \sum_(a_n, \dots, a_{s - 1}) - P(a_0, a_1, \dots, a_{s - 1})\), то есть вероятность всякого случайного - сообщения \(n\) есть сумма вероятностей всех продолжения этого сообщения до - длины \(s\). -\end{enumerate} - -Текст, порождаемый таким источником, является вероятностным аналогом языка. Он -обладает одинаковыми с языком частотными характеристиками $k$-грамм. Задавая -определённое вероятностное распределение на множестве открытых текстов, задаётся -соответствующая модель источника открытых сообщений. - -Например, в модели стационарного источника независимых символов алфавита -(\emph{позначная модель открытых текстов}) предполагается, что вероятности -сообщений полностью определяются вероятностями использования отдельных букв -алфавита в случайном тексте - -$$P(a_0, a_1, \dots, a_{n - 1}) = \prod_{i = 0}^{n - 1} P(x_i = a_i)$$ - -где для всех \(i \in {0, 1, \dots, n - 1}\) и любого \(a \in Z_m P(x_i = a) > -0\); \(\sum_{a \in Z_m} P(x_i = a) = 1\). - -Открытый текст такого источника является реализацией последовательности -независимых испытаний в полиномиальной вероятностной схеме с числом исходов, -равным \(m\). - -Множество исходов взаимнооднозначно соответствует множеству всех символов -алфавита. - -Частота букв в разных языках: -\begin{itemize} - \item \emph{Русский язык}: О (11\%), И (8.9\%), Е, А, Н, Т - \item \emph{Английский язык}: E (12.86\%), T (9.72\%), A, I, N, R -\end{itemize} - -Эта модель эффективно используется для дешифрования текстов, защищаемых шифром -простой замены. - -Самые частые биграммы: -\begin{itemize} - \item \emph{Русский язык}: СТ (1.74\%), НО (1.29\%), ЕН, ТО, НА -\end{itemize} - -Наиболее частые триграммы: -\begin{itemize} - \item \emph{Русский язык}: СТО, ЕНО, НОВ, ТОВ, ОВО -\end{itemize} - -Информация, которую реально несёт каждая буква сообщения меньше, чем её -максимальная информация при случайном и равновероятном появлении. - -В связи с ним возник термин "избыточность языка". - -Поэтому часть букв открытого текста можно опустить без потери содержания -потерянная информация будет восстановлена другими буквам сообщения вследствие -закономерностей языка. - -\subsection{Критерий распознавания открытого текста} - -(а) Открытый текст представляет собой реализацию независимых испытаний случайной -величины, значениями которой являются буквы алфавита \(A = {a_1, a_2, \dots, -a_n}\), появляющиеся в соответствии с распределением вероятностей \(P(A) = -(p(a_1), p(a_2), \dots, p(a_n))\). - -Требуется определить, является ли случайная последовательность \(c_1 c_2 \dots -c_l\) букв алфавита \(A\) открытым текстом или нет. - -Пусть \(H_0\) --- гипотеза, состоящая в том, что данная последовательность --- -открытый текст, \(H_1\) --- альтернативная гипотеза. - -В простейшем случае при гипотезе \(H_1\) последовательность \(c_1 c_2 -\dots c_l\) можно рассматривать как случайную и равносильную, то есть при -расшифровании криптограммы с помощью ложного ключа получается "бессмысленная" -последовательность знаков. - -В более общем случае можно считать, что при гипотезе \(H_1\) последовательность -\(c_1 c_2 \dots c_l\) представляет собой реализацию независимых испытаний -некоторой случайной величины, значениями которой являются буквы алфавита -\(A = \{ a_1, \dots, a_n \}\), появляющиеся в соответствии с распределением -вероятностей \(Q(A) = (q(a_1), \dots, q(a_n))\). - -При таких договорённостях можно применить, например, \emph{наиболее мощный -критерий} различения двух простых гипотез, который даёт \emph{лемма -Неймана-Пирсона}. - -В силу своего вероятностного характера такой критерий может совершать ошибки -двух родов: -\begin{enumerate} - \item - критерий может принять открытый текст за случайный набор знаков. Такая - ошибка называется \emph{ошибкой первого рода}, её вероятность равна \(\alpha - = p(H_1/H_0)\). - \item - Критерий может принять случайный набор знаков за открытый текст. Такая - ошибка называется \emph{ошибкой второго рода} и её вероятность \(\beta = - p(H_0/H_1)\). -\end{enumerate} - -Эти ошибки определяют качество работы критерия. В криптографических -исследованиях естественно минимизировать вероятность ошибки первого рода, чтобы -не "пропустить" открытый текст. - -Лемма Неймана-Пирсона при заданной вероятности первого рода минимизирует также -вероятность ошибки второго рода. - -(б) Критерии на открытый текст, использующие запретные сочетания знаков, -например, k-граммы подряд идущих букв, называются \emph{критериями запретных -k-грамм}. - -Отбирается некоторое число \(s\) редких k-грамм, которые объявляются запретными. - -Теперь, просматривая последовательно k-грамму за k-граммой анализируемой -последовательности \(c_1 c_2 \dots c_l\), она объявляется случайной, как только -в ней встретится одна из запретных k-грамм, и открытым текстом в противном -случае. - -Такие критерии также могут совершить ошибки в принятии решения. В простейших -случаях их можно рассчитать. Несмотря на свою простоту, критерии запретных -k-грамм являются весьма эффективными. - -\subsection{(1.4) Математические модели шифров} - -\subsubsection{(1) Алгебраическая модель шифра} - -Введём алгебраическую модель шифра (шифрсистемы), предложенную К. Шенноном. - -Пусть \(X, K, Y\) --- конечные множества возможных открытых текстов, ключей и -криптограмм соответственно; \(E_k : X \to Y\) --- правило зашифрования на ключе -\(k \in K\). - -Множество \(\{ E_k : k \in K \}\) обозначим через \(E\), а множество \(\{ E_k(x) -: x \in X \}\) --- через \(E_k(X)\). - -Пусть \(D_k : E_k(X) \to X\) --- правило расшифрования на ключе \(k \in K\), и -\(D\) --- множество \(\{ D_k : k \in K \}\). - -Если ключ \(k \in K\) представляется в виде \(k = (k_o, k_p)\), где \(k_o\) ---- ключ зашифрования, а \(k_p\) --- ключ расшифрования (причём \(k_o \neq -k_p\)), то \(E_k\) понимается как функция \(E_{k_p}\), а \(D_k\) --- как функция -\(D_{k_p}\). - -\emph{Шифром (шифрсистемой)} называется совокупность $$\sum_A = (X, K, Y, E, -D)$$ введённых множеств, для которых выполняются следующие свойства: -\begin{enumerate} - \item Для любых \(x \in X\) и \(k \in K\) выполняется равенство \(D_k(E_k(x)) = x\); - \item \(Y = \cup_{k \in K} E_k(X)\). -\end{enumerate} - -Неформально, шифр --- это совокупность множеств возможных открытых текстов (то, -что шифруется), возможных ключей (то, с помощью чего шифруется), возможных -шифртекстов (то, во что шифруется), правил зашифрования и правил расшифрования. - -Условие (1) отвечает требованию однозначности расшифрования. Из условия (1) -следует свойство инъективности функции \(E_k\): если \(x_1, x_2 \in X\), причём -\(x_1 \neq x_2\), то при любых \(k \in K\) выполняется неравенство \(E_k(x_1) -\neq E_k(x_2)\). - -Условие (2) означает, что любой элемент \(y \in Y\) может быть представлен в -виде \(E_k(x)\) для подходящих элементов \(x \in X\) и \(k \in K\). - -В общем случае утверждение "для любых \(k \in K\) и \(y \in E_k(X)\) выполняется -равенство \(E_k(D_k(y)) = y\)" является неверным. - -Реальный шифр отождествляется с его математической моделью \(\sum_A\), которая -называется \emph{алгебраической моделью шифра}. - -\subsubsection{(2) Вероятностная модель шифра} - -Следуя К. Шеннону, введём априорные распределения вероятностей \(P(X)\) и -\(P(K)\) на множестве \(X\) и \(K\) соответственно. - -Для любого \(x \in X\) определена вероятность \(p_X(x) \in P(X)\) и для любого -\(k \in K\) --- вероятность \(p_K(k) \in P(K)\), причём выполняются равенства -$$\sum_{x \in X} p_X(x) = 1 \text{ и } \sum_{k \in K} p_K(k) = 1$$ - -В тех случаях, когда требуется знание распределений \(P(X)\) и \(P(K)\), -используется вероятностная модель \(\Sigma_B\), состоящая из пяти множеств, -связанных условиями (1) и (2) определения шифра и двух вероятностных -распределений: - -$$\Sigma_B = (X, K, Y, E, D, P(X), P(K))$$ - -Вероятностные характеристики шифров используются только в криптоанализе. - -В большинстве случаев множества \(X\) и \(Y\) представляют собой объединения -декартовых степеней некоторых множеств \(A\) и \(B\) соответственно, так что для -некоторых натуральных \(L\) и \(L_1\): $$X = \cup_{L = 1}^L A^l \text{ и } Y = -\cup_{L = 1}^{L_1} B^l$$ - -Множества \(A\) и \(B\) называются соответственно \emph{алфавитом открытого -текста} и \emph{алфавитом шифрованного текста}. - -\subsubsection{(3) Основные требования к шифрам} - -Для современны криптографических систем защиты информации сформулированы -следующие общепринятые требования: -\begin{enumerate} - \item зашифрованное сообщение должно поддаваться чтению только при наличии ключа; - \item - число операция, необходимых для определения использованного ключа шифрования - по фрагменту шифрованного сообщения и соответствующего ему открытого текста, - должно быть не меньше общего числа возможных ключей; - \item - число операция, необходимых для расшифровывания информации путём перебора - всевозможных ключей должно иметь строгую нижнюю оценку и выходить за пределы - возможностей современных компьютеров (с учётом возможности использования - сетевых вычислений); - \item знание алгоритма шифрования не должно влиять на надёжность защиты; - \item - незначительное изменение ключа (сообщения?) должно приводить к существенному - изменению вида зашифрованного сообщения даже при использовании одного и того - же ключа; - \item структурные элементы алгоритма шифрования должны быть неизменными; - \item дополнительные биты \dots{} -\end{enumerate} - -\emph{\emph{ДОПИСАТЬ!!!}} - -\subsection{(1.5) Шифры перестановки} - -\subsubsection{(1) \emph{Определение}} - -Шифр перестановки --- шифр, при котором буквы открытого текста при шифровании -меняются друг с другом. Ключи шифра является перестановка номеров букв открытого -текста. - -Множество всех подстановок на множестве \(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 Вертикальная перестановка. -В этой системе также используется прямоугольная таблица, в которую сообщение -записывается построкам слева направо. - -Выписывается сообщение по вертикали (сверху вниз), при этом столбцы -выбираются в порядке, определяемом числовым ключом (например, в -алфавитном порядке букв ключа). - -\emph{Без примера ничему не выучишься}, 27 букв - -\begin{center} -\begin{tabular}{llllll} -б & е & з & п & р & и\\ -м & е & р & а & н & и\\ -ч & е & м & у & н & е\\ -в & ы & у & ч & и & ш\\ -ь & с & я & - & - & -\\ -\hline -ж & ё & л & у & д & ь\\ -\end{tabular} -\end{center} - -рнниеееысбмчвьзрмуяпаучииеш -\end{enumerate} - -Более сложные маршрутные перестановки могут использовать другие геометрические -фигуры и более "хитрые" маршруты, например, при обходе шахматной доски "ходом -коня", пути в некотором лабиринте и тому подобное. - -\subsubsection{(3) Элементы криптоанализа шифров перестановки} - -(а) Приведём основные идеи, используемые при вскрытии вертикальных перестановок. - -Заметим, что это буквы каждого столбца заполненного прямоугольника выписываются -в криптограмму подряд, то есть криптограмма разбивается на отрезки, являющиеся -столбцами таблицы. - -Поэтому при дешифровании следует попытаться соединить две группы -последовательных букв криптограммы так, чтобы они образовывали читаемые -комбинации. - -Для этого естественно использовать наиболее частые биграммы открытого текста, -которые можно составить из букв криптограммы. - -Если для первой пробы выбрано, например, сочетание НИ, то можно по очереди -приписывать к каждой букве Н криптограммы каждую букву и из неё. - -При этом несколько букв, стоящих до и после данной буквы Н, и несколько букв, -стоящих до и после данной буквы И, соединяются в пары, то есть получаются два -столбца букв, записанные рядом: - -\begin{center} -\begin{tabular}{ll} -I & II\\ -\ldots{} & \ldots{}\\ -Н & И\\ -\ldots{} & \ldots{}\\ -\end{tabular} -\end{center} - -Длина столбцов неизвестна, но используя положение конкретных букв, можно -получить на них некоторые ограничения: -\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} -\end{enumerate} - -Для выбранного сочетания НИ получается по одной паре столбцов для каждого -конкретного выбора букв Н и И из криптограммы, и из них целесообразно отобрать -ту пару, которая содержит наиболее частые биграммы. - -При автоматизации этого процесса можно приписать каждой биграмме вес, равный -частоте её появления в открытом тексте. - -Тогда отбирается та пара столбцов, которая имеет наибольший вес. - -Появление одной биграммы с низкой частотой может указать на то, что длину -столбца надо ограничить. - -Выбрав пару столбцов аналогичным образом подбирается к ним третий (справа или -слева) и так далее. Описанная процедура значительно упрощается при использовании -вероятных слов, то есть слов, которые могут встретиться в тексте с большой -вероятностью. - -(б) Рассмотрим метод, применимый к любым шифрам перестановки. - -Допустим, что к двум или более сообщениям (или отрезкам сообщений) одинаковой -длины применяется один и тот же шифр перестановки. - -Тогда очевидно, что буквы, которые находились на одинаковых местах в открытых -текстах, окажутся на одинаковых местах и в криптограммах. - -Выпишем криптограммы одну под другой так, что первые буквы всех сообщений -оказываются в первом столбце, вторых --- во втором и так далее. - -палец -> ЕПЦЛА -волна -> НВАЛО -Ключ: 41532 - -Если предположить, что две конкретные буквы в одном из сообщений идут один -за другой в открытом тексте, то буквы, стоящие на тех же местах в каждом из -остальных сообщений, соединяются подобным же образом. - -Значит, они могут служить проверкой правильности первого предположения. - -К каждому из указанных двубуквенных сочетаний можно добавить третью букву -для образования триграммы и так далее. - -Если располагать не менее чем 4 сообщениями одинаковой длины, то можно с -уверенностью гарантировать их вскрытие подобным образом. - -Если ключ зашифрования совпадает с ключом расшифрования, то такие шифры называют -\emph{симметричными}, иначе --- \emph{асимметричными}. - -\subsection{(1.6) Шифры простой замены} - -\subsubsection{(1) \emph{Шифр замены}} - -\emph{Шифр замены} --- шифр, при котором фрагменты открытого текста (отдельные -буквы или группы букв) заменяются некоторыми их эквивалентами в криптограмме. - -Определим модель \(\Sigma_A = (X, K, Y, E, D)\) произвольного шифра замены. - -Будем считать, что открытые и шифрованные тексты являются словами в алфавитах A -и B соответственно. \(X \subset A^*, \, Y \subset B^*, \, |A| = n, \, |B| = m\). - -Перед зашифрованием открытый текст предварительно представляется в виде -последовательностей подслов, называемых \emph{шифровеличинами} (слова из -\(A^*\)). - -При зашифровании шифрвеличины заменяются некоторыми их эквивалентами в -шифртексте, которые называются \emph{шифробозначениями} (слова из \(B^*\)). - -Пусть -\(U = (u_1, \dots, u_N)\) --- множество возможных шифрвеличин. -\(V = (v_1, \dots, v_N)\) --- множество возможных шифробозначений. -При этом \(N \geq n, \, M \geq m, \, M \geq N\). - -Для определения правила зашифрования \(E_k(x)\) в общем случае понадобится ряд -обозначений и понятие \emph{распределителя}, который, по сути, и будет выбирать -в каждом такте шифрования замену соответствующей шифровеличине. - -Поскольку \(M \geq N\), множество \(V\) можно представить в виде объединения \(V -= \cup_{i = 1}^{N} V^{(i)}\) непересекающихся непустых подмножеств \(V^{(i)}\). - -Рассмотрим произвольное семейство, состоящее из \(r\) таких разбиений множества -\(V\): $$V = \cup_{i = 1}^{N} V^{(i)}_\alpha, \, \alpha = \overline{1, r}, \, -r \in N,$$ и соответствующее семейство биекций: $$\varphi_\alpha : U \to \{ -V^{(1)}_\alpha, \dots, V^{(N)}_\alpha \},$$ для которых \(\varphi_\alpha (u_i) = -V^{(i)}_\alpha, \, i = \overline{1, N}\). - -Рассмотрим также произвольное отображение \(\psi : K \times \mathbb{N} \to -\mathbb{N}^*_r\), где \(\mathbb{N}_r = \{ 1, 2, \dots, r \}\), такое, что для -любых \(k \in K, \, l \in \mathbb{N}\) $$\psi(k, l) = a^{(k)}_1 \dots a^{(k)}_l, -\, a^{(k)}_j \in \mathbb{N}_r, \, j = \overline{1, l}$$ - -Последовательность \(\psi(k, l)\) называется \emph{распределителем}, отвечающим -данным значениям \(k \in K,\, l \in \mathbb{N}\). - -Теперь можно определить правило зашифрования произвольного шифра замены. Пусть -$$x \in X, x = x_1 \dots x_l, x_i \in U, i = \overline{1, l}, k \in K, \quad -\psi(k, l) = a^{(k)}_1 \dots a^{(k)}_l$$ - -Тогда \(E_k(x) = y\), где \(y = y_1 \dots y_l, y_j \in -\varphi_{\alpha^{(k)}}(x_j), j = \overline{1, l} \quad (1) !!!\). - -В качестве \(y_j\) можно выбрать любой элемент множества -\(\varphi_{\alpha^{(k)}}(x_j)\). - -Всякий раз при шифровании этот выбор можно производить случайно, например, с -помощью некоторого \emph{рандомизатора} типа игровой рулетки. - -Для однозначных шифров замены, у которых правило дешифрования \(E_k(x)\) -является однозначной функцией, например, шифр гаммирования, справедливо свойство -$$\forall \alpha, i : |V^{(i)}_\alpha| = 1$$ для многозначных шифров замены, -например, шифров пропорциональной замены: $$\exists \alpha, i : |V^{(i)}_\alpha| -> 1$$ - -Далее будем заниматься в основном изучением однозначных замен, получивших -наибольшее практическое применение. - -Итак, далее \(M = N\) и \(\varphi_\alpha(u_i) = v^{(i)}_\alpha, i = \overline{1, -M}\). - -Для шифра однозначной замены определение правила зашифрования можно -уточнить в формуле (1) включение следует заменить равенством $$y_j = -\varphi_{\alpha_j^{(k)}} (x_j), j = \overline{1, l} \quad (1')$$ - -Если для некоторого числа \(q \in N\) выполняются включения \(v_i \in B^q, i -= \overline{1, N}\), то соответствующий шифр замены называется \emph{шифром -равнозначной замены}, в противном случае --- \emph{шифром разнозначной замены}. - -В подавляющем большинстве случаев используются шифры замены, для которых \(U \in -A^p\) для некоторого \(p \in \mathbb{N}\). - -При \(p = 1\) говорят о \emph{поточных шифрах замены}, при \(p > 1\) --- о -\emph{блочных шифрах замены}. - -В случае \(r = 1\) шифр замены называют \emph{одноалфавитным шифром замены} -или \emph{шифром простой замены}. В противном случае --- \emph{многоалфавитным -шифром замены}. - -\subsubsection{(2) Одноалфавитные однозначные замены называются \emph{шифрами простой замены}.} - -Введём шифр простой замены в алфавите \(A\). - -Пусть \(X = Y = \cup_{i = 1}^L A^i, \, K \subseteq S(A)\), где \(S(A)\) --- -симметрическая группа подстановок множества \(A\). - -Для любого ключа \(k \in K\), открытого текста \(x = (x_1, \dots, x_l)\) -и шифрованного текста \(y = (y_1, \dots, y_i)\) правила зашифрования и -расшифрования шифра простой замены в алфавите \(A\) определяются формулами: -\begin{align*} - E_k(x) &= (k(x_1), \dots, k(x_1)), \\ - D_k(x) &= (k^{-1}(y_1), \dots, k^{-1}(y_1)), -\end{align*} -где \(k^{-1}\) --- подстановка, обратная к \(k\). - -Например, в рассказе Артура Конана Дойля "Пляшущие человечки", бандит Аб Слени -использовал шифр, где заменялись схематическими человеческими фигурками в разных -позах, при этом каждая поза этих человечков является отдельной буквой. - -\subsubsection{(3) Лозунговый шифр} - -При этом методе осуществляется посимвольная замена букв открытого текста на -буквы шифроалфавита, который совпадает с алфавитом открытых текстов. - -В первой строке шифровальной таблицы записывается алфавит языка открытых -текстов. - -Во второй, начиная с некоторого места записывается лозунг (пароль). - -Затем на оставшихся местах второй строки, начиная с места следующего за паролем, -записывается полный алфавит с пропуском тех букв, которые встречаются в пароле. - -Закончив движение по строке, возвращаемся в её начало, процесс продолжается. - -\emph{ПРИМЕР!!!} - -\subsubsection{(4) Шифр простой неравнозначной замены} - -Пример --- шифр Марк. - -\emph{ПРИМЕР!!!} - -Буквы, стоящие во второй строке таблицы при шифровании заменяются стоящими над -ними, остальные буквы --- двузначными числами "строка-столбец". - -\subsubsection{(5) Анализ шифров простой замены} - -(а) Методы вскрытия шифра простой однобуквенной замены. - -(а) Методы вскрытия шифра простой однобуквенной замены основан на том, что с -точностью до переобозначений частотные характеристики $m$-грамм криптограммы и -открытого текста одинаковы. - -При этом используются частотные характеристики предполагаемого открытого текста, -полученные с учётом "характера переписки". - -Обычно выделяют следующие этапы алгоритма: -\begin{enumerate} - \item - Подсчёт частот шифробозначений, а также некоторых их сочетаний - (например, биграмм). - - Если длина текста достаточно велика, то найденные частоты окажутся - близкими к значениям частот знаков открытого текста; - \item - Выявление шифробозначений, заменяющих гласные и согласные буквы. - - Основано на характерных свойствах этих букв, например, удвоение - гласных в открытом тексте происходит реже, чем согласных. - - \item - Выдвижение гипотез о значениях шифробозначений и их проверка. - - Восстановление истинных значений шифробозначений. - - При этом учитывается, что каждая буква имеет предпочтительных - связей, которые составляют её наиболее характерную особенность. - - Как правило, такие гипотезы подтверждаются не полностью. - - Хорошим критерием при этом является "читаемость" - восстанавливаемого открытого текста. -\end{enumerate} - -Приведём описание эвристического алгоритма дешифрования, основанного на идее -Томаса Якобсена. -\begin{enumerate} - \item - Построить начальный вариант ключа \(k\) на основе сравнения частот - знаков криптограмм и открытого текста. - \item - Положить $v = f(D_k(y))$, где \(f(t) = \sum_{i,j}|\Delta_{ij}(t) - b_{ij}|\) - --- "целевая функция", \(\Delta(t) = (\Delta_{ij}(t))_{n \times m}\) --- - матрица биграмм данного текста \(t\), \(n\) --- число букв алфавита. \(B = - (b_{ij})_{n \times m}\) --- эталонная матрица биграмм открытого текста. - \item Положить \(k' = k\). - \item - Поменять местами в нижней строке подстановки \(k'\) некоторую пару букв, - например, \(\alpha\) и \(\beta\). - \item Положить \(v' = f(D_{k'}(y))\). - \item Если \(v' < v\), то положить \(k = k', \, v' = v\) и перейти к 4). - \item Перейти к шагу 3). -\end{enumerate} - -Алгоритм заканчивается, когда условие \(v' < v\) не выполняется в течение -некоторого числа итераций, например, 100. - -Если шифр простой замены не является однобуквенным, то при вскрытии криптограммы -необходимо попытаться восстановить множество шифрвеличин. - -Если задача решена, то дальнейшая работа аналогична. - -(б) Некоторые особенности вскрытия равнозначных шифров простой замены. - -\begin{enumerate} - \item - Длины повторений фрагментов и расстояния между ними должны быть - кратны значности шифра (\emph{значность шифра} --- количество знаков - (цифр или букв), образующих одно шифробозначений). - \item - Находя НОД этих чисел с большей вероятностью получается искомая значность. - \item - Подсчитать общее число шифробозначений, если это число близко к ожидаемому - числу шифробозначений (например, к числу букв алфавита), и диаграмма их - повторяемости близка к табличной, то, скорее всего, значность определена - верно. -\end{enumerate} - -(в) Некоторые особенность вскрытия разнозначных шифров простой замены - -\begin{enumerate} - \item - В этом случае числа, равные длинам повторений и расстояниям между ними, - скорее всего, взаимно просты в совокупности. - - Для определения множества шифрообозначений помогает естественное - ограничение, которым обычно пользуются при составлении таблицы - шифрообозначений. - - Оно связано с требованием однозначности расшифрования и заключается в том, - чтобы ни одно из шифрообозначений не являлось началом никакого другого - шифрообозначения (в теории кодирования в подобной ситуации говорит о - \emph{префиксном коде}); - \item - Если значность шифрообозначений колеблется в незначительных пределах, - то перебор сравнительно небольшого числа вариантов приводит (с учётом - ограничения) к правильному определению большинства шифрообозначений. - - Некоторые затруднения могут возникать лишь при определении значности - шифрообозначений, редко встречающихся в тексте. - - Как правило, эти проблемы решаются вместе с попытками прочтения тех участков - криптограммы, для которых восстановленная значность шифрообозначений не - вызывает сомнений. -\end{enumerate} - -Увеличение значности шифрообозначений делает шифр неэкономным, поэтому получили -распространение шифры, использующие одно- и двузначные шифрообозначения. - -Для таких шифров наибольшую повторяемость в шифртексте имеют цифры, с которых -начинаются двузначные шифрообозначения. - -Выдвигая гипотезы о таких цифрах и отмечая в шифртексте соответствующие -двузначные шифрообозначения, можно восстановить и однозначные шифрообозначения, -оказавшиеся в шифртексте между некоторыми двузначными шифрообозначениями. - -\subsubsection{(6) Блочные шифры простой замены.} - -Пример --- Шифр Хилла. - -Шифр Хилла --- полиграммный шифр подстановки, основанный на линейной алгебре и -модульной арифметике. - -Изобретён американским математиком Л. Хиллом в 1929 году. - -Пусть мощность алфавита равна \(m\). - -Каждой букве присваивается число, равное порядковому номеру алфавита, последней -букве --- 0 (полная система вычетов по модулю \(m\)). - -/ !!!ТАБЛИЦА С БУКВАМИ И ИХ НОМЕРАМИ / - -Пусть открытый текст разбивается на блоки длины \(n\). Шифрование осуществляется -поблочно. Пусть \(\vec{x}\) --- вектор-строка длины \(n\) (над кольцом вычетов -\(Z_m\)). - -Сообщение преобразуется из открытого текста заменой букв соответствующими -числами. - -Рассмотрим кольцо \(Z_m\). - -Выбирается обратимая матрица \(A\) размерности \(n \times n\) над кольцом -\(Z_m\) и вектор-строка \(\vec{a}\) размерности \(n\) над \(Z_m\). - -Шифрование осуществляется по формуле \(\vec{y} = \vec{x} A + \vec{a}\) (все -действия осуществляются по модулю \(m\), то есть в кольце \(Z_m\)). - -Ключом шифра является пара \((A, \vec{a})\). - -Тогда дешифрование \(\vec{x} = (\vec{y} - \vec{a}) A^{-1}\). - -\emph{Пример}: Еду = \((6, 5, 20) = \vec{x}, m = 32, \vec{x} = (6, 5, -12)\) - -Матрица \(A = \begin{pmatrix} - 1 & 1 & 1 \\ - 1 & 2 & 2 \\ - 1 & 2 & 3 -\end{pmatrix}\) - -Матрица \(A^{-1} = \begin{pmatrix} - 2 & -1 & 0 \\ - -1 & 2 & -1 \\ - 0 & -1 & 1 -\end{pmatrix}\) - -\(\vec{a} = (1, 8, -12)\) - -$$\vec{y} = \vec{x} A + \vec{a} = (6, 5, -12) \begin{pmatrix} - 2 & -1 & 0 \\ - -1 & 2 & -1 \\ - 0 & -1 & 1 -\end{pmatrix} + (1, 8, -12) = (-1, -8, -20) + (1, 8, -12) = (0, 0, 0) = \text{яяя}$$ - -$$\vec{x} = (\vec{y} - \vec{a}) A^{-1} = (-1, -8, 12) \begin{pmatrix} - 2 & -1 & 0 \\ - -1 & 2 & -1 \\ - 0 & -1 & 1 -\end{pmatrix} = (6, 5, 20) = \text{еду}$$ - -Для нахождения обратимых матриц над кольцом \(Z_m\) предложен следующий -практический способ: -\begin{enumerate} - \item - Нужно взять произвольную нижнюю треугольную матрицу над \(Z_m\) с - определителем, равным 1 (для этого достаточно положить равными 1 все - элементы главной диагонали). - \item Далее берётся верхняя треугольная матрица над \(Z_m\) с определителем, равным 1. - \item Перемножив эти матрица, получаем обратимую матрицу над кольцом \(Z_m\). -\end{enumerate} - -Пример: -$$\begin{pmatrix} - 1 & 0 & 0 \\ - 1 & 1 & 0 \\ - 1 & 1 & 1 -\end{pmatrix} \cdot -\begin{pmatrix} - 1 & 1 & 1 \\ - 0 & 1 & 1 \\ - 0 & 0 & 1 -\end{pmatrix} = -\begin{pmatrix} - 1 & 1 & 1 \\ - 1 & 2 & 2 \\ - 1 & 2 & 3 -\end{pmatrix}$$ - -Особенно удобно для практического применения шифра Хилла, когда матрица \(A\) -является \emph{инволютивной}, то есть \(A^{-1} = A\). Тогда \(\vec{x} = (\vec{y} -- \vec{a}) A\). - -Как построить инволютивную матрицу? - -\begin{enumerate} - \item - Пусть для заданных \(m\) и \(n\) имеется пара взаимнообратных матриц \(A\) - и \(A^{-1}\). Возьмём любую диагональную инволютивную матрицу \(I\) (можно - просто выбрать элементы главной диагонали равными 1 и -1). - \item Тогда \(A I A^{-1}\) --- инволютивная матрица. -\end{enumerate} - -\begin{remark} - К настоящему времени не найдена простая формула для подсчёта - количества инволютивных матриц над $Z_m$. -\end{remark} - -Увеличение значности шифрвеличин резко усложняет попытки вскрытия открытого -текста по известному тексту криптограмм. - -Однако свойство линейности является их криптографической слабостью, например, -задача нахождения ключа является не слишком трудоёмкой, если известны \(n + 1\) -пар блоков открытого текста и соответствующих их блоков шифртекста, полученные -на данном ключе. - -\section{2. Шифры многоалфавитной замены} - -Напомним, что правило зашифрования многоалфавитного шифра однозначной замены -определяется следующим образом. - -Пусть $x = (x_1, \dots, x_l)$ --- открытый текст, представленный -последовательностью шифрвеличин $x_i \in U, i = \overline{1, l}$ и $k$ --- -произвольный ключ. - -Тогда $E_k = (\pi_1(x_1), \dots, \pi_l(x_l))$, где $\pi_i, i = \overline{1, l}$ ---- некоторые подстановки на множестве всех шифрвеличин, однозначно определяемые -данным ключом. - -При этом здесь и далее ограничимся рассмотрением случая, когда множества -шифрвеличин и шифрообозначений совпадают друг с другом ($U = V$). - -На практике используются в основном поточные многоалфавитные шифры, среди -которых выделяется два больших подкласса --- шифры, реализуемые дисковыми -шифраторами и шифры гаммирования. - -\subsection{2.1 Дисковые шифраторы} - -\subsubsection{Шифр Альберти} - -Л. Альберти в 1466 г. написал труд о шифрах. В этой работе был предложен шифр, -основанный на использовании \textit{шифровального диска}. - -\textbf{!!!КАРТИНКА С ПРИМЕРОМ!!!} - -Шифровальный диск представлял собой пару соосных дисков разного диаметра. - -Больший из них --- неподвижный, его окружность разделена на 24 равных -сектора, в которые вписаны 20 букв латинского алфавита в их естественном -порядке и 4 цифры (от 1 до 4). - -При этом из 24-буквенного алфавита были удалены 4 буквы, без которых можно -было обойтись, подобно тому, как в русском языке обходятся без Ъ, Ё, Й. - -Меньший диск --- подвижный, по его окружности, разбитой также на 24 сектора, -были вписаны все буквы перемешанного латинского алфавита. - -Имея два таких прибора, корреспонденты договаривались о первой индексной -букве на подвижном диске. - -При шифровании сообщения отправитель ставил индексную букву против любой -буквы большего диска. - -Он информировал корреспондента о таком положении диска, записывая эту букву -внешнего диска в качестве первой буквы шифртекста. - -Очередная буква открытого текста отыскивалась на неподвижном диске и стоящая -против неё буква меньшего диска являлась результатом её зашифрования. - -После того как были зашифрованы несколько букв текста, положение индексной -буквы изменялось, о чём также каким-либо образом передавалось корреспонденту. - -Такой шифр имел две особенности: -\begin{enumerate} - \item - Шифровальный диск использовал несколько алфавитов для зашифрования - (\textit{многоалфавитные шифры}). - \item - Шифровальный диск позволял использовать так называемые \textit{коды с - перешифрованием}: для этой цели на внешнем диске имелись цифры. - - Альберти составил \textit{код}, состоящий из 336 кодовых групп, - занумерованных от 11 до 4444. - - Каждому кодовому обозначению соответствовала некоторая законченная фраза. - - Когда такая фраза встречалась в открытом сообщении, на заменялась - соответствующим кодовым обозначением, а с помощью диска цифры - зашифровывались как обычные знаки открытого текста, превращались в буквы. -\end{enumerate} - -\subsubsection{Колёсные шифраторы} - -Почти половина XX века была связана с использованием колёсных шифраторов. - -Различные их конструкции были запатентованы в одно и то же время (в период -1917--1919 гг.) в разных странах: американцем Э.~Х.~Хеберном (шифрующий диск), -голландцем Х.~Ф.~Кохом (шифрующий диск, в котором роль электричества выполняла -пневматика), немцем А.~Шербиусом (шифромашина <<Энигма>>) и шведом А.~Г.~Даммом -(дисковая машина, которая никогда не была реализована). - -Шифрмашина <<Энигма>> в двух отношениях отличалась от других дисковых машин: -\begin{enumerate} - \item - После блока дисков была расположена неподвижная обратимая розетка - (пластина), контакты которой были попарно соединены друг с другом. Импульс - тока, приходивший на этот контакт, заворачивался и вновь проходил через блок - дисков в противоположном направлении. Это давало двойное шифрование каждой - буквы; - \item - Неравномерное движение дисков, которое управлялось зубчатыми колёсами. - - В довоенный период и во время второй мировой войны <<Энигма>> широко - использовалась в германской армии, ВМС и ВВС. - - Она была портативной, работала от батареи, имела деревянный футляр. - - Недостаток --- она не печатала шифртекст (а имела лишь загорающиеся - лампочки, отвечающие буквам), и для быстрой работы требовались 3--4 - человека. - -\end{enumerate} - -С <<Энигмой>> теснейшим образом связан ход многих событий периода второй -мировой войны. - -С <<Энигмой>> связано также появление первой в истории вычислительной -машины, сконструированный в 1942 году для перебора ключевых элементов -группой специалистов-криптографов под руководством А. Тьюрингом. - -В 1934 году Б. Хагелин создал свою очередную машину B-211, которую снабдил -печатающим устройством, работавшим со скоростью около 200 знаков в минуту. - -На тот момент она была самой портативной печатающей шифрмашиной. - -В том же 1934 году французский генштаб заказал Б. Хагелину карманную -печатающую машину, которая могла бы обслуживать одним человеком. Через -некоторое время такая машина была изготовления. - -Она реализовывала шифр гаммирования, причём для выработки гаммы была -использована идея суммирующего устройства, состоящего из комбинационных линеек, -расположенных в цилиндрическом барабане. - -На линейках рядами были расположены так называемые рейтеры. - -При повороте барабана на 360 градусов рейтеры, вступая во взаимодействие с -другими элементами схемы, могли выдвигать некоторые линейки влево, причём -число выдвинутых линеек и определяло значение гаммы (от 0 до 25) в данный такт -шифрования. - -Во взаимодействие с рейтерами вступали штифты, расположенные на колёсах блока -дисков, составляющего вторую основную часть машины. - -Размеры и схема движения дисков обеспечивали период, приблизительно равный $1.01 -\cdot 10^8$. - -Расположение рейтеров и штифтов могло легко меняться, они являлись ключевыми -элементами. - -Это машина С-36. - -По размерам она была меньше телефонного аппарата, весила вместе с футляром около -2.5 килограмм. - -Французы сразу же сделали заказ на 5000 машин. - -Позднее машина была существенно усовершенствована, ею заинтересовались в США. - -В 1939 г. она была взята на вооружение США. - -Под военным наименованием М-209 она использовалась в качестве полевого шифра -на протяжении всей второй мировой войны. - -Всего было произведено около 140000 таких машин. - -Позже фирма Хагелин стала производить широко известные машины С-48, C-52, T-55 -и многие другие. +% \include{lectures/lecture1.tex} +% \include{lectures/lecture2.tex} +\include{lectures/lecture3.tex} +\include{lectures/lecture4.tex} +\include{lectures/lecture5.tex} +\include{lectures/lecture6.tex} +\include{lectures/lecture7.tex} +\include{lectures/lecture8.tex} \end{document} |