Добавлены лекции 23 и 24

4 files changed, 224 insertions, 0 deletions

diff --git a/cryptography/cryptography.pdf b/cryptography/cryptography.pdf
index fd22024..4a43143 100644
--- a/cryptography/cryptography.pdf
+++ b/cryptography/cryptography.pdf
diff --git a/cryptography/cryptography.tex b/cryptography/cryptography.tex
index 584e854..ec4c0ba 100644
--- a/cryptography/cryptography.tex
+++ b/cryptography/cryptography.tex
@@ -41,5 +41,6 @@
 \input{lectures/lecture21.tex}
 \input{lectures/lecture22.tex}
 \input{lectures/lecture23.tex}
+\input{lectures/lecture24.tex}
 
 \end{document}
diff --git a/cryptography/lectures/lecture23.tex b/cryptography/lectures/lecture23.tex
index ed979e9..82e8162 100644
--- a/cryptography/lectures/lecture23.tex
+++ b/cryptography/lectures/lecture23.tex
@@ -1,3 +1,4 @@
+% Лекция 23 (31.03.23)
 \begin{itemize}
   \item
     \textbf{Зашифрование}
diff --git a/cryptography/lectures/lecture24.tex b/cryptography/lectures/lecture24.tex
new file mode 100644
index 0000000..cc212f1
--- /dev/null
+++ b/cryptography/lectures/lecture24.tex
@@ -0,0 +1,222 @@
+% Лекция 24 (07.04.23)
+
+\section{Хэш-функции}
+
+\subsection{Основные свойства}
+
+Пусть $V$ --- некоторый конечный алфавит, через $V^*$ обозначается совокупность
+всех слов в этом алфавите, то есть множество конечных последовательностей,
+составленных из элементов множества $V$.
+
+Пусть $k$ --- натуральное число, через $V^k$ обозначим множество всех слов
+длины $k$ над алфавитом $V$.
+
+\emph{Хэш-функция} --- отображение $h : V^* \to V^k$, которое каждому слову
+произвольной длины сопоставляет слово длины $k$. Если $p \in V^*$, то $h(p)$
+называется \emph{свёрткой слова $p$} или \emph{digest для $p$}.
+
+В криптографии хэш-функции применяются для решения следующих задач:
+\begin{enumerate}
+  \item
+    Построения систем контроля целостности данных при их передаче или хранении.
+
+    В данном случае для каждого набора данных вычисляется значение хэш-функции
+    (называемое \emph{кодом аутентификации} сообщения или \emph{имитовставкой}),
+    которое передаётся или хранится вместе с самими данными.
+
+    При получении данных пользователь вычисляет значение свёртки и сравнивает с
+    имеющимся контрольным значением. Несовпадение говорит об изменении данных.
+
+    Данная хэш-функция должна позволять осуществлять обнаружение не только
+    случайных ошибок в наборах данных, возникающих при их хранении и передаче,
+    но и сигнализировать об активных атаках злоумышленника, пытающегося
+    осуществить навязывание ложной информации.
+
+    Для этого хэш-функция должна зависеть от секретного параметра --- ключа
+    пользователя, который должен быть известен передающей и проверяющей
+    сторонам. Такие хэш-функции называются \emph{ключевыми}.
+
+    Имитовставки, формируемые с помощью ключевых хэш-функций, не должны
+    позволять противнику создавать поддельные сообщения при атаках типа имитация
+    и модифицировать передаваемые сообщения при атаках типа <<подмена>>;
+  \item
+    Аутентификации источника данных.
+
+    В данном случае стороны друг другу не доверяют, поэтому в такой ситуации
+    применяют схемы цифровой подписи, позволяющие осуществлять аутентификацию
+    источника данных.
+
+    Как правило, при этом сообщение сначала <<сжимается>> с помощью хэш-функции,
+    а затем подписывается личной подписью с помощью секретного ключа
+    пользователя.
+
+    В данном случае хэш-функция не зависит от секретного ключа, может быть
+    фиксирована и известна всем.
+
+    Основными требованиями к ней являются гарантии невозможности подмены
+    подписанного документа, а также подбора двух различных сообщения
+    с одинаковым значением хэш-функции (такая пара сообщений образует
+    \emph{коллизию}).
+
+    Как правило, хэш-функции строят на основе так называемых \emph{одношаговых
+    сжимающих функций $y = f(x_1, x_2)$} двух переменных, где $x_i$ и $y$ ---
+    двоичные векторы длины $m$ и $n$ соответственно, причём $n$ --- длина
+    свёртки.
+
+    Для получения значения $h(M)$ сообщение $M$ сначала разбивается на блоки
+    длины $m$ (последний блок при необходимости дополняется до полного), а
+    затем к полученным блокам $M_1, M_2, \dots, M_N$ применяют следующую
+    последовательную процедуру вычисления свёртки:
+    % TODO: сделать ссылку и нумерацию
+    \begin{align*}
+      H_0 &= v; \\
+      H_i &= f(M_i, H_{i - 1}),\, i = 1, \dots, N; \quad (6.1) \\
+      h(M) &= H_N;
+    \end{align*}
+    Здесь $v$ --- некоторый фиксированный начальный вектор.
+
+    Если функция $f$ зависит от ключа, то этот вектор можно положить равным
+    нулевому вектору, иначе этот вектор можно составить из фрагментов,
+    указывающих дату, время, номер сообщения и т.~п.
+
+    При таком подходе свойства хэш-функции $h$ полностью определяются свойствами
+    одношаговой сжимающей функции $f$.
+
+    Отображение $h : V^* \to V^k$ является \emph{криптографической
+    (односторонней) хэш-функцией}, если оно удовлетворяет следующим четырём
+    условиям:
+    \begin{enumerate}
+      \item
+        Для любого слова $p \in V^*$ значение $h(p)$ вычислительно легко
+        устанавливается;
+      \item
+        \emph{(Противодействие определению прообраза)} Если известно, что $q$
+        является свёрткой некоторого слова, то практически невозможно найти
+        слово $p$, для которого $h(p) = q$;
+      \item
+        \emph{(Противодействие обнаружению второго прообраза)} Для данного слова
+        $p$ невозможно найти другое слово $p'$ с такой же свёрткой: $h(p') =
+        h(p)$;
+      \item
+        \emph{(Противодействие коллизии)} Невозможно найти два разных слова $p$
+        и $p'$ с одинаковой свёрткой: $h(p) = h(p')$.
+    \end{enumerate}
+\end{enumerate}
+
+
+\subsection{Бесключевые и ключевые хэш-функции}
+
+\paragraph{Ключевые функции хэширования.}
+
+Данные функции называются \emph{кодами аутентификации сообщений} (MAC) и
+применяются в системах с симметричными ключами.
+
+Они дают возможность без дополнительных средств гарантировать правильность
+источника данных и целостность данных в системах с доверяющими друг другу
+пользователями.
+
+В криптографических приложениях к ним предъявляются следующие основные
+требования:
+\begin{itemize}
+  \item
+    Невозможность фабрикации (высокая сложность подбора сообщения с правильным
+    значением свёртки);
+  \item
+    Невозможность модификации (высокая сложность подбора для заданного сообщения
+    с известным значением свёртки другого сообщения с правильным значением
+    свёртки).
+\end{itemize}
+
+Иногда эти свойства объединяют в одно более сильное свойство --- свойство
+\emph{вычислительной устойчивости}: высокая сложность подбора для заданного
+множества сообщения $\set{x_1, \dots, x_t}$ с известными значениями свёрток ещё
+одного сообщения $x$, $x \neq x_i$, $i = 1, \dots, t$, с правильным значением
+свёртки.
+
+От ключевых хэш-функций не требуется устойчивости к коллизиям. Обычные атаки на
+ключевые хэш-функции заключаются в имитации, а также в подмене передаваемых
+сообщений с целью навязывания приёмной стороне ложных сообщений.
+
+Типы построения:
+\begin{enumerate}
+  \item
+    В качестве примера хэш-функции, построенной на основе одношаговой сжимающей
+    функции --- алгоритм, который совпадает с режимом выработки имитовставки
+    в ГОСТ Р 34.13-2015.
+  \item
+    Ещё одной основой для построения ключевых хэш-функций могут служить
+    бесключевые хэш-функции: для вычисления значения свёртки ключ приписывается
+    к исходному сообщению, а именно
+    \begin{align*}
+      H &= h(k, y, M, k), \text{или} \\
+      H &= h(k, y_1, h(k, y_2, M)),
+    \end{align*}
+    где $y, y_1, y_2$ --- дополнения ключа $k$ до размера, кратного длине блока
+    $n$.
+  \item
+    Также существуют ключевые хэш-функции, разработанные независимо с учётом
+    эффективной реализации на современных ЭВМ (например, в алгоритме MAA
+    (message authenticator algorithm)).
+\end{enumerate}
+
+
+\paragraph{Бесключевые функции хэширования.}
+
+Данные хэш-функции называются кодами обнаружения ошибок (MDC, MIC). Они дают
+возможность с помощью дополнительных средств (шифрования, использования
+защищённого канала или цифровой подписи) гарантировать целостность данных.
+
+Могут применяться в системах как с доверяющими, так и не доверяющими друг
+другу пользователями.
+
+Обычно требуется выполнение следующих свойств:
+\begin{itemize}
+  \item
+    Однонаправленность (высокая сложность нахождения сообщения с заданным
+    значением свёртки);
+  \item
+    Устойчивость к коллизиям (высокая сложность нахождения пары сообщения с
+    одинаковыми значениями свёртки);
+  \item
+    Устойчивость к нахождению второго прообраза (высокая сложность нахождения
+    второго сообщения с тем же значением свёртки для заданного сообщения с
+    известным значением свёртки).
+\end{itemize}
+
+% TODO: утв 6.1, ссылка на уравнение
+\begin{statement}
+  Если функция хэширования $h$ построена на основе одношаговой сжимающей
+  функции $f$ по правилу (6.1), то из устойчивости к коллизиям функции $f$
+  следует устойчивость к коллизиям функции $h$.
+\end{statement}
+
+% TODO: утв 6.2
+\begin{statement}
+  Если хэш-функция устойчива к коллизиям, то она устойчива к нахождению второго
+  прообраза.
+\end{statement}
+
+% TODO: утв 6.3
+\begin{statement}
+  Устойчивая к коллизиям функция не обязана быть однонаправленной.
+\end{statement}
+
+% TODO: утв 6.4
+\begin{statement}
+  Пусть $h : X \to Y$ --- хэш-функция и $|X| > 2|Y|$. Тогда если существует
+  эффективный алгоритм обращения функции $h$, то существует вероятностный
+  алгоритм нахождения коллизии функции $h$ с вероятностью успеха, большей
+  $\frac{1}{2}$.
+\end{statement}
+
+Пусть $E_k$ --- алгоритм блочного шифрования, $n$ --- размер блока, $l$ ---
+размер ключа, $G$ --- некоторое отображение, ставящее в соответствие вектору
+длины $n$ вектор длины $l$. Примеры одношаговых сжимающих функций, построенных
+на основе алгоритма $E_k$:
+\begin{itemize}
+  \item $f(x, H) = E_x(H) \oplus H$ (Дэвис --- Мейер);
+  \item $f(x, H) = E_{G(H)}(x) \oplus x$ (Матиас --- Мейер --- Осеас);
+  \item $f(x, H) = E_{G(H)}(x) \oplus x \oplus H$ (Миагучи --- Принель).
+\end{itemize}
+
+% TODO: дописать