Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
21. а) Если бы (*) было справедливо для 61 и 6162, то, поделив одно сравнение на другое (это возможно, так как функции как справа, так и слева мультипликативны), мы получим, что (*) выполняется также для 62. С другой стороны, если бы (*) не выполнялось для некоторого 6, то множество элементов вида 6с, состоящее из произведений 6 на все элементы с, для которых (*) выполняется, состояло бы из элементов, не удовлетворяющих (*). б) Взять, например, 6 = 1 4дп/р, где р2\п. Тогда (^-) = 1, но 6; = 1, только если p\j. Однако для j = (п — 1)/2 это не так. в) Покажем, что (^) = —1, однако ftt"-1)/2 = 1 (mod п/р) и, следовательно, сравнение 6^™-1)/2 = —1 (mod п/р) (и, тем более, такое сравнение по модулю п) не может иметь места. Далее, пусть а\ — любой невычет по модулю р и а2 = 1. Теперь примените китайскую теорему об остатках, чтобы получить решение 6 для пары сравнений х = а\ (mod р), х = а2 (mod п/р).
22. б2 = (1 + a)p(t + a) = (t + ap)(t + a) = (t - a){t + a) = t2 - a2 = а где третье из равенств следует из того, что а = \/<2 — а сопряжено с ар = —V2 — а;
236
ОТВЕТЫ К УПРАЖНЕНИЯМ
заметим, что 4 Є Fp, так как по условию а имеет два квадратных корня в Fp, и потому его квадратные корни в Fp2 на самом деле лежат в Fp.
23. Пусть 4 — наименьший положительный вычет п(р_1)/4 по модулю р. Тогда 4 — квадратный корень из —1 по модулю р, т. е. р|(42 + 1). Далее вычислить с + di = НОД (р, 4 + і) (см. упражнение 14 к § I. 2).
§111.1
1. «We sewed a smile on a horse's ass, and a year later it was elected President.»
2. Вывести равенство b = 19 из того, что буква «X» — самая частая в ши-фртексте. Сообщение имеет вид: WEWERELUCKYBECAUSEOFTENTHEFREQ U ENCYMETHODN EEDSLONGERCIPHERTEXT.
3. THRPXDH.
4. SUCCESSATLAST.
5. AGENT 006 IS DEAD 007.
6. Есть 9 возможных вариантов для а' и 6': а' — 1,4,7,10,13,16,19,22,25 и 4' = 21,6,18,3,15,0,12,24,9 соответственно. Ничего не остается, как просто перепробовать все эти 9 вариантов. Получаем следующие варианты открытого текста: «I DY IB RIF», «I PS IH RIX», «I AM IN RIO», «I MG IT RIF», «I YA IZ RIX», «I JV IE RIO», «I VP IK RIF», «I GJ IQ RIX», «I SD IW RIO». Осмысленный текст дает только третий вариант: P = 7С + 18 (mod 27).
7. а) N. б) Np(N) = N2Up1N^ ~ ?)¦ в) 312, 486, 812, 240.
8. а) Если а ф 1, то сравнение (а — I)P ее —6 (mod N) имеет ровно одно решение в поле Fjv = Z/NZ. б) P = 0 всегда фиксированно. При четном N (тогда а нечетно) сравнение (а — I)P ее 0 (mod N) имеет, по крайней мере, два решения: P = OnP= N/2. в) N четно, 4 нечетно. Более общий пример: 4 не делится на НОД (а - 1, N).
9. N2ip(N2) = N4HplN(l - і); 210912; 354294; 682892; 216000.
10. а) а1 = 435, 4' = 64; «FOUNDTHEGOLD». б) а = 115, 6 = 76; «AWO FU WAE».
11. а) Из первых двух сравнений ключ найти невозможно, но, взяв разность первого и третьего сравнений, получим 139а' = 247 (mod 900), что дает\а' = 73 и 4' = 768. Сообщение: «ARE YOU JOKING?». б) а = 37, 4 = 384; «FWU ORI DCCUVGA». ~У
12. «СССР».
13. Сравнение P = 37Р + 384 (mod 900) влечет за собой ЗР ее 43 (mod 75); таких биграмм нет.
14. а) Композиция I = P + b\ (mod N) и С ее / + bi (mod N) — это С ее P + 4 (mod N) с b = b\ + Ь2. б) Композиция будет линейным преобразованием с а = а\ ¦ ai. в) Композиция будет аффинным преобразованием с а = а\ ¦ ai и 4 = а? ¦ b\ + 4г.
15. P ее 642С 4- 187 (mod 853); «DUMB IDEA*.
16. Сначала найти, что / ее 201С + 250 (mod 881), а потом — что P ее 331/ + 257 (mod 757); «NO RETREAT».
§И1.2
1. При шифровании использовано ключевое слово «SPY». Открытый текст (здесь для удобства вставлены пробелы и знаки пунктуации): «I had asked that а cable from Washington to New Delhi summarizing the results of the aid consortium be repeated to me through the Toronto Consulate. It arrived in code; no facilities
ОТВЕТЫ К УПРАЖНЕНИЯМ
237
existed for decoding. They brought it to me at the airport — a mass of numbers. I asked if they assumed I could read it. They said no. I asked how they managed. They said when something arrived in code, they phoned Washington and had the original message read to them.» (Джон Кеннет Гэлбрайт «Дневник посла»; цитируется по работе Mellen G. Е. Cryptology, computers and common sense. — In: Computers and Security. Vol. III).
/3 2\ /19 10\ ч /11 11\ x / 820 0 \ ч / 127 303\
2-а)! ).6)( ). в ( ). г ). д)( ).
M 1/ \23 16/ \2A 1 / Vo 801/ \546 353/
3. a) (^). б) Решений нет (умножение второго сравнения на 2 и вычитание результата из первого дает 6г/ EEE 8 (mod 9), что невозможно, так как влечет за собой 3|8). в) («), ®, (°). г)0,©, (I).
4. а) (21) • б) (о) • в) Любой вектор с у = х, т. е. (Jj) , (j) , (2) и т. д. г) Любой вектор вида (15^_п). д) Решений нет.
с „\ (7&7\ ,ч /626ч ч /0\ ч /Оч (WU ( 202 ч /303ч /404-, /505ч, /606%
5. а) (759). б) (233). в) (0). г) (0), (505), (1010), (404), (эоэ), (303), (gog),
/707ч /808ч /909ч /1010ч \ п ( 31 ч _ ., ч
