From 6346c39c3b4349f3381172d7300bb985212b8f98 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Tue, 25 Oct 2022 13:50:08 +0400 Subject: =?UTF-8?q?=D0=94=D0=BE=D0=BA=D1=83=D0=BC=D0=B5=D0=BD=D1=82=20?= =?UTF-8?q?=D0=BF=D0=BE=20=D0=BA=D1=80=D0=B8=D0=BF=D1=82=D0=BE=D0=B3=D1=80?= =?UTF-8?q?=D0=B0=D1=84=D0=B8=D0=B8=20=D1=80=D0=B0=D0=B7=D0=B4=D0=B5=D0=BB?= =?UTF-8?q?=D1=91=D0=BD=20=D0=BD=D0=B0=20=D0=BB=D0=B5=D0=BA=D1=86=D0=B8?= =?UTF-8?q?=D0=B8?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- cryptography/cryptography.pdf | Bin 379912 -> 379600 bytes cryptography/cryptography.tex | 1104 +----------------------------------- cryptography/lectures/lecture3.tex | 194 +++++++ cryptography/lectures/lecture4.tex | 161 ++++++ cryptography/lectures/lecture5.tex | 187 ++++++ cryptography/lectures/lecture6.tex | 165 ++++++ cryptography/lectures/lecture7.tex | 228 ++++++++ cryptography/lectures/lecture8.tex | 162 ++++++ cryptography/maker.sh | 3 +- 9 files changed, 1107 insertions(+), 1097 deletions(-) create mode 100644 cryptography/lectures/lecture3.tex create mode 100644 cryptography/lectures/lecture4.tex create mode 100644 cryptography/lectures/lecture5.tex create mode 100644 cryptography/lectures/lecture6.tex create mode 100644 cryptography/lectures/lecture7.tex create mode 100644 cryptography/lectures/lecture8.tex (limited to 'cryptography') diff --git a/cryptography/cryptography.pdf b/cryptography/cryptography.pdf index cfb58fa..0c63985 100644 Binary files a/cryptography/cryptography.pdf and b/cryptography/cryptography.pdf differ 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} diff --git a/cryptography/lectures/lecture3.tex b/cryptography/lectures/lecture3.tex new file mode 100644 index 0000000..930b360 --- /dev/null +++ b/cryptography/lectures/lecture3.tex @@ -0,0 +1,194 @@ +% Лекция 3 (19.09.22) +\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} + +Информация, которую реально несёт каждая буква сообщения меньше, чем её +максимальная информация при случайном и равновероятном появлении. + +В связи с ним возник термин "избыточность языка". + +Поэтому часть букв открытого текста можно опустить без потери содержания +потерянная информация будет восстановлена другими буквам сообщения вследствие +закономерностей языка. diff --git a/cryptography/lectures/lecture4.tex b/cryptography/lectures/lecture4.tex new file mode 100644 index 0000000..16eb0d2 --- /dev/null +++ b/cryptography/lectures/lecture4.tex @@ -0,0 +1,161 @@ +% Лекция 4 (26.09.22) +\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{ДОПИСАТЬ!!!}} diff --git a/cryptography/lectures/lecture5.tex b/cryptography/lectures/lecture5.tex new file mode 100644 index 0000000..8e42a0c --- /dev/null +++ b/cryptography/lectures/lecture5.tex @@ -0,0 +1,187 @@ +% Лекция 5 (03.10.22) +\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} + +Для выбранного сочетания НИ получается по одной паре столбцов для каждого +конкретного выбора букв Н и И из криптограммы, и из них целесообразно отобрать +ту пару, которая содержит наиболее частые биграммы. + +При автоматизации этого процесса можно приписать каждой биграмме вес, равный +частоте её появления в открытом тексте. + +Тогда отбирается та пара столбцов, которая имеет наибольший вес. + +Появление одной биграммы с низкой частотой может указать на то, что длину +столбца надо ограничить. + +Выбрав пару столбцов аналогичным образом подбирается к ним третий (справа или +слева) и так далее. Описанная процедура значительно упрощается при использовании +вероятных слов, то есть слов, которые могут встретиться в тексте с большой +вероятностью. + +(б) Рассмотрим метод, применимый к любым шифрам перестановки. + +Допустим, что к двум или более сообщениям (или отрезкам сообщений) одинаковой +длины применяется один и тот же шифр перестановки. + +Тогда очевидно, что буквы, которые находились на одинаковых местах в открытых +текстах, окажутся на одинаковых местах и в криптограммах. + +Выпишем криптограммы одну под другой так, что первые буквы всех сообщений +оказываются в первом столбце, вторых --- во втором и так далее. diff --git a/cryptography/lectures/lecture6.tex b/cryptography/lectures/lecture6.tex new file mode 100644 index 0000000..54d51b8 --- /dev/null +++ b/cryptography/lectures/lecture6.tex @@ -0,0 +1,165 @@ +% Лекция 6 (10.10.22) + +палец -> ЕПЦЛА +волна -> НВАЛО +Ключ: 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$-грамм криптограммы и +открытого текста одинаковы. + +При этом используются частотные характеристики предполагаемого открытого текста, +полученные с учётом "характера переписки". diff --git a/cryptography/lectures/lecture7.tex b/cryptography/lectures/lecture7.tex new file mode 100644 index 0000000..bd17ef1 --- /dev/null +++ b/cryptography/lectures/lecture7.tex @@ -0,0 +1,228 @@ +% Лекция 7 (17.10.22) +Обычно выделяют следующие этапы алгоритма: +\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\) +пар блоков открытого текста и соответствующих их блоков шифртекста, полученные +на данном ключе. diff --git a/cryptography/lectures/lecture8.tex b/cryptography/lectures/lecture8.tex new file mode 100644 index 0000000..aea84b0 --- /dev/null +++ b/cryptography/lectures/lecture8.tex @@ -0,0 +1,162 @@ +% Лекция 8 (24.10.22) +\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 +и многие другие. diff --git a/cryptography/maker.sh b/cryptography/maker.sh index ab2df1c..e847acf 100755 --- a/cryptography/maker.sh +++ b/cryptography/maker.sh @@ -15,7 +15,8 @@ doc() { clean() { set -o xtrace rm -rf _minted-* - rm -f *.aux *.dvi *.fdb_latexmk *.fls *.log *.out *.toc + find . -name "*.aux" -exec rm {} \; + rm -f *.dvi *.fdb_latexmk *.fls *.log *.out *.toc } help() { -- cgit v1.2.3