ГОСТ Р 34.10-94

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

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

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

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

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

СУЗ

ш

ГОССТАНДАРТ РОССИИ Москва

Предисловие

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

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

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

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

<С) Издательство стандартов, 1994

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

II

ГОСТ P 34.10-94

6    Вычислить

N = Г2*р-‘ / (qQ) Ц-К^Р^-1 Y) / (qQ2^l0M) I •

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

7    k: = 0.

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

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

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

2qQ(N+k) (_mo(J р) =

2q(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    Вычислить последовательность (yi, . . . , у₃₂) по рекурсивному правилу у₁₊х = (97781173 yi+c) (mod 2³²).

31

4    Вычислить Y= S Vi2³²¹.

i=0‘

5    Уо: = Уз2-

6    Вычислить

N =    /(qQ)] + |(2^fp-' Y)/(qQ2'⁰²⁴) j.

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

7    k: = 0.

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

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

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

2qQ(N+k)(_{mod р}) _{= 1?}

2q(^N+*<)(mod р)^1.

7

ГОСТ Р 34.10—94

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

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

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

7.5 Процедура С

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

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

р-1

2    Вычислить f = d<i (mod р).

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

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

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

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

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

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

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

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

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

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

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

А.2,1 Процедура А

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

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

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

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

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

Задают числа Xo=3DFC46Fl и c = D. /

Вычисляют последовательность t=(512, 1256, И2'8, 64, 32),

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

9

ГОСТ Р 34.10—94

Ь=32,	р4= 8000000В
*3=64,	р3= 9ААА6ЕВЕ	4АА58337
t2= 128,	р2= C67CE4AF	720F7BBA	B5FEBF37	В9Е74807
ti = 266,	рг= 931A58FB 4B56898F	5F0DCDF2 7F921A07	FE7549BC 66O1IEDBI	3P19F472 8C93DC75
t0=512,	р0= 8В08ЕВ13 DA2.67.65D 316А0Е29 8C6DFD0F	5AF966AA 6D38D30C 198460FA С2С565АВ	B39DF294 F1C06AAE D2B19DC3 B0BF1FAF	538580С7 0D1228C3 81С15С88 F9518F85

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

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

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

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

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

ВСС02СА0	CE4F0753	ЕС16105Е	E5D530AA
00D39F31	71842АВ2	С334А26В	5F576E0F
Затем вновь с помощью процедуры А 1=512 битов:			получают простое число Q длиной
CCEF6F73	87В6417Е	С67532А1	86ЕС619С
A4DB132F	СА02621А	DE216F1D	F6F8114C
DB3D9209	7D978C6F	583С3301	4174АА1С
1AFCCEB2	843В1D35	0D2E5D16	855А7477
И, наконец, получают простое число р длиной 1=1024 битов:
AB8F3793	8356529Е	871514С1	F48C5CBC
E77B2F4F	С9А2673А	C2C1653D	А8984090
C0AC7377	5159А26В	EF59909D	4С984663
1270Е166	53А62346	68F2A52A	01А39В92
1490Е694	C0F404B5	8D2E1497	0FCCB478
F98D01E9	75А1028В	9536D9.12	DE5236D2
DD2FC396	В7715359	4D417878	0E5F16F7
18471Е21	11С8СЕ64	A7D7E196	FA57142D

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

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

ГОСТ Р 34.10-94

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

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

931A58FB    6F0DCDF2    FE7549BC    3B19F472

4B56898F    7F921A07    6601ЕЦВ1    8C93DC75

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

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

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

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

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

Р-1

!=d ^q (mod р) - 9E96031S AFAD2538 06755984 8EBE2CD4

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

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

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

11

р=г EE8172AE 854510Е2 ЕА0А12ВЗ 6ВВ0С345	8996608F 977A4D63 43E9190F D165976E	В69359В8 ВС97322С 23J77539 F2195EC9	9ЕВ82А69 E5DC3386 84583978 B1C379E3
q— 98915Е7Е B064BDC7	C8265EDF 285DD50D	CDA31E88 7289F0AC	F24809DD 6F49DD2D
а= 9Е960315 AFAD2538 06755984 8EBE2CD4	00С8774А В4В612Г70А А49Е5093 6AC3D849	869582D4 6F7C8837 04D648BE 5В142АА6	AFDE2127 B50D50F2 2АВ5ААВ1 СЕ23Е21С
А.3.1 Процедура подписи сообщения
Пусть х- 30363145 35324234	38303830 31413237	34363045 38324331	42353244 38443046
— секретный ключ, М — подписываемое функции h от сообщения М есть		сообщение,	причем значение
h(M) =ш= 35344541 43363345	32454236 37414342	44313445 34454136	34373139 31454230
Пусть целое число.
k« 90F3A564 11В7105С	439242F5 64E4F539	186ЕВВ22 Q807E636	4С8Е2238 2DF4C72A

Тогда
r*=ak(mod р)** 47681С97 D07A7E02: FF0AD188 98.E4AD8C	4373В065 Е311846Е 02643В5С FC689817	ЗС6СА965 97А8С126 6С998775 76ВА8216	C8F86127 3F8A76AF 0С6В0458 3ADBC988
r'eWjnod q) *= 3E5F895E 57В784С5	276D81>D2 7ABDBD80	D52C0763 7BC44FD4	270А4581 3A32AC06
=sxr'+km(mod q) e 3F0DD5D4 DBF72959	400D47C0 2Е37С748	8Е4СЕ505 56DAB851	FF7434B6 15А60955
Таким образом, цифровая подпись для сообщения М есть
<r'>M»H<s>«e- 3E5F895E 3F0DD5D4 DBF72959	276D81D2 7ABDBD80 400D4I7C0 2Е37С748	D52C0763 7BC44FD4 8Е4СЕ605 56DAB851	270А4581 3A32AC06 FF7434B6 15А60955

12

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

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

14

ГОСТ Р 34.10-94

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

Ш

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Mi — полученное сообщение, Miep*M

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

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

(Р-1).

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

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

[dj — наибольшее целое число, не большее чем 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    Выработать целое число k, 0<k<q.

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

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

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

s = (xr' + kh(M) (mod q).

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

Подписью для сообщения М является вектор <г^/>₂5б||<s>256-

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

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

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

3

ГОСТ Р 34.10-94

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

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

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

0<s<q и 0<r^/<q.

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

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

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

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

v=(h(Mi))4-²(mod q).

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

zi = sv (mod q) и

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

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

u= (a^zly^z2(mod p))(mod q).

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

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

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

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

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

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

7.1 Процедура А

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

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

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

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

4

ГОСТ Р 34.10-94

1    Уо: = х₀

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

to: = t

Если ti>17, то t_1+L =[ti /2J,

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

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

4    m: = s-l

5    Вычислить r_m =rt_m-i-i/1€Г[.

6    Вычислить последовательность (у_ь . . ., у_г ) по рекурсивному правилу у₁₊₁ = (19381 yi+c) (mod 2¹⁶).

^г.п“¹

7    Вычислить* Y_m= 2 v_i2¹⁶¹.

i-o '

8уо: = У,_т-

9    Вычислить N = f2m^_1 p_m+1]+f(2'm-¹Y_m)/(p_m+,2^1,rn’)J-Если N нечетно, то N: = N+1.

10    k: —0.

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

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

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

₂Pm₊l<N+k) _{(mod рш) = 1>}

2<N+kT (nipd p _m

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

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

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

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

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

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

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

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

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

1    у₀: = х₀

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

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

5

ГОСТ Р 34.10-94

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

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

4    m: = s—1.

б Вычислить r_m = ft_m/32j.

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

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

i=0 *

8уо:=Уг,„-

9    Вычислить N = f2m ‘/'Pm+ll + K²” ^lY_m)/(Pm+l2^32rm)]-Если N нечетно, то N : = N+1.

10    k: = 0.

11    ВЫЧИСЛИТЬ pm=p_m+i (N + k)"+l.

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

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

2^pm+ⁱ<^N+M (mod p_m) = 1,

2(^N+k){mod p_m)=^l.

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

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

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

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

7.3 ПроцедураВ

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

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

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

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

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

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

63

4    Вычислить Y= 2 y_t 2¹®¹,

но

5у₀:«Уб4.

б