Предисловие

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

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

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

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

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

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

ГОСТ Р 34.10-94

СОДЕРЖАНИЕ

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

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

3    Обозначения    *............ I

4    Общие положения     .......... 2

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

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

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

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

III

ВВЕДЕНИЕ

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

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

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

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

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

IV

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

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

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

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

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

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

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

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

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

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

Mi — полученное сообщение, Miep*.^!)

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

р — простое число, 2⁵⁰⁹<р<2⁵¹² либо 2¹⁰²⁰<р<2¹⁰²⁴. q — простое число, 2²⁵⁴<q<2²⁵⁶ и q является делителем для (Р—!)•

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

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

[d] — наибольшее целое число, не большее чем d. e: = g — присвоение параметру е значения g. х — секретный ключ пользователя для формирования подписи, 0<x<q.

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

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

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

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

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

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

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

2

ГОСТ Р 34.10-94

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

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

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

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

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

1    Вычислить h(M)-— значение хэш-функции h от сообщения М.

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

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

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

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

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

л.

s=(xr'+kh(M) (modq).

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

Подписью для сообщения М является вектор <г'>25б|| <s>25o-

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

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

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

3

ГОСТ Р 34.10-94

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

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

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

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

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

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

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

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

✓ч

v= (h(Mj))^<*"²(mod q).

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

Z| = sv (mod q) и

z₂ = (q—г') v(mod q).

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

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

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

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

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

Получение простых чисел осуществляется с' использованием линейного конгруэнтного датчика по модулю 2¹⁶ или по модулю 2³² (х , = bx_n_! + с). При этом пользователь должен задавать начальное состояние хо и параметр датчика с.

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

Ниже изложены процедуры получения параметров р, q и а.

7.1 Процедура А

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

Получение чисел осуществляется с использованием линейного конгруэнтного датчика х_л= (19381 x_n-_l+c)(mod 2¹⁶).

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

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

4

ГОСТ Р 34.10-94

1    Уо’ — Хо

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

to:—t.

Если ti>17, то t|_+t =lti /2J,

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

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

4    m: = s—1

5    Вычислить r_m =rt_in+i/16Г|.

6    Вычислить последовательность (уi, .... у_Г|п ) по рекурсивному правилу у_И1 =(19381 у,+c)(mod 2¹⁶).

^гш”¹

7    Вычислит# Y_m= 2 v,2^,ei.

i-o ’

8уо: = Уг_ш-

9    Вычислить    p_m+1l+f(2m-¹Y_m)/(p_ra+12^,erm)J.

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

10    k: = 0.

11    Вычислить p_m — Pm+l (N + k) + 1.

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

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

2^pm+l(N+k) (mod p_m) = l,

2^(N+k)(mod р_т)Ф\.

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

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

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

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

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

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

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

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

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

1    Уо: = Хо

2    Вычислить последовательность чисел (to, ti,t_e)no правилу: to- = t.

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

5

ГОСТ Р 34.10-94

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

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

4    m:=s—1.

5    Вычислить г„, =ft_ra/32|

6    Вычислить последовательность (у_ь . . . , у_г ) по рекурсивному правилу у_|+1 = (97781173 yi+c) mod (2³²).

^rm^—1

7    Вычислить Y_m= t v,2³²¹.

i-o’

8yo^; = y_rm.

9    Вычислить N = f2^m Vpm+il+lP ^m ‘Y_m)/(p_m+l2³²4l*

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

10    k: = 0.

И Вычислить p_m =p_m+1 (N-fk) +1.

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

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

2^Pm+i<^N+^k) _(mod p_m)=l,

2<^N+k,(mod p_m)^I.

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

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

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

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

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

7.3 Процедура В

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

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

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

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

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

3    Вычислить последовательность (у_ь . . . , Уб4) по рекурсивному правилу yi-ri = (19381 у, 4-с) (mod 2¹⁶).

63

4    Вычислить Y= 2 y,2^,el,

l-o

5    Уо:~Уб4.

S