Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
§IV.3
1. а) 24, 30, 11, 13. б) 1,а2 + а, а, а + 1.
2. 1) Чтобы оправдать переход к сравнению 21O = 1, заметим, что если х < <р(За) является решением 2ха = 1 (mod 3а), то y(3Q) — х является решением исходного сравнения. Если а = 2 (mod 3), то решаем 2х(2а) = 1 (mod 3а), где 2а = 1 (mod 3). Тогда х + 1 является решением исходного сравнения. Если а = 1 (mod 3), то решение х должно быть четным, так как 2нечетн = 2 (mod 3).
3) Для доказательства того, что (*)j выполняется при Zj-г = (1— aj-l)/3J_1,
ОТВЕТЫ К УПРАЖНЕНИЯМ
241
вычислить левую часть (*);- по модулю З1'. Она равна aj-iffjij2 = (1 — 3J "1x^2)SJi12. Далее посредством биномиального разложения показать, что
(1 + 3)3J xj-2 = і 4. 3;_1i;_2 (mod 3J). Таким образом, левая часть в (*);- сравнима с (1 — х2 _232(J "1^)1 т.е. с 1 по модулю V . Наконец, чтобы оценить число двоичных операций, заметить, что при выполнении шага 3) каждый раз производится по паре умножений и делений целых чисел по 0(a) бит, т. е. на каждом шаге производится 0(а2) двоичных операций. Таким образом, вся процедура требует 0(а3) двоичных операций.
3. а) Чтобы упростить вычисление (дь)а в F312, воспользоваться тем, что (с+ di)32 = с2 + d2. Ответ: А+ Bi = 26 + 28г. б) 20+ 13г. в) P = 6С+18 (mod 31). г) YOU'RE JOKING!
4. a) Ke = 1951280, наименьший неотрицательный вычет этого числа по модулю 264 равен 7 • 263 + 0 ¦ 262 + 13-26 + 6; однако к нему надо прибавить
/7 0 \ ./15 0 \
единицу, чтобы получить обратимую матрицу шифрования ); б)
43 7/ 413 15/
DONOTPAY.
5. Преобразования j\ должны коммутировать, т.е. JaJB = ІВІА Для всех пар пользователей А и В. Нужно использовать их вместе с хорошей схемой подписи (как указано в условии), и не должно существовать практической возможности определить ключ для Ja по паре (Р, Ja(P))- Например, преобразования сдвига Ia[P) = Р + Ь или линейное Ja[P) = яР удовлетворяют первому условию, но не удовлетворяют второму, так как по паре (Р, P + 6) (или (P1 аР)) легко находится Ь (или а). Пример в тексте удовлетворяет этим условиям, так как по нашим предположениям задача дискретного логарифмирования не может быть решена за разумное время.
6.P= 6229 =«GO!».
7. а) Сначала заменить і на р - 1 — х и свести задачу к эквивалентному сравнению дх а = 1 (mod р). Положить I = 2к их = zo+2?i + -- - + 2'_1?/_i. Пусть <7;- = д2' (mod р) и a.j = j*o + 2zi + --- + 2-> lz,-ia (moc} p) (в качестве ao берется а). На j-м шаге вычислить H2^1"1 = ±1 и положить Xj _i = 0 при +1 и Xj-i = 1 при —1; вычислить также gj = д2_г и aj = 1 • При j = I работа заканчивается, б) 0(log4 р). в) к = 7912.
8. THEYREFUSEOURTERMS.
9. Чтобы найти х, Алиса сводит сравнение gs = yrrx = дат + кх к Сравнению S = аг + кх (mod р — 1), которое имеет решение х = k~l [S — аг) (mod р — 1). Боб знает р, д и у = у а и может проверить, что gs = yr rx (mod р), так как он получил пару (г, х) вместе с 5. Наконец, любой, кто умеет решать задачу дискретного логарифмирования, может определить а по д и у и подделать подпись, найдя х.
10. 107.
11. а) 9/128 = 7,03%, 160/1023 = 15,64%. б) 70/2187 = 3,20%, 1805/29524 = 6,11% (см. следствие из предложения II. 1.8).
12. а) Число нормированных многочленов равно (pn+1 — 1)/(р — 1) ~ рп ¦ Числом произведений степени ниже п можно пренебречь. Число П] неприводимых
нормированных многочленов степени / равно j(pf — Л</</ d\f ^nd) ~ ^r- Число произведений степени п равно тогда следующей сумме по всем разбиениям числа п = idd (id > 0):
E/Пі + t'l - 1\ /Пт + im - 1\ ^ „у- _1_
\ і'і )"\ іт )~Р 2— 2'2 3'з ¦¦¦m^hHi^.-- -іт\'
242
ОТВЕТЫ К УПРАЖНЕНИЯМ
Таким образом,
р(п, m)=Yz (udidiA
Это выражение, очевидно, положительно. Чтобы проверить оценку Р(п,т) < 1, заметим, что имеется приблизительно рп/п нормированных неприводимых многочленов степени п, поэтому вероятность того, что нормированный многочлен не разлагается в произведение нужного вида, не меньше 1/п. б) 57J;+2;'=n 0<i j (2J**!jї)— 1 -в) Р(3, 2) = 2/3, Р(4, 2) = 5/12, Р(5, 2) = 13/60, Р(6, 2) = 19/180, Р(7^2) = 29/630.
§IV.4
1. а) Да, 1. б) Да, 0. в) Нет, 2. г) Нет, 0. д) Да, 1. е) Нет, 1.
2. а) Использовать индукцию по к. б) Для доказательства второй части взять
Vi > 1 + Vi-I + ¦ ¦ • + "о И ПОЛОЖИТЬ V = V{ — 1.
3. Использовать индукцию.
4. a) IXTERCEPTCONVOY. б) 89, 3, 25, 11, 41, 60, 65.
5. FORMULA STOLEN!
6. BRIBE HIM!
§IV.5
1. Вероятность успешного Т-кратного обмана равна 2~Т и при T —> оо стремится к 0.
2. а) Числа е и е + і по модулю N, которые Вивалес получает на шагах 2 и 3 процедуры, принадлежат диапазону от 0 до N — 1. При большом числе испытаний Вивалес получит довольно хорошее представление о величине N. б) Положить N1 очень большим целым, кратным N, и заменить N на. N' в описании шагов 1 и 3.
3. Величины, получаемые Вивалесом на шаге 3, представляют собой верхние оценки для х. Величины, которые на шаге 3 посылает Клайд, не ограничены снизу, в отличие от величин X + е, посылаемых Пикарой.
