path: root/cryptography/cryptography.tex

\documentclass{../Lecture}

\usepackage{../preamble}

\title{Криптографические методы защиты информации}
\author{Андрей Гущин}
\date{\today}

\begin{document}

\maketitle
\tableofcontents

\section{\ldots{}}

\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
и многие другие.

\end{document}