BaseDefinitions.tex

В данной главе введем основные определения, которые будут использоваться в этой работе. Начнем с формального определения хеш-функции:\\\\
Пусть \\
\hspace*{0.3cm} $\{0, 1\}^n$  - множество строк длины $m$, состоящих из битов $0$ или $1$.\\
\hspace*{0.3cm} \mbox{$\{0, 1\}^*$ - множество всех строк конечной длины, состоящих из битов $0$ или $1$.} \\\\
\textbf{ Определение 1.}
Криптографической хеш-функцией $h$ называется преобразование вида
\begin{center}
$h: \{0, 1\}^* \rightarrow \{0, 1\}^n$
\end{center}
обладающее следующими свойствами:
\begin{enumerate}  
\item Значение $h(M) ($где $M \in \{0, 1\}^*)$ должно ''вычисляться легко''
\item При изменении всего лишь одного бита входного сообщения значение $h(M)$ меняет хотя бы половину своих битов
\item Прообраз для заданного $h(M)$ должен ''вычисляться сложно'' (pre-image resistance)
\item Второй прообраз  $M^{'} \neq  M$, такой что $h(M^{'}) = h(M)$, должен ''вычисляться сложно'' (second pre-image resistance)
\item Нахождение $M$ и $M^{'} \neq M$, таких что $h(M) = h(M^{'})$, ''вычисляется сложно'' (collision resistance)\\
\end{enumerate}
\textbf{ Замечание 1.}
Далее под ''хеш-функцией'' для удобства имеем в виду ''криптографическую хеш-функцию''.\\\\
Входную строку $M$ будем называть ''сообщением''. Значение хеш-функции $h(M)$ будем называть ''хешем'', ''хеш-кодом'' или ''хеш-суммой''.\\\\
Под фразами ''вычисляется сложно'' или ''вычислительно неразрешима'' далее подразумеваем, что задача не решается за разумное время на современной вычислительной технике (очевидно, что задачи из свойств 2), 3) и 4) можно решить, например, полным перебором).\\\\
\textbf{ Пример 1. }
Пусть $h$ - хеш-функция, определенная российским стандартом ГОСТ Р 34.11-2012 256 (ее описание см. далее). Ниже представлены результаты хеширования некоторых строк (результат представлен в шестнадцатеричной системе счисления):\\
\begin{enumerate}  
\item $M = $ \mbox{''Московский Государственный Университет имени М. В. Ломоносова'' $\Rightarrow$ }\\
$h(M)$ = ''2609a10022385596400318f6b959b9d449edbf7820ec188c7d8ddbc06a09ab0b''
\item $M = $ ''МГУ им. М. В. Ломоносова'' $\Rightarrow$ \\
$h(M)$ = ''15414d11b2cbd98c858870463ed42189023845521f1bcb914817897c9f312d43''
\item $M = $ ''МГУ им М. В. Ломоносова'' $\Rightarrow$ \\
$h(M)$ = ''4b54a14ab2320e4ed25e542410e424aad19ccc04fcd4debf46430efa6d972326''\\
\end{enumerate}
\textbf{ Замечание 2.}
Отличие двух последних примеров состоит в присутствии и отсутствии знака точки: ''им.'' и ''им''. Но, как следует из свойства 2) определения 1, хеши различаются очень сильно.\\\\

Следующее определение играет важную роль при построении хеш-функций.\\\\
\textbf{ Определение 2. }
Блочным шифром называются алгоритмы шифрования и расшифрования с одинаковым ключом $K \in \{0,1\}^m$ (то есть так называемый симметричный шифр), представляемые в виде функций $E_K$ и $D_K$ и являющимися для каждого фиксированного ключа биективным отображением на множестве $\{0, 1\}^n$:\\
\begin{center}
$E_K(M) := E(K, M) : \{0, 1\}^m \times \{0, 1\}^n \rightarrow \{0, 1\}^n$,\\
$D_K(C) := D(K, C) : \{0, 1\}^m \times \{0, 1\}^n \rightarrow \{0, 1\}^n$,\\
\end{center}
причем $D=E^{-1}$, то есть $\forall K:$
\begin{center}
$D_K(E_K(M)) = M$ и\\
$E_K(D_K(C)) = C$.
\end{center}