monoalphabetic_ciphers.tex

\section{Моноалфавитные шифры}\label{section-substitution-cipher}\index{шифр!моноалфавитный|(}
\selectlanguage{russian}

Преобразования открытого текста в шифротекст могут быть описаны различными функциями. Если функция преобразования является аддитивной, то и соответствующий шифр называется \emph{аддитивным}. Если это преобразование является аффинным, то шифр называется \emph{аффинным}.

\subsection{Шифр Цезаря}\label{section-caesar-cipher}\index{шифр!Цезаря}

Известным примером простого шифра замены является \emph{шифр Цезаря}. Процедура шифрования состоит в следующем (рис.~\ref{fig:caesar}). Записывают все буквы латинского алфавита в стандартном порядке:
    \[ A B C D E \dots Z. \]
Делают циклический сдвиг влево, например на три буквы и записывают все буквы во втором ряду, начиная с четвёртой буквы $D$. Буквы первого ряда заменяют соответствующими (как показано стрелкой на рисунке) буквами второго ряда. После такой замены слова не распознаются теми, кто не знает ключа. Ключом $K$ является первый символ сдвинутого алфавита.

\begin{figure}[thb]
\[ \begin{array}{ccccccccccc}
    \text{A} & \text{B} & \text{C} & \text{D} & \text{E} & & \text{V} & \text{W} & \text{X} & \text{Y} & \text{Z} \\
    \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \dots & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \\
    \text{D} & \text{E} & \text{F} & \text{G} & \text{H} & & \text{Y} & \text{Z} & \text{A} & \text{B} & \text{C} \\
\end{array} \]
	\caption{Шифр Цезаря\index{шифр!Цезаря}}
	\label{fig:caesar}
\end{figure}

\example
В русском языке сообщение \texttt{изучайтекриптографию} посредством шифрования с ключом $K = \text{\texttt{г}}$ (сдвиг вправо на 3 символа по алфавиту) преобразуется в \texttt{лкцъгмхзнултхсёугчлб}.
\exampleend

Недостатком любого шифра замены является то, что в шифрованном тексте сохраняются все частоты появления букв открытого текста и корреляционные связи между буквами. Они существуют в каждом языке. Например, в русском языке чаще всего встречаются буквы $A$ и $O$. Для дешифрования криптоаналитик имеет возможность прочитать открытый текст, используя частотный анализ букв шифротекста. Для <<взлома>> шифра Цезаря достаточно найти одну пару букв -- одну замену.

\subsection{Аддитивный шифр перестановки}\index{шифр!перестановки аддитивный}

Рисунок~\ref{fig:caesar-additiv} поясняет \emph{аддитивный шифр} перестановки на алфавите. Все 26 букв латинского алфавита нумеруют по порядку от 0 до 25. Затем номер буквы меняют в соответствии с уравнением:
    \[ y = x + b \mod 26, \]
где $x$ -- прежний номер, $y$ -- новый номер, $b$ -- заданное целое число, определяющее сдвиг номера и известное только легальным пользователям. Очевидно, что шифр Цезаря является примером аддитивного шифра.

\begin{figure}[thb]
\[ \begin{array}{ccccccccccc}
    \text{A} & \text{B} & \text{C} & \text{D} & \text{E} & & \text{V} & \text{W} & \text{X} & \text{Y} & \text{Z} \\
    \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \dots & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \\
    0 & 1 & 2 & 3 & 4 & & 21 & 22 & 23 & 24 & 25 \\
    \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \dots & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \\
    3 & 4 & 5 & 6 & 7 & & 24 & 25 & 0 & 1 & 2 \\
    \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \dots & \downarrow & \downarrow & \downarrow & \downarrow & \downarrow \\
    \text{D} & \text{E} & \text{F} & \text{G} & \text{H} & & \text{Y} & \text{Z} & \text{A} & \text{B} & \text{C} \\
\end{array} \]
	\caption{Шифр Цезаря\index{шифр!Цезаря} как пример аддитивного шифра\index{шифр!перестановки аддитивный}}
	\label{fig:caesar-additiv}
\end{figure}

\subsection{Аффинный шифр}\label{section-affine-cipher}\index{шифр!афинный}

Аддитивный шифр является частным случаем \emph{аффинного шифра}. Правило шифрования сообщения имеет вид
    \[ y = a x + b \mod n. \]
Здесь производится умножение номера символа $x$ из алфавита, $x\in \set\{ 0, 1, 2, \dots, N \leq n-1 \}$, на заданное целое число $a$ и сложение с числом $b$ по модулю целого числа $n$. Ключом является $K = (a, b)$.

Расшифрование осуществляется по формуле
    \[ x = (y - b) a^{-1} \mod n. \]

Чтобы обеспечить обратимость в этом шифре, должен существовать единственный обратный элемент $a^{-1}$ по модулю $n$. Для этого должно выполняться условие $\gcd(a,n) = 1$, то есть $a$ и $n$ должны быть взаимно простыми числами ($\gcd$ -- обозначение термина с английского greatest common divisor -- наибольший общий делитель, $\text{НОД}$). Очевидно, что для <<взлома>> такого шифра достаточно найти две пары букв -- две замены.

\index{шифр!моноалфавитный|)}