Материал: Основы криптографической защиты информации. Мокроусов А.Н., Радько Н.М

функция h: X Y, легко вычислимая и такая, что для любого сообщения M значение h(M) = H (свѐртка) имеет фиксированную битовую длину.

Как правило, хеш-функции строят на основе одношаговых сжимающих функций y = f(x1, x2), где xi и y – двоичные векторы длины m и n соответственно, причѐм n – длина свѐртки. Для получения значения h(M) сообщение M сначала разбивается на блоки длины m (при этом если длина сообщения не кратна m, то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам М1, М2,…, МN применяют следующую последовательную процедуру вычисления свѐртки:

H0 ,

Hi f Mi , Hi 1 ,i 1, , N , h M H N .

Здесь v – некоторый фиксированный начальный вектор. Если функция f зависит от ключа, то этот вектор можно положить равным нулевому вектору. Если же функция f не зависит от ключа, то для исключения возможности перебора коротких сообщений (при попытках обращений хеш-функции) этот вектор можно составить из фрагментов, указывающих дату, время, номер сообщения и т.д.

Особо выделяют два важных типа криптографических хеш-функций – ключевые и бесключевые. Первые применяются в системах с симметричными ключами. Ключевые хеш-

функции называются кодами аутентификации сообщения

(МАС). Они дают возможность без дополнительных средств гарантировать как правильность источника данных, так и целостность данных в системах с доверяющими друг другу пользователями.

Бесключевые хеш-функции называются кодами обнаружения ошибок (MDC, MIC). Они дают возможность с помощью дополнительных средств (например, шифрования, использования защищѐнного канала или цифровой подписи) гарантировать целостность данных. Эти хеш-функции могут

40

применяться в системах как с доверяющими, так и не доверяющими друг другу пользователями.

4.2.Пример функции хэширования – ГОСТ Р 34.11-94

4.2.1.Общие сведения

Указанный стандарт определяет процедуру вычисления хэш-функции для любой последовательности двоичных данных. Функция хэширования заключается в сопоставлении произвольному набору данных в виде последовательности двоичных символов его образа фиксированной небольшой длины, что позволяет использовать эту функцию в процедурах электронной подписи для сокращения времени формирования и проверки подписи. Эффект сокращения времени достигается за счет вычисления подписи только под образом подписываемого набора данных.

4.2.2. Область применения

Указанный стандарт определяет алгоритм и процедуру вычисления хэш-функции для любой последовательности двоичных символов, которые применяются в криптографических методах обработки и защиты информации, в том числе для реализации процедур электронной подписи (ЭЦП) при передаче, обработке и хранении информации в автоматизированных системах.

Определенная в стандарте функция хэширования используется при реализации систем электронной цифровой подписи на базе асимметричного криптографического алгоритма по ГОСТ Р 34.10-94 “Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма”.

41

4.2.3.Обозначения

Внастоящем документе используются следующие обозначения:

B*

Множество всех конечных слов в алфавите B={0,1}. Чтение слов и нумерация знаков алфавита (символов) осуществляется справа налево (номер правого символа в слове равен единице, второго справа - двум и т.д.).

/A|

Длина слова A <- B*.

Vk (2)

Множество всех бинарных слов длины k.

A||B

Конкатенация слов A, B <- B* - слово длины |A|+|B|, в котором левые |A| символов образуют слово A, а правые |B| символов образуют слово B. Можно также использовать обозначение A||B

= AB.

Ak

Конкатенация k экземпляров слова A(A<- B*).

<N>k

Слово длины k, содержащее двоичную запись вычета N(mоd2k) неотрицательного целого числа

N.

A`

Неотрицательное целое число, имеющее двоичную запись A (A<- b*).

&

Побитовое сложение слов одинаковой длины по модулю 2.

&’

Сложение по правилу A&’B = <A`+B`>,

(k=|A|+|B|)/

42

M

Последовательность двоичных символов, подлежащая хэшированию (сообщение в системе ЭЦП), M <- B*.

h

Хэш-функция, отображающая последователь-

ность M <- B* в слово h(M) <- V256(2).

Ek(A)

Результат зашифрования слова A на ключе K с использованием алгоритма шифрования по ГОСТ 28147 в режиме простой замены (K <-

V256(2), A <-V64(2)).

H

Стартовый вектор хэширования.

e := g

Присвоение параметру e значения g.

<-

Обозначение принадлежности диапазону.

4.2.4. Общие положения

Под хэш-функцией h понимается зависящее от параметра [стартового вектора хэширования H, являющегося словом из V256(2)] отображение:

Для определения хэш-функции необходимы:

алгоритм вычисления шаговой функции хэширования c т.е. отображения:

описание итеративной процедуры вычисления значения хэш-функции h.

4.2.5. Шаговая функция хэширования

Алгоритм вычисления шаговой функции хэширования включает в себя три части, реализующие последовательно:

43

генерацию ключей - слов длины 256 битов с использованием исходных данных слов H, M <- V256(2);

шифрующее преобразование - зашифрование 64битовых подслов слова H на ключах Ki (I=1, 2, 3, 4) с использованием алгоритма по ГОСТ 28147 в режиме простой замены с исходными данными:

H=h4||h3||h2||h1, h1<-V64(2), i=1,4 и набор ключей K1,K2,K3,K4

в результате данного этапа образуется последовательность:

S=s4||s3||s2||s1,

перемешивающее преобразование результата шифрования с исходными данными в виде:

слово H, M<- V256(2) и слово S <- V256(2),

4.2.6. Процедура вычисления хэш-функции

Исходными данными для процедуры вычисления значения функции h является подлежащая хэшированию последовательность M <- B*. Параметром является стартовый вектор хэширования H - произвольное фиксированное слово из

V256(2).

Процедура вычисления функции h на каждой итерации использует следующие величины:

M <- B* - часть последовательности M, не прошедшая процедуру хэширования на предыдущих итерациях;

H <- V256(2) - текущее значение хэш-функции;

S <- V256(2) -текущее значение контрольной суммы;

L <- V256(2) - текущее значение длины обработанной на предыдущих итерациях части последовательности M.

5. ЦИФРОВАЯ ПОДПИСЬ

Цифровая подпись для сообщения является числом, зависящим от самого сообщения и от некоторого секретного, известного только подписывающему субъекту, ключа. При этом

44