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

ГОСТ Р 34.11-94
Группа П85

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


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

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

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

Information technology.
Cryptographic Data Security.
Hashing function

ОКСТУ 5002

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

Предисловие

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

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

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

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

ВВЕДЕНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- длина слова .

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

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

- конкатенация экземпляров слова .

- слово длины , содержащее двоичную запись вычета неотрицательного целого числа .

- неотрицательное целое число, имеющее двоичную запись .

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

- сложение по правилу , .

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

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

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

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

: = - присвоение параметру значения .

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

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

-------.

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

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

------- ;

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

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

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

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

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

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

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

Рассмотрим .

Пусть

,

где ;

;

.

Обозначают .

Используют преобразование --------
слова в слово, ,

где

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

- слова ;

- параметры: слова (=2, 3, 4), имеющие значения

и .

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

1 Присвоить значения

.

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

3 Присвоить .

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

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

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

, , , .

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

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

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

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

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

,

и набор ключей , , , .

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

, где =1, 2, 3, 4.

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

.

5.3 Перемешиваюшее преобразование

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

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

слова и слово .

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

--------

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

, ,

в слово

.

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

,

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

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

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

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

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

- текущее значение хэш-функции;

- текущее значение контрольной суммы;

- текущее значение длины обработанной на предыдущих итерациях части последовательности .

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

Этап 1

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

еличин

1.1

1.2

1.3

1.4

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

Этап 2

2.1 Проверить условие .

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

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

2.2

2.3

2.4

2.5

2.6

2.7

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

Этап 3

3.1 Вычислить подслово слова . Далее выполнить последовательность вычислений:

3.2

3.3

3.4

3.5

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

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

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

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

ПРИЛОЖЕНИЕ А

(справочное)

Заполнение узлов замены , ,..., и значение стартового вектора хэширования , указанные в данном приложении, рекомендуется использовать только в проверочных примерах для настоящего стандарта.

А.1 Использование алгоритма ГОСТ 28147

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

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

	8	7	6	5	4	3	2	1
0	1	D	4	6	7	5	E	4
1	F	B	B	C	D	8	B	A
2	D	4	A	7	A	1	4	9
3	0	1	0	1	1	D	C	2
4	5	3	7	5	0	A	6	D
5	7	F	2	F	8	3	D	8
6	A	5	1	D	9	4	F	0
7	4	9	D	8	F	2	A	E
8	9	0	3	4	E	E	2	6
9	2	A	6	A	4	F	3	B
10	3	E	8	9	6	С	8	1
11	E	7	5	E	C	7	1	C
12	6	6	9	0	B	6	0	7
13	B	8	C	3	2	0	7	F
14	8	2	F	B	5	9	5	5
15	C	C	E	2	3	B	9	3

В столбце с номером , , в строке с номером , , приведено значение в шестнадцатеричной системе счисления.

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

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

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

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

		=	00000000	00000000	00000000	00000000
			00000000	00000000	00000000	00000000

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

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

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

текста

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

хэш-функции

		=	00000000	00000000	00000000	00000000
			00000000	00000000	00000000	00000000

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

		=	00000000	00000000	00000000	00000000
			00000000	00000000	00000000	00000000

длина текста

		=	00000000	00000000	00000000	00000000
			00000000	00000000	00000000	00000100

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

		=	00000000	00000000	00000000	00000000
			00000000	00000000	00000000	00000100

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

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

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

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

Вырабатывают ключи

		=	733D2C20	65686573	74746769	79676120
			626Е7373	20657369	326С6568	33206D54
		=	110C733D	0D166568	130E7474	06417967
			1D00626E	161A2065	090D326C	4D393320
		=	80B111F3	730DF216	850013F1	C7E1F941
			620C1DFF	3ABAE91A	3FA109F2	F513B239
		=	A0E2804E	FF1B73F2	ECE27A00	E7B8C7E1
			EE1D620C	AC0CC5BA	A804C05E	A18B0AEC

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

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

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

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

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

Получают

		=	E7860419	0D2A562D	8D345899	00FF0E28
			5203ЕВС8	5D9BCFFD	42АВВССЕ	32ВС0В1В

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

		=	CF9A8C65	505967А4	68А03В8С	42DE7624
			D99С4124	883DA687	561C7DE3	3315С034

Полагают , вычисляют :

	=	CF68D956	9АА09С1С	8C3B417D	658C24E3
		50428833	59DE3D15	6776А6С1	A4248734
	=	8FCF68D9	809AА09С	3С8С3В41	C7658C24
		ВВ504288	2859DE3D	666676А6	B3A42487
	=	4E70CF97	3С8065А0	853С8СС4	57389А8С
		CABB50BD	E3D7A6DE	D1996788	5CB35B24
	=	584E70CF	С53С8065	48853С8С	1657389A
		EDCABB50	78E3D7A6	EED19867	7F5CB35B
	=	66B70F5E	F163F461	468А9528	61D60593
		Е5ЕС8А37	3FD42279	3CD1602D	DD783Е86
	=	2В6ЕС233	С7ВС89Е4	2АВС2692	5FEA7285
		DD3848D1	С6АС997А	24F74E2B	09A3AEF7

Вновь полагают и вычисляют :

	=	5817F104	0BD45D84	B6522F27	4AF5B00B
		А531В57А	9C8FDFCA	BB1EFCC6	D7A517A3
	=	Е82759Е0	C278D950	15СС523С	FC72EBB6
		D2C73DA8	19А6САС9	3E8440F5	C0DDB65A
	=	77483AD9	F7C29CAA	EB06D1D7	841BCAD3
		FBC3DAA0	7CB555F0	D4968080	0A9E56BC
	=	А 1157965	2D9FBC9C	088С7СС2	46FB3DD2
		7684ADCB	FA4ACA06	53EFF7D7	C0748708
	=	2AEBFA76	A85FB57D	6F164DE9	2951A581
		С31Е7435	4930FD05	1F8A4942	550A582D
	=	FAFF37A6	15A81669	2CFF3EF8	B68CA247
		E09525F3	9F811983	2ЕВ81975	D366C4B1

Таким образом, результат хеширования есть

	=	FAFF37A6	15A81669	1CFF3EF8	B68CA247
		E09525F3	9F811983	2ЕВ81975	D366C4B1

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

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

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


ШАГ 1

		=	00000000	00000000	00000000	00000000
			00000000	00000000	00000000	00000000

		=	73616820	65676173	73656D20	6С616Е69
			6769726F	20656874	2065736F	70707553
		=	73736720	61656965	686D7273	20206F6F
			656С2070	67616570	616E6875	73697453
		=	14477373	0С0С6165	1F01686D	4F002020
			4С50656С	04156761	061D616E	1D277369
		=	CBFF14B8	6D04F30C	96051FFE	DFFFB000
			35094CAF	72F9FB15	7CF006E2	AB1AE227
		=	ЕВАССВ00	F7006DFB	Е5Е16905	B0B0DFFF
			ВА1С3509	FD118DF9	F61B830F	F8C554E5
		=	FF41797C	EEAADAC2	43C9B1DF	2E14681C
			EDDC2210	1EE1ADF9	FA67E757	DAFE3AD9
		=	F0CEEA4E	368B5A60	C63D96C1	E5B51CD2
			A93BEFBD	2634F0AD	CBBB69CE	ED2D5D9A

ШАГ 2

		=	F0CEEA4E	368B5A60	C63D96C1	Е5В51СD2
			A93BEFBD	2634F0AD	CBBB69CE	ED2D5D9A
		=	00000000	00000000	00000000	00007365
			74796220	3035203D	20687467	6E656C20
		=	F0C6DDEB	CE3D42D3	EA968D1D	4EC19DA9
			36Е51683	8ВВ50148	5A6FD031	60В790ВА
		=	16А4С6А9	F9DF3D3B	E4FC96EF	5309C1BD
			FB68E526	2CDBB534	FE161C83	6F7DD2C8
		=	C49D846D	1780482С	9086887F	C48C9186
			9DCB0644	D1E641E5	A02109AF	9D52C7CF
		=	BDB0C9F0	756Е9131	E1F290EA	50E4CBB1
			1CAD9536	F4E4B674	99F31E29	70C52AFA
		=	62А07ЕА5	EF3C3309	2СЕ1В076	173D48CC
			6881ЕВ66	F5C7959F	63FCA1F1	D33C31B8
		=	95ВЕА0ВЕ	88D5AA02	FE3C9D45	436CE821
			В8287СВ6	2СВС135В	3E339EFE	F6576CA9

ШАГ 3

		=	95BEA0BE	88D5AA02	FE3C9D45	436CE821
			В8287СВ6	2СВС135В	3E339EFE	F6576СА9
		=	00000000	00000000	00000000	00000000
			00000000	00000000	00000000	00000190
		=	95FEB83E	ВЕ3С2833	A09D7C9E	BE45B6FE
			88432CF6	D56CBC57	AAE8136D	02215В39
		=	8695FEB8	1ВВЕ3С28	E2A09D7C	48ВE45В6
			DA88432C	EBD56CBC	7FABE813	F292215B
		=	В9799501	141В413С	1ЕЕ2А062	0СВ74145
			6FDA88BC	D0142A6C	FА80АА16	15F2FDB1
		=	94В97995	7D141B41	С21ЕЕ2А0	040СВ741
			346FDA88	46D0142A	BDFA81AA	DC1562FD
		=	D42336E0	2А0А6998	6С65478А	3D08A1B9
			9FDDFF20	4808Е863	94FD9D6D	F776A7AD
		=	47E26AFD	3Е7278А1	7D473785	06140773
			A3D97E7E	А744СВ43	08АА4С24	3352С745

ШАГ 4

		=	47E26AFD	3Е7278А1	7D473785	06140773
			A3D97E7E	А744СВ43	08АА4С24	3352С745
		=	73616820	65676173	73656D20	6061E1CE
			DBE2D48F	509A88B1	40CDE7D6	DED5E173
		=	340E7848	83223B67	025AAAAB	DDA5F1F2
			5B6AF7ED	1575DE87	19E64326	D2BDF236
		=	03DC0ED0	F4CD26BC	8B595F13	F5A4A55E
			А8В063СВ	ED3D7325	6511662А	7963008D
		=	C954EF19	D0779A68	ED37D3FB	7DA5ADDC
			4A9D0277	78ЕF765В	С4731191	7ЕВВ21В1
		=	6D12BC47	D9363D19	1Е3С696F	28F2DC02
			F2137F37	64Е4С18В	69CCFBF8	EF72B7E3
		=	790DD7A1	066544ЕА	2829563С	3C39D781
			25EF9645	EE2C05DD	A5ECAD92	2511A4D1
		=	0852F562	3B89DD57	AEB4781F	E54DF14E
			EAFBC135	0613763А	0D770AA6	57ВА1А47

Таким образом, результат хэширования есть

		=	0852F562	3B89DD57	AEB4781F	E54DF14E
			EAFBC135	0613763А	0D770AA6	57ВА1А47