perfect_secure_systems.tex

\chapter{Совершенная криптостойкость}\index{криптостойкость!совершенная|(}
\selectlanguage{russian}

Рассмотрим модель криптосистемы, в которой Алиса выступает источником сообщений $m \in \group{M}$. Алиса использует некоторую функцию шифрования, результатом вычисления которой является шифртекст $c \in \group{C}$:

	\[c = E_{K_1}\left(m\right).\]

Шифртекст $c$ передаётся по открытому каналу легальному пользователю Бобу, причём по пути он может быть перехвачен нелегальным пользователем (криптоаналитиком) Евой.

Боб, обладая ключом расшифрования $K_2$, расшифровывает сообщение с использованием функции расшифрования:
	\[m' = D_{K_2}\left(c \right).\]

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

Будем называть криптосистему \emph{корректной}, если она обладает следующими свойствами:
\begin{itemize}
	\item легальный пользователь имеет возможность однозначно восстановить исходное сообщение, то есть:
					\[H \left( M | C K \right) = 0, \]
					\[m' = m\]
	\item выбор ключа шифрования не зависит от исходного сообщения:
					\[ I \left( K ; M \right) = 0, \]
					\[ H \left( K | M \right) = H \left( K \right). \]
\end{itemize}

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

\section[Определения]{Определения совершенной криптостойкости}

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

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

\begin{definition}\label{perfect_by_probabilities}
Будем называть криптосистему \emph{совершенно криптостойкой}, если апостериорное распределение вероятностей исходного случайного сообщения $m_i \in \group{M}$ при регистрации случайного шифртекста $c_k \in \group{C}$ совпадает с априорным распределением~\cite{Gultyaeva:2010}:

	\[\forall m_j \in \group{M}, c_k \in \group{C} \hookrightarrow P \left( m = m_j | c = c_k \right) = P \left( m = m_j \right).\]
\end{definition}

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

\begin{definition}\label{perfect_by_enthropy}
Будем называть криптосистему \emph{совершенно криптостойкой}, если условная энтропия сообщения\index{энтропия!условная}\index{энтропия!открытого текста} при известном шифртексте равна безусловной:
\begin{gather*}
	H \left( M | C \right) = H \left( M \right),\\
	I \left( M; C \right) = 0.
\end{gather*}
\end{definition}

Можно показать, что определения~\ref{perfect_by_probabilities} и~\ref{perfect_by_enthropy} тождественны.

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

Найдём оценку количества информации, которое содержит шифртекст $C$ относительно сообщения $M$:
\[ I(M; C) = H(M) - H(M | C). \]
Очевидны следующие соотношения условных и безусловных энтропий~\cite{GabPil:2007}:
\begin{gather*}
H(K|C)=H(K|C)+H(M|KC)=H(MK|C),\\
H(MK|C)=H(M|C)+H(K|MC)\geq H(M|C),\\
H(K)\geq H(K|C)\geq H(M|C).
\end{gather*}
Отсюда получаем:
 \[ 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)$ соответственно. Известно, что $H(M) \leq L(M)$~\cite{GabPil:2007}. Равенство $H(M) = 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)$.

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

\index{криптостойкость!совершенная|)}

\section{Криптосистема Вернама}\index{криптосистема!Вернама|(}

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

Пусть сообщение представлено двоичной последовательностью длины $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} \]
для всех ключей.

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

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

Найдём вероятностное распределение $N$-блоков шифртекстов, используя формулу:
\begin{multline*}
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}. 
\end{multline*}


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

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

Найдём условное распределение:
\begin{multline*}
    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},
\end{multline*}
так как ключ и открытый текст являются независимыми случайными величинами. Итого:
    \[ P(c=b | m=a) = \frac{1}{2^N}. \]

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

\index{криптосистема!Вернама|)}

\input{unicity_distance}