Добавлена 11 лекция

1 files changed, 180 insertions, 0 deletions

diff --git a/cryptography/lectures/lecture11.tex b/cryptography/lectures/lecture11.tex
new file mode 100644
index 0000000..d125e20
--- /dev/null
+++ b/cryptography/lectures/lecture11.tex
@@ -0,0 +1,180 @@
+% Лекция 10 (14.11.22)
+
+Пусть $K(y) = \set{k \in K : \exists x \in X,\, E_k(x) = y}$ --- множество
+ключей, для каждого из которых $y$ является результатом зашифрования некоторого
+осмысленного открытого текста длины $L$.
+
+Если мы располагаем криптограммой $y$, то число ложных ключей равно $|K(y)| -
+1$, так как лишь один из допустимых ключей является истинным.
+
+Среднее число ложных ключей относительно всех возможных криптограмм длины $L$
+определяется формулой
+\begin{equation*}
+  \kappa_L = \sum_{y \in Y} p(y) \cdot (|K(y)| - 1) =
+  (\sum_{y \in Y} p(y) \cdot |K(y)|) - 1
+\end{equation*}
+
+% Теорема 1?
+\begin{theorem}
+  Для любого рассматриваемого шифра $\Sigma_B$ с равновероятными ключами при
+  достаточно больших значениях $L$ имеет место неравенство
+  \begin{equation*}
+    \kappa_L \geq \frac{|K|}{n^{L \cdot R} \Lambda} - 1
+  \end{equation*}
+\end{theorem}
+
+% TODO: убрать нумерацию
+Назовём \emph{расстоянием единственности} для шифра $\Sigma_B$ натуральное число
+$L_0$, для которого ожидаемое число ложных ключей $\kappa_L = 0$, при этом
+\begin{equation*}
+  L_0 = \ceil*{\frac{\log_2 |K|}{R_\Lambda \cdot \log_2 n}} \quad (9.3)
+\end{equation*}
+
+По сути, \emph{расстояние единственности} есть средняя длина криптограммы,
+необходимая для однозначного восстановления истинного ключа.
+
+Например, для шифра простой замены с параметрами $n = 26, |K| = 26!, R_\Lambda =
+0.5$, формула (9.3) даёт оценку $L_0 = 38$.
+
+Это значит, что для английского языка в среднем по криптограмме длиной около 40
+можно однозначно определить открытый текст, что приблизительно соответствует
+практическому опыту.
+
+
+\subsection{Стойкость шифров}
+
+Надёжность или стойкость шифров определяется объёмом работы криптоаналитика,
+необходимой для их вскрытия. До сих пор создание шифров с \emph{доказуемой
+стойкостью является сложной проблемой}. В криптографии рассматривают два
+подхода к стойкости --- \emph{теоретическую} и \emph{практическую} (или \emph{%
+вычислительную}) \emph{стойкость}.
+
+\subsubsection{Теоретическая стойкость}
+
+К. Шеннон назвал шифр \emph{совершенным}, если для любого открытого текста
+знания, которые могут быть получены из соответствующей ему криптограммы, не
+раскрывают никакой информации об открытом тексте, за исключением, возможно, его
+длины.
+
+Следующее определение формализует подход к теоретической стойкости шифра (только
+по отношению к атаке на основе единственной криптограммы).
+
+\emph{Шифр $\Sigma_B$} называется \emph{совершенным}, если $\forall x \in X,
+y \in Y$ выполняется равенство $p(x/y) = p_X(x)$.
+
+% TODO: добавить окружение
+\begin{statement}
+  % \textbf{Утверждение 1.}
+  Если шифр $\Sigma_B$ --- совершенный, то $|X| \leq
+  \|Y| leq |K|$. На практике чаще всего $X = Y$. Такие шифры называются
+  \emph{эндоморфными}.
+\end{statement}
+
+% Теорема 2?
+\begin{theorem}[К. Шеннон]
+  Пусть $\Sigma_B$ --- шифр, для которого $|X| = |Y| = |K|$. Тогда шифр
+  $\Sigma_B$ --- совершенный тогда и только тогда, когда выполняются два
+  условия:
+  \begin{enumerate}
+    \item
+      Для любых $x \in X, y \in Y$ существует единственный ключ $k \in K$, для
+      которого $E_k(x) = y$;
+    \item
+      Распределение вероятностей $P(K)$ --- равномерное, то есть для любого
+      ключа $p_K(k) = \frac{1}{|K|}$.
+  \end{enumerate}
+\end{theorem}
+
+В случае, когда $X = Y = K = Z_n$, шифры табличного гаммирования со случайными
+равновероятными ключами, и только они являются единственными совершенными
+шифрами.
+
+Теорема Шеннона может быть обобщена и для некоторых других криптоатак.
+
+\subsubsection{Практическая стойкость}
+
+Средний объём работы $W(N)$, необходимый для определения ключа по криптограмме,
+состоящей из $N$ букв, измеренный в удобных \emph{элементарных операциях},
+К. Шеннон предложил назвать \emph{рабочей характеристикой шифра}.
+
+Это среднее значение берётся по всем сообщениям и всем ключам с соответствующими
+им вероятностями.
+
+Функция $W(N)$ характеризует средние затраты (временные и материальные),
+необходимые для практического дешифрования криптограммы.
+
+На рисунке приведена рабочая характеристика шифра простой замены (пунктир
+--- имеется несколько возможных решений; по мере увеличения объёма перехвата
+количество необходимой работы быстро уменьшается).
+% TODO: рисунок 1
+\textbf{TODO: рисунок 1}
+
+Практическую стойкость шифра обычно оценивают с помощью величины
+$W_\text{д}(\infty)$, которую можно назвать \emph{достигнутой оценкой} рабочей
+характеристики.
+
+Она определяется средней трудоёмкостью наилучшего из известных методов вскрытия
+данного шифра.
+
+Большое значение имеет математическая модель вычислений, используемая при оценке
+практической стойкости шифра.
+
+По сути, речь идёт о модели гипотетической ЭВМ, которой располагает
+потенциальный противник и которая способна реализовать крупный фрагмент
+алгоритма вскрытия как одну элементарную операцию (например, опробования одного
+ключа и проверку результата расшифрования).
+
+\subsection{Имитостойкость шифров}
+
+\emph{Попытка имитации} --- противник посылает криптограмму от имени законного
+отправителя.
+
+\emph{Попытка подмены} --- если передаётся криптограмма и противник заменяет её
+на другую.
+
+\emph{Имитостойкость шифра} определяется как его способность противостоять
+попыткам противника по имитации или подмене.
+
+Естественной мерой имитостойкости шифра служит вероятность соответствующего
+события
+\begin{itemize}
+  \item $D_k(y) \in X$ --- для попытки имитации сообщения;
+  \item $(D_k(y') \in X) \land (y' \neq y)$ --- для попытки подмены сообщения.
+\end{itemize}
+
+Пусть также $p_\text{им} = \max_{y \in Y} p(D_k(y) \in X)$ --- \emph{вероятность
+имитации}, $p_\text{подм} = \max_{y, y' \in Y, y' \neq y} p(D_k(y') \in X)$ ---
+\emph{вероятность подмены}.
+
+Полагая, что противник выбирает ту попытку, которая с большей вероятностью
+приводит к успеху, вводят также \emph{вероятность навязывания} формулой
+$p_\text{н} = \max \set{p_\text{им}, p_\text{подм}}$.
+
+\begin{statement} % Утверждение 2?
+  Для шифра $\Sigma_B$ с равновероятными ключами имеет место достижимая оценка
+  $p_\text{им} \geq \frac{|X|}{|Y|}$.
+\end{statement}
+
+Для эндоморфного шифра с равновероятными ключами $p_\text{им} = 1$, что
+означает, что такой шифр максимально уязвим к угрозе имитации сообщения,
+поэтому, несмотря на многие положительные качества, эндоморфные шифры нуждаются
+в \emph{имитозащите}.
+
+% TODO: \ref{statement2}
+Утверждение 2 показывает, что имитостойкость шифра растёт пропорционально
+отношению $\frac{|Y|}{|X|}$.
+
+Это объясняет широко используемые для имитозащиты способ введения избыточности в
+передаваемое сообщение, например, дополнительных <<добавок>> к передаваемому
+сообщению типа аутентификаторов или \emph{имитовставок}.
+
+\begin{statement} % Утверждение 3
+  Для шифра $\Sigma_B$ c равновероятными ключами имеет место достижимая оценка
+  $p_\text{подм} \geq \frac{|X| - 1}{|Y| - 1}$.
+\end{statement}
+
+Итак, вероятность навязывания $p_\text{н}$ для шифра с равновероятными ключами
+удовлетворяет неравенству $p_\text{н} \geq \frac{|X|}{|Y|}$.
+
+Обозначим через $I(Y, K)$ \emph{взаимную информацию} между $Y$ и $K$, то есть
+величину, определяемую формулой $I(Y, K) = H(Y) - H(Y/K)$.