per-char_encryption.tex

\section{Посимвольное шифрование}
\selectlanguage{russian}

Потоковые шифры осуществляют посимвольное шифрование открытого текста. Их основные достоинства: большая скорость шифрования по сравнению с блоковыми шифрами и относительно простая реализация.

Пусть имеется двоичная последовательность $x_{1} x_{2} \dots x_{N}$, представляющая открытый текст, и последовательность ключей $k_{1} k_{2} \dots k_{N}$. Шифрованная последовательность представляет собой сумму по модулю 2 этих двух последовательностей
\[ \begin{array}{l}
    y_{1} = x_{1} \oplus k_{1}, \\
    y_{2} = x_{2} \oplus k_{2}, \\
    \dots \\
    y_{N} = x_{N} \oplus k_{N}.
\end{array} \]

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

Существует много способов построения двоичных последовательностей с распределением, близким к равномерному. Они называются псевдослучайными последовательностями\index{число!псевдослучайное}.

Пусть имеем некоторую двоичную последовательность $z_{1} z_{2} \ldots z_{N}$, полученную в результате подбрасывания <<неправильной монеты>> (монета считается неправильной, так как дает неравномерное распределение) с неравномерным распределением. Когда выпадал герб, записывали символ $1$. Когда выпадала решка, записывали символ $0$. Чтобы теперь приблизить распределение к равномерному, преобразуем эту последовательность. Разделим символы на пары. Если $z_{1} z_{2} = 11$ или $z_{1} z_{2} = 00$, то пара выбрасывается из последовательности; если $z_{1} z_{2} =10$, то записываем новый символ $u=1$; если $z_{1} z_{2} =01$, то записываем новый символ $u=0$. Получаем новую двоичную последовательность символов $u_{1}u_{2}\ldots $, у которой распределение нулей и единиц ближе к равномерному.
%(См. \textbf{Приложение 2}).