ГОСТ 34.310-95 Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе ассиметричного криптографического алгоритма

ГОСТ Р 34.10—94

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

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

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

ПРОЦЕДУРЫ ВЫРАБОТКИ И ПРОВЕРКИ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ НА БАЗЕ АСИММЕТРИЧНОГО КРИПТОГРАФИЧЕСКОГО АЛГОРИТМА

Издание официальное

ГОССТАНДАРТ РОССИИ

Москва

Предисловие

• 1 РАЗРАБОТАН Главным управлением безопасности связи Феде-* рального агентства правительственной связи и информации И Всероссийским научно-исследовательским институтом стандарт тизации

ВНЕСЕН Техническим комитетом по стандартизации ТК 22 «Информационная технология» и Федеральным агентством правительственной связи и информации

• 2 ПРИНЯТ И ВВЕДЕН В ДЕЙСТВИЕ Постановлением Госстандарта России от 23.05.94 № 154

• 3 ВВЕДЕН ВПЕРВЫЕ

© Издательство стандартов, 1994

Настоящий стандарт не может быть полностью или частично воспроизведен, 1иражирован и распространен в качестве официального издания без разрешения Госстандарта России

СОДЕРЖАНИЕ

• 1 Область применения

• 2 Нормативные ссылки.......... . , .

• 3 Обозначения . . _.............

• 4 ОбгЦис положения .

• 5 Процедура выработки подписи

• 6 Процедура проверки подписи

• 7 Процедуры получения чисел р, q и а

Приложение А Проверочные примеры

ВВЕДЕНИЕ

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

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

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

Настоящий стандарт определяет процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма с применением функции хэширования.

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

ГОСТ Р 34.10—94

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

Информационная технология. КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма.

Information technology.

Cryptographic Data Security.

Produce and check procedures of Electronic Digital Signature based on Asymmetric Cryptographic Algorithm.

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

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

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

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

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

В настоящем стандарте использованы ссылки на следующий стандарт:

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

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

В настоящем стандарте используются следующие обозначения.

Р* — множество всех конечных слов в алфавите р = {0,1}.

|А| — длина слова А^р*.

Vr(2) — множество всех бинарных слов длины к.

z(mod n) — наименьшее по значению неотрицательное число, сравнимое с z по модулю числа п.

<N>_k — слово длины к, содержащее двоичную запись вычета N(mod 2^к) неотрицательного целого числа N.

А — неотрицательное целое число, имеющее двоичную запись А (А ер*) (под длиной числа будем понимать номер старшего значащего бита в двоичной записи’числа).

А||В — конкатенация слов А, Вер* — слово длины | А| + | В |, в котором левые |А| символов образуют слово А, а правые |В| символов образуют слово В. Можно также использовать обозначение A|jB=AB.

A^k — конкатенация к экземпляров слова А(Аер*).

М — передаваемое сообщение, Мёр*.

М| — полученное сообщение, Л^ер*.^

h — хэш-функция, отображающая сообщение М в слово h(M)eV₂₅₆(2).

р — простое число, 2°⁰⁹<р<2⁵¹² либо 2¹⁰²⁰<р<2¹⁰²⁴.

q — простое число, 2²⁵⁴<q<2²⁵⁶ и q является делителем для (р—1).

а — целое число, 1 <а<р—1, при этом a^<’(mod р) = 1.

к — целое число, 0<k<q.

[d] — наименьшее целое число, не меньшее чем d.

[d] — наибольшее целое число, не большее чем d.

e: = g — присвоение параметру е значения g.

х — секретный ключ пользователя для формирования подписи, 0<x<q.

у — открытый ключ пользователя для проверки подписи, y=a^x(mod р).

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

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

Алгоритм вычисления функции хэширования установлен в ГОСТ Р 34.11.

Процедуры цифровой подписи допускают как программную, так и аппаратную реализацию.

Система ЭЦП включает в себя процедуры выработки и проверки подписи под данным сообщением.

¹) Отправляемые и получаемые последовательности, в том числе сообщения и подписи, могут отличаться друг от -друга из-за случайных или преднамеренных искажений.

Цифровая подпись, состоящая из двух целых чисел, представленных в виде слов в алфавите 0, вычисляется с помощью определенного набора правил, изложенных в стандарте.

Числа р, q и а, являющиеся параметрами системы, должны быть выбраны (выработаны) по процедуре, описанной в пункте 7. числа р, q и а не являются секретными. Конкретный набор их значений может быть общим для группы пользователей. Целое число к, которое генерируется в процедуре подписи сообщения, должно быть секретным и должно быть уничтожено сразу после выработки подписи. Число 1< снимается с физического датчика случайных чисел или вырабатывается псевдослучайным методом с использованием секретных параметров.

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

Текст сообщения, представленный в виде двоичной последовательности символов, подвергается обработке по определенному алгоритму, в результате которого формируется ЭЦП для данного сообщения.

Процедура подписи сообщения включает в себя следующие этапы:

• 1 Вычислить h(M)-—значение хэш-функции h от сообщения М. Если h(M) (mod q) =0, присвоить h(M) значение 0²⁵⁵1.

• 2 Выработать целое число k, 0<k<q.

• 3 Вычислить два значения: r = a^k(mod р) и r'=r(mod q).

Если-г' = 0, перейти к этапу 2 и выработать другое значение числа к.

• 4 С использованием секретного ключа х пользователя (отправителя сообщения) вычислить значение

$= (xr'4-kh(M) (modq).

Если s = 0, перейти к этапу 2, в противном случае закончить работу алгоритма.

Подписью для сообщения М является вектор <г'>₂₅₆||<$>2.w.

Отправитель направляет адресату цифровую последовательность символов, состоящую из двоичного представления текста сообщения и присоединительной к нему ЭЦП.

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

Получатель должен проверить подлинность сообщения и подлинность ЭЦП, осуществляя ряд операций (вычислений).

Это возможно при наличии у получателя открытого ключа отправителя, пославшего сообщение.

Процедура проверки включает в себя следующие этапы:

• 1 Проверить условия:

0<s<q и 0<r'<q.

Если хотя бы одно из этих условий не выполнено, то подпись считается недействительной.

• 2 Вычислить h(Mj) — значение хэш-функции h от полученного сообщения Mi.

Если h(M|) (mod q)=0, присвоить h(M|) значение 0²⁵³1,

• 3 Вычислить значение

v= (h(M_I))⁽»-²(mod q).

• 4 Вычислить значения:

Z| = sv (mod q) и z₂ = (q—г') v(mod q).

• 5 Вычислить значение

u = (a^z,y^x2(mod p))(mod q)

• 6 Проверить условие: r'=u.

При совпадении значений r^z и и получатель принимает решение о том, что полученное сообщение подписано данным отправителем и в процессе передачи не нарушена целостность сообщения, т. е. Mi=M. В противном случае подпись считается недействительной.

• 1 Уо: = х_о

• 2 Вычислить последовательность чисел (to, ti, ...» t_s) по правилу:

t₀: = t.

Если t_f>17, то t|-H=[ti/2j,

Если tj <17, то s: = i.

• 3 Найти наименьшее простое число р₃ длины t_s битов,

• 4 m: = s—1

• 5 Вычислить г=rt_inxi/16].

• 6 Вычислить последовательность (у_ь ...» у_||п) по рекурсивному правилу yi <! = (19381 yi +с) (mod 2¹⁶).

^rin“^l

• 7 Вычислит# Y_m= S v_f2¹⁶¹.

i-0 '

• ⁸ Уо: = Уг_т-

• 9 Вычислить N=^-‘ p_m+l]+f(2^f;-'Y_m)/(p_in+12'^erm)J.

Если N нечетно, то N: = N+1,

10k: = 0.

• 11 Вычислить p_m =Pm+i (N + k) + 1.

• 12 Если p_m >2Х то перейти к шагу 6.

• 13 Проверить условия:

2Pm+l<^N+k) (mod p_m)_ J*

2(N+k) (_mocj p_m

Если хотя бы одно из условий не выполнено, то k: = k + 2 и перейти к шагу 11.

Если оба условия выполнены, то m: = m—1.

• 14 Если т^О, то перейти к шагу 5.

Если т<0, то ро — искомое простое число р и pi — искомое простое число q.

• 7.2 Процедура А'

Процедура позволяет получать простые числа р длины t^33 битов с простым делителем q длины lt/2] битов числа р-1.

Получение числа осуществляется с использованием линейного конгруэнтного датчика х_п — (97781173 х_п-_г +с) (mod 2³²).

Задаются число Хо с условием 0<х₀<2³² и нечетное число с с условием 0<с<2³².

Процедура вычисления включает в себя следующие шаги:

• 1 Уо- = х_о

• 2 Вычислить последовательность чисел (to, t_h..., t₈)no правилу: t₀: = t.

Если ti>33, то t|+i =[ti/2J,„

Если tj <33, то s: = i

• 3 Найти наименьшее простое число р₃длины t_s битов.

• 4 m: = s—1.

• 5 Вычислить г_ш =Пт/32Т.

• 6 Вычислить последовательность (у_ь ...» у_Г(П ) по рекурсивному правилу уц-! = (97781173 y_t 4-с) mod (2³²).

^rm-'

• 7 Вычислить Y_m^e 2 v^³²¹.

i-0"

• 8 Уо: = Уг_т-

• 9 Вычислить N = f2^nl J+l(2 m ¹Y_m)/(p_m._H2^32rm)|.

Если N нечетно, то N :==N+1.

• 10 k: = 0.

• 11 Вычислить p_m =Pm-rl (N + k) + 1.

• 12 Если p_m>2^tfn , то перейти к шагу 6.

• 13 Проверить условия:

2^₽">+i^(N+k) (mod p,_n) = l,

2<N+k)(mod p„,)#=!.

Если хотя бы одно из условий не выполнено, то k: = k + 2 и

перейти к шагу 11.

Если оба условия выполнены, то m: = m—1.

• 14 Если гп^О, то перейти к шагу 5.

Если т<0, то ро — искомое простое число р и pi — искомое простое число q.

• 7.3 Процедура В

Процедура позволяет получать простые числа р длины t_p = 1021 4-1024 битов с делителем q длины t_q =2554-256 битов числа р-1.

Задаются число х₀ с условием 0<х₀<2¹⁶ и нечетное число с с условием 0<с<2¹⁶.

Процедура вычисления включает в себя следующие шаги:

• 1 По процедуре А получить простое число q длины t_q битов.

• 2 По процедуре А получить простое число Q длины 512 битов, при этом пункт 1 процедуры А не выполнять, а сохранить значение у₀, полученное в конце работы шага L

• 3 Вычислить последовательность (у...... уб«) по рекурсив

ному правилу у_Нл = (19381 yj +с) (mod 2¹⁶).

63

• 4 Вычислить Y= 2 Vi2^lbl,

l-o'

• 5 Уо:“Уб4.

• 6 Вычислить

N = [2^,p-^,/(qQ)|x[(2^tp-¹Y)/(qQ2^)|.

Если N нечетно, то N: = N+1.

• 7 к: = 0.

• 8 Вычислить p = qQ(N + k) + l.

• 9 Если р>2 р , то перейти к шагу 3.

• 10 Проверить условия:

2qQ<N+k)(mod р) = 1,

24(N+k) (_mod р)=^1.

Если оба условия выполнены, то р и q — искомые простые числа.

Если хотя бы одно из условий не выполнено, то k: = k+2 и перейти к шагу 8.

Последовательность шагов повторить до выполнения условий на шаге 10.

• 7.4 Процедура В'

Процедура позволяет получать простые числа р длины t_p= 1021-г-1024 битов с делителем q длины t_q =255-^256 битов числа р—1.

Задаются число х₀ с условием 0<х_о<2³² и нечетное число с с условием 0<с<2³².

Процедура вычисления включает в себя следующие шаги:

• 1 По процедуре А' получить простое число q длины t_q битов.

• 2 По процедуре А' получить простое число Q длины 512 битой, при этом пункт 1 процедуры А' не выполнять, а сохранить значение уо, полученное в конце работы шага 1.

• 3 Вычислить последовательность (у₍, . . . , узг) по рекурсивному правилу y_I+i = (97781173 yi+c) (mod 2³²).

31

• 4 Вычислить Y= S v₍2³²¹,

i-0’

• 5 Уо-=У32-

• 6 Вычислить

N = [2 / (qQ) ] — | (2^ Y) / (qQ2¹⁰²⁴) |.

Если N нечетно, то N: = N+1.

• 7 k: = 0.

• 8 Вычислить p = qQ(N + k) + l.

• 9 Если р>2*Р, то перейти к шагу 3.

• 10 Проверить условия:

2qQ(N+k) (mod р) = 1,

2<i^(N+k) (mod р)=^=Е

Если оба условия выполнены, то р и q — искомые простые числа.

Если хотя бы одно из условий не выполнено, то k: = k + 2 и перейти к шагу 8.

Последовательность шагов повторить до выполнения условий на шаге 10.

• 7.5 Процедура С

Процедура позволяет получить число а при заданных р и q.

• 1 Произвольно выбрать число d, l<d<p—1.

p-i

• 2 Вычислить f = d4 (mod p).

3'Если f=l, то перейти к шагу 1.

Если f#=l, то a : = f.

Конец работы алгоритма.

Проверочные примеры для вышеизложенных процедур получения чисел р, q и а, выработки и проверки подписи приведены з приложении А.»

Приложение А

(справочное)

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

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

А1 Представление чисел и векторов

Длины чисел и векторов, а также элементы последовательности t записывают в десятичной системе счисления.

Последовательности двоичных символов записывают как строки шестнадцатеричных цифр, в которых каждая цифра соответствует четырем знакам ее двоичного представления.

А.2 Примеры к процедурам получения чисел р, q и числа а для реализации ЭЦП

А.2.1 Процедура А

Необходимо получить простое число р длины 512 битов с простым делителем q длины.256 битов числа р—1.

Задают числа Хо=5ЕС9 и с—7341.

Вычисляют последовательность (=(512, 256, 128, 64, 32, 16).

Тогда в процессе выполнения процедуры будет получена последовательность

pi и ро — искомые числа q и р соответственно.

А.2.2 Процедура А'

Необходимо получить простое число р длины 512 битов с простым делителем q длины 256 битов числа р—1.

Задают числа x₀=3DFC46Fl и c=D. * .

Вычисляют последовательность (=(512, 256, 1<2«8, 64, 32).

Тогда в процессе выполнения процедур будет получена последовательность простых чисел:

А.2.3 Процедура В

Необходимо получить простое число р длины <1024 битов с простым делителем q длины 256 битов числа р—1.

Задают начальные значения х₀=А565 и с=538В.

С помощью процедуры А получают простое число q длиной 1 = 256 битов:

ВСС02СА0 CE4F0753 ЕС16105Е E5D530AA

00D39F31 71842АВ2 С334А26В 5F576E0F

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

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

А.2.4 Процедура В'

Необходимо получить простое число р длины 1024 битов с простым делителем q длины 256 битов числа р— I.

Задают начальные значения xo=3DFC46Fil и c=D.

С помощью процедуры А получают простое число q длиной 1=256 битов:

931A58FB 6F0DCDF2 FE7549BC 3F-19F472

4B56898F 7F921A07 6601Et)Bl 8C93DC75

процедуры А получают простое число Q длиной

А.2.5 Процедура С

и q, полученные в А.2,1 по процедуре А:

Так как f^l, то f — искомое число a:=f

А.З Примеры процедур выработки и проверки ЭЦП на базе асимметричного криптографического алгоритма

Пусть по процедуре А с начальными условиями х₀=5ЕС9 и с=7341 выработаны числа р, q и а:

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

Пусть х- 30363145 38303830

35324234 31413237

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

Тогда

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

А.3.2 Процедура проверки подписи

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

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

Замечание

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

y=a^x(mod- р).

Пусть

т— 35344541 32454236

43363345 37414342

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

z_a=(q~г') v(mod q)= 18В04С46 G1D9E875 5ZJFDA9E

3AFD0A8D FCADB67C 505C7F03

Условие r^z—и выполнено. Это означает, что подпись подлинная.

УДК 681.3.06:006.354 П85 ОКСТУ 5002

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

14