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

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

ГОСТ Р 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