ГОСТ 34.311-95 Информационная технология. Криптографическая защита информации. Функция хэширования

БЗ 3-94/131

ГОСТ Р 34.11—94

ГОСУДАРСТВЕННЫЙ СТАНДАРТ РОССИЙСКОЙ ФЕДЕРАЦИИ

ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ

КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА

ИНФОРМАЦИИ

ФУНКЦИЯ ХЭШИРОВАНИЯ

Издание афщяалыгое

ГОССТАНДАРТ РОССИИ Москва

Предисловие

1 РАЗРАБОТАН Главным управлением безопасности связи Федерального агентства правительственной связи и информации ir Всероссийским научно-исследовательским институтом стандартизации

ВНЕСЁН Техническим комитетом по стандартизации ТК 22 «Информационная технология» и Федеральным агентством правительственной связи и информации

2 ПРИНЯТ И ВВЕДЕН В ДЕЙСТВИЕ Постановлением Госстандарта России от 23.05.94 № 154

3 ВВЕДЕН ВПЕРВЫЕ

© Издательство стандартов, 1994

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

Госстандарта России

it

СОДЕРЖАНИЕ

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

2 Нормативные ссылки...........I

3 Обозначения.............I

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

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

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

Приложение А Проверочные примеры .

О) СО tO

ВВЕДЕНИЕ

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

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

Криптографические методы защиты информации являются объектом серьезных научных исследований и стандартизации на национальных, региональных и международных уровнях.

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

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

ГОСУДАРСТВЕННЫЙ СТАНДАРТ РОССИЙСКОЙ ФЕДЕРАЦИИ

Информационная технология

КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ

Функция хэширования

Information technology.

Cryptographic Data Security-Hashing function

Дата введения 1995—01—01

1 ОБЛАСТЬ ПРИМЕНЕНИЯ

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

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

2 НОРМАТИВНЫЕ ССЫЛКИ

В настоящем стандарте использованы ссылки на сле^}^гющие стандарты:

ГОСТ 28147—89 Системы обработки информации. Защита криптографическая. Алгоритмы криптографического преобразования.

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

3 ОБОЗНАЧЕНИЯ

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

Издание официальное

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

|А| — длина слова Af*B*.

Vk(2) —множество всех бинарных слов длины к.

А||В — конкатенация слов А, В 6 В* — слово длины |А| + |В|, в котором левые |А| символов образуют слово А» а правые |В| символов образуют слово В. Можно также использовать обозначение

АЦВ-АВ.

А ^к~~ конкатенация к экземпляров слова A (At В*),

— слово длины к, содержащее двоичную запись вычета N(mod 2^К) неотрицательного целого числа N.

А — неотрицательное целое число, имеющее двоичную запись A (At В*).

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

0 ' — сложение по правилу А Ф'В = <А+В>_к, (к = |А|—|В|).

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

h — хли-ф>нкция, отображающая последовательность Мб В* в СЛОВО Р (М> б V256 (2) .

Е_к(А) рез>льтат зашифрования слова А на ключе К с использованием алгоритма шифрования по ГОСТ 28147 в режиме простой замены (K6V₂₅₅(2), Аб V₆4(2)).

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

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

4 ОБЩИЕ ПОЛОЖЕНИЯ

Под хэш-функцией h понимается зависящее от параметра гартового вектора хэширования Н, являющегося словом из

56(2)) отображение

I

i

С

^25Г,(2).

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

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

отображения

х: V,_3C<2) х\\Д2>

Vre<2);

— описание итеративном процедуры вычисления значения

хэш-функции h.

б ШАГОВАЯ ФУНКЦИЯ ХЭШИРОВАНИЯ

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

— генерацию ключей — слов длины 256 битов;

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

— перемешивающее преобразование результата шифрования.

5.1 Генерация ключей.

РассмотримХ=(Ь₃₅₆, Ь₂₅₅» • • b^eVa^).

Пусть Х = х₄||хз||х₂||х₁ =

^lelfaibll- ■ -hi =

= ^32ll^3t|| • • • |Rl,

где X₃=(bix64 ,. .., b(i-nx64+i)6V_e4(2), i=l,4;

⁷J)=(Wxie, .. ., b<j-1)_Xi&-fl)6V,₆(2), j = 1,16;

6_k=(bnx8,..., b_(k_i,x«4a)ev_a(2), k = П35.

Обозначают A(X)=(x, © x₂)]x JxJxg.

Используют преобразование P: V_26G(2)--------^V₂₆₆(2)

слова £₃₉jj... |R, в слово^32)1- • •!$ ?i>,

где <p(i + l+4(k—l))=8l+k, 1=0н~3, k=l-*-8.

Для генерации ключей необходимо использовать следующие исходные данные;

— слова Н, M6V₂5e(2);

— параметры: слова Q (i = 2, 3, 4), имеющие значения С₂=с₄ = 0²⁰⁶ и C_s=lWl¹4)*l‘^04^e)4^0⁸l⁸)⁴(l⁸0^s)⁴.

При вычислении ключей реализуется следующий алгоритм -

1 Присвоить значения J: — 1, U: = H, V: = M.

2 Выполнить вычисление

W = U®V, K, = P(W).

3 Присвоить i: —Н-1.

4 Проверить условие i=5.

При положительном исходе перейти к шагу 7. При отрицательном — перейти к шагу 5.

5 Выполнить вычисление _

U:=A(U)®q, V: = A(A(V))_f W: = U,®V, K,= P(W).

6 Перейти к шагу 3.

7 Конец работы алгоритма.

5.2 Шифрующее преобразование

На данном этапе осуществляется зашифрование 64-битных подслов слова Н на ключах Ki (i — 1, 2, 3, 4).

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

H-hJhelhdht, h₁6V_G4(2), i = M

и набор ключей Кь Кг, Кз, К*.

Реализуют алгоритм зашифрования и получают слова

Si —Ек_г(Н]), где 1=1, 2_} 3, 4.

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

S^sJsJIsJs,.

5 3 Перемешивающее преобразование

г а д< ином этапе осуществляется перемешивание полученной дослещ вательности с примененьем регистра сдвига.

Исходными данными являются:

слоьа Н, McV₂56(2) и слово S6 Уг5в(2).

Пусть отображение

......“^V₂se(2)

преобразует слово

V! • ■ -llv,, ^r/»6V_i4(2), J=ГГ 16

ь слово

^rH<$^r/2&y3®^rl_ie4i3&Viell^rhell-■ -1Мг-

Тогда в качестве значения шаговой функции хэширования принимается слово

х(М, Н)=ф^п|(Н^,Фф(МФ((»¹²(5))), где ф¹ - i-я степень преобразования ф.

6 ПРОЦЕДУРА ВЫЧИСЛЕНИЯ ХЭШ-ФУНКЦИИ

Исходными данными для процедуры вычисления значения функции h является подлежащая хэшированию последовательность Mf< В*. Параметром является стартовый вектор хэширования Н — произвольное фиксированное слово из V₂se (2).

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

Мб В* — часть последовательности М, не Прошедшая процедуры хэширования на предыдущих итерациях;

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

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

L6 У₂5б(2) — текущее значение длины обработанной на предыдущих итерациях части последовательности М.

Алгоритм вычисления функции h включает в себя этапы:

Этап 1

Присвоить начальные значения текущих величин

1.1 М:=М

1.2 Н: = Н

1.3 Е: = (Р«

1.4 L: = О²⁶⁰

1.5 Переход к этапу 2

Этап 2

2.1 Проверить условие )М|>256.

При положительном исходе перейти к этапу 3.

В противном случае выполнить последовательность вычисле-ний:

2.2 L:= <L+|M|>₂₅₆

2.3 М^/:=*0??⁶"^,м^ ||М

2.4 2; = £®'М'

2.5 Н:-*(М', Н)

2.6 H:=*(L, Н)

27 Н:—х(2, Н)

2.8 Конец работы алгоритма Этап 3

3.1 Вычислить подслово М₃6 V₂₅₆(2) слова М (M=M_P||M_S). Далее выполнить последовательность вычислений:

3.2 H:~x(M_s, Н)

3.3 L:= <jL"j“25b>256

3.4

3.5 М: =М_Р

3.6 Перейти к этапу 2.

Значение величины Н, полученное на шаге 2.7, является значением функции хэширования h (М).

Проверочные примеры для вышеизложенной процедуры вычисления хэш-функции приведены в приложении А.

ПРИЛОЖЕНИЕ А (справочное)

ПРОВЕРОЧНЫЕ ПРИМЕРЫ

Заполнение узлов замены Яь . ., Яз и значение стартового вектора хэширования Н, указанные в данном приложении, рекомендуется использовать только в проверочных примерах для настоящего стандарта А1 Использование алгоритма ГОСТ 28147

В качестве шифрующего преобразования в приводимых ниже примерах используется алгоритм ГОСТ 28147 з режиме простой замены

При этом заполнение узлов замены щ, лэ, . .,ла блока подстановки л следующее.

В столбце с номером j, j^=l,8, в строке с номером i, i=0,15, приведено значение ttj(i) в шестнадцатеричной системе счисления

А2 Представление векторов

Последовательности двоичных символов будем записывать как строки шестнадцатеричных цифр, в которых каждая цифра соответствует четырем знакам ее двоичного представления

АЗ Примеры вычисления значения хэ ш-ф у н к ц и и

В качестве стартового вектора хэширования принимают, например, нулевой вектор

н = 00000000 оооооооо 00000000 OOGOOOOO оооооооо оооооооо оооооооо оооооооо

А3 1 Пусть необходимо выполнить хэширование сообщения

М= 73657479 62203233 3D687467 6Е656С20 2С656761 7373656D 20736920 73696854

Выполняют присвоение начальных значений:

текста

М —73657479 ^203233 3D687467 6Е656С20 9С656761 70.C356D 20736920 73696854

хэш-функции

H-OOOGOOOO 00000000 00000000 00000000

оооооооо оооооооо 00000000 OQOOOOOO

суммы блоков текста

z-оооооооо оооооооо оооооооо оооооооо оооооооо оооооооо ооосоооо оооооооо

длины текста

L —оооооооо оооооооо оооооооо оооооооо оооооооо оооооооо оооооооо оооооооо

Так как длина сообщения, подлежащего хэшированию, равна 256 битах (32 байтам),

L — ОС000000 ОООООООО ОООООООО ОООООООО ОООООООО ОООООООО ОООООООО 00000100

М'-М- 73657479 62203233 3D687167 6Е656С20

2С656761 7373656D 20736920 73696854, то

нет необходимости дописывать текущий блок нулями,

£=~М'=« 73657479 62203233 3D687467 6Е656С20 2С556761 7373656D 20736920 73696854

Переходят к вычислению значения шаговой функции хэширования х (М, Н). Вырабатывают ключи

Осуществляют зашифрование 64-битных подслов блока Н с помощью алго-ритма по ГОСТ 28147.

Блок hi — ОООООООО 00000000 зашифровывают на ключе Ki и получают si-* = 42АВВССЕ 32ВС0В1В.

Блок 1*2 = 00000000 00000000 зашифровывают на ключе К2 и получают S2 = -5203ЕВС8 5D9BCFFD.

блок ha-=00200000 00000000 зашифровывают на ключе Кз и получают s₃ = «8D345899 OOFFOE28.

Блок 1*4 = 00000000 00000000 зашифровывают на ключе Кл и получают s₄== -Е7860419 0D2A562D.

Получают

S- Е7860419 0D2A562D 8D345899 O3FF0E28

5203ЕВС8 5D9BCFFD 42АВВССЕ 32ВС0В1В

Выполняют перемешивающее преобразование с применением регистра сдви~ га и получают

Е-х(М, Н)« CF9A8C65 Е’)5967А4 68А03Е8С 42DE7624

D99C4I24 883DA687 561C7DE3 3315С034

Полагают Н — Е, вычисляют к (L, Н).

А32 Пусть необходимо выполнить хэширование сообщения

М- 7365 74796220 3035203D 20687457 6Е656С20 73616820 65676173 73656D20 6С616Е69 6769726F 20656874 2065736F 70707553

Так как длина сообщения, подлежащего хэшированию, равна 400 битам (50 байтам), то разбивают сообщение на два блока и второй (старший) блок дописывают нулями В процессе вычислений получают-

ШАГ I

н-оооооооо оооооооо оооозооо оооооооо оооооооо оооооооо ОСИ¹ ооооо оооооооо

УДК 681.3.06:006.354 П85 ОКСТУ 5002

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

Редактор Л. В. Афанасенко Технический редактор Н. С. Гришанова Корректор А. С. Черноусова

Сдано в наб 24 06 94 Подп в печ 19 08 94 Уел п л 0 93 Уел кр.*отт В,9|.

Уч-изд л 0,84 Тираж 300 экз С 1585

Ордена «Знак Почета» Издательство стандартов, 107076, Москва, Колодезный пер.. 14 Тнп «Московский печатник» Москва, Лялин пер , 6 Зак 208