hash-function_properties.tex

\section{Свойства}
\selectlanguage{russian}

\textbf{Хэш-функцией} называется отображение, переводящее аргумент произвольной длины в значение фиксированной длины.

\example
Приведем пример метода построения хэш-функции, называемый методом Меркла~---~Дамгарда\index{структура!Меркла~---~Дамгарда}.~\cite{Merkle:1979, Merkle:1990, Damgard:1990}

Пусть имеется файл $X$ в виде двоичной последовательности некоторой длины. Разделяем $X$ на несколько отрезков фиксированной длины, например по 256 символов:  $m_{1} \| m_{2} \| m_{3} \| \ldots \| m_{t}$. Если длина файла $X$ не является кратной 256 бит, то последний отрезок дополняем нулевыми символами и обозначаем $m'_{t}$.
Обозначим $t$ -- новую длину последовательности. Считаем каждый отрезок $m_i, i = \overline{1,t}$ двоичным представлением целого числа.

Для построения хэш-функции используем рекуррентный способ вычисления. Предварительно введем вспомогательную функцию $\chi(m, H)$, называемую функцией компрессии, или сжимающей функцией. Задаем начальное значение $H_{0} = 0^{256} \equiv \underbrace{000 \ldots 0}_{256} $. Далее вычисляем
\[ \begin{array}{l}
    H_1 = \chi( m_1, H_0), \\
    H_2 = \chi( m_2, H_1), \\
    \dots \\
    H_t = \chi( m'_t, H_{t-1}). \\
\end{array} \]
Считаем $H_{t} = h(X)$ хэш-функцией.
\exampleend

\textbf{Однонаправленной} функцией\index{функция!однонаправленная} $f(x)$ называется функция, обладающая следующими свойствами:
\begin{itemize}
    \item вычисление значения функции $f(x)$ для всех значений аргумента $ x$ является \textit{вычислительно легкой} задачей;
    \item нахождение аргумента $x$, соответствующего значению  функции $f(x)$, является \textit{вычислительно трудной} задачей.
\end{itemize}

Свойство однонаправленности, в частности, означает, что если в аргументе $x$ меняется хотя бы один символ, то для любого $x$ значение функции $H(x)$ меняется непредсказуемо.

\textbf{Криптографической хэш-функцией} $H(x)$ называется хэш-функция, имеющая следующие свойства.
\begin{itemize}
    \item Однонаправленность: \emph{вычислительно невозможно} по значению функции найти прообраз.
    \item \emph{Слабая устойчивость к коллизиям}\index{устойчивость к коллизиям} (слабо бесконфликтная функция): для заданного аргумента $x$ \emph{вычислительно невозможно} найти другой аргумент $y \neq x: ~ H(x) = H(y)$.
    \item \emph{Сильная устойчивость к коллизиям} (cильно бесконфликтная функция): \emph{вычислительно невозможно} найти пару разных аргументов $x \neq y: ~ H(x) = H(y)$.
\end{itemize}

Из требования на устойчивость к коллизиям, в частности, следует свойство (близости к) равномерности распределения хэш-значений.

При произвольной длине последовательности $X$ длина хэш-функции $H(X)$  в российском стандарте ГОСТ Р 34.11-94 равна 256, в американском стандарте SHA несколько различных значений длин -- 160, 192, 256, 512 символов.