ГОСТ Р 34.10-94

Группа П85

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


Информационная технология

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

Процедуры выработки и проверки электронной цифровой подписи
 на базе асимметричного криптографического алгоритма

Information technology. Cryptographic Data Security.
Produce and check procedures of Electronic Digital Signature based
on Asymmetric Cryptographic Algorithm

       
ОКСТУ 5002

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

Предисловие

     
     
     1 РАЗРАБОТАН Главным управлением безопасности связи Федерального агентства правительственной связи и информации и Всероссийским научно-исследовательским институтом стандартизации
     
     ВНЕСЕН Техническим комитетом по стандартизации ТК 22 "Информационная технология" и Федеральным агентством правительственной связи и информации
     
     2 ПРИНЯТ И ВВЕДЕН В ДЕЙСТВИЕ постановлением Госстандарта России от 23.05.94 N 154
     
     3 ВВЕДЕН ВПЕРВЫЕ
     

ВВЕДЕНИЕ

     
     
     Расширяющееся применение информационных технологий при создании, обработке, передаче и хранении документов требует в определенных случаях сохранения конфиденциальности их содержания, обеспечения полноты и достоверности.
     
     Одним из эффективных направлений защиты информации является криптография (криптографическая защита), широко применяемая в различных сферах деятельности в государственных и коммерческих структурах.
     
     Криптографические методы защиты информации являются объектом серьезных научных исследований и стандартизации на национальных, региональных и международных уровнях.
     
     Настоящий стандарт определяет процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма с применением функции хэширования.
     
     Электронная цифровая подпись обеспечивает целостность сообщений (документов), передаваемых по незащищенным телекоммуникационным каналам общего пользования в системах обработки информации различного назначения, с гарантированной идентификацией ее автора (лица, подписавшего документ).
     

1 ОБЛАСТЬ ПРИМЕНЕНИЯ

     
     
     Настоящий стандарт устанавливает процедуры выработки и проверки электронной цифровой подписи (ЭЦП) сообщений (документов), передаваемых по незащищенным телекоммуникационным каналам общего пользования в системах обработки информации различного назначения, на базе асимметричного криптографического алгоритма с применением функции хэширования.
     
     Внедрение системы ЭЦП на базе настоящего стандарта обеспечивает защиту передаваемых сообщений от подделки, искажения и однозначно позволяет доказательно подтвердить подпись лица, подписавшего сообщение.
     

2 НОРМАТИВНЫЕ ССЫЛКИ

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

3 ОБОЗНАЧЕНИЯ

     
     
     В настоящем стандарте используются следующие обозначения.
     
     - множество всех конечных слов в алфавите  = {0,1}.
     
     |А| - длина слова .
     
     (2) - множество всех бинарных слов длины k.
     
     z (mod n) - наименьшее по значению неотрицательное число, сравнимое с z по модулю числа n.
     
     <N> - слово длины k, содержащее двоичную запись вычета N (mod 2) неотрицательного целого числа N.
     
      - неотрицательное целое число, имеющее двоичную запись  (под длиной числа будем понимать номер старшего значащего бита в двоичной записи числа).
     
     А||В - конкатенация слов A, - слово длины |А|+|В|, в котором левые |А| символов образуют слово А, а правые |В| символов образуют слово В. Можно также использовать обозначение А||В=АВ.
     
     A - конкатенация k экземпляров слова .
     
     М - передаваемое сообщение, .
     
     М - полученное сообщение, .
________________________
Отправляемые и получаемые последовательности, в том числе сообщения и подписи, могут отличаться друг от друга из-за случайных или преднамеренных искажений.
     
     
     h - хэш-функция, отображающая сообщение М в слово  (2).
     
     р - простое число, 2 < p < 2 либо 2 < p < 2.
     
     q - простое число, 2< q < 2  и q является делителем для (р - 1).
     
     а - целое число, 1 < а < р - 1, при этом а(mod p) = 1.
     
     k - целое число, 0 < k < q.
     
     [d] - наименьшее целое число, не меньшее чем d.
     
     [d] - наибольшее целое число, не большее чем d.
     
     e: = g - присвоение параметру е значения g.
     
     х - секретный ключ пользователя для формирования подписи, 0 < x < q.
     
     у - открытый ключ пользователя для проверки подписи, у = a (mod р).
     

4 ОБЩИЕ ПОЛОЖЕНИЯ

     
     Система ЭЦП базируется на методах криптографической защиты данных с использованием хэш-функции.
     
     Алгоритм вычисления функции хэширования установлен в ГОСТ Р 34.11.
     
     Процедуры цифровой подписи допускают как программную, так и аппаратную реализацию.
     
     Система ЭЦП включает в себя процедуры выработки и проверки подписи под данным сообщением.
     
     Цифровая подпись, состоящая из двух целых чисел, представленных в виде слов в алфавите , вычисляется с помощью определенного набора правил, изложенных в стандарте.
     
     Числа р, q и а, являющиеся параметрами системы, должны быть выбраны (выработаны) по процедуре, описанной в пункте 7; числа р, q и а не являются секретными. Конкретный набор их значений может быть общим для группы пользователей. Целое число k, которое генерируется в процедуре подписи сообщения, должно быть секретным и должно быть уничтожено сразу после выработки подписи. Число k снимается с физического датчика случайных чисел или вырабатывается псевдослучайным методом с использованием секретных параметров.
     

5 ПРОЦЕДУРА ВЫРАБОТКИ ПОДПИСИ

     
     
     Текст сообщения, представленный в виде двоичной последовательности символов, подвергается обработке по определенному алгоритму, в результате которого формируется ЭЦП для данного сообщения.
     
     Процедура подписи сообщения включает в себя следующие этапы:
     
     1 Вычислить h(M) - значение хэш-функции h от сообщения М.
     
     Если  (mod q) = 0, присвоить h(M) значение 01.
     
     2 Выработать целое число k, 0 < k < q.
     
     3 Вычислить два значения:
     
     r = a(mod р) и r' = r (mod q).
     
     Если r' = 0, перейти к этапу 2 и выработать другое значение числа k.
     
     4 С использованием секретного ключа х пользователя (отправителя сообщения) вычислить значение
     
      (mod q).
     
     Если s = 0, перейти к этапу 2, в противном случае закончить работу алгоритма.
     
     Подписью для сообщения М является вектор <r'> || <s>.
     
     Отправитель направляет адресату цифровую последовательность символов, состоящую из двоичного представления текста сообщения и присоединительной к нему ЭЦП.
     

6 ПРОЦЕДУРА ПРОВЕРКИ ПОДПИСИ

     
     
     Получатель должен проверить подлинность сообщения и подлинность ЭЦП, осуществляя ряд операций (вычислений).
     
     Это возможно при наличии у получателя открытого ключа отправителя, пославшего сообщение.
     
     Процедура проверки включает в себя следующие этапы:
     
     1 Проверить условия:
     
     0 < s < q и 0 < r' < q.
     
     Если хотя бы одно из этих условий не выполнено, то подпись считается недействительной.
     
     2 Вычислить h(M) - значение хэш-функции h от полученного сообщения M.     

     Если (M)(mod q) = 0, присвоить h(M) значение 01.
     
     3 Вычислить значение     

     v = ((M)) (mod q).
     
     4 Вычислить значения:
     
     z= sv (mod q) и
     
     z = (q - r') v (mod q).
     
     5 Вычислить значение
     
     u = (ay(mod p))(mod q).
     
     6 Проверить условие: r' = u.
     
     При совпадении значений r' и u получатель принимает решение о том, что полученное сообщение подписано данным отправителем и в процессе передачи не нарушена целостность сообщения, т. е. M= M. В противном случае подпись считается недействительной.
     

7 ПРОЦЕДУРЫ ПОЛУЧЕНИЯ ЧИСЕЛ р, q и а

     
     Получение простых чисел осуществляется с использованием линейного конгруэнтного датчика по модулю 2 или по модулю 2 (х= bx+ с). При этом пользователь должен задавать начальное состояние х и параметр датчика с.
     
     Заданные величины необходимо зафиксировать (запомнить) для возможности проведения проверки того, что простые числа получены по установленной процедуре.
     
     Ниже изложены процедуры получения параметров р, q и а.
     
     7.1 Процедура А
     
     Процедура позволяет получать простые числа р длины t17 битов с простым делителем q длины [t/] битов числа р-1.
     
     Получение чисел осуществляется с использованием линейного конгруэнтного датчика х= (19381 х+с) (mod 2).
     
     Задаются число х с условием 0 < х< 2 и нечетное число с с условием 0 < с < 2.
     
     Процедура вычисления включает в себя следующие шаги:
     
     1 y: = x
     
     2 Вычислить последовательность чисел (t, t, ..., t) по правилу:
     
     t: = t.
     
     Если t17, то t =[t/2],
     
     Если t < 17, то s: = i.
     
     3 Найти наименьшее простое число р, длины t битов.
     
     4 m: = s - 1
     
     5 Вычислить r =[t/16].
     
     6 Вычислить последовательность (у, ..., у) по рекурсивному правилу у = (19381 у + с) (mod 2).
     
     7 Вычислить .
     
     8 y: = y.
     
     9 Вычислить N = [2m/p] + [(2mY)/( p2].
     
     Если N нечетно, то N : = N+1.
     
     10 k : = 0.
     
     11 Вычислить p = p (N + k) + 1.
     
     12 Если р > 2m, то перейти к шагу 6.
     
     13 Проверить условия:
     
     2(mod p) = 1,
     
     2(mod p)  1.
     
     Если хотя бы одно из условий не выполнено, то k : = k + 2 и перейти к шагу 11.
     
     Если оба условия выполнены, то m : = m - 1.  
     
     14 Если m  0, то перейти к шагу 5.
     
     Если m < 0, то р - искомое простое число р и p - искомое простое число q.
     
     7.2 Процедура А'
     
     Процедура позволяет получать простые числа р длины t  33 битов с простым делителем q длины [t/2] битов числа р-1.
     
     Получение числа осуществляется с использованием линейного конгруэнтного датчика х = (97781173 х + с) (mod 2).
     
     Задаются число х с условием 0 < Х < 2 и нечетное число с с условием 0 < с < 2.
     
     Процедура вычисления включает в себя следующие шаги:
     
     1 у: = х
     
     2 Вычислить последовательность чисел (t, t, ?, t) пo правилу:
     
     t : = t.
     
     Если  t  33, то t = [t/2],
     
     Если t < 33, то s : = i
     
     3 Найти наименьшее простое число р длины t битов.
     
     4 m : = s - 1.
     
     5 Вычислить r = [t /32].
     
     6 Вычислить последовательность (y, ..., y) по рекурсивному правилу y= (97781173 y+ c) mod (2).
     
     7 Вычислить  .
     8 y : = y.
     
     9 Вычислить N = [2m/p] + [(2mY)/(p2)].
     
     Если N нечетно, то N : = N + 1.
     
     10 k : = 0.
     
     11 Вычислить p = p (N + k) + 1.
     
     12 Если р > 2m, то перейти к шагу 6.
     
     13 Проверить условия:
     
     2(mod p) = 1,
     
     2  (mod p)  1.
     
     Если хотя бы одно из условий не выполнено, то k : = k + 2 и перейти к шагу 11.
     
     Если оба условия выполнены, то m : = m - 1.  
     
     14 Если m  0, то перейти к шагу 5.
     
     Если m < 0, то р - искомое простое число р и p - искомое простое число q.
     
     7.3 Процедура B
     
     Процедура позволяет получать простые числа р длины t= 10211024 битов с делителем q  длины t= 255256 битов числа р - 1.
     
     Задаются число х с условием 0 < х < 2 и нечетное число с с условием 0 < с < 2.
     
     Процедура вычисления включает в себя следующие шаги:
     
     1 По процедуре А получить простое число q длины t битов.
     
     2 По процедуре А получить простое число Q длины 512 битов, при этом пункт 1 процедуры А не выполнять, а сохранить значение у, полученное в конце работы шага 1.
     
     3 Вычислить последовательность (y, ..., y) по рекурсивному правилу y= (19381 y+ c) (mod 2).
     
     4 Вычислить .
     5 y : = y.
     
     6 Вычислить
     
     N = [2p/(qQ)] + [(2pY)/(qQ2)].
     
     Если N нечетно, то N : = N + 1.
     
     7 k : = 0.
     
     8 Вычислить p = qQ (N + k) + 1.
     
     9 Если р > 2p, то перейти к шагу 3.
     
     10 Проверить условия:
     
     2(mod р) = 1,
     
     2(mod р) 1.
     
     Если оба условия выполнены, то р и q - искомые простые числа.
     
     Если хотя бы одно из условий не выполнено, то k : = k + 2 и перейти к шагу 8.
     
     Последовательность шагов повторить до выполнения условий на шаге 10.
     
     7.4 Процедура В'
     
     Процедура позволяет получать простые числа р длины t = 10211024 битов с делителем q длины t = 255256 битов числа р - 1.
     
     Задаются число х с условием 0 < х < 2 и нечетное число с с условием 0 < с < 2.
     
     Процедура вычисления включает в себя следующие шаги:
     
     1 По процедуре А' получить простое число q длины t битов.
     
     2 По процедуре A' получить простое число Q длины 512 битов, при этом пункт 1 процедуры А' не выполнять, а сохранить значение у, полученное в конце работы шага 1.
     
     3 Вычислить последовательность (y, ..., у) по рекурсивному правилу y = (97781173 у + с) (mod 2).
     
     4 Вычислить  .
     5 y : = y.
     
     6 Вычислить
     
     N = [2p/ (qQ)] + [(2pY)/(qQ2)].
     
     Если N нечетно, то N : = N + 1.
     
     7 k : = 0.
     
     8 Вычислить p = qQ (N + k) + 1.
     
     9 Если р > 2, то перейти к шагу 3.
     
     10 Проверить условия:
     
     2(mod р) = 1,
     
     2(mod р) 1.
     
     Если оба условия выполнены, то р и q - искомые простые числа.
     
     Если хотя бы одно из условий не выполнено, то k : = k + 2 и перейти к шагу 8.
     
     Последовательность шагов повторить до выполнения условий на шаге 10.
     
     7.5 Процедура С
     
     Процедура позволяет получить число а при заданных р и q.
     
     1 Произвольно выбрать число d, 1 < d < p -1.
     
     2 Вычислить  (mod p).
     
     3 Если f = 1, то перейти к шагу 1.
     
     Если f  1, то a : = f.
     
     Конец работы алгоритма.
     
     Проверочные примеры для вышеизложенных процедур получения чисел р, q и а, выработки и проверки подписи приведены в приложении А.
     

Приложение А
(справочное)

ПРОВЕРОЧНЫЕ ПРИМЕРЫ

     
     
     Значения параметров х, с, d, х, у, k, указанные в приложении, рекомендуется использовать только в проверочных примерах для настоящего стандарта.

     
     А1 Представление чисел и векторов
     
     Длины чисел и векторов, а также элементы последовательности t записывают в десятичной системе счисления.
     
     Последовательности двоичных символов записывают как строки шестнадцатиричных цифр, в которых каждая цифра соответствует четырем знакам ее двоичного представления.
     
     А.2 Примеры к процедурам получении чисел р, q и числа а для реализации ЭЦП
     
     А.2.1 Процедура А
     
     Необходимо получить простое число р длины 512 битов с простым делителем q длины 256 битов числа р - 1.
     
     Задают числа х= 5EC9 и с = 7341.
     
     Вычисляют последовательность t = (512, 256, 128, 64, 32, 16).
     
     Тогда в процессе выполнения процедуры будет получена последовательность простых чисел:
     
     

     
     р и р - искомые числа q и р соответственно.
     
     А.2.2 Процедура А'
     
     Необходимо получить простое число р длины 512 битов с простым делителем q длины 256 битов числа р - 1.
     
     Задают числа x= 3DFC46F1 и c = D.
     
     Вычисляют последовательность t = (512, 256, 128, 64, 32).
     
     Тогда в процессе выполнения процедур будет получена последовательность простых чисел:
     

     
     p  и p  - искомые числа q и р соответственно.
     
     A.2.3 Процедура В

     
     Необходимо получить простое число р длины 1024 битов с простым делителем q длины 256 битов числа р - 1.
     
     Задают начальные значения х = А565 и с = 538В.
     
     С помощью процедуры А получают простое число q длиной  = 256 битов:
     

     
     Затем вновь с помощью процедуры А получают простое число Q длиной  = 512 битов:
     

     
     И, наконец, получают простое число р длиной  = 1024 битов:
     

     
     А.2.4 Процедура В'
     
     Необходимо получить простое число р длины 1024 битов с простым делителем q длины 256 битов числа р - 1.
     
     Задают начальные значения x = 3DFC46F1 и c = D.
     
     С помощью процедуры А получают простое число q длиной = 256 битов:
     

     
     Затем вновь с помощью процедуры А получают простое число Q длиной = 512 битов:
     

     
     И, наконец, получают простое число р длиной = 1024 битов:
     

     
     A.2.5 Процедура С
     
     Пусть заданы числа р и q, полученные в А.2.1 по процедуре А:
     

     
     Выбирают число d = 2.
     
     Вычисляют
     

     
     Так как f 1, то f - искомое число a : = f
     
     А.3 Примеры процедур выработки и проверки ЭЦП на базе асимметричного криптографического алгоритма
     
     Пусть по процедуре А с начальными условиями x= 5ЕС9 и с = 7341 выработаны числа р, q и а:
     

     
     А.3.1 Процедура подписи сообщения

     
     - секретный ключ, М - подписываемое сообщение, причем значение хэш-функции h от сообщения М есть
     

     
     Пусть целое число
     

     
     Тогда
     

     
     Таким образом, цифровая подпись для сообщения М есть
     

     
     А.3.2 Процедура проверки подписи
     
     Пусть дано сообщение М (в данном случае M = M), его цифровая подпись
     

     
     и открытый ключ подписавшего сообщение
     

     
     Замечание
     
     Данный открытый ключ у соответствует секретному ключу х, использованному в примере подписи сообщения М
     
     у = а (mod р).
     
     Пусть
     

     
     - значение хэш-функции h для сообщения M.
     
     Условия 0 < r' < q и 0 < s < q выполняются.
     
     Вычисляют
     

     
     Таким образом:
     

     
     Условие r' = u выполнено. Это означает, что подпись подлинная.
     
     
     
     Текст документа сверен по:
     официальное издание
     Госстандарт России -
     М.: Издательство стандартов, 1994