BuildingFunctions.tex

В общем случае в основе построения хеш-функций лежит итеративная последовательная схема, когда на вход каждой итерации поступает блок исходного текста и результат предыдущей итерации. Ядром каждой итерации служит функция сжатия $f$, принимающая на вход блок определенной длины $m$ и результат предыдущей итерации длины $n$, то есть:
\begin{center}
$f: \{0, 1\}^m \times \{0, 1\}^n \rightarrow \{0, 1\}^n$
\end{center}
Данная конструкция называется Структурой Меркла-Дамгарда, которая была придумана независимо Ральфом Мерклом и Иваном Дамгардом. Ими же было установлено, что если функция сжатия устойчива к коллизиям, то и хеш-функция будет также устойчива к коллизиям.\\\\
Опишем подробнее все шаги схемы:\\\\
\hspace*{0.3cm} Пусть $M\in\{0, 1\}^*$ - исходное сообщение для хеширования.
\begin{enumerate}  
\item Разобьем сообщение $M$ на блоки $M_1, \dots , M_s $ длины $m$.
\item Дополним входное сообщение заранее определенным образом (например, нулями), если длина $M$ не кратна $m$.
\item Определить начальное значение $H_0$
\item $i$-й шаг итерации $(i = 1, \dots , s)$ заключается в вычислении значения $H_i = f(M_i, H_{i-1})$
\item Значение $H_s$ (возможно, после некоторых дополнительных преобразований) и является конечным хешем сообщения $M$.\\
\end{enumerate}
\textbf{Определение 3.} Структурой Меркла-Дамгарда называется приведенный выше алгоритм вычисления хеша (рис. 1).\\\\
картинка\\
картинка\\
картинка\\
картинка\\
картинка\\
картинка\\
картинка\\
картинка
\newpage
Также существуют улучшенные схемы, основанные на структуре Меркла-Дамгарда:
\begin{itemize}  
\item Структура Девиса-Мейера
\item Структура Матиса-Мейера-Осеаса
\item Структура Миагучи-Пренеля\\
\end{itemize}
Во всех этих схемах в качестве функции сжатия $f$ используется блочный шифр $E$. Например, могут использоваться следующие популярные стандарты шифрования - DES, AES или ГОСТ 28147-89.\\
Ниже приведем более подробное описание каждой из схем.

\subsection{Структура Девиса-Мейера}
Как сказано выше, данная структура использует блочный шифр $E$. В качестве ключа шифр использует входной блок, а на вход подается результат предыдущей итерации (для первой итерации - это некоторое начальное значение). Затем для полученного результата выполняем операцию побитового сложения с значением предыдущей итерации (см. рис 2). Результат сложения и будет финальным значением итерации. Математически все это записывает так:
\begin{center}
$H_i = E_{M_i}(H_{i-1}) \oplus H_{i-1}$
\end{center}
картинка\\
картинка\\
картинка\\
картинка\\
картинка\\
\subsection{Структура Матиса-Мейера-Осеаса}
Отличие этой структуры от предыдущей заключается в том, что входной блок и значение предыдущей итерации меняются местами. Однако получается несоответствие длин, так как длина ключа и длина выходного значения шифра имеют разные значения. В связи с этим надо иметь какое-то дополнительное преобразование $g$:
\begin{center}
$g: \{0, 1\}^n \rightarrow \{0, 1\}^m$
\end{center}
Тогда перед выполнением шифра $E$ применяем функцию $g$ к результату предыдущей итерации и уже полученное значение используем в качестве ключа шифра.\\
Далее к результату шифра применяем операцию побитового сложения с входным блоком (см. рис. 3). Математически данные преобразования выглядят так:
\begin{center}
$H_i = E_{g(H_{i-1})}(M_i) \oplus M_i$
\end{center}
картинка\\
картинка\\
картинка\\
картинка\\
картинка\\
\subsection{Структура Миагучи-Пренеля}
Эта структура считается самой популярной и надеждной из представленных здесь схем. Она аналогична предыдущей структуре за исключением того, что для операции побитового сложения добавляется еще одно слагаемое - результат предыдущей итерации. Таким образом, математически весь алгоритм записывается так:
\begin{center}
$H_i = E_{g(H_{i-1})}(M_i) \oplus M_i \oplus H_{i-1}$
\end{center}
картинка\\
картинка\\
картинка\\
картинка\\
картинка\\