monoalphabetic_ciphers.tex

\section{Моноалфавитные шифры}
\selectlanguage{russian}


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

\subsection{Шифр Цезаря}

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

\[ \begin{array}{ccccccccc}
    \text{A} & \text{B} & \text{C} & \text{D} & \text{E} & & \text{X} & \text{Y} & \text{Z} \\
    \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \dots & \downarrow & \downarrow & \downarrow \\
    \text{C} & \text{D} & \text{E} & \text{F} & \text{G} & & \text{Z} & \text{A} & \text{B} \\
\end{array} \]

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

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


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

Следующий рисунок
%Рисунок \ref{fig:zamena}
поясняет \textbf{аддитивный шифр} перестановки\index{шифр!аддитивный перестановки} на алфавите. Все 26 букв латинского алфавита нумеруют по порядку от 0 до 25. Затем номер буквы меняют в соответствии с уравнением
    \[ y = x + b \mod 26, \]
где $x$ -- прежний номер, $y$ -- новый номер, $b$ -- заданное целое число, определяющее сдвиг номера и известное только легальным пользователям. Очевидно, что шифр Цезаря является примером аддитивного шифра.
  	
\[ \begin{array}{ccccccccc}
    \text{A} & \text{B} & \text{C} & \text{D} & \text{E} & & \text{X} & \text{Y} & \text{Z} \\
    \downarrow & \downarrow & \downarrow & \downarrow & \downarrow & \dots & \downarrow & \downarrow & \downarrow \\
    2 & 3 & 4 & 5 & 6 & & 25 & 0 & 1 \\
\end{array} \]


\subsection{Аффинный шифр}

Аддитивный шифр является частным случаем \textbf{аффинного шифра}\index{шифр!афинный}. Правило шифрования сообщения имеет вид
    \[ 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{НОД}$). Очевидно, что для "взлома" такого шифра достаточно найти две пары букв -- две замены.