Товары в корзине: 0 шт Оформить заказ
Стр. 1 

18 страниц

396.00 ₽

Купить ГОСТ Р 34.10-94 — бумажный документ с голограммой и синими печатями. подробнее

Распространяем нормативную документацию с 1999 года. Пробиваем чеки, платим налоги, принимаем к оплате все законные формы платежей без дополнительных процентов. Наши клиенты защищены Законом. ООО "ЦНТИ Нормоконтроль"

Наши цены ниже, чем в других местах, потому что мы работаем напрямую с поставщиками документов.

Способы доставки

  • Срочная курьерская доставка (1-3 дня)
  • Курьерская доставка (7 дней)
  • Самовывоз из московского офиса
  • Почта РФ

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

 Скачать PDF

Заменен на ГОСТ Р 34.10-2001

Оглавление

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

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

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

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

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

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

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

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

 
Дата введения01.01.1995
Добавлен в базу01.10.2014
Завершение срока действия01.07.2002
Актуализация01.02.2020

Этот ГОСТ находится в:

Организации:

23.05.1994УтвержденГосстандарт России154
РазработанВНИИ стандартизации
РазработанГлавное управление безопасности связи Федерального агентства правительственной связи и информации
ИзданИздательство стандартов1994 г.

Information technology. Cryptographic data security. Produce and check procedures of electronic digital signature based on asymmetric cryptographic algorithm

Стр. 1
стр. 1
Стр. 2
стр. 2
Стр. 3
стр. 3
Стр. 4
стр. 4
Стр. 5
стр. 5
Стр. 6
стр. 6
Стр. 7
стр. 7
Стр. 8
стр. 8
Стр. 9
стр. 9
Стр. 10
стр. 10
Стр. 11
стр. 11
Стр. 12
стр. 12
Стр. 13
стр. 13
Стр. 14
стр. 14
Стр. 15
стр. 15
Стр. 16
стр. 16
Стр. 17
стр. 17
Стр. 18
стр. 18

ГОСТ Р 34.10-94

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

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

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

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

94/130


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

СУЗ

ш

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

Предисловие

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

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

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

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

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

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

II

ГОСТ P 34.10-94

6    Вычислить

N = Г2*р-‘ / (qQ) Ц-К^Р-1 Y) / (qQ2l0M) 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 Процедура В'

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

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

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

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

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

3    Вычислить последовательность (yi, . . . , у32) по рекурсивному правилу у1+х = (97781173 yi+c) (mod 232).

31

4    Вычислить Y= S Vi2321.

i=0‘

5    Уо: = Уз2-

6    Вычислить

N =    /(qQ)] + |(2fp-' Y)/(qQ2'024) j.

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

7    k: = 0.

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

9    Если р>24Р, то перейти к шагу 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 и а, выработки и проверки подписи приведены в приложении А.<


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

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

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

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

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

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

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

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

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

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

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

простых чисел:

t5 = 16, р5= 8003

t4 = 32,

р4= AD4B0FAB

t3 = 64,

рз= B25D28A7

1A62D775

t2= 128,

р2= 9С992766

8Е6Е4908

954А9АЕ1

3773АЕ75

Ц = 256,

р,= 98915Е7Е B064BDC7

С 8265 ED F 285DD50D

CDA34E88 7289F0 А С

F24809DD

6F49DD2D

t0 = 512,

р0= ЕЕ8172АЕ 854510Е2 ЕА0А12ВЗ 6ВВ0С345

8996608F

977A4D63

43E9190F

D165976E

В69359В8

ВС97322С

23477539

F2195EC9

9ЕВ82А69

E5DC3386

84583978

B1G379E3

Pi и ро

— искомые числа q

и р соответственно.

. А.2.2 Процедура А'


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

Необходимо получить простое число р длины 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 битов:

BB124D6C    255D373F

96397506    6F8980B1

12D34BF3    3B536899

D9529BC8    С9653929


FA7D5DF5    5CE0DB4.4

C7CB68DF    6C6E8D27

C7I150C4D    F82FC171i

D6682CF5    FBBA1B3D


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

9АС27325    62F6D9B4

E03D750F    0B9806i75

606.D06C2    18В35А6С

8B1DE453    1C8FA8E7

2I1B28708    97F6A27A

8AD386E4    A0E4DFCB

D0BI126A8    122С7382

ECDDF6AF    D355DFB7

Е2С4191С

F18E7FB6

5FC730D9

3706919А

AF43C2BF

С4450ВСА

09152435

F285A986


4B5F222F

7А290ЕА1

75BF3FAA

АВ92Е0С5

FQ16251E

235А5В74

ABCFE48B

4615C66D


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

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

р= ЕЕ8172АЕ    8996608F

854510Е2    977A4D63

ЕА0А12ВЗ    43E9190F

6ВВ0С345    D165976E

q= 98915Е7Е    C8265EDF

B064BDC7    285DD50D


В69359В8    9ЕВ82А69

ВС97322С    E5DC3386

23177539    84583978

F2195EC9    B1C379E3

CDA31E88    F24809DD

7289F0AC    6F49DD2D


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

Р-1

00С8774А    869582D4

В4В6270А    6F7C8837

А49Е'5093    04D648BE

6AC3D849    5В142АА6

AFDE2127

B50D50F2

2АВ5ААВ1

СЕ23Е21С

!=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

ГОСТ Г 34.10-94


А.3.2 Процедура проверки подписи

Пусть дано сообщение М| (в данном случае Mi=M), его цифровая подпись


< Г'> 256 И <-s >256 = 3E5F895E    276D81D2

57В784С5    7ABDBD80

3F0DD5D4    400D47C0

DBF72959    2Е37С748


D62C0763

7BC44FD4

8Е4СЕ505

56DAB851


270А4581

3A32AC06

FF7434B6

15А60955


и открытый ключ подписавшего сообщение


у- EE19Q2A4    0692D273

8E35F9D1    65FA9901

3245ШС1    1А6Е2725

AFE1C308    1259BE9F


EDC1B5AD

CAF00D27

26589CD6

СЕЕ667А2


C55F9112

0.18BA6DF

E6A2EDDA

701F4352


Замечание


Данный открытый ключ у соответствует секретному ключу х, использованному в примере подписи сообщения М y=ax(mod-p).

Пусть

ш- 35344541    32454236    44313445    34373139

43363345    37414342    34454Ш6    31454230


— значение хэш-функции h для сообщения JV1,.

Условия 0<r'<q и 0<s<q выполняются.

Вычисляют

v«=mq-2(mod q) — 72515Е01    DDFA6507    Е3682С01    CD285CBF

89Е462ЕЕ    Е37В3865    91SB6730    DEA77050


Zi=»sv (mod q)- 77S6DC3C6    4E83B73B

B87DAED5    8686009B


02B78826

5D387CC4


6873EAFF

EAF5B744


z2=(q_r') v(mod q) = 18B04C46    G1D9E875    57JFDA9E    95364DDE

3AFD0A8D    FCADB67C    505C7F03    A5185DFD


u= (az‘y*a (mod p))(mod q)= 3E5F895E    276D81D2    D52C0763    270A458I

57B784C5 7ABDBD80 7BC44FD4 3A32AC06


Таким образом:

г'» 3E5F895E

276D81D2

D52C0763

270А458Ц

57В784С6

7ABDBD80

7BC44FD4

3A32AC06

u- 3E5F895E

276D81D2

D52C0763

270А4581

57В784С5

7ABDBD80

7BC44FD4

3A32AC06

Условие rVu выполнено. Это означает, что подпись подлинная.


13


УДК 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).

р — простое число, 2509<р<2512 либо 21020<р<21024. q — простое число, 2254<q<2256 и q является делителем для

(Р-1).

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

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

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

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

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

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

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

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

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

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

2

ГОСТ Р 34.10-94

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

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

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

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

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

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

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

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

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

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

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

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

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

Подписью для сообщения М является вектор <г/>25б||<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) значение О2551.

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

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

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

zi = sv (mod q) и

z2— (q—г') v(mod q).

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

u= (azlyz2(mod p))(mod q).

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

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

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

Получение простых чисел осуществляется с' использованием линейного конгруэнтного датчика по модулю 216 или по модулю 232 (x(1 = bxn_1 +с). При этом пользователь должен задавать начальное состояние х0 и параметр датчика с.

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

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

7.1 Процедура А

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

Получение чисел осуществляется с использованием линейного конгруэнтного, датчика хл= (19381 xn-1+c)(mod 216).

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

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

4

ГОСТ Р 34.10-94

1    Уо: = х0

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

to: = t

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

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

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

4    m: = s-l

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

6    Вычислить последовательность (уь . . ., уг ) по рекурсивному правилу у1+1 = (19381 yi+c) (mod 216).

г.п“1

7    Вычислить* Ym= 2 vi2161.

i-o '

8уо: = У,т-

9    Вычислить N = f2m_1 pm+1]+f(2'm-1Ym)/(pm+,21,rn’)J-Если N нечетно, то N: = N+1.

10    k: —0.

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

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

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

2Pm+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 xn-t +с) (mod 232).

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

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

1    у0: = х0

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

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

5

ГОСТ Р 34.10-94

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

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

4    m: = s—1.

б Вычислить rm = ftm/32j.

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

7    Вычислить Ym== 2 v^321.

i=0 *

8уо:=Уг,„-

9    Вычислить N = f2m ‘/'Pm+ll + K2lYm)/(Pm+l232rm)]-Если N нечетно, то N : = N+1.

10    k: = 0.

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

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

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

2pm+i<N+M (mod pm) = 1,

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

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

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

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

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

7.3 ПроцедураВ

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

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

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

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

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

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

63

4    Вычислить Y= 2 yt 21®1,

но

0:«Уб4.

б