ГОСТ Р 34.11-94. Государственный стандарт Российской Федерации. Информационная технология. Криптографическая защита информации. Функция хэширования
(принят и введен в действие Постановлением Госстандарта России от 23.05.1994 № 154)
Внимание
Документ утратил силу с 1 января 2013 года в связи с изданием Приказа Росстандарта от 07.08.2012 № 216-ст. Взамен введен в действие ГОСТ Р 34.11-2012. Документ утратил силу с 1 января 2013 года в связи с изданием Приказа Росстандарта от 07.08.2012 № 216-ст. Взамен введен в действие ГОСТ Р 34.11-2012.
ИСТОРИЯ ИЗМЕНЕНИЙ НОРМАТИВНО-ТЕХНИЧЕСКИХ АКТОВ
flowchart LR n0["ГОСТ Р 34.11-94"]:::rst click n0 "https://bukva.ai/docs/standart-154" "ГОСТ Р 34.11-94. Государственный стандарт Российской Федерации. Информационная технология. Криптографическая защита информации. Функция хэширования (принят и введен в действие Пост" n1["ГОСТ Р 34.11-2012"]:::doc click n1 "https://bukva.ai/docs/gost-r-34-11-2012" "ГОСТ Р 34.11-2012. Национальный стандарт Российской Федерации. Информационная технология. Криптографическая защита информации. Функция хэширования (утв. и введен в действие Приказо" n0 --> n1 classDef rst fill:#FFEBEB,stroke:#8B0000,color:#000; classDef doc fill:#EBFFEB,stroke:#006400,color:#000; classDef notEnt fill:#FFFFEB,stroke:#FF8C00,color:#000;
от 23 мая 1994 г. № 154
ГОСУДАРСТВЕННЫЙ СТАНДАРТ РОССИЙСКОЙ ФЕДЕРАЦИИ
КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ
Information technology. Cryptographic data security. Hashing function
1 января 1995 года
ПРЕДИСЛОВИЕ
1. Разработан Главным управлением безопасности связи Федерального агентства правительственной связи и информации и Всероссийским научно-исследовательским институтом стандартизации.
Внесен Техническим комитетом по стандартизации ТК 22 «Информационная технология» и Федеральным агентством правительственной связи и информации.
2. Принят и введен в действие Постановлением Госстандарта России от 23.05.94 № 154.
ВВЕДЕНИЕ
Расширяющееся применение информационных технологий при создании, обработке, передаче и хранении документов требует в определенных случаях сохранения конфиденциальности их содержания, обеспечения полноты и достоверности.
Одним из эффективных направлений защиты информации является криптография (криптографическая защита), широко применяемая в различных сферах деятельности в государственных и коммерческих структурах.
Криптографические методы защиты информации являются объектом серьезных научных исследований и стандартизации на национальных, региональных и международных уровнях.
Настоящий стандарт определяет процедуру вычисления хэш-функции для любой последовательности двоичных символов.
Функция хэширования заключается в сопоставлении произвольного набора данных в виде последовательности двоичных символов и его образа фиксированной небольшой длины, что позволяет использовать эту функцию в процедурах электронной цифровой подписи для сокращения времени подписывания и проверки подписи. Эффект сокращения времени достигается за счет вычисления подписи только под образом подписываемого набора данных.
1. ОБЛАСТЬ ПРИМЕНЕНИЯ
Настоящий стандарт определяет алгоритм и процедуру вычисления хэш-функции для любой последовательности двоичных символов, которые применяются в криптографических методах обработки и защиты информации, в том числе для реализации процедур электронной цифровой подписи (ЭЦП) при передаче, обработке и хранении информации в автоматизированных системах.
Определенная в настоящем стандарте функция хэширования используется при реализации систем электронной цифровой подписи на базе асимметричного криптографического алгоритма по ГОСТ Р 34.10.
2. НОРМАТИВНЫЕ ССЫЛКИ
В настоящем стандарте использованы ссылки на следующие стандарты:
ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритмы криптографического преобразования.
ГОСТ Р 34.10-94 Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма.
3. ОБОЗНАЧЕНИЯ
В настоящем стандарте используются следующие обозначения:
В* — множество всех конечных слов в алфавите В = {0,1}. Чтение слов и нумерация знаков алфавита (символов) осуществляются справа налево (номер правого символа в слове равен единице, второго справа — двум и т.д.).
|А| — длина слова А принадлежит В*.
V (2) — множество всех бинарных слов длины k. k
А||В — конкатенация слов А, В принадлежат В* — слово длины |А|
- |В|, в котором левые |А| символов образуют слово А, а правые |В| символов образуют слово В. Можно также использовать обозначение А||В = АВ. k
А - конкатенация k экземпляров слова А (А принадлежит В*).- слово длины k, содержащее двоичную запись вычета
k
k
N(mod 2 ) неотрицательного целого числа N. ~
А — неотрицательное целое число, имеющее двоичную запись А (А принадлежит В*).
{+} — побитовое сложение слов одинаковой длины по модулю 2.
~ ~ {+}' - сложение по правилу А {+}' В = , (k = |A| =
k
|B|).
М — последовательность двоичных символов, подлежащая хэшированию (сообщение в системах ЭЦП), М принадлежит В*.
h — хэш-функция, отображающая последовательность М принадлежит В* в слово h(M) принадлежит V (2). 256
Е (А) — результат зашифрования слова А на ключе К с к использованием алгоритма шифрования по ГОСТ 28147 в режиме простой
замены (К принадлежит V (2), A принадлежит V (2)).
256 64
Н — стартовый вектор хэширования.
e := g — присвоение параметру е значения g.
4. ОБЩИЕ ПОЛОЖЕНИЯ
Под хэш-функцией h понимается зависящее от параметра [стартового вектора хэширования Н, являющегося словом из V (2)]
256
отображение:
Для определения хэш-функции необходимы: - алгоритм вычисления шаговой функции хэширования каппа, т.е. отображения:
каппа: V (2) x V (2) -----> V (2); 256 256 256
- <a id="p100049"></a>описание итеративной процедуры вычисления значения
хэш-функции h.
5. ШАГОВАЯ ФУНКЦИЯ ХЭШИРОВАНИЯ
Алгоритм вычисления шаговой функции хэширования включает в себя три части, реализующие последовательно: - генерацию ключей — слов длины 256 битов; - шифрующее преобразование — зашифрование 64-битных подслов слова Н на ключах K (i = 1, 2, 3, 4) с использованием алгоритма i по ГОСТ 28147 в режиме простой замены; - перемешивающее преобразование результата шифрования.
5.1 Генерация ключей
Рассмотрим Х = (b , b ,..., b ) принадлежит V (2). 256 255 1 256 Пусть X = x ||x ||x ||x = 4 3 2 1 = эта ||эта ||...||эта = 16 15 1 = кси ||кси ||...||кси , 32 31 1
где:
___
х = (b ,..., b ) принадлежит V (2), i = 1,4;
i i x 64 (i - 1) x 64 + 1 64
___
эта = (b ,..., b ) принадлежит V (2), j = 1,6;
j j x 16 (j - 1) x 16 + 1 16
____
кси = (b ,..., b ) принадлежит V (2), k = 1,32.
k k x 8 (k - 1) x 8 + 1 8
Обозначают A(X) = (x {+} x )||x ||x ||x .
1 2 4 3 2
Используют преобразование P: V (2) ----> V (2),
256 256
слова кси ||...||кси в слово кси ||...||кси ,
32 1 фи(32) фи(1)
где:
фи(i + 1 + 4(k - 1)) = 8i + k, i = от 0 до 3, k = от 1 до 8.
Для генерации ключей необходимо использовать следующие исходные данные: - слова Н, M принадлежат V (2); 256 - параметры: слова С (i = 2, 3, 4), имеющие значения: i
256 8 8 16 24 16 8 8 8 2 8 8 8 8 4 8 8 4 С = С = 0 и С = 1 0 1 0 1 0 (0 1 ) 1 0 (0 1 ) (1 0 ) . 2 4 3
При вычислении ключей реализуется следующий алгоритм:
1. <a id="p100065"></a>Присвоить значения
i := 1, U := H, V := M.
2. <a id="p100066"></a>Выполнить вычисление
___
W = U {+} V, K = P(W).
i
3. <a id="p100067"></a>Присвоить i := i + 1.
4. <a id="p100068"></a>Проверить условие i = 5.
При положительном исходе перейти к шагу 7. При отрицательном — перейти к шагу 5.
5. <a id="p100070"></a>Выполнить вычисление:
___ ___ U := A(U) {+} C , V := A(A(V)), W := U {+} V, K = P(W). i i
-
Перейти к шагу 3.
5.2 Шифрующее преобразование
На данном этапе осуществляется зашифрование 64-битных подслов слова Н на ключах K (i = 1, 2, 3, 4).
i
Для шифрующего преобразования необходимо использовать следующие исходные данные: ___
H = h ||h ||h ||h , - h принадлежит V (2), i = 1,4 4 3 2 1 i 64
и набор ключей К , К , К , К . 1 2 3 4
Реализуют алгоритм зашифрования и получают слова:
s = E (h ), i к i
i
где i = 1, 2, 3, 4.
В результате данного этапа образуется последовательность:
5.3 Перемешивающее преобразование
На данном этапе осуществляется перемешивание полученной последовательности с применением регистра сдвига.
слова Н, М принадлежат V (2) и слово S принадлежит V (2). 256 256
фи: V (2) ----> V (2) 256 256
преобразует слово:
____
эта ||...||эта , эта принадлежит V (2), i = 1,16 16 1 1 16
в слово:
___ ___ ___ ___ ___ эта {+} эта {+} эта {+} эта {+} эта {+} эта ||эта ||...||эта . 1 2 3 4 13 16 16 2 Тогда в качестве значения шаговой функции хэширования
принимается слово:
61 ___ ___ 12 каппа(М, Н) = фи (Н {+} фи(М {+} фи (S))),
i
где фи - i-я степень преобразования фи.
6. ПРОЦЕДУРА ВЫЧИСЛЕНИЯ ХЭШ-ФУНКЦИИ
Исходными данными для процедуры вычисления значения функции h является подлежащая хэшированию последовательность М принадлежит В*. Параметром является стартовый вектор хэширования Н - произвольное фиксированное слово из V (2).
256
Процедура вычисления функции h на каждой итерации использует следующие величины:
М принадлежит В* — часть последовательности М, не прошедшая процедуры хэширования на предыдущих итерациях;
H принадлежит V (2) — текущее значение хэш-функции; 256
СИГМА принадлежит V (2) — текущее значение контрольной 256 суммы;
L принадлежит V (2) — текущее значение длины обработанной на 256 предыдущих итерациях части последовательности М.
Алгоритм вычисления функции h включает в себя этапы:
Присвоить начальные значения текущих величин:
1.1 М := М
1.2 Н := Н
256
1.3 СИГМА := 0
256
1.4 L := 0
1.5 Переход к этапу 2.
2.1 Проверить условие |М| > 256.
При положительном исходе перейти к этапу 3.
В противном случае выполнить последовательность вычислений: ~
2.2 L := <L + |M|>
256 - |М| 256
2.3 М' := 0 ||М
2.4 СИГМА := СИГМА {+}' М'
2.5 Н := каппа(М', Н)
2.6 Н := каппа(L, H)
2.7 Н := каппа(СИГМА, H)
2.8 Конец работы алгоритма.
3.1. Вычислить подслово М принадлежит V (2) слова М (М = s 256
М ||М ). Далее выполнить последовательность вычислений: p s
3.2 H := каппа(М , Н)
s
3.3 L := <L + 256>
256
___
3.4 СИГМА := СИГМА {+}' М
s
3.5 М := М
p
3.6 Перейти к этапу 2.
Значение величины Н, полученное на шаге 2.7, является значением функции хэширования h(M).
Проверочные примеры для вышеизложенной процедуры вычисления хэш-функции приведены в Приложении А.
Заполнение узлов замены пи , пи ,..., пи и значение 1 2 8 стартового вектора хэширования Н, указанные в данном Приложении, рекомендуется использовать только в проверочных примерах для
настоящего стандарта.
А.1. Использование алгоритма ГОСТ 28147
В качестве шифрующего преобразования в приводимых ниже примерах используется алгоритм ГОСТ 28147 в режиме простой замены.
При этом заполнение узлов замены пи , пи ,..., пи блока 1 2 8
подстановки пи следующее:
│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 C 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 |
___
В столбце с номером j, j = 1,8, в строке с номером i, i =
0,15, приведено значение пи (i) в шестнадцатеричной системе j счисления.
Последовательности двоичных символов будем записывать как строки шестнадцатеричных цифр, в которых каждая цифра
соответствует четырем знакам ее двоичного представления.
А.3. Примеры вычисления значения хэш-функции
В качестве стартового вектора хэширования принимают, например, нулевой вектор:
Н = 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000.
А.3.1. Пусть необходимо выполнить хэширование сообщения: М = 73657479 62203233 3D687467 6E656C20 2C656761 7373656D 20736920 73696854.
Выполняют присвоение начальных значений: текста М = 73657479 62203233 3D687467 6E656C20 2С656761 7373656D 20736920 73696854 хэш-функции Н = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 суммы блоков текста СИГМА = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 длины текста L = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000.
Так как длина сообщения, подлежащего хэшированию, равна 256 битам (32 байтам), L = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
М' = М = 73657479 62203233 3D687467 6E656C20
2C656761 7373656D 20736920 73696854,
то нет необходимости дописывать текущий блок нулями,
СИГМА = М' = 73657479 62203233 3D687467 6E656C20
2C656761 7373556D 20736920 73696854.
Переходят к вычислению значения шаговой функции хэширования каппа(М, Н).
K = 733D2C20 65686573 74746769 79676120
1 626E7373 20657369 326C6568 33206D54
K = 110C733D 0D166568 130E7474 06417967
2 1D00626E 161A2065 090D326C 4D393320
K = 80B111F3 730DF216 850013F1 C7E1F941
3 620C1DFF 3ABAE91A 3FA109F2 F513B239
K = A0E2804E FF1B73F2 ECE27A00 E7B8C7E1
4 EE1D620C AC0CC5BA A804C05E A18B0AEC.
Осуществляют зашифрование 64-битных подслов блока Н с помощью
алгоритма по ГОСТ 28147.
Блок h = 00000000 00000000 зашифровывают на ключе K и 1 1 получают s = 42ABBCCE 32BC0B1B.
1
Блок h = 00000000 00000000 зашифровывают на ключе K и 2 2 получают s = 5203EBC8 5D9BCFFD.
2
Блок h = 00000000 00000000 зашифровывают на ключе K и 3 3 получают s = 8D345899 00FF0E28.
3
Блок h = 00000000 00000000 зашифровывают на ключе K и 4 4 получают s = E7860419 0D2A562D.
4
S = E7860419 0D2A562D 8D345899 00FF0E28
5203EBC8 5D9BCFFD 42ABBCCE 32BC0B1B.
Выполняют перемешивающее преобразование с применением регистра сдвига и получают:
КСИ = каппа(М, H) = CF9A8C65 505967A4 68A03B8C 42DE7624
D99C4124 883DA687 561C7DE3 3315C034.
Полагают H = КСИ, вычисляют каппа(L, H):
K = CF68D956 9AA09C1C 8C3B417D 658C24E3
1 50428833 59DE3D15 6776A6C1 A4248734
K = 8FCF68D9 809AA09C 3C8C3B41 C7658C24
2 BB504288 2859DE3D 666676A6 B3A42487
K = 4E70CF97 3C8065A0 853C8CC4 57389A8C
3 CABB50BD E3D7A6DE D1996788 5CB35B24
K = 584E70CF C53C8065 48853C8C 1657389A
4 EDCABB50 78E3D7A6 EED19867 7F5CB35B
S = 66B70F5E F163F461 468A9528 61D60593
E5EC8A37 3FD42279 3СD1602D DD783E86
КСИ = 2B6EC233 C7BC89E4 2ABC2692 5FEA7285
DD3848D1 C6AC997A 24F74E2B 09A3AEF7.
Вновь полагают H = КСИ и вычисляют каппа(СИГМА, H):
K = 5817F104 0BD45D84 B6522F27 4AF5B00B
1 A531B57A 9C8FDFCA BB1EFCC6 D7A517A3
K = E82759E0 C278D950 15CC523C FC72EBB6
2 D2C73DA8 19A6CAC9 3E8440F5 C0DDB65A
K = 77483AD9 F7C29CAA EB06D1D7 841BCAD3
3 FBC3DAA0 7CB555F0 D4968080 0A9E56BC
K = Al157965 2D9FBC9C 088C7CC2 46FB3DD2
4 7684ADCB FA4ACA06 53EFF7D7 C0748708
S = 2AEBFA76 A85FB57D 6F164DE9 2951A581
C31E7435 4930FD05 1F8A4942 550A582D
КСИ = FAFF37A6 15A81669 1CFF3EF8 B68CA247
E09525F3 9F811983 2EB81975 D366C4B1.
Таким образом, результат хэширования есть:
H = FAFF37A6 15A81669 1CFF3EF8 B68CA247
E09525F3 9F811983 2EB81975 D366C4B1.
А.3.2. Пусть необходимо выполнить хэширование сообщения:
М = 7365 74796220 3035203D 20687467 6E656C20 73616820 65676173
73656D20 6C616E69 6769726F 20656874 2065736F 70707553.
Так как длина сообщения, подлежащего хэшированию, равна 400 битам (50 байтам), то разбивают сообщение на два блока и второй
(старший) блок дописывают нулями. В процессе вычислений получают:
H = 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
M = 73616820 65676173 73656D20 6C616E69
6769726F 20656874 2065736F 70707553
K = 73736720 61656965 686D7273 20206F6F
1 656C2070 67616570 616E6875 73697453
K = 14477373 0C0C6165 1F01686D 4F002020
2 4C50656C 04156761 061D616E 1D277369
K = CBFF14B8 6D04F30C 96051FFE DFFFB000
3 35094CAF 72F9FB15 7CF006E2 AB1AE227
K = EBACCB00 F7006DFB E5E16905 B0B0DFFF
4 BA1C3509 FD118DF9 F61B830F F8C554E5
S = FF41797C EEAADAC2 43C9B1DF 2E14681С
EDDC2210 1EE1ADF9 FA67E757 DAFE3AD9
КСИ = F0CEEA4E 368B5A60 C63D96C1 E5B51CD2
A93BEFBD 2634F0AD CBBB69CE ED2D5D9A
H = F0CEEA4E 368B5A60 C63D96C1 E5B51CD2
A93BEFBD 2634F0AD CBBB69CE ED2D5D9A
M' = 00000000 00000000 00000000 00007365
74796220 3035203D 20687467 6E656C20
K = F0C6DDEB CE3D42D3 EA968D1D 4EC19DA9
1 36E51683 8BB50148 5A6FD031 60B790BA
K = 16A4C6A9 F9DF3D3B E4FC96EF 5309C1BD
2 FB68E526 2CDBB534 FE161C83 6F7DD2C8
K = C49D846D 1780482C 9086887F C48C9186
3 9DCB0644 D1E641E5 A02109AF 9D52C7CF
K = BDB0C9F0 756E9131 E1F290EA 50E4CBB1
4 1CAD9536 F4Е4B674 99F31E29 70C52AFA
S = 62A07EA5 EF3C3309 2CE1B076 173D48CC
6881EB66 F5C7959F 63FCA1F1 D33C31B8
КСИ = 95BEA0BE 88D5AA02 FE3C9D45 436CE821
B8287CB6 2CBC135B 3E339EFE F6576CA9
H = 95BEA0BE 88D5AA02 FE3C9D45 436CE821
B8287CB6 2CBC135B 3E339EFE F6576CA9
L = 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000190
K = 95FEB83E BE3C2833 A09D7C9E BE45B6FE
1 88432CF6 D56CBC57 AAE8136D 02215B39
K = 8696FEB8 1BBE3C28 E2A09D7C 48BE45B6
2 DA88432C EBD56CBC 7FABE813 F292215B
K = В9799501 141B413C 1EE2A062 0CB74145
3 6FDA88BC D0142A6C FA80AA16 15F2FDB1
K = 94B97995 7D141B41 C21EE2A0 040CB741
4 346FDA88 46D0142A BDFA81AA DC1562FD
S = D42336E0 2A0A6998 6C65478A 3D08A1B9
9FDDFF20 4808E863 94FD9D6D F776A7AD
КСИ = 47E26AFD 3E7278A1 7D473785 06140773
A3D97E7E A744CB43 08AA4C24 3352C745
H = 47E26AFD 3E7278A1 7D473785 06140773
A3D97E7E A744CB43 08AA4C24 3352C745
СИГМА = 73616820 65676173 73656D20 6C61Е1СЕ
DBE2D48F 509A88B1 40CDE7D6 DED5E173
K = 340E7848 83223B67 025AAAAB DDA5F1F2
1 5B6AF7ED 1575DE87 19E64326 D2BDF236
K = 03DC0ED0 F4CD26BC 8B595F13 F5A4A55E
2 A8B063CB ED3D7325 6511662A 7963008D
K = C954EF19 D0779A68 ED37D3FB 7DA5ADDC
3 4A9D0277 78ЕF765В C4731191 7EBB21B1
K = 6D12BC47 D9363D19 1E3C696F 28F2DC02
4 F2137F37 64E4C18B 69CCFBF8 EF72B7E3
S = 790DD7A1 066544EA 2829563C 3C39D781
25EF9645 EE2C05DD A5ECAD92 2511A4D1
КСИ = 0852F562 3B89DD57 AEB4781F E54DF14E
EAFBC135 0613763A 0D770AA6 57BA1A47.
Таким образом, результат хэширования есть:
H = 0852F562 3B89DD57 AEB4781F E54DF14E
EAFBC135 0613763A 0D770AA6 57BA1A47.