ГОСТ Р 34.11-94
ГОСУДАРСТВЕННЫЙ СТАНДАРТ РОССИЙСКОЙ ФЕДЕРАЦИИ
ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ
КРИПТОГРАФИЧЕСКАЯ ЗАЩИТАИНФОРМАЦИИ
ФУНКЦИЯ ХЭШИРОВАНИЯ
БЗ 3—94/131
Издание афпргнлънее
ГОССТАНДАРТ РОССИИ Москва
Предисловие
! РАЗРАБОТАН Главным управлением безопасности связи Федерального агентства правительственной связи и информации ir Всероссийским научно-исследовательским институтом стандартизации
ВНЕСЕН Техническим комитетом по стандартизации ТК 22 «Информационная технология» и Федеральным агентством правительственной связи и информации
2 ПРИНЯТ И ВВЕДЕН В ДЕЙСТВИЕ Постановлением Госстандарта России от 23.05.94 № 154
3 ВВЕДЕН ВПЕРВЫЕ
© Издательство стандартов, 1994
Настоящий стандарт не может быть полностью или частично воспроизведен, тиражирован и распространен в качестве официального издания без разрешения Госстандарта России
ГОСТ Р 34.11—94
хэш-функции
Н = 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
Переходят к вычислению значения шаговой функции хэширования х (М, Н). Вырабатывают ключи | ||||||||||||||||||||
|
Осуществляют зашифрование 64-битных подслов блока Н с помощью алгоритма по ГОСТ 28147.
Блок hi = 00000000 00000000 зашифровывают на ключе Ki и получают -42АВВССЕ 32ВС0В1В.
Блок h2 = 00000000 00000000 зашифровывают на ключе К2 и получают S2 = - 5203ЕВС8 5D9BCPFD.
Блок ha-00000000 00000000 зашифровывают на ключе Кз и получают s3= «8D345899 00FF0E28.
Блок h4=00000000 00000000 зашифровывают на ключе Ка и получают s4== -Е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, Н). | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
АЗ 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
14477373 4С50656С |
0С0С6165 04156761 |
1F01686D 061D6I6E |
4F002D20 1D277369 | |
Кз- |
CBFF14B8 |
6D04F30C 7 |
96051FFE |
DFFFBOO0 |
К4 = |
ЕВАССВОО ВА1С3509 |
F7006DFB FD118DF9 |
Е5Е16905 F61B830F |
BOBODFFF F8C554E5 |
s= |
FF41797C EDDC2210 |
EEAADAC2 43C9B1DF 1EE1ADF9 FA67E757 |
2Е14681C DAFE3AD9 | |
3 = |
F0CEEA4E A93BEFBD |
368В5А60 2634F0AD |
C63D96C1 СВВВ69СЕ |
E5B51CD2 ED2D5D9A |
ШАГ 2 | ||||
Н— |
F0CEEA4E |
368В5А60 |
C63D96C1 |
E5B51CD2 |
A93BEFBD |
2634F ОАО |
СВВВ69СЕ |
ED2D5D9A | |
м'— |
00000000 00000000 00000000 00С07365 | |||
74796220 3035203D20687467 6Е656С20 | ||||
F0C6DDEB |
CE3D42D3 |
EA968D1D |
4EC19DA9 | |
36Е51683 |
8ВВ50148 |
5A6FD031 |
60В790ВА | |
16А4С6А9 |
F9DF3D3B |
E4FC96EF |
53C9C1BD | |
FB68E526 |
2CDBB534 |
FE161C83 |
6F7DD2C8 | |
Ка= |
C49D846D |
1780482С |
9086887F |
С48С9186 |
9DCB0544 |
D1E641E5 |
A02109AF |
9D52C7CF | |
BDB0C9FO |
756Е9131 |
E1F290EA |
50Е4СВВ1 | |
1CAD9536 |
F4E4B674 |
99F31E29 |
70C52AFA | |
62А07ЕА5 |
EF3C3309 |
2СЕ1В076 |
173D48CC | |
6881ЕВ66 |
F5C7959F |
63FCAIFI |
D33C3IB8 | |
95ВЕА0ВЕ |
88D5AA02 |
FE3C9D45 |
436СЕ821 | |
В8287СВ6 ШАГ 3 |
2СВС135В |
3E339EFE |
F6576CA9 | |
95ВЕА0ВЕ |
8SD5AA02 |
FE3C9D45 |
436СЕ821 | |
В8287СВ6 |
2СВС135В |
3E339EFE |
F6576CA9 | |
оооооооо 00000000 оооооооо 00000000 | ||||
00000000 ОООООООО ОООООООО 00000190 | ||||
Xi- |
ЪЕзсаш |
АШУ1С&Е | ||
88432CF6 |
D56CBC57 |
AAE8136D |
02215В39 | |
Ks= |
8695FEB8 |
1ВВЕЗС28 |
E2A09D7C |
48ВЕ45В6 |
DA88432C |
EBD56CBC |
7FABE813 |
F292215B | |
В9799501 |
141В413С |
1ЕЕ2А062 |
0CB74U5 | |
6FDA88BC |
D0142A6C |
FA80AA16 |
15F2FDB1 | |
94В97995 |
7П> j 41В41 |
С21ЕЕ2А0 |
040СВ741 | |
346FDA88 |
46D0142A |
BDFA81AA |
DC1562FD | |
S «•* |
D42336E0 |
2А0А6998 |
6С65478А |
3D08A1B9 |
9FDDFF20 |
4808Е853 |
911 D9D6D |
F776A7AD |
9
ГОСТ Р 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 — хош-ф>нкция, отображающая последовательность Мб В* в слове р(М>б У25б(2).
Ек(А) оез>льтат зашифрования слова А на ключе К с использованием алгоритма шифрования по ГОСТ 28147 в режиме простой замены (K6V256 (2), Аб V64(2)).
Н - стартовый вектор хэширования.
е -g — присвоение параметру е значения g. 1
ГОСТ Р 34.11-94
б ШАГОВАЯ ФУНКЦИЯ ХЭШИРОВАНИЯ
Алгоритм вычисления шаговой функции хэширования включает в себя три части, реализующие последовательно:
— генерацию ключей — слов длины 256 битов;
— шифрующее преобразование — зашифрование 64-битных подслов слова Н на ключах Ki (i=l, 2, 3, 4) с использованием алгоритма по ГОСТ 28147 в режиме простой замены;
— перемешивающее преобразование результата шифрования.
5.1 Генерация ключей.
РассмотримХ=(Ь356, Ь255, • • b,)6V256(2).
Пусть Х=х4|!х3||х2|х1 =
=111б1Ы1- ■ -bi =
— ^32l!^3l|| • • • ||^1>
где Xj=(bix64.....b(i-i)x64+i)CVe4(2), i—1,4;
’ll —(b/xie, .. ., b(j-i)Xi6+i)6VI6(2), j= 1,16;
6k=(btx8,..., b,k-i)xe±i)eva(2)> k=i732.
Обозначают A(X)=(x, ф х2),]х4||хз||х2.
Используют преобразование P: V26C(2)-------->-V256(2)
слова S33jj... IIS, в слово;<W32)|I|. . .fS fi>,
где <p(i + l+4(k-l))=8i+k, 1=0н~3, k = l-^8.
Для генерации ключей необходимо использовать следующие исходные данные:
— слова Н, M6V25e(2);
— параметры: слова С, (i = 2, 3, 4), имеющие значения C2=C4=02ss и С3 = 1 ®081160241160s(0818)21 ^(О818)1( 1803)1.
При вычислении ключей реализуется следующий алгоритм -
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-hJh3|Mhb Ь,ГЛ^(2), i = M
и набор ключей Кь Кг, Кз, К*.
Реализуют алгоритм зашифрования и получают слова
5г~--Ек,0ч), где 1-1, 2, 3, 4.
В результате данного этапа образуется последовательность
$ — sjssjjsjs,.
5 3 Перемешивающее преобразование
г л д< ином этапе осуществляется перемешивание полученной послед* вательности с применением регистра сдвига.
Исходными данными являются:
слока Н, М(.У25б(2) и слово S6 Уг5в(2).
Пусть отображение
*:Vsftbp........-Ушв(2)
преобразует слово
V!- ■ -llv,, VtfVl6(2), I== 1,16
ь СЛОВО
глв‘>?2Ф1:з®^®'Ч1зФЧ1б813|в1- ■ Jv2-
Тогда н качестве значения шаговой функции хэширования принимается слово
х(м,
где ф1- i-я степень преобразования ф.
6 ПРОЦЕДУРА ВЫЧИСЛЕНИЯ ХЭШ~ФУНКЦИИ
Исходными данными для процедуры вычисления значения функции h является подлежащая хэшированию последовательность Мб В*. Параметром является стартовый вектор хэширования Н — произвольное фиксированное слово аз V2se (2).
ГОСТ Р 34.lt—94
Процедура вычисления функции h на каждой итерации использует следующие величины:
Мб В* — часть последовательности М, не Прошедшая процедуры хэширования на предыдущих итерациях; не Vase (2) —текущее значение хэш-функции;
2 6 V256(2) —текущее значение контрольной суммы;
L6 У25б(2) — текущее значение длины обработанной на предыдущих итерациях части последовательности М.
Алгоритм вычисления функции h включает в себя этапы:
Этап 1
Присвоить начальные значения текущих величин
1.1 М:=М
1.2 Н: = Н
1.3 Е:=0ЗЛ«
1.4 L:—026ti
1.5 Переход к этапу 2
Этап 2
2.1 Проверить условие }М)>256.
При положительном исходе перейти к этапу 3.
В противном случае выполнить последовательность вычислений:
2.2 L: — <L+|M|>356
2.3 ||М
2.4 Е; = £®'М'
2.5 Н:^х(М', Н)
2.6 H:=x(L, Н)
2.7 Н:=х(Е, Н)
2.8 Конец работы алгоритма
Этап 3
3.1 Вычислить подслово М36 V256(2) слова М (M=MP||MS)_ Далее выполнить последовательность вычислений:
3.2 H:-x(Ms, Н)
3.3 L:= <L-j-25b>266
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
Выполняют присвоение начальных значений:
М=73657479 *<>203233 3D687467 6Е656С20 9С656761 7o,C556D 20736920 73696854
текста
1
ОБЩИЕ ПОЛОЖЕНИЯ
Под хэш-функцией h понимается зависящее от параметра гартового вектора хэширования Н, являющегося словом из
56 (2) 1 отображение
1 : С1 V25fi(2).
Для определения хэш-функции неЗбходимы:
— алгоритм вычисления шаговой функции хэширования т. е. отображения
*: V236(J) xV>rb(2)......Vre<2);
— описание итеративной процедуры вычисления значения хэш-функции h.