GOST3410 (ГОСТ Р 34.10-94. Выработка и проверка цифровой подписи на базе асимметричного криптографического алгоритма)

ГОСТ Р 34.10-94

СОДЕРЖАНИЕ

стр.

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

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

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

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

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

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

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

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

ГОСТ Р 34.10-94

ВВЕДЕНИЕ

Расширяющееся применение информационных технологий при соз-

дании, обработке, передаче и хранении документов требует в определен-

ных случаях сохранения конфиденциальности их содержания, обеспечения

полноты и достоверности.

Одним из эффективных направлений защиты информации является

криптография (криптографическая защита), широко применяется в разли-

чных сферах деятельности в государственных и коммерческих структурах.

Криптографические методы защиты информации являются объек-

том серьезных научных исследований и стандартизации на национальных,

региональных и международных уровнях.

Настоящий стандарт определяет процедуры выработки и проверки

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

кого алгоритма с применением функции хеширования.

Электронная цифровая подпись обеспечивает целостность сообще-

ний (документов), передаваемых по незащищенным телекоммуникацион-

ным каналам общего пользования в системах обработки информации раз-

личного назначения, с гарантированной индетификацией ее автора (лица,

подписавшего документ).

ГОСТ Р 34.10-94

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

ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ. КРИПТОГРАФИЧЕСКАЯ ЗА-

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

НОГО КРИПТОГРАФИЧЕСКОГО АЛГОРИТМА.

Information technology. Criptographic Data Security. Produce and check

procedures of Electronic Digital Signature based on Asymmetric Criptogra-

phic Algorithm.

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

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

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

Внедрение системы ЭЦП на базе настоящего стандарта обеспечивает

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

зволяет доказательно подтвердить подпись лица, подписавшего сообщение.

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

ГОСТ Р 34.10-94

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

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

ГОСТ Р 34.11-94 Информационная технология. Криптографическая за-

щита информации. Функция хеширования.

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

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

^*-множество всех конечных слов в алфавите 

-длина слова ^*

V_k(2)-множество всех бинарных слов длины k

z (mod n)-наименование по значению неотрицательное число, срав-

нимое с z по модулю числа n.

_k слово длины k, содержащее двоичную запись вычета N (mod 2^k) неотрицательного целого числа N.

А-неотрицательное целое число, имеющее двоичную запись А (А^* )

(под длиной числа будем понимать номер старшего значащего бита в

двоичной записи числа).

Аконкатенация слов А, В^* - слово длины  в кото-

ром левые  символов образуют слово А, а правые  симво-

лов образуют слово В. Можно также использовать обозначение

А

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

М - передаваемое сообщение, М^* .

М₁ -полученное сообщение, М₁ ^{* 1)} .

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

ГОСТ Р 34.10-94

р- простое число, 2⁵⁰⁹  р  2⁵¹² либо 2¹⁰²⁰  р 2¹⁰²⁴ .

q- простое число, 2²⁵⁴  q  2²⁵⁶ и q является делителем для (p-1)

а- целое число, 1  а  р-1, при этом а^q (mod p)=1.

k- целое число, 0 k  q.

dнаименьшее целое число, не меньше, чем d.

dнаименьшее целое число, не большее, чем d

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

х- секретный ключ пользователя для формирования подписи.

0  х  q.

у-открытый ключ пользователя для проверки подписи.

у = а^x (mod p).

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

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

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

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

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

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

ГОСТ Р 34.10-94

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

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

ло k, которое генерируется в процедуре подписи сообщения , должно

быть секретным и должно быть уничтожено сразу после выработки

подписи. Число k снимается с физического датчика случайных чисел

или вырабатывается псевдослучайным методом с использованием

секретных параметров.

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

Текст сообщения, представленный в виде двоичной последова-

тельности символов, подвергается обработке по определенному ал-

горитму, в результате которого формируется ЭЦП для данного сооб-

щения.

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

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

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

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

3. Вычислить два значения :

r=a^k (mod p) и r’ = r (mod q).

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

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

сообщения) вычислить значение

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

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

Подписью сообщения М является вектор  r’ ₂₅₆   s ₂₅₆ .

ГОСТ Р 34.10-94

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

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

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

Это возможно при наличии у получателя открытого ключа отправи-

теля, пославшего сообщение,

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

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

0 s  q и 0  r’  q.

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

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

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

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

v= (h(M₁ ))^q-2 (mod q)

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

z₁ = sv (mod q) и

z₂ = (q-r’ ) v (mod q)

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

u = (a^s1 y^s2 (mod p)) (mod q)

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

ГОСТ Р 34.10-94

При совпадении значений r и u получатель принимает решение о том, что полученное сообщение подписано данным отправителем и

в процессе передачи не нарушена целостность сообщения, т.е. М =М

В противном случае подпись считается недействительной.

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

Получение простых чисел осуществляется с использованием линей-

ного конгруэнтного датчика по модулю 2¹⁶ или по модулю 2³²

(x_n = bx_n-1 + с). При этом пользователь должен задать начальное

состояние х₀ и параметр датчика с.

Заданные величины необходимо зафиксировать (запомнить) для

возможности проведения проверки того, что простые числа получены по установленной процедуре,

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

7.1 Процедура А

Процедура позволяет получать простые числа p длины t  17 битов

с простым делителем q длины  t/2  битов числа р-1.

Получеине чисел осуществляется с использованием линейного кон-груэнтного датчика х_n = (19381 x_n-1 + с) (mod 2¹⁶ ) Задаются число х₀ с условием 0  x₀  2¹⁶ и нечетное число с

с условием 0  с  2¹⁶

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

1. ₀ : = X₀

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

ГОСТ Р 34.10-94

t₀ := t.

Если t_i  17, то t_i+1 =  t_i /2 

Если t_i  17, то s := 1.

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

4. m := s-1.

5. Вычислить r_m = t_m /16 

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

7. Вычислить y_m =  y₁ 2¹⁶¹

8. y₀ := y_rm

9. Вычислить N = 2^t-1 / p_m+1 ^t-1 y_m )/(p_m+1 2^16r ) Если N нечетно , то N := N+1

10. k := 0

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

12. Если р_m  2^t , то перейти к шагу 6

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

2^{p (N+k)} (mod p_m ) = 1,

2^(N+k) (mod p_m )  1.

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

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

ГОСТ Р 34.10-94

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

Если m < 0, то p₀- искомое простое число р и р₁- искомое простое число q.

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

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

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

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

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

1. у₀ := x₀

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

t₀ := t.

Если t_i33, то t_i+1= t_i/2 ,

Если t_i<33, то s := I

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

4. m := s-1.

5. Вычислить r_m=  t_m/32 

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

7. Вычислить у_m=  у₁ 2³²¹.

ГОСТ Р 34.10-94

8. у₀ := у_r

9. Вычислить N = 2^{t -1}/ p_m+1  + (2^{t -1} y_m)/(p_m+1 2^32r )

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

10. k := 0

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

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

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

2^{р (N+k)} (mod p_m) = 1,

2^(N+k) (mod p_m)  1

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

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

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

Если m < 0, то р₀ - искомое простое число р и р₁ - искомое простое число q.

7.3 Процедура В

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