Элементы теории чисел и криптозащита. Воронков Б.Н - 79 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

79
+ 1 = 7 будет простым числом. Теперь выберем h = 4; мы найдём
4
⋅ 7 + 1 = 29 является простым числом. Напишите программу, которая на-
ходит малые значения
h, для которых продолжаются ряды до пределов, оп-
ределяемых расширенной точностью представления чисел в ЭВМ
(2 · 29 + 1 = 59, 12
⋅ 59 + 1 = 709, . . .).
21. Криптосистема RSA
21.1. Упражнения (вычисления и др.)
1. Если n является произведением двух нечётных простых чисел,
n = pq, и если р и q будут приблизительно равны, тогда применим метод,
данный Ферма для факторизации
n. Это проделывается следующим обра-
зом. Заметим, что,
n = pq =
2
2
pq+
⎛⎞
⎜⎟
⎝⎠
–
2
2
pq−
⎛⎞
⎜⎟
⎝⎠
. Представим это как t
2
– s
2
,
где
s будет малым, а t не должно быть больше, чем
n
. Начиная с
t = [
n
] + 1, мы представим t
2
– n и проверим, не является ли оно квадра-
том; если нет, тогда добавим 1 к
t и повторим снова. Когда t
2
– n = s
2
, тогда,
конечно,
n = (t + s)(t – s).
Смысл вышеизложенного, с точки зрения метода двухключевой крип-
тографии, заключается в том, что два простых числа
р и q не должны выби-
раться слишком близкими; реально они различаются на три – четыре циф-
ры, что является достаточным, чтобы сделать метод Ферма непрактичным.
Напишите программу, реализующую метод Ферма. Испытайте
n = pq, где
р = 57 685 933, а q = 57 700 183; попробуйте то же значение р, а
q = 58 000 171. Заметьте разницу в количестве шагов для этих двух случаев!
Вы можете создать свой пример, используя программу для нахождения
простых чисел, близких к выбранным. Вы, может быть, удивитесь, как час-
то метод заканчивается после одного шага (т. е., при
t = [
n
] + 1), когда со-
множители
р и q совсем близки.
Попробуйте представить в виде сомножителей число
n = 1 112 470 797 641 561 909 (которое возникает при делении 10
22
+ 1 на
относительно малые множители 89 и 101), используя Вашу программу.
2. Представим аргумент для определения для заданного
р, насколько
велико может быть простое число
q > p в случае, когда методу Ферма тре-
буется только один шаг для факторизации
n = pq (см. выше, пункт (1)). Зна-
чения
t начинаются с t = [ n ] + 1, а когда t = (p + q)/2, метод прекращает
свою работу и простые множители оказываются найденными. Необходимое
количество шагов определяется как
()
1
.
22
pq
npqpq
+
⎡
⎤⎡⎤
−=+−
⎣
⎦⎣⎦
То есть, <
()
1
1,
2
pq pq+− +
когда оно ≤ 2, если и только если

Страницы