БЗ 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 в режиме простой замены (K6V255(2), Аб V64(2)).
Н - стартовый вектор хэширования.
е ~g— присвоение параметру е значения g.
4 ОБЩИЕ ПОЛОЖЕНИЯ
Под хэш-функцией h понимается зависящее от параметра гартового вектора хэширования Н, являющегося словом из
56(2)) отображение
I
i
С
^25Г,(2).
Для определения хэш-функции необходимы:
— алгоритм вычисления шаговой функции хэширования и, т. е.
отображения
х: V,3C
Vre<2);
— описание итеративном процедуры вычисления значения
хэш-функции h.
б ШАГОВАЯ ФУНКЦИЯ ХЭШИРОВАНИЯ
Алгоритм вычисления шаговой функции хэширования включает в себя три части, реализующие последовательно:
— генерацию ключей — слов длины 256 битов;
— шифрующее преобразование — зашифрование 64-битных подслов слова Н на ключах Ki (i=l, 2, 3, 4) с использованием алгоритма по ГОСТ 28147 в режиме простой замены;
— перемешивающее преобразование результата шифрования.
5.1 Генерация ключей.
РассмотримХ=(Ь356, Ь255» • • b^eVa^).
Пусть Х = х4||хз||х2||х1 =
^lelfaibll- ■ -hi =
= ^32ll^3t|| • • • |Rl,
где X3=(bix64 ,. .., b(i-nx64+i)6Ve4(2), i=l,4;
7J)=(Wxie, .. ., b 6k=(bnx8,..., b(k_i,x«4a)eva(2), k = П35. Обозначают A(X)=(x, © x2)]x JxJxg. Используют преобразование P: V26G(2)--------^V266(2) слова £39jj... |R, в слово^32)1- • •!$ ?i>, где Для генерации ключей необходимо использовать следующие исходные данные; — слова Н, M6V25e(2); — параметры: слова Q (i = 2, 3, 4), имеющие значения С2=с4 = 0206 и Cs=lWl14)*l‘^04e)4^08l8)4(l80s)4. При вычислении ключей реализуется следующий алгоритм - 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). Для шифрующего преобразования необходимо использовать следующие исходные данные: и набор ключей Кь Кг, Кз, К*. Реализуют алгоритм зашифрования и получают слова Si —Екг(Н]), где 1=1, 2} 3, 4. В результате данного этапа образуется последовательность 5 3 Перемешивающее преобразование г а д< ином этапе осуществляется перемешивание полученной дослещ вательности с примененьем регистра сдвига. Исходными данными являются: Пусть отображение ......“^V2se(2) преобразует слово V! • ■ -llv,, r/»6Vi4(2), J=ГГ 16 ь слово rH<$r/2&y3®rlie4i3&Viellrhell-■ -1Мг- Тогда в качестве значения шаговой функции хэширования принимается слово х(М, Н)=фп|(Н,Фф(МФ((»12(5))), где ф1 - i-я степень преобразования ф. 6 ПРОЦЕДУРА ВЫЧИСЛЕНИЯ ХЭШ-ФУНКЦИИ Исходными данными для процедуры вычисления значения функции h является подлежащая хэшированию последовательность Mf< В*. Параметром является стартовый вектор хэширования Н — произвольное фиксированное слово из V2se (2). Процедура вычисления функции h на каждой итерации использует следующие величины: Мб В* — часть последовательности М, не Прошедшая процедуры хэширования на предыдущих итерациях; HeV2M(2) —текущее значение хэш-функции; 2 6 V256(2) —текущее значение контрольной суммы; L6 У25б(2) — текущее значение длины обработанной на предыдущих итерациях части последовательности М. Алгоритм вычисления функции h включает в себя этапы: Этап 1 Присвоить начальные значения текущих величин 1.1 М:=М 1.2 Н: = Н 1.3 Е: = (Р« 1.4 L: = О260 1.5 Переход к этапу 2 Этап 2 2.1 Проверить условие )М|>256. При положительном исходе перейти к этапу 3. В противном случае выполнить последовательность вычисле-ний: 2.2 L:= 256 2.3 М/:=*0??6",м^ ||М 2.4 2; = £®'М' 2.5 Н:-*(М', Н) 2.6 H:=*(L, Н) 27 Н:—х(2, Н) 2.8 Конец работы алгоритма Этап 3 3.1 Вычислить подслово М36 V256(2) слова М (M=MP||MS). Далее выполнить последовательность вычислений: 3.2 H:~x(Ms, Н) 3.3 L:= 256 3.4 3.5 М: =МР 3.6 Перейти к этапу 2. Значение величины Н, полученное на шаге 2.7, является значением функции хэширования h (М). Проверочные примеры для вышеизложенной процедуры вычисления хэш-функции приведены в приложении А. ПРИЛОЖЕНИЕ А (справочное) ПРОВЕРОЧНЫЕ ПРИМЕРЫ Заполнение узлов замены Яь . ., Яз и значение стартового вектора хэширования Н, указанные в данном приложении, рекомендуется использовать только в проверочных примерах для настоящего стандарта А1 Использование алгоритма ГОСТ 28147 В качестве шифрующего преобразования в приводимых ниже примерах используется алгоритм ГОСТ 28147 з режиме простой замены При этом заполнение узлов замены щ, лэ, . .,ла блока подстановки л следующее. 8 7 6 5 4 3 о А 1 0 1 D 4 6 7 5 Е 4 1 F В В С D 8 В А 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 f 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, j^=l,8, в строке с номером i, i=0,15, приведено значение ttj(i) в шестнадцатеричной системе счисления А2 Представление векторов Последовательности двоичных символов будем записывать как строки шестнадцатеричных цифр, в которых каждая цифра соответствует четырем знакам ее двоичного представления АЗ Примеры вычисления значения хэ ш-ф у н к ц и и В качестве стартового вектора хэширования принимают, например, нулевой вектор А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 суммы блоков текста длины текста Так как длина сообщения, подлежащего хэшированию, равна 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 Переходят к вычислению значения шаговой функции хэширования х (М, Н). Вырабатывают ключи Ki = 733D2C20 626Е7373 65686573 20657369 74746769 326С6568 79676120 33206D54 1I0C733D ! D0C626E 0D166568 I6IА2065 130Е7474 090D326C 06417967 4D393320 Кз- 8ЭВ1ИРЗ 620C1DFF 730DF2I6 3ABAE9IА 850013F1 3FA109F2 C7EIF941 F513B239 К* = А0Е2804Е EEJD620C FFSB73F2 АС0СС5ВА ЕСЕ27АОО А804С05Е Е7В8С7Е1 А18В0АЕС Осуществляют зашифрование 64-битных подслов блока Н с помощью алго-ритма по ГОСТ 28147. Блок hi — ОООООООО 00000000 зашифровывают на ключе Ki и получают si-* = 42АВВССЕ 32ВС0В1В. Блок 1*2 = 00000000 00000000 зашифровывают на ключе К2 и получают S2 = -5203ЕВС8 5D9BCFFD. блок ha-=00200000 00000000 зашифровывают на ключе Кз и получают s3 = «8D345899 OOFFOE28. Блок 1*4 = 00000000 00000000 зашифровывают на ключе Кл и получают s4== -Е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, Н). Ki— CF68D956 50428833 9ЛА09С1С 59DE3D 15 8C3B417D 6776А6С1 658С24ЕЗ А4248734 к2- 8FCF68D9 ВВ504288 609 W9C 2859DE3D ЗГ8СЗВ41 666676А 5 С7658С24 ВЗ 4 42487 Кз- 4C70CF97 CABB50BD ЗС8С65А0 E3D7A6DE 853С8СС4 D19Э6788 5738948С 6СВ35В24 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, Н) К1 — 58I7FI04 А531В57А 0BD45D84 9C8FDFCA B6522F27 BB1EFCC6 4AF5BOOB D7A517A3 К2= Е82759Е0 D2C73DA8 C278D950 I9A6CAC9 15СС523С 3E8440F5 FC72EBB6 C0DDB65A Кз = 77483A D9 FBC3DAA0 F7C29CAA 7CB555F0 FB06D1D7 D4968080 841BCAD3 ОАЭЕ56ВС к*= АП 57965 7684ADCB 2D9FBC9C F А4А СА06 D88C7CC2 53EFF7D7 46FB3DD2 С0748708 S- 2AEBFA76 С31Е7435 A85FB57D 4930FD05 6F164DE9 1F8A4942 2951А581 550A582D s = FAFF37A6 F09525F3 I5A81669 9F811983 ICFF3EF8 2ЕВ81975 В68СА247 D366C4B1 Таким образом, результат хэширования есть Н = FAFF37A6 E09525F3 15А81669 9F811983 1CFF3EF8 2ЕВ81975 В68СА247 D366C4B1 А32 Пусть необходимо выполнить хэширование сообщения М- 7365 74796220 3035203D 20687457 6Е656С20 73616820 65676173 73656D20 6С616Е69 6769726F 20656874 2065736F 70707553 Так как длина сообщения, подлежащего хэшированию, равна 400 битам (50 байтам), то разбивают сообщение на два блока и второй (старший) блок дописывают нулями В процессе вычислений получают- ШАГ I М = 73616820 65676173 73656D20 6С616Е69 6769726F 20656874 2065736F 70707553 к,= 73736720 61656%5 6C6D7273 20206F6F 656С2070 67616570 616Е6875 73697453 14477373 4С50656С 0C0C6I65 04156761 1F01686D 061D616E 4F002020 1D277369 Кз- CBFF14B8 шт^к? 6D04F30C TiY-Wb\b 96051FFE 7 СЕйШЕА DFFFBOO0 К4- ЕВАССВОО ВА1С3509 F7006DFB FD118DF9 Е5Е16905 F61B830F BOBODFFF F8C554E5 S“ FF41797C EDDC2210 EEAADAC2 43C9B1DF 1EE1ADF9 FA67E757 2Е14681С DAFE3AD9 Е = F0CEEA4E A93BEFBD 368В5А60 2634 F0AD C63D96CI СВВВ69СЕ E5B51CD2 ED2D5D9A ШАГ 2 н- F0CEEA4E 368В5А60 C63D96C1 E5B51CD2 A93BEFBD 2634F ОАО СВВВ69СЕ ED2D5D9A м'— 00000000 00000000 00000000 00С07365 74796220 3035203D 20687467 6Е656С20 F0C6DDEB CE3D42D3 EA968D1D 4EC19DA9 36E5I683 8ВВ50148 5A6FD031 60В790ВА 16А4С6А9 F9DF3D3B E4FC96EF 53C9C1BD FB68E526 2CDBB534 FE161C83 6F7DD2C8 C49D845D 1780482С 9086887F С48С9186 9DCB0644 DIE641E5 A02109AF 9D52C7CF BDB0C9FO 756E9I31 E1F290EA 50E4CBBi 1CAD9536 F4E4B674 99F31E29 70C52AFA 62А07ЕА5 EF3C3309 2СЕ1В076 173D48CC 688IEB66 F5C7959F 63FCAIFI D33C3IB8 Е^= 95ВЕА0ВЕ 88D5AA02 FE3C9D45 436СЕ821 В8287СВ6 2СВС135В 3E339EFE F6576CA9 ШАГ 3 95ВЕА0ВЕ 8SD5AA02 FE3C9D45 436СЕ821 В8287СВ6 2СВС135В 3E339EFE F6576CA9 оооооооо оооооооо оооооооо оооооооо 00000000 00000000 ОООООООО 00000190 *i= ‘й'ЗЕЕВЛ&Е вдасаш Атшсад. WEAtfiWE 88432CF6 D56CBC57 AAE8136D 02215В39 Кз= 8695FEB8 1ВВЕЗС28 E2A09D7C 48ВБ45В6 DA88432C EBD56CBC 7FABE813 F292215B В9799501 141В413С 1ЕЕ2А062 0CB74U5 6FDA88BC D0J42A6C FA80AA16 15F2FDB1 Kd= 94В97995 7Г>] 41 В4] С21ЕЕ2А0 040СВ741 346FDA88 46D0142A BDFA81AA DC1562FD S» D42336E0 2А0А6998 6С65478А 3D08A1B9 9FDDFF20 48CSL853 911 D9D6D F776A7AD Е — 47E26AFD ЗЕ7278А1 7D473785 06140773 ШАГ 4 A3D97E7E А744СВ43 08АА4С24 3352С745 Н = 47E26AFD ЗЕ7278А1 7D473785 06140773 A3D97E7E А744СВ43 08АА4С24 3352С745 2 = 73616820 65676173 73656D20 6C6IE1CE DBE2D48F 509А88В1 40CDE7D6 DED5E173 Ki« 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 C473I191 7ЕВВ21В1 К4 = 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 57BAIA47 Таким образом, результат хэширования есть 0852F562 3B89DD57 AEB4781F E54DF14E EAFBC135 0613763А 0D770AA6 57ВА1А47 УДК 681.3.06:006.354 П85 ОКСТУ 5002 Ключевые слова: информационная технология, криптографическая защита информации, электронная цифровая подпись, асимметричный криптографический алгоритм, системы обработки информации, защита сообщений, подтверждение подписи, хэш-функция, функция хэширования Редактор Л. В. Афанасенко Технический редактор Н. С. Гришанова Корректор А. С. Черноусова Сдано в наб 24 06 94 Подп в печ 19 08 94 Уел п л 0 93 Уел кр.*отт В,9|. Уч-изд л 0,84 Тираж 300 экз С 1585 Ордена «Знак Почета» Издательство стандартов, 107076, Москва, Колодезный пер.. 14 Тнп «Московский печатник» Москва, Лялин пер , 6 Зак 208H-hJhelhdht, h16VG4(2), i = M
S^sJsJIsJs,.
слоьа Н, McV256(2) и слово S6 Уг5в(2).
н = 00000000 оооооооо 00000000 OOGOOOOO оооооооо оооооооо оооооооо оооооооо
оооооооо оооооооо 00000000 OQOOOOOO
z-оооооооо оооооооо оооооооо оооооооо оооооооо оооооооо ооосоооо оооооооо
L —оооооооо оооооооо оооооооо оооооооо оооооооо оооооооо оооооооо оооооооо
н-оооооооо оооооооо оооозооо оооооооо оооооооо оооооооо ОСИ1 ооооо оооооооо