- Законы
- Кодексы
- Форум
Информационная технология. Криптографическая защита информации. Функция хэширования. ГОСТ Р 34.11-94
Текст документа по состоянию на июль 2011 года
Утвержден
Постановлением
Госстандарта России
от 23 мая 1994 г. N 154
Дата введения -
1 января 1995 года
ПРЕДИСЛОВИЕ
1. Разработан Главным управлением безопасности связи Федерального агентства правительственной связи и информации и Всероссийским научно-исследовательским институтом стандартизации.
Внесен Техническим комитетом по стандартизации ТК 22 "Информационная технология" и Федеральным агентством правительственной связи и информации.
2. Принят и введен в действие Постановлением Госстандарта России от 23.05.94 N 154.
3. Введен впервые.
ВВЕДЕНИЕ
Расширяющееся применение информационных технологий при создании, обработке, передаче и хранении документов требует в определенных случаях сохранения конфиденциальности их содержания, обеспечения полноты и достоверности.
Одним из эффективных направлений защиты информации является криптография (криптографическая защита), широко применяемая в различных сферах деятельности в государственных и коммерческих структурах.
Криптографические методы защиты информации являются объектом серьезных научных исследований и стандартизации на национальных, региональных и международных уровнях.
Настоящий стандарт определяет процедуру вычисления хэш-функции для любой последовательности двоичных символов.
Функция хэширования заключается в сопоставлении произвольного набора данных в виде последовательности двоичных символов и его образа фиксированной небольшой длины, что позволяет использовать эту функцию в процедурах электронной цифровой подписи для сокращения времени подписывания и проверки подписи. Эффект сокращения времени достигается за счет вычисления подписи только под образом подписываемого набора данных.
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
отображение:
h: B* -----------> V (2).
256
Для определения хэш-функции необходимы:
- алгоритм вычисления шаговой функции хэширования каппа, т.е.
отображения:
каппа: V (2) x V (2) -----> V (2);
256 256 256
- описание итеративной процедуры вычисления значения хэш-функции 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. Присвоить значения
i := 1, U := H, V := M.
2. Выполнить вычисление
___
W = U {+} V, K = P(W).
i
3. Присвоить i := i + 1.
4. Проверить условие i = 5.
При положительном исходе перейти к шагу 7. При отрицательном -
перейти к шагу 5.
5. Выполнить вычисление:
___ ___
U := A(U) {+} C , V := A(A(V)), W := U {+} V, K = P(W).
i i
6. Перейти к шагу 3.
7. Конец работы алгоритма. 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.
В результате данного этапа образуется последовательность:
S = s ||s ||s ||s .
4 3 2 1
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. М := М
1.2. Н := Н
256
1.3. СИГМА := 0
256
1.4. L := 0
1.5. Переход к этапу 2.
Этап 2
2.1. Проверить условие |М| > 256.
При положительном исходе перейти к этапу 3.
В противном случае выполнить последовательность вычислений:
~
2.2. L :=
256 - |М| 256
2.3. М' := 0 ||М
2.4. СИГМА := СИГМА {+}' М'
2.5. Н := каппа(М', Н)
2.6. Н := каппа(L, H)
2.7. Н := каппа(СИГМА, H)
2.8. Конец работы алгоритма.
Этап 3
3.1. Вычислить подслово М принадлежит V (2) слова М (М =
s 256
М ||М ). Далее выполнить последовательность вычислений:
p s
3.2. H := каппа(М , Н)
s
3.3. L :=
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
счисления.
А.2. Представление векторов
Последовательности двоичных символов будем записывать как
строки шестнадцатеричных цифр, в которых каждая цифра
соответствует четырем знакам ее двоичного представления.
А.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 байтам), то разбивают сообщение на два блока и второй (старший) блок дописывают нулями. В процессе вычислений получают:
ШАГ 1
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
ШАГ 2
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
ШАГ 3
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
ШАГ 4
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.
Комментарии
Комментирование через социальные сервисы Facebook и Вконтакте:
Навигация
ФедеральноеИнформация
-