ГОСТ Р 34.10-94
Группа П85
ГОСУДАРСТВЕННЫЙ СТАНДАРТ РОССИЙСКОЙ ФЕДЕРАЦИИ
Информационная технология
КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ
Процедуры выработки и проверки электронной цифровой подписи
на базе асимметричного криптографического алгоритма
Information technology. Cryptographic Data Security.
Produce and check procedures of Electronic Digital Signature based
on Asymmetric Cryptographic Algorithm
ОКСТУ 5002
Дата введения 1995-01-01
Предисловие
1 РАЗРАБОТАН Главным управлением безопасности связи Федерального агентства правительственной связи и информации и Всероссийским научно-исследовательским институтом стандартизации
ВНЕСЕН Техническим комитетом по стандартизации ТК 22 "Информационная технология" и Федеральным агентством правительственной связи и информации
2 ПРИНЯТ И ВВЕДЕН В ДЕЙСТВИЕ постановлением Госстандарта России от 23.05.94 N 154
3 ВВЕДЕН ВПЕРВЫЕ
ВВЕДЕНИЕ
Расширяющееся применение информационных технологий при создании, обработке, передаче и хранении документов требует в определенных случаях сохранения конфиденциальности их содержания, обеспечения полноты и достоверности.
Одним из эффективных направлений защиты информации является криптография (криптографическая защита), широко применяемая в различных сферах деятельности в государственных и коммерческих структурах.
Криптографические методы защиты информации являются объектом серьезных научных исследований и стандартизации на национальных, региональных и международных уровнях.
Настоящий стандарт определяет процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма с применением функции хэширования.
Электронная цифровая подпись обеспечивает целостность сообщений (документов), передаваемых по незащищенным телекоммуникационным каналам общего пользования в системах обработки информации различного назначения, с гарантированной идентификацией ее автора (лица, подписавшего документ).
1 ОБЛАСТЬ ПРИМЕНЕНИЯ
Настоящий стандарт устанавливает процедуры выработки и проверки электронной цифровой подписи (ЭЦП) сообщений (документов), передаваемых по незащищенным телекоммуникационным каналам общего пользования в системах обработки информации различного назначения, на базе асимметричного криптографического алгоритма с применением функции хэширования.
Внедрение системы ЭЦП на базе настоящего стандарта обеспечивает защиту передаваемых сообщений от подделки, искажения и однозначно позволяет доказательно подтвердить подпись лица, подписавшего сообщение.
2 НОРМАТИВНЫЕ ССЫЛКИ
В настоящем стандарте использованы ссылки на следующий стандарт:
ГОСТ Р 34.11-94 Информационная технология. Криптографическая защита информации. Функция хэширования.
3 ОБОЗНАЧЕНИЯ
В настоящем стандарте используются следующие обозначения.
|А| - длина слова
z (mod n) - наименьшее по значению неотрицательное число, сравнимое с z по модулю числа n.
<N>
А||В - конкатенация слов A,
A
М - передаваемое сообщение,
М
________________________
h - хэш-функция, отображающая сообщение М в слово
р - простое число, 2
q - простое число, 2
а - целое число, 1 < а < р - 1, при этом а
k - целое число, 0 < k < q.
[d] - наименьшее целое число, не меньшее чем d.
[d] - наибольшее целое число, не большее чем d.
e: = g - присвоение параметру е значения g.
х - секретный ключ пользователя для формирования подписи, 0 < x < q.
у - открытый ключ пользователя для проверки подписи, у = a
4 ОБЩИЕ ПОЛОЖЕНИЯ
Система ЭЦП базируется на методах криптографической защиты данных с использованием хэш-функции.
Алгоритм вычисления функции хэширования установлен в ГОСТ Р 34.11.
Процедуры цифровой подписи допускают как программную, так и аппаратную реализацию.
Система ЭЦП включает в себя процедуры выработки и проверки подписи под данным сообщением.
Цифровая подпись, состоящая из двух целых чисел, представленных в виде слов в алфавите
Числа р, q и а, являющиеся параметрами системы, должны быть выбраны (выработаны) по процедуре, описанной в пункте 7; числа р, q и а не являются секретными. Конкретный набор их значений может быть общим для группы пользователей. Целое число k, которое генерируется в процедуре подписи сообщения, должно быть секретным и должно быть уничтожено сразу после выработки подписи. Число k снимается с физического датчика случайных чисел или вырабатывается псевдослучайным методом с использованием секретных параметров.
5 ПРОЦЕДУРА ВЫРАБОТКИ ПОДПИСИ
Текст сообщения, представленный в виде двоичной последовательности символов, подвергается обработке по определенному алгоритму, в результате которого формируется ЭЦП для данного сообщения.
Процедура подписи сообщения включает в себя следующие этапы:
1 Вычислить h(M) - значение хэш-функции h от сообщения М.
Если
2 Выработать целое число k, 0 < k < q.
3 Вычислить два значения:
r = a
Если r' = 0, перейти к этапу 2 и выработать другое значение числа k.
4 С использованием секретного ключа х пользователя (отправителя сообщения) вычислить значение
Если s = 0, перейти к этапу 2, в противном случае закончить работу алгоритма.
Подписью для сообщения М является вектор <r'>
Отправитель направляет адресату цифровую последовательность символов, состоящую из двоичного представления текста сообщения и присоединительной к нему ЭЦП.
6 ПРОЦЕДУРА ПРОВЕРКИ ПОДПИСИ
Получатель должен проверить подлинность сообщения и подлинность ЭЦП, осуществляя ряд операций (вычислений).
Это возможно при наличии у получателя открытого ключа отправителя, пославшего сообщение.
Процедура проверки включает в себя следующие этапы:
1 Проверить условия:
0 < s < q и 0 < r' < q.
Если хотя бы одно из этих условий не выполнено, то подпись считается недействительной.
2 Вычислить h(M
Если
3 Вычислить значение
v = (
4 Вычислить значения:
z
z
5 Вычислить значение
u = (a
6 Проверить условие: r' = u.
При совпадении значений r' и u получатель принимает решение о том, что полученное сообщение подписано данным отправителем и в процессе передачи не нарушена целостность сообщения, т. е. M
7 ПРОЦЕДУРЫ ПОЛУЧЕНИЯ ЧИСЕЛ р, q и а
Получение простых чисел осуществляется с использованием линейного конгруэнтного датчика по модулю 2
Заданные величины необходимо зафиксировать (запомнить) для возможности проведения проверки того, что простые числа получены по установленной процедуре.
Ниже изложены процедуры получения параметров р, q и а.
7.1 Процедура А
Процедура позволяет получать простые числа р длины t
Получение чисел осуществляется с использованием линейного конгруэнтного датчика х
Задаются число х
Процедура вычисления включает в себя следующие шаги:
1 y
2 Вычислить последовательность чисел (t
t
Если t
Если t
3 Найти наименьшее простое число р
4 m: = s - 1
5 Вычислить r
6 Вычислить последовательность (у
7 Вычислить
8 y
9 Вычислить N = [2
Если N нечетно, то N : = N+1.
10 k : = 0.
11 Вычислить p
12 Если р
13 Проверить условия:
2
2
Если хотя бы одно из условий не выполнено, то k : = k + 2 и перейти к шагу 11.
Если оба условия выполнены, то m : = m - 1.
14 Если m
Если m < 0, то р
7.2 Процедура А'
Процедура позволяет получать простые числа р длины t
Получение числа осуществляется с использованием линейного конгруэнтного датчика х
Задаются число х
Процедура вычисления включает в себя следующие шаги:
1 у
2 Вычислить последовательность чисел (t
t
Если t
Если t
3 Найти наименьшее простое число р
4 m : = s - 1.
5 Вычислить r
6 Вычислить последовательность (y
7 Вычислить
8 y
9 Вычислить N = [2
Если N нечетно, то N : = N + 1.
10 k : = 0.
11 Вычислить p
12 Если р
13 Проверить условия:
2
2
Если хотя бы одно из условий не выполнено, то k : = k + 2 и перейти к шагу 11.
Если оба условия выполнены, то m : = m - 1.
14 Если m
Если m < 0, то р
7.3 Процедура B
Процедура позволяет получать простые числа р длины t
Задаются число х
Процедура вычисления включает в себя следующие шаги:
1 По процедуре А получить простое число q длины t
2 По процедуре А получить простое число Q длины 512 битов, при этом пункт 1 процедуры А не выполнять, а сохранить значение у
3 Вычислить последовательность (y
4 Вычислить
5 y
6 Вычислить
N = [2
Если N нечетно, то N : = N + 1.
7 k : = 0.
8 Вычислить p = qQ (N + k) + 1.
9 Если р > 2
10 Проверить условия:
2
2
Если оба условия выполнены, то р и q - искомые простые числа.
Если хотя бы одно из условий не выполнено, то k : = k + 2 и перейти к шагу 8.
Последовательность шагов повторить до выполнения условий на шаге 10.
7.4 Процедура В'
Процедура позволяет получать простые числа р длины t
Задаются число х
Процедура вычисления включает в себя следующие шаги:
1 По процедуре А' получить простое число q длины t
2 По процедуре A' получить простое число Q длины 512 битов, при этом пункт 1 процедуры А' не выполнять, а сохранить значение у
3 Вычислить последовательность (y
4 Вычислить
5 y
6 Вычислить
N = [2
Если N нечетно, то N : = N + 1.
7 k : = 0.
8 Вычислить p = qQ (N + k) + 1.
9 Если р > 2
10 Проверить условия:
2
2
Если оба условия выполнены, то р и q - искомые простые числа.
Если хотя бы одно из условий не выполнено, то k : = k + 2 и перейти к шагу 8.
Последовательность шагов повторить до выполнения условий на шаге 10.
7.5 Процедура С
Процедура позволяет получить число а при заданных р и q.
1 Произвольно выбрать число d, 1 < d < p -1.
2 Вычислить
3 Если f = 1, то перейти к шагу 1.
Если f
Конец работы алгоритма.
Проверочные примеры для вышеизложенных процедур получения чисел р, q и а, выработки и проверки подписи приведены в приложении А.
Приложение А
(справочное)
ПРОВЕРОЧНЫЕ ПРИМЕРЫ
Значения параметров х
А1 Представление чисел и векторов
Длины чисел и векторов, а также элементы последовательности t записывают в десятичной системе счисления.
Последовательности двоичных символов записывают как строки шестнадцатиричных цифр, в которых каждая цифра соответствует четырем знакам ее двоичного представления.
А.2 Примеры к процедурам получении чисел р, q и числа а для реализации ЭЦП
А.2.1 Процедура А
Необходимо получить простое число р длины 512 битов с простым делителем q длины 256 битов числа р - 1.
Задают числа х
Вычисляют последовательность t = (512, 256, 128, 64, 32, 16).
Тогда в процессе выполнения процедуры будет получена последовательность простых чисел:
t | р | 8003 |
|
|
| |||
t | p | AD4B0FAB |
|
|
| |||
t | p | B25D28A7 | 1A62D775 |
|
| |||
t | р | 9C992766 | 8E6E4908 | 964A9AE1 | 3773AE75 | |||
t | p | 98915E7E B064BDC7 | C8265EDF 285DD50D | CDA31E88 7289F0AC | F24809DD 6F49DD2D | |||
t | p | EE8172AE 854510E2 ЕА0А12ВЗ 6BB0C345 | 8996608F 977A4D63 43E9190F D165976E | B69359B8 BC97322C 23177539 F2195EC9 | 9EB82A69 E5DC3386 84583978 B1C379E3 |
р
А.2.2 Процедура А'
Необходимо получить простое число р длины 512 битов с простым делителем q длины 256 битов числа р - 1.
Задают числа x
Вычисляют последовательность t = (512, 256, 128, 64, 32).
Тогда в процессе выполнения процедур будет получена последовательность простых чисел:
t | p | 8000000B |
|
| ||||
t | p | 9AAA6EBE | 4AA58337 |
| ||||
t | p | C67CE4AF | 720F7BBA | B5FEBF37 | B9E74807 | |||
t | p | 931A58FB 4B56898F | 6F0DCDF2 7F921A07 | FE7549ВС 6601EDB1 | 3F19F472 8C93DC75 | |||
t | p | 8B08EB13 DA26765D 316A0E29 8C6DFD0F | 5AF966AA 6D38D30C 198460FA C2C565AB | B39DF294 F1C06AAE D2B19DC3 B0BF1FAF | 538580C7 0D1228C3 81C15C88 F9518F85 |
p
A.2.3 Процедура В
Необходимо получить простое число р длины 1024 битов с простым делителем q длины 256 битов числа р - 1.
Задают начальные значения х
С помощью процедуры А получают простое число q длиной
ВСС02СА0 | CE4F0753 | ЕС16105Е | E5D530AA | |||
00D39F31 | 71842АВ2 | С334А26В | 5F576E0F |
Затем вновь с помощью процедуры А получают простое число Q длиной
СCEF6F73 | 87В6417Е | С67532А1 | 86ЕС619С | |||
A4DB132F | CA02621A | DE216F1D | F6F8114С | |||
DB3D9209 | 7D978C6F | 583С3301 | 4174АА1С | |||
1AFCCEB2 | 843В1D35 | 0D2E5D16 | 855А7477 |
И, наконец, получают простое число р длиной
АВ8F3793 | 8356529E | 871514С1 | F48C5CBC | |||
E77B2F4F | C9A2673A | C2C1653D | A8984090 | |||
С0АС7377 | 5159A26B | EF59909D | 4C984663 | |||
1270E166 | 53A62346 | 68F2A52A | 01A39B92 | |||
1490E694 | C0F104В5 | 8D2E1497 | 0FCCB478 | |||
F98D01E9 | 75А1028В | 9536D912 | DE5236D2 | |||
DD2FC396 | В7715359 | 4D417878 | 0E5F16F7 | |||
18471E21 | 11С8СЕ64 | A7D7E196 | FA57142D |
А.2.4 Процедура В'
Необходимо получить простое число р длины 1024 битов с простым делителем q длины 256 битов числа р - 1.
Задают начальные значения x
С помощью процедуры А получают простое число q длиной
931A58FB | 6F0DCDF2 | FE7549BC | 3F19F472 | |||
4B56898F | 7F921A07 | 6601EDB1 | 8C93DC75 |
Затем вновь с помощью процедуры А получают простое число Q длиной
BB124D6C | 255D373F | FA7D5DF5 | 5CE0DB44 | |||
96397506 | 6F8980B1 | C7CB68DF | 6C6E8D27 | |||
12D34BF3 | 3В536899 | C7150C4D | F82FC171 | |||
D9529BC8 | C9653929 | D6682CF5 | FBBA1B3D |
И, наконец, получают простое число р длиной
Е2С4191С | 4B5F222F | 9АС27325 | 62F6D9B4 | |||
F18E7FB6 | 7А290ЕА1 | E03D750F | 0B980675 | |||
5FC730D9 | 75BF3FAA | 606D05C2 | 18B35A6C | |||
3706919А | АВ92Е0С5 | 8B1DE453 | 1C8FA8E7 | |||
AF43C2BF | F016251E | 21В28708 | 97F6A27A | |||
С4450ВСА | 235А5В74 | 8AD386E4 | A0E4DFCB | |||
09152435 | ABCFE48B | D0B126A8 | 122C7382 | |||
F285A986 | 4615C66D | ECDDF6AF | D355DFB7 |
A.2.5 Процедура С
Пусть заданы числа р и q, полученные в А.2.1 по процедуре А:
p = | ЕЕ8172АЕ 854510Е2 ЕА0А12В3 6ВВ0С345 | 8996608F 977A4D63 43E9190F D165976E | B69359B8 ВС97322С 23177539 F2195ЕС9 | 9ЕВ82А69 E5DC3386 84583978 В1С379Е3 | |||
q = | 98915Е7Е B064BDC7 | C8265EDF 285DD50D | CDA31E88 7289F0AC | F24809DD 6F49DD2D |
Выбирают число d = 2.
Вычисляют
|
|
|
|
Так как f
А.3 Примеры процедур выработки и проверки ЭЦП на базе асимметричного криптографического алгоритма
Пусть по процедуре А с начальными условиями x
р = | ЕЕ8172АЕ 854510Е2 ЕА0А12ВЗ 6ВВ0С345 | 8996608F 977A4D63 43E9190F D165976E | В69359В8 ВС97322С 23177539 F2195ЕС9 | 9ЕВ82А69 E5DC3386 84583978 В1С379Е3 | |||
q = | 98915E7E B064BDC7 | C8265EDF 285DD50D | CDA31E88 7289F0AC | F24809DD 6F49DD2D | |||
a = | 9E960315 AFAD2538 06755984 8EBE2CD4 | 00С8774А В4В6270А А49Е5093 6AC3D849 | 869582D4 6F7C8837 04D648BE 5B142AA6 | AFDE2127 B50D50F2 2АВ5ААВ1 СЕ23Е21С |
А.3.1 Процедура подписи сообщения
Пусть х = | 30363145 | 38303830 31413237 | 34363045 38324331 | 42353244 38443046 |
- секретный ключ, М - подписываемое сообщение, причем значение хэш-функции h от сообщения М есть
h(M) = m = | 35344541 43363345 | 32454236 37414342 | 44313445 | 34373139 31454230 |
Пусть целое число
k = | 90F3A564 11B7105C | 439242F5 64E4F539 | 186EBB22 0807E636 | 4C8E2238 2DF4C72A |
Тогда
r = а | 47681C97 D07A7E02 FF0AD188 98E4AD8C | 4373B065 E311846E 02643B5C FC689817 | 3C6CA965 97A8C126 6C998775 76BA8216 | C8F86127 3F8A76AF 0C6B0458 3ADBC988 | |||
r' = r (mod q) = | 3E5F895E 57B784C5 | 276D81D2 7ABDBD80 | D52C0763 7BC44FD4 | 270A4581 3A32AC06 | |||
s = xr' + km(mod q) = | 3F0DD5D4 DBF72959 | 400D47C0 2E37C748 | 8E4CE505 56DAB851 | FF7434B6 15A60955 |
Таким образом, цифровая подпись для сообщения М есть
< r'> | 3E5F895E 57B784C5 3F0DD5D4 DBF72959 | 276D81D2 7ABDBD80 400D47C0 2E37C748 | D52C0763 7BC44FD4 8Е4СЕ505 56DAB851 | 270A4581 3A32AC06 FF7434B6 15А60955 |
А.3.2 Процедура проверки подписи
Пусть дано сообщение М
< r'> | 3E5F895E 57B784C5 3F0DD5D4 DBF72959 | 276D81D2 7ABDBD80 400D47C0 2E37C748 | D52C0763 7BC44FD4 8E4CE505 56DAB851 | 270A4581 3A32AC06 FF7434B6 15А60955 |
и открытый ключ подписавшего сообщение
y = | ЕЕ1902А4 8E35F9D1 324519С1 AFE1C308 | 0692D273 65FA9901 1А6Е2725 1259BE9F | EDC1B5AD CAF00D27 26589CD6 СЕЕ667А2 | C55F9112 018BA6DF E6A2EDDA 701F4352 |
Замечание
Данный открытый ключ у соответствует секретному ключу х, использованному в примере подписи сообщения М
у = а
Пусть
m = | 35344541 43363345 | 32454236 37414342 | 44313445 34454136 | 34373139 31454230 |
- значение хэш-функции h для сообщения M
Условия 0 < r' < q и 0 < s < q выполняются.
Вычисляют
v = mq | 72515E01 89Е462ЕЕ | DDFA6507 E37B3865 | Е3682С01 918В6730 | CD285CBF DEA77050 | |||
z | 776DC3C6 B87DAED5 | 4E83B73B 8686009В | 02В78826 5D387CC4 | 6873EAFF EAF5B744 |
z | 18B04C46 3AFD0A8D | C1D9E875 | 571FDA9E 505C7F03 | 95354DDE A5185DFD |
u = (а | 3E5F895E 57B784C5 | 276D81D2 | D52C0763 7BC44FD4 | 270A4581 3A32AC06 |
Таким образом:
r' = | 3E5F895E 57В784С5 | 276D81D2 7ABDBD80 | D52C0763 7BC44FD4 | 270A4581 3A32AC06 | |||
u = | 3E5F895E 57B784C5 | 276D81D2 7ABDBD80 | D52C0763 7BC44FD4 | 270A4581 3A32AC06 |
Условие r' = u выполнено. Это означает, что подпись подлинная.
Текст документа сверен по:
Госстандарт России -
М.: Издательство стандартов, 1994