Утвержден

Постановлением

Госстандарта России

от 23 мая 1994 г. N 154

Дата введения -

1 января 1995 года

ГОСУДАРСТВЕННЫЙ СТАНДАРТ РОССИЙСКОЙ ФЕДЕРАЦИИ

ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ

КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ

ФУНКЦИЯ ХЭШИРОВАНИЯ

INFORMATION TECHNOLOGY. CRYPTOGRAPHIC DATA SECURITY.

HASHING FUNCTION

ГОСТ Р 34.11-94

ПРЕДИСЛОВИЕ

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 экземпляров слова А (А принадлежит В*).

    <N>  - слово  длины  k,  содержащее  двоичную  запись   вычета

       k

       k

N(mod 2 ) неотрицательного целого числа N.

    ~

    А - неотрицательное целое число,  имеющее  двоичную  запись  А

(А принадлежит В*).

    {+} - побитовое сложение слов одинаковой длины по модулю 2.

                                               ~   ~

    {+}' -  сложение  по  правилу  А {+}' В = <A + B> , (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 := <L + |M|>

                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 := <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

счисления.

    А.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.