ГОСТ Р 34.11-94

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

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

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

ИНФОРМАЦИИ

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

Издание афпргнлънее

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

Предисловие

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

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

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

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

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

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

хэш-функции

Н = 00000000 00000000 00000000 00000000

оооооооо 00000000 оооооооо оооооооо

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

2 -=00000000 оооооооо оооооооо оооооооо оооооооо оооооооо ооосоооо оооооооо

длины текста

L-оооооооо оооооооо оооооооо оооооооо оооооооо оооооооо оооооооо оооооооо

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

L-ОООООООО ОООООООО ОООООООО оооооооо ОООООООО ОООООООО оооооооо 00000100

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

2С656761 7373656D 20736920 73696854, то

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

—хЭД' —73657479 62203233 3D687467 6Е656С20 2С556761 7373656D 20736920 73696854

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

Кх~ 733D2C20 626Е7373 65686573 20657369 74746769 326С6568 79676120 33206D54 к2- 110C733D 1D0C626E 0D166568 16IA2065 130Е7474 090D326C 06417967 4D393320 Кз = 8ЭВ111F3 620C1DFF 730DF216 ЗАВАЕ91А 850013F1 3FA109F2 C7E1F941 F513B239 К4 = А0Е2804Е EE1D620C FF1B73F2 АС0СС5ВА ЕСЕ27АОО А804С05Е Е7В8С7Е1 А18В0АЕС

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

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

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

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

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

Получают

S— Е7860419    0D2A562D    8D345899    03FF3E28

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

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

Е- х (М, Н)- CF9A8C65 Б')5967А4    68А03В8С    42DE7624

D99C4I24    883DA687    561C7DE3    3315С034

7

Полагают H=^S, вычисляют к (L, Н).

Ki — CF68D956 50428833 9АА09С1С 59DE3D15 8C3B417D 6776А6С1 658С24ЕЗ А4248734 к2= 8FCF68D9 ВВ504288 809 W9C 2859DF3D ЗГ8СЗВ41 666676А 5 С7658С24 ВЗ442487 Кз=^ 4C70CF97 CABB50BD ЗС8С65А0 E3D7A6DE 853С8СС4 D1906788 57389А8С 6СВ35В24 Ki = 584E70CF EDCABB50 С53С8065 78E3D7A6 48853С8С EED19867 1657389А 7F5CB35B S- 66B70F5E Е5ЕС8А37 F163F461 3FD42279 468А9528 3CD1602D 61D60593 DD783E86 Е = 2В6ЕС233 DD3848D1 С7ВС89Е4 С6АС997А 2АВС2692 24F74E2B 5FEA7285 09A3AEF7 Вновь полагают Н = S и вычисляют х (2, Н) Ki= 58I7F104 А531В57А 0BD45D84 9C8FDFCA B6522F27 BBIEFCC6 4AF5B00B D7A517A3 К2= Е82759Е0 D2C73DA8 C278D950 I9A6CAC9 I5CC523C 3E8440F5 FC72EBB6 CODDB65A к»= 77483AD9 FBC3DAA0 F7C29CAA 7CB555F0 FB06D1D7 D4968080 841BCAD3 0А9Е56ВС АП 57965 7684ADCB 2D9FBC9C FA4ACA06 088С7СС2 53EFF7D7 46FB3DD2 С0748708 S- 2AEBFA76 С31Е7435 A85FB57D 4930FD05 6F164DE9 1F8A4942 2951A58I 550A582D S = FAFF37A6 F09525F3 15А81669 9F811983 ICFF3EF8 2ЕВ81975 В68СА247 D366C4B1 Таким образом, результат хэширования есть Н = FAFF37A6 E09525F3 15А81669 9F811983 1CFF3EF8 2ЕВ81975 В68СА247 D366C4B1

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

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

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

ШАГ 1

Н = ОООООО0О оооооооо оооооооо оосооооо оооооооо оооооооо 00(00030 оооооооо

М =	73616820	65676173	73656D20	6С616Е69
	6769726F	20656874	2065736F	70707553
Ki =	73736720	61656Q65	6C6D7273	20206F6F
	656С2070	67616570	616Е6875	73697453

ГОСТ Р 34.11 —94

Е —	47E26AFD	ЗЕ7278А1	7D473785	06140773
A3D97E7E ШАГ 4		А744СВ43	08АА4С24	3352С745
Н =	47E26AFD	ЗЕ7278А1	7D473785	06140773
	A3D97E7E	А744СВ43	08АА4С24	3352С745
2 =	73616820	65676173	73656D20	6С61Е1СЕ
	DBE2D48F	509А88В1	40CDE7D6	DED5E173
К| =	340Е7848	83223В67	025ААААВ	DDA5F1F2
	5B6AF7ED	1575DE87	19Е64326	D2BDF236
	03DC0ED0	F4CD26BC	8B595F13	F5A4A55E
	А8В063СВ	ED3D7325	6511662А	7963008D
Кз-	C954EF19	D0779A68	ED37D3FB	7DA5ADDC
	4A9D0277	78EF765B	С4731191	7ЕВВ21В1
Ki=	6D12BC47	D9363D19	1E3C696F	28F2DC02
	F2137F37	64Е4С18В	69CCFBF8	EF72B7E3
S —	790DD7A1	066544ЕА	2829563С	3C39D781
	25EF9645	EE2C05DD	A5ECAD92	2511A4D1
н-	0852F562	3B89DD57	AEB4781F	E54DF14E
	EAFBC135	0613763А	OD770AA6	57ВА1А47
Таким	образом, результат хэширования есть
	0852F562	3B89DD57	AEB4781F	E54DF14E
	EAFBC135	0613763А	0D770AA6	57ВА1А47

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

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

11

ВВЕДЕНИЕ

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

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

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

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

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

IV

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

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

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

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

Information technology.

Cryptographic Data Security.

Hashing function

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

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

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

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

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

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

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

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

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

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

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

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

|А| — длина слова At В*.

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

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

АЦ В — АВ.

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

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

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

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

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

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

h — хош-ф>нкция, отображающая последовательность Мб В* в слове р(М>б У₂5б(2).

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

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

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

ГОСТ Р 34.11-94

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

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

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

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

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

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

РассмотримХ=(Ь₃₅₆, Ь₂₅₅, • •    b,)6V₂₅₆(2).

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

=¹11б1Ы1- ■ -bi =

— ^32l!^3l|| • • • ||^1>

где Xj=(bix64.....b(i-i)x64+i)CV_e4(2), i—1,4;

’ll —(b/xie, .. ., b(j-i)_Xi6+i)6V_I6(2), j= 1,16;

6_k=(b_tx8,..., b,_k-i₎xe±i)ev_a(2)_> k=i732.

Обозначают A(X)=(x, ф х₂),]х₄||хз||х₂.

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

слова S₃₃jj... IIS, в слово;<_W32)^|I|. . .fS _fi>,

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

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

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

—    параметры: слова С, (i = 2, 3, 4), имеющие значения C₂=C₄=0^2ss и С₃ = 1 ®0⁸1¹⁶0²⁴1¹⁶0^s(0⁸1⁸)²1 ^(О⁸1⁸)¹( 1⁸0³)¹.

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

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

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

w=uav, k,=p(W).

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

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

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

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

U:=A(U)®C„ V:=A(A(V))_f \V: = U,®V, K,= P(W).

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

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

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

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

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

H-hJh₃|Mh_b Ь,ГЛ^(2), i = M

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

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

5г~--Ек,0ч), где 1-1, 2, 3, 4.

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

$ — sjssjjsjs,.

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

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

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

слока Н, М(.У₂5б(2) и слово S6 Уг5в(2).

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

*:V_sftbp........-У_шв(2)

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

V!- ■ -llv,, VtfV_l6(2), I== 1,16

ь СЛОВО

^глв‘>?2Ф¹:з®^®'Ч1зФЧ1б8¹3|в1- ■ Jv2-

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

х(м,

где ф¹- i-я степень преобразования ф.

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

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

ГОСТ Р 34.lt—94

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

Мб В* — часть последовательности М, не Прошедшая процедуры хэширования на предыдущих итерациях; не Vase (2) —текущее значение хэш-функции;

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

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

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

Этап 1

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

1.1    М:=М

1.2    Н: = Н

1.3    Е:=0^ЗЛ«

1.4    L:—0^26ti

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

Этап 2

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

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

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

2.2    L: — <L+|M|>₃₅₆

2.3    ||М

2.4    Е; = £®'М'

2.5    Н:^х(М', Н)

2.6    H:=x(L, Н)

2.7    Н:=х(Е, Н)

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

Этап 3

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

3.2    H:-x(M_s, Н)

3.3    L:= <L-j-25b>₂₆₆

3.4    Е: = £ф'М_в

3.5    М:=М_Р

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

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

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

5

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

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

Заполнение узлов замены яь я* • • > и значение стартового вектора хэширования Н, указанные в данном приложении, рекомендуется использовать только в проверочных примерах для настоящего стандарта А1 Использование алгоритма ГОСТ 28147 В качестве шифрующего преобразования в приводимых ниже примерах используется алгоритм ГОСТ 28147 з режиме простой замены

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

	8	7	6	5	4	3	о	1
0	1	D	4	6	7	5	Е	4
1	F	В	В	С	D	в	В	А
2	D	4	А	/	А	1	4	9
3	0	1	0	1	1	D	С	2
4	5	3	7	5	0	А	6	D
5	7	F	2	F	8	3	D	8
6	А	5	1	П	9	4	Р	0
7	4	9	D	8	F	2	А	Е
8	9	0	3	4	Е	Е	2	6
9	2	А	6	А	4	F	3	В
10	3	Е	8	9	6	(.	8	I
И	Е	7	5	Е	С	7	1	С
12	6	6	9	0	В	6	0	7
13	В	8	С	3	2	0	7	F
14	8	2	F	в	5	9	5	5
15	С	С	Е	2	3	В	9	3
В столбце с номером			!, J = 1.8,	в строке	с	номером 1,	1=0,15,	ПрИ£

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

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

АЗ Примеры вычисления значения хэш-функции В качестве стартового вектора хэширования принимают, например, нулевой вектор

Н=00000ООО оооооооо оооооооо оооооооо

оооооооо оооооооо оооооооо оооооооо

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

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

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

текста

1

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

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

₅₆ (2) 1 отображение

1 : С¹    V₂₅fi(2).

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

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

*: V₂₃₆(J) xV>r_b(2)......V_re<2);

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