Расширяющееся применение информационных технологий при создании, обработке, передаче и хранении документов требует в определенных случаях сохранения конфиденциальности их содержания, обеспечения полноты и достоверности.
Одним из эффективных направлений защиты информации является криптография (криптографическая защита), широко применяется в различных сферах деятельности в государственных и коммерческих структурах.
Криптографические методы защиты информации являются объектом серьезных научных исследований и стандартизации на национальных, региональных и международных уровнях.
Настоящий стандарт определяет процедуры выработки и проверки электронной цифровой подписи на базе асимметрического криптографического алгоритма с применением функции хеширования.
Электронная цифровая подпись обеспечивает целостность сообщений (документов), передаваемых по незащищенным телекоммуникационным каналам общего пользования в системах обработки информации различного назначения, с гарантированной индетификацией ее автора (лица, подписавшего документ).
1
ГОСУДАРСТВЕННЫЙ СТАНДАРТ РОССИЙСКОЙ ФЕДЕРАЦИИ
ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ. КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ. ПРОЦЕДУРЫ ВЫРАБОТКИ И ПРОВЕРКИ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ НА БАЗЕ АСИММЕТРИЧНОГО КРИПТОГРАФИЧЕСКОГО АЛГОРИТМА.
Information technology. Criptographic Data Security. Produce and check procedures of Electronic Digital Signature based on Asymmetric Criptographic Algorithm.
Дата введения 1995-01-01
1 ОБЛАСТЬ ПРИМЕНЕНИЯ
Настоящий стандарт устанавливает процедуры выработки и проверки электронной цифровой подписи (ЭЦП) сообщений (документов), передаваемых по незащищенным телекоммуникационным каналам общего пользования в системах обработки информации различного назначения, на базе асимметричного криптографического алгоритма с применеинем функции хеширования.
Внедрение системы ЭЦП на базе настоящего стандарта обеспечивает защиту передаваемых сообщений то подделки, искажения и однозначно позволяет доказательно подтвердить подпись лица, подписавшего сообщение.
2 НОРМАТИВНЫЕ ССЫЛКИ
В настоящем стандарте использованы ссылки на следующий стандарт:
ГОСТ Р 34.11-94 Информационная технология. Криптографическая защита информации. Функция хэширования.
2
3 ОБОЗНАЧЕНИЯ
В настоящем стандарте используются следующие обозанчения: Р*-множество всех конечных слов в алфавите Р={0,1}.
|А|-длина слова АеР*.
Vk (2)-множество всех бинарных слов длины к z (mod n)-наименование по значению неотрицательное число, сравнимое с z по модулю числа п.
<N>k -слово длины к, содержащее двоичную запись вычета N (mod 2k) неотрицательного целого числа N. А-неотрицательное целое число, имеющее двоичную запись А
(АеР* )
(под длиной числа будем понимать номер старшего значащего
бита в
двоичной записи числа).
А||В-конкатенация слов А, Вер* - слово длины |а|+|в|,в
котором левые |А| символов образуют слово А, а правые
|в| символов образуют слово В. Можно также использовать
обозначение а||в=АВ.
Ак- конкатенация к экземпляров слова А (АеР* ).
М - передаваемое сообщение, Мер* .
Мi -полученное сообщение, Мгер* 1] .
h - хэш-функция, отображающая сообщение М в слово
h(M) eV256 (2)
1) Отправляемые и получаемые последовательности, в том числе сообщения и подписи, могут отличаться друг от друга из-за случайных или преднамеренных искажений.
з
р- простое число, 2509 < р < 2512 либо 21020 < р <21024.
q- простое число, 2254 < q < 2256 и q явлвется делителем для (p-1)
а- целое число, 1 < а < р-1, при этом аq (mod p)=l.
k- целое число, 0< к < q.
-наименьшее целое число, не меньше, чем d.
LdJ-наименьшее целое число, не большее, чем d е : = g - присвоение параметру е значения g. х- секретный ключ пользователя для формирования подписи.
О < х < q.
у-открытый ключ пользователя для проверки подписи. у = ах (mod p).
4 ОБЩИЕ ПОЛОЖЕНИЯ
Система ЭЦП базируется на методах криптографической
защиты данных с использованием хеш-функции.
Алгоритмы вычисления функции хэширования установлен в
ГОСТ Р 34.11.
Процедуры цифровой подписи допускают как программную,
так и аппаратную реализацию.
Система ЭЦП включает в себя процедуры выработки и
проверки подписи под данных сообщением.
Цифровая подпись, состоящая из двух целых чисел,
представленных в виде слов в алфавите |3 , вычисляется с помощью определенного набора правил, изложенных в тексте стандарта .
4
Числа р, q и а, являющиеся параметрами системы, должны быть выбраны (выработаны) по процедуре, описанной в пункте 7.
Числа р, q и а не являются секретными. Конкретный набор их значений может быть общим для группы пользователей. Целое число k, которое генерируется в процедуре подписи сообщения , должно быть секретным и должно быть уничтожено сразу после выработки подписи. Число k снимается с физического датчика случайных чисел или вырабатывается псевдослучайным методом с использованием секретных параметров.
5 ПРОЦЕДУРА ВЫРАБОТКИ ПОДПИСИ
Текст сообщения, представленный в виде двоичной последовательности символов, подвергается обработке по определенному алгоритму, в результате которого формируется ЭЦП для данного сообщения.
Процедура подписи сообщения включает в себя следующие этапы:
1.Вычислить h(M) -значение хеш-функции h от сообщения М.
Если h(M)(mod q)=0, присвоить h(M) значение О255 1.
2.Выработать целое число k, 0<k < q.
3.Вычислить два значения : r=ak (mod р) и г’ = г (mod q).
Если г’ =0, перейти к этапу 2 и выработать другое значение числа к.
4.С использованием секретного ключа х пользователя (отправиетля сообщения) вычислить значение
s= (xr’ + kh(М))(mod q).
Если s=0, перейти к этапу 2, в противном случае
закончить работу алгоритма.
Подписью сообщения М является вектор < г’ >256II < s
•^256
Отправитель направляет адресанту цифровую последовательность символов, состоящую из двоичного представления текста сообщения и присоединенной к нему ЭЦП.
5
6 ПРОЦЕДУРА ПРОВЕРКИ ПОДПИСИ
Получатель должен проверить подлинность сообщения и подлинность ЭЦП, осуществляя ряд операций (вычислений). Это возможно при наличии у получателя открытого ключа отправителя, пославшего сообщение, Процедура проверки включает в себя следующие этапы:
1. Проверить условие:
0< s < q и 0 < r’ < q.
Если хотя бы одно из этих условий не выполнено, то
подпись считается недействительной.
2. Вычислять h(M1 )-значение хеш-функции h от полученного сообщения М1 .
Если H(M1 )(mod q)=0, присвоить h(M1 ) значение 0255 1.
3. Вычислить значение
v= (h(M1 ))q-2 (mod q)
4. Вычислить значения: z1 = sv (mod q) и z2 = (q-r’ ) v (mod q)
5. Вычислить значение
u = (as1 ys2 (mod p)) (mod q)
6. Проверить условие: r’ = u.
При совпадении значений r и u получатель принимает решение о том, что полученное сообщение подписано данным отправителем и
в процессе передачи не нарушена целостность сообщения, т.е. М =М В противном случае подпись считается недействительной.
7 ПРОЦЕДУРЫ ПОЛУЧЕНИЯ ЧИСЕЛ p, q И а
Получение простых чисел осуществляется с использованием линейного конгруэнтного датчика по модулю 216 или по модулю 232 (xn = bxn-1 + с). При этом пользователь
6
должен задать начальное состояние х0 и параметр датчика с.
Заданные величины необходимо зафиксировать (запомнить) для возможности проведения проверки того, что простые числа получены по установленной процедуре, Ниже изложены процедуры получения параметров р, q и а.
7.1 Процедура А
Процедура позволяет получать простые числа р длины t > 17 битов
с простым делителем q длины L t/2 J битов числа р-1. Получеине чисел осуществляется с использованием линейного кон-груэнтного датчика хп = (19381 хп_! + с) (mod 216 )Задаются число х0 с условием 0 <
х0 < 216 и нечетное число с
с условием 0 < с < 216
Процедура вычисления включает в себя следующие шаги:
1.Y0 : = Х0
2.Вычислить последовательность чисел (t0 , ti , ..., t5 ) по правилу:
t0 := t.
Если ti > 17, то ti+i = L ti /2 J
Если ti < 17, то s := 1.
3.Найти наименьшее простое число р длины t битов.
4.m := s-1.
5.Вычислить rm = [~tm /16 1
6.Вычислить последовательность {уг,....../Угт ) по
Если хотя бы одно из условий не выполнено , то к :=к +
2 и перейти к шагу 11.
Если оба условия выполнены, то m := m-1.
14. Если m>0 , то перейти к шагу 5.
Если m < 0, то р0- искомое простое число р и рг- искомое
простое число q.
7.2 Процедура А’
Процедура позволяет получать простые числа р длины t>33
битов с простым делителем q длины Lt/2J битов числа р-1. Получение чисел осуществляется с использованием линейного конгруэнтного датчика хп= (97781173 хп_! + с ) (mod 232)
Задаются число х0 с условием 0< х0 < 232 и нечетное число с условием 0< с < 232. Процедура вычисления включает в себя следующие шаги:
1.у0 := х0
2.Вычислить последовательность чисел (t0, tlr....., ts)
по правилу:
t0 := t.
Если ti>33, то ti+i=L ti/2 J, Если ti<33, то s := I
3.Найти наименьшее простое число ps длины ts битов.
4.m := s-1.
5.Вычислить rm= Г tm/32 1
6. Вычислить последовательность ( уlf.....,уrm) по
рекурсивному правилу уi+i= (97781173 уi + с) mod (232).
7.Вычислить уm= X уi 2321.
8.у0 := уг
9.Вычислить N = [2t_1/ pm+11 + L(2fc_1ym)/(pm+1 232r )J
Если N нечетно, то N := N + 1
10.k := 0
11.Вычислить рm = pm+i (N + k) + 1
12.Если рm > 2t, то перейти к шагу б
13.Проверить условия : 2р(N+k)(mod pm) = 1,
2(N+k) (mod pm) Ф 1
8
Если хотя бы одно из условий не выполнено, то к := к+2
и перейти к шагу 11.
Если оба условия выполнены, то m := m-1.
14. Если m > 0, то перейти к шагу 5.
Если m < 0, то ро - искомое простое число р и рг -
искомое простое число q.
7.3 Процедура В
Процедура позволяет получать простые числа р длины tp =
1021 -г- 1024 битов с делителем q длины tq = 255 -s- 256
битов числа р-1.
Задаются число х0 с условием 0 < х0 < 216 и нечетное
число с условием 0 < с < 216.
Процедура вычисления включает в себя следующие шаги:
1.По процедуре А получить простое число q длины tq битов.
2.По процедуре А получить простое число Q длины 512 битов, при этом пункт 1 процедуры А не выполнять, а сохранить значение у0, полученное в конце работы шага 1.
N =[2t -1/(qQ)l + L(2t_1 у)/( qQ21024)J Если N нечетно, то N := N+1
7.к := 0
8.Вычислить р = qQ(N + к) + 1
9/ Tckb р > 2е, то перейти к шагу 3. 10. Проверить условия:
2qQ(N+k) (mod р) = Х/
2q(N+k) (mod p) Ф1
Если оба условия выполнены, то р и q - искомые простые
числа.
Если хотя бы одно не выполнено. то к := к + 2 и перейти
к шагу 8.
последовательность шагов повторить до выполнения
условий на шаге 10.
7.4 Процедура В’
9
Процедура позволяет получать простые числа р длины tp=
1021-5- 1024 битов с делителем q длины tq = 255 -s- 256
битов числа р-1.
Задаются число х0 с условием 0 < х0 < 232 и нечетное
число с с условием 0 < с < 232.
Процедура вычисления включает в себя следующие шаги:
1.По процедуре А’ получить простое число q длины tq битов.
2.По процедуре А’ получить простое число Q длины 512 битов, при этом пункт 1 процедуры А’ не выполнять, а сохранить значение у0, полученное в конце работы шага 1.
А.3 Примеры процедур выработки и проверки ЭЦП на базе
асимметричного криптографического алгоритма
Пусть по процедуре А с начальными условиями х0 = 5EC9 и
с = 7341 выработаны числа
p = EE8172AE 8996608F
854510E2 977A4D63
EA0A12B3 43E9190F
6BB0C345 D165976E
р, q и а : B69359B8 BC97322C 32177539 F2195EC9
9EB82A69 E5DC3386 84583978 B1C379E3
q = 98915E7E B064BDC7
C8265EDF 285DD50D
CDA31E88 7289F0AC
F24809DD 6F49DD2D
a = 9E960315 AFAD2538 06755984 8EBE2CD4
00C8774A B4B6270A A49E5093 6AC3D849
86958D4 6F7C8837 04D648BE 5B142AA6
AFDE2127 B50D50F2 2AB5AAB1 CE23E21C
15
А.3.1 Процедура подписи собщения
Пусть х = 30363145 38303830 34363045 42353244 35324234 31413237 38324331 38443046 - секретный ключ, М - подписываемое сообщение, причем значение хэш-функции h от сообщения М есть h (M) = m 35344541 32454236 44313445 34373139
43363345
37414342 34454136 31454230
Пусть целое число k = 90F3A564 439242F5 11B7105C 64E4F539
186ЕВВ22 0807Е636
4С8Е2238 2DF4C72A
Тогда r=ak(mod p)
47681С974373В065
D07A7E02Е311846Е
FF0AD18802643В5С
98E4AD8CFC689817
ЗС6СА965C8F86127
97А8С1263F8A76AF
6С9987750С6В0458
76ВА82163ADBC988
r’=r(mod q)=
3E5F895E 276D81D2 57B784C5 7ABDBD80
D52C0763 270A4581 7BC44FD4 3A32AC06
s=xr’+km(mod q)=
3F0DD5D4 400D47C0 8E4CE505 FF7434B6
DBF72959 2E37C748 56DAB851 15A60955
Таким образом, цифровая подпись для сообщения М есть
<r’>256I I
<S>256 =
3E5F895E 276D81D2 D52C0763 270A458
1 57B784C5 7ABDBD80 7BC44FD4 3A32AC0
b
3F0DD5D4 400D47C0 8E4CE505 FF7434B
b
DBF72959 2E37C748 56DAB851 15A6095
5
16
А.3.2 Процедура проверки подписи
Пусть дано сообщение Мг(в данном случаи М, = М), его
цифровая подпись
<г’>95б I I 3E5E895E 276D81D2 D52C0763 270А4581
<S>256 =
57В784С5 7ABDBD80 7BC44FD4 ЗА32АС06 3F0DD5D4 400D47C0 8Е4СЕ505 FF7434B6 DBF72959 2Е37С748 56DAB851 15А60955 и открытый ключ подписавшего сообщение у = ЕЕ1902А4 0692D273 EDC1B5AD C55F9112 8E35F9D1 65FA9901 CAF00D27 018BA6DF 324519С1 1А6Е2725 26589CD6 E6A2EDDA AFF1C308 1259BE9F СЕЕ667А2 701F4352
Замечание
Данный открытый ключ у соответсвует секретному ключу х, использованному в примере подписи сообщения М у = ах (mod p) Пусть
m = 35344541 32454236 44313445 34373139 43363345 37414342 34454136 31455430 - значение хэш-функции h для сообщения Мг Условия 0 < r’ < q и 0 < s < q выполняются. Вычисляют