Купить ГОСТ Р 34.10-94 — бумажный документ с голограммой и синими печатями. подробнее
Распространяем нормативную документацию с 1999 года. Пробиваем чеки, платим налоги, принимаем к оплате все законные формы платежей без дополнительных процентов. Наши клиенты защищены Законом. ООО "ЦНТИ Нормоконтроль"
Наши цены ниже, чем в других местах, потому что мы работаем напрямую с поставщиками документов.
Устанавливает процедуры выработки и проверки электронной цифровой подписи (ЭЦП) сообщений (документов), передаваемых по незащищенным телекоммуникационным каналам общего пользования в системах обработки информации различного назначения, на базе асимметричного криптографического алгоритма с применением функции хэширования. Внедрение системы ЭЦП на базе стандарта обеспечивает защиту передаваемых сообщений от подделки, искажения и однозначно позволяет доказательно подтвердить подпись лица, подписавшего сообщение.
1 Область применения
2 Нормативные ссылки
3 Обозначения
4 Общие положения
5 Процедура выработки подписи
6 Процедура проверки подписи
7 Процедуры получения чисел p, q, и а
Приложение А Проверочные примеры
Дата введения | 01.01.1995 |
---|---|
Добавлен в базу | 01.10.2014 |
Завершение срока действия | 01.07.2002 |
Актуализация | 01.01.2021 |
23.05.1994 | Утвержден | Госстандарт России | 154 |
---|---|---|---|
Разработан | ВНИИ стандартизации | ||
Разработан | Главное управление безопасности связи Федерального агентства правительственной связи и информации | ||
Издан | Издательство стандартов | 1994 г. |
Чтобы бесплатно скачать этот документ в формате PDF, поддержите наш сайт и нажмите кнопку:
ГОСУДАРСТВЕННЫЙ СТАНДАРТ РОССИЙСКОЙ ФЕДЕРАЦИЙ
ИНФОРМАЦИОННАЯ ТЕХНОЛОГИЯ
ПРОЦЕДУРЫ ВЫРАБОТКИ И ПРОВЕРКИ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ НА БАЗЕ АСИММЕТРИЧНОГО КРИПТОГРАФИЧЕСКОГО АЛГОРИТМА
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).
| |||||||||||||||||||||||||||||||||||
. А.2.2 Процедура А' |
Тогда в процессе выполнения процедуры будет получена последовательность
Необходимо получить простое число р длины 512 битов с простым делителем q длины 256 битов числа р—1.
Задают числа Xo=3DFC46Fl и c = D. /
Вычисляют последовательность t=(512, 1256, И2'8, 64, 32),
Тогда в процессе выполнения процедур будет получена последовательность простых чисел:
Ь=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,
Задают начальные значения 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 и а:
р=г 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
Таким образом: | ||||||||||||||||
| ||||||||||||||||
Условие rVu выполнено. Это означает, что подпись подлинная. |
13
УДК 681.3.06:006.354 П85 ОКСТУ-5002
Ключевые слова: информационная технология, криптографиям ская защита информации, электронная цифровая подпись, ассим-метричный криптографический алгоритм, системы обработки Информации, защита сообщений, подтверждение подписи, хэш-фуйк-ция, функция хэширования
14
СОДЕРЖАНИЕ
1 Область применения ........ 1
2 Нормативные ссылки . . . ... 1
3 Обозначения . ............ 1
4 Общие положения .. 2
5 Процедура выработки подписи........... 3
6 Процедура проверки подписи ........... 3
7 Процедуры получения чисел р, q и а ........ 4
Приложение А Проверочные примеры....... 9
Ш
ВВЕДЕНИЕ
Расширяющееся применение информационных технологий при создании, обработке, передаче и хранении документов требует в определенных случаях сохранения конфиденциальности их содержания, обеспечения полноты и достоверности.
Одним из эффективных направлений защиты информации является криптография (криптографическая защита), широко применяемая в различных сферах деятельности в государственных и коммерческих структурах.
Криптографические методы защиты информации являются объектом серьезных научных исследований И стандартизации на национальных, региональных и международных уровнях.
Настоящий стандарт определяет процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма с применением функции хэширования.
Электронная цифровая подпись обеспечивает целостность сообщений (документов), передаваемых по незащищенным телекоммуникационным каналам общего пользования в системах обработки информации различного назначения, с гарантированной идентификацией ее автора (лица, подписавшего документ).
IV
ГОСУДАРСТВЕННЫЙ СТАНДАРТ РОССИЙСКОЙ ФЕДЕРАЦИИ
Информационная технология.
КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ.
Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма.
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
Цифровая подпись, состоящая из двух целых чисел, представленных в виде слов в алфавите (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
Это возможно при наличии, у получателя открытого ключа отправителя, пославшего сообщение.
Процедура проверки включает в себя следующие этапы:
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
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).
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
Если 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 + K2” lYm)/(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,
но
5у0:«Уб4.
б