perfect_secure_systems.tex

\section[Криптосистема совершенной стойкости]{Криптосистема совершенной \protect\\ стойкости}
\selectlanguage{russian}

Понятие совершенной секретности (или стойкости) введено американским ученым Клодом Шенноном. В конце Второй мировой войны он закончил работу, посвященную теории связи в секретных системах\cite{Shannon:1949:CTS}. Эта работа вошла составной частью в собрание его трудов, вышедшее в русском переводе в 1963 году \cite{Shannon:1963}. Понятие о стойкости шифров по Шеннону связано с решением задачи криптоанализа по одной криптограмме.

Криптосистемы совершенной стойкости могут применяться как в современных вычислительных сетях так и для шифрования любой бумажной корреспонденции. Основной проблемой применения данных шифров для шифрования больших объемов информации является необходимость распространения ключей объемом, не меньшим чем передаваемые сообщения.

\subsection{Условие совершенной криптостойкости}


Пусть $M$ -- множество открытых текстов, подлежащих шифрованию, $K$ -- множество ключей, $C$ -- множество зашифрованных сообщений для выбранного ключа, $A$ и $B$ -- легальные пользователи.

\textbf{Утверждается следующее}: если сообщение из $M$ и соответствующий ему шифротекст из $C$ -- статистически независимые случайные величины, то такая криптосистема обладает \textbf{совершенной криптостойкостью}.

Докажем это утверждение. Так как шифрование является однозначной функцией, то пара (шифротекст, ключ) однозначно определяет открытый текст и, следовательно, условная энтропия открытого текста равна 0:
\[H(M|K,C)=0.\]
Найдем оценку количества информации, которое содержит шифротекст $C$ относительно сообщения  $M$
\[ I(M; C) = H(M) - H(M | C). \]
Очевидны следующие соотношения условных и безусловных энтропий \cite{GabPil:2007}:
\[H(K|C)=H(K|C)+H(M|K,C)=H(M,K|C),\]
\[H(M,K|C)=H(M|C)+H(K|M,C)\geq H(M|C),\]
\[H(K)\geq H(K|C)\geq H(M|C).\]
Отсюда получаем:
 \[ I(M; C) = H(M) - H(M | C)\geq H(M)-H(K). \]
Из последнего неравенства следует, что взаимная информация между сообщением и шифротекстом равна нулю, если энтропия ключа не меньше энтропии сообщений. С другой стороны, взаимная информация между сообщением и шифротекстом равна нулю, если они статистически независимы. Таким образом условием  совершенной криптостойкости является неравенство
\[ H(M) \leq  H(K).\]
%Если утверждение верно, то количество информации в шифротексте относительно открытого текста $I(M; C)$ равно нулю:
%  \[ I(M; C) = H(M) - H(M | C) = 0, \]
%так как для статистически независимых величин условная энтропия равна безусловной энтропии, то есть $H(M) = H(M | C)$.

%Функцию шифрования обозначим $E: \{ M, K \} \rightarrow C$. Процедура шифрования состоит из следующих шагов.
%\begin{itemize}
%    \item Легальный пользователь $A$ выбирает ключ $k \in K$ и секретно сообщает его легальному пользователю $B$ (дополнительная задача -- распределение ключей).
%    \item По открытому сообщению $m \in M$ и выбранному ключу $k$ вычисляют шифрованное сообщение $c = E_k(m) \in C$.
%\end{itemize}

%Основное требование при шифровании состоит в том, чтобы при выбранном ключе $k$ вычисление $c$  было легкой задачей для любого сообщения $m$.

%Функцию расшифрования обозначим $D: \{ C, K \} \rightarrow M$.  Процедура расшифрования состоит из следующих шагов.
%\begin{itemize}
%    \item Легальный пользователь $B$ получает от $A$ секретный ключ $k \in K$.
 %   \item $B$ по принятому шифрованному сообщению $c \in C$ и известному  ключу $k$ вычисляет открытое сообщение $m = D_k(c) \in M$.
%\end{itemize}

%Основное требование: при выбранном ключе $k$ вычисление $m$ должно быть легкой задачей для любого $c$. С другой стороны, при неизвестном ключе $k$ вычисление открытого сообщения $m$ по известному шифрованному сообщению $c$ должно быть трудной задачей для любого $c$.

%Криптостойкость шифра оценивается числом операций, необходимым для определения: открытого текста $m$ по шифротексту $c$, либо ключа шифрования $k$ по открытому тексту $m$ и шифротексту $c$.

%$M, C, K$ интерпретируются как случайные величины.
%Пусть заданы  распределения вероятностей $P_m(M), P_c(C), P_k(K)$. По определению шифрование $C = E_K(M)$ -- детерминированная функция своих аргументов.
%Если при выбранном шифре оказалось, что открытый текст $M$ и шифротекст $C$ -- статистически независимые случайные величины, то считается, что такая система обладает совершенной криптостойкостью.


%\subsection{Длина ключа}

%Пусть сообщения $m\in M$ и ключи $r\in K$ являются независимыми случайными величинами. Это значит, что их совместная вероятность $P_{mk}(M, K)$ равна произведению отдельных вероятностей:
%\[P_{mk}(M, K) = P_m(M) \cdot P_k(K).\]
%Пусть $C = E_K(M)$ -- множество шифрованных текстов, $M = D_K(C)$ -- множество расшифрованных текстов. Можно найти вероятности $P_c(C), P_{mck}(M,C,K)$.

%Используя известные соотношения о безусловной и условной энтропии~\cite{GabPil:2007}, оценим энтропию открытых текстов $M$ с учетом статистической независимости $M$ и $C$:
 %   \[ H(M) = H(M | C) \leq H(MK | C) = H(K | C) + H(M | CK) = \]     \[ = H(K | C) \leq H(K). \]

%Так как энтропия открытого текста при заданном шифротексте и известном ключе равна нулю, то $H(M|CK)=0$.  В результате получаем     \[ H(M) \leq H(K). \]

Обозначим $L(M)$ и $L(K)$ длину сообщений и ключа, соответственно. Известно~\cite{GabPil:2007}, что $H(M)\leq L(M)$ и равенство достигается, когда сообщения состоят из статистически независимых и равновероятных символов. Такое же свойство выполняется и для случайных ключей $H(K)\leq L(K)$. Таким образом, достаточным условием совершенной криптостойкости системы можно считать неравенство
 \[ L(M) \leq L(K)\]
при случайном выборе ключа.

%С другой стороны, энтропия открытого текста $H(M)$ характеризует  длину последовательности для описания случайной величины $M$ (открытого сообщения), а $H(K)$ характеризует  длину последовательности для описания ключа. Следовательно, совершенная криптостойкость возможна только тогда, когда  длина ключа не меньше, чем длина шифруемого сообщения, то есть     \[ H(M) \leq H(K). \] Как правило, длина сообщения заранее неизвестна и ограничена большим числом. Выбрать ключ длины не меньшей, чем возможное сообщение не представляется возможным или рациональным, и один и тот же ключ (или его преобразования) используется многократно для шифрования блоков сообщения фиксированной длины. То есть, $H(K) \ll H(M)$.

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


\subsection{Криптосистема Вернама}

Приведем пример системы с совершенной криптостойкостью.

Пусть сообщение представлено двоичной последовательностью длины $N$:
    \[ m = (m_1, m_2, \dots, m_N). \]
Распределение вероятностей сообщений $P_m(m)$ может быть любым.  Ключ также представлен двоичной последовательностью $ k = (k_1, k_2, \dots, k_N)$ той же длины, но с равномерным распределением
    \[ P_k(k) = \frac{1}{2^N} \]
для всех ключей.

Шифрование в криптосистеме \textbf{Вернама} осуществляется путем покомпонентного суммирования по модулю алфавита последовательностей открытого текста и ключа:
    \[ C = M \oplus K = (m_1 \oplus k_1, ~ m_2 \oplus k_2, \dots,  m_N \oplus k_N). \]

Легальный пользователь знает ключ и осуществляет расшифрование:
    \[ M =C \oplus K = (m_1 \oplus k_1, ~ m_2 \oplus k_2, \dots, m_N \oplus k_N). \]

Найдем вероятностное распределение $N$-блоков шифротекстов, используя формулу
    \[ P(c = a) = P(m \oplus k = a) = \sum_{m} P(m) P(m \oplus k = a | m) = \]
    \[ = \sum_{m} P(m) P(k \oplus m) = \sum_{m} P(m) \frac{1}{2^N} = \frac{1}{2^N}. \]

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

Запишем совместное распределение открытых текстов и шифротекстов:
    \[ P(m = a, c = b) ~=~ P(m = a) ~ P(c = b | m = a). \]

Найдем условное распределение
    \[ P(c = b | m = a) ~=~ P(m \oplus k = b | m = a) ~= \]
    \[ =~ P(k = b \oplus a | m = a) ~=~ P(k = b \oplus a) ~=~ \frac{1}{2^N}, \]
так как ключ и открытый текст являются независимыми случайными величинами. Итого:
    \[ P(c=b | m=a) = \frac{1}{2^N}. \]

Подстановка правой части этой формулы в формулу для совместного распределения дает
    \[ P(m=a,c=b)=P(m=a)\frac{1}{2^N}, \]
что доказывает независимость шифротекстов и открытых текстов в этой системе. По доказанному выше количество информации в шифротексте относительно открытого текста равно нулю. Это значит, что рассмотренная криптосистема Вернама обладает совершенной секретностью (криптостойкостью) при условии, что для каждого $N$-блока (сообщения) генерируется случайный (одноразовый) $N$-ключ.


\subsection{Расстояние единственности}

В реальной ситуации длина ключа может быть меньше длины открытого текста, поскольку передача ключа при больших объемах текста будет затруднена большим объемом ключа.  Это означает, что энтропия ключа может быть меньше энтропии открытого текста: $H(K)< H(M)$. Для таких ситуаций важным понятием является \textbf{расстояние единственности}.

Пусть шифрованное сообщение $C$ состоит из $N$ символов алфавита, состоящего из $L$ букв:
\[
    C = (C_1, C_2, \dots, C_N).
\]
Пусть символы этой последовательности выбираются случайно и независимо из заданного алфавита.

Криптоаналитик теоретически может вычислить последовательность энтропий:
\[ \begin{array}{l}
    h_0 = H(K), \\
    h_1 = H(K | C_1), \\
    h_2 = H(K | C_1, C_2), \\
    \dots \\
    h_n = H(K | C_1, C_2, \dots, C_n), \\
    \dots
\end{array} \]

Функция $h_n$ называется \emph{функцией неопределенности ключа}. Она является невозрастающей функцией числа условных величин $n$. Если для некоторого значения $n = n_u$ окажется, что $h_{n_u} = 0$, то это будет означать, что ключ $K$ является детерминированной функцией первых $n_u$ случайных величин $C_1, C_2, \dots, C_{n_u}$ и при неограниченных вычислительных возможностях может быть вычислен. Число $n_u$ называется \emph{расстоянием единственности}.

Найдем типичное поведение функции $h_n$ и значение расстояния единственности $n_u$. Используем следующие предположения.
\begin{itemize}
    \item Криптограф всегда стремится спроектировать систему таким образом, чтобы символы шифрованного текста имели равномерное распределение и, следовательно, энтропия шифротекста имела максимальное значение:
            \[ H(C_1 C_2 \dots C_n) \approx n \log_2 L, ~ n = 1, 2, \dots, N. \]
    \item Имеет место соотношение
            \[ H(C | K) = H(C_1 C_2 \dots C_N | K)  =  H(M), \]
        которое следует из цепочки равенств
            \[ H(MCK) = H(M) + H(K | M) + H(C | MK) = H(M) + H(K), \]
        так как
            \[ H(K | M) = H(K), ~~ H(C | MK) = 0, \]
            \[H(MCK) = H(K) + H(C | K) + H(M | CK) = H(K) + H(C | K), \]
        поскольку
            \[ H(M | CK) = 0, \]
            \[ H(C | K) =  H(M). \]
    \item Предполагается, что для любого $n \le N$ приближенно выполняется соотношение
        \[ H(C_n | K) \approx \frac{1}{N} H(M), \]
        \[ H(C_1 C_2\dots C_n | K) \approx \frac{n}{N} H(M). \]
\end{itemize}

Вычислим энтропию $H(C_1 C_2 \dots C_n K)$ двумя способами:
    \[ H(C_1 C_2 \dots C_n K) = H(C_1 C_2 \dots C_n) + H(K | C_1 C_2 \dots C_n) \approx \]
        \[ \approx n \log_2 L + h_n, \]
    \[H(C_1 C_2 \dots C_n K) = H(K) + H(C_1 C_2 \dots C_n | K) \approx \]
        \[ \approx H(K) + \frac{n}{N} H(M). \]

Отсюда следует, что
    \[ h_n \approx H(K) + n \left( \frac{H(M)}{N} - \log_2 L \right) \]
и
    \[ n_u = \frac{H(K)}{ \left( 1 - \frac{H(M)}{N \log_2 L} \right) \log_2 L} = \frac{H(K)}{\rho \log_2 L}. \]
Здесь
    \[ \rho = 1 - \frac{H(M)}{N \log_2 L} \]
означает избыточность источника открытых текстов.

%Минимальное $n$, при котором накопленная избыточность текста превысит энтропию ключа
%    \[ \frac{n}{N} H(M) = H(K), \]
%    \[ n = N \frac{H(K)}{H(M)}. \]

Несмотря на то, что теоретический вывод о совершенной криптостойкости для практики не приемлем, так как требует большого объема ключа, сравнимого с объемом открытого текста, разработанные идеи находят успешное применение в современных криптосистемах. Вытекающий из идей Шеннона принцип  выравнивания апостериорного распределения символов в шифротекстах используется в современных криптосистемах с помощью многократных итераций, включающих замены и перестановки.