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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

81
ясните, как это можно дешифровать, и почему это является гарантирован-
ной подписью.
21.2. Проект. Напишите программу, которая моделировала бы от-
правление посланий между двумя людьми. Все необходимые составляющие
представлены в программе, реализующей метод RSA. Добавьте возмож-
ность отправки подписи.
21.3. Упражнения
1. Пусть число р будет вида 4k +3 и пусть a и b удовлетворяют срав-
нению
a ≡ b
2
(mod p), где p не делит a (эквивалентно p не делит b). Теорема
Ферма показывает, что
b
4k+2
≡ 1 (mod p). Используйте это, чтобы показать,
что (
a
k+1
)
2
≡ a (mod p), т. е., что x = a
k+1
является решением x
2
≡ a (mod p).
(Здесь роль
b сводится к тому, что а сравнимо с квадратом по модулю р.
Заметим, что
x
2
≡ a (mod p) ⇔ x
2
≡ b
2
(mod p) ⇔ x ≡ ±b (mod p), так как р яв-
ляется простым числом, отсюда
b = ±a
k+1
, и существуют два решения:
x = ±a
k+1
и сравнение x
2
≡ a (mod p).
2. Пусть n=pq, где р и q – разные простые числа, оба сравнимые
с 3 (mod 4), и пусть
а ≡ b
2
(mod n), как ранее. Используя тот факт, что
x
2
≡ a (mod n) ⇔ x
2
≡ a (mod p) ⇔ x
2
≡ a (mod q), докажите, что существует
точно
четыре решения x
2
≡ a (mod n).
Чтобы найти их точно, выберем
r и s такими, что rp + sq = 1 (напом-
ним, что
р и q – разные простые числа, так что (p, q) = 1), и пусть
x
1
≡ a (mod p), x
2
≡ a (mod q). (Метод вышеприведённого пункта (1) может
быть использован для нахождения
х
1
и х
2
). Покажите, что х = x
1
sq + x
2
rp
удовлетворяет x
2
≡ a (mod p и mod q) и, отсюда (mod n). Используя два вы-
бора для
х
1
и два выбора для х
2
, получим четыре решения ( почему они обя-
зательно различны по (mod
n)?).
3. Теперь мы подошли к «орлянке» по телефону. У нас снова два дей-
ствующих лица –
R и G.
а)
R выбирает два больших простых числа р и q, оба совпадающих с 3
по mod 4, а затем посылает
G произведение n = pq.
б)
G выбирает случайно число b, для которого 1 ≤ b ≤ n – 1, и вычис-
ляет
а ≡ b
2
(mod n). (Заметим, что а ≡ 0 (mod n); почему это?) G отправляет а
абоненту
R.
в)
R определяет четыре решения x
2
≡ a (mod n), используя вышепри-
ведённые методы пунктов (1) и (2). Искомыми решениями будут
± b (где b
то же, что в (б)) и два других, скажем,
± с.
г) Теперь подходит розыгрыш.
R отсылает назад G одно из четырёх
решений, которое он нашёл. Существенная разница будет между
± b или
± с. Аргументом является то, что если R отсылает назад ± b G, тогда R «вы-
играл»; если
R отсылает назад ± с G, тогда R «проигрывает». Итак, R «уга-

Страницы