Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
25. a) P = A1C + В1, Д' = ( 14 78M1 В' = (322); «HIT ARMY BASE!
\821 206 /
HEADQUARTERS*, б) С = АР+В, A= 3° Y В = (3°l); «!N JUFYKTEGOUL
V 10 7 / 4
IB'.VFEXU! JH ALGQGJ?».
26. 298(292 - 1)(292 - 29)=341 208 073 352 438 880.
27. 91 617 661 629 000 000.
(18 21 19ч із 18 з J; «SENDROSESANDCAVIARJAMESBOND». 3 19 11'
§IV.l
1. (™) = т(т — 1)/2 для классической криптосистемы и т для системы с открытым ключом. При т = 1000 это дает 499500 против 1000.
2. Один из возможных способов таков. Инвесторы и брокеры используют систему с V = С. Пользователь А посылает сообщение пользователю В, предварительно преобразуя каждый элемент сообщения P в fBfAl{P). Каждое сообщение включает в себя свой идентификационный номер. Пользователь В должен сразу же уведомить о получении сообщения с указанием идентификационного номера сообщения, полученного от А. При этом каждый элемент P уведомляющего сообщения перед отправлением преобразуется в J4Zg1IP) (аналогично двойному шифрованию, использованному А при посылке исходного сообщения). Если А не получил уведомление от В, то он посылает свое сообщение повторно, и так до тех пор, пока не получит ответ. Потом, когда из-за потери капиталов или по другим причинам возникнет спор о том, кто именно и какое послал сообщение, брокер сможет доказать, что сообщение было послано А, ибо никто, кроме А (и суда), не может создать сообщение, читаемое с помощью преобразования fAf?l- Аналогично, А сможет доказать, что сообщение с данным идентификационным номером было принято пользователем В (так как никто другой не мог бы послать уведомительное сообщение) и от В можно потребовать предоставить полученное сообщение суду.
3. В данном случае подойдет криптосистема с открытым ключом, использующая случайные целые числа (удовлетворяющие, возможно, некоторым условиям) для построения ключей шифрования и дешифрования при помощи какого-нибудь алгоритма. Компьютер программируется на генерацию случайных целых чисел, которые используются для получения пары ключей К = {Ke, К о). Компьютер передает Kd ("с не ^e) во внешний мир и сохраняет Ke (ко не Kp) у себя. Поэтому любой может читать его сообщения, но никто не сможет создать сообщение, дешифруемое с помощью ключа Kd- (Эта ситуация обратна по отношению к обычной криптографии с открытым ключом. Там любой может послать сообщение, но только пользователь может прочитать его.) Для совместно работающих ученых вполне возможно запрограммировать компьютер так, чтобы никто не мог
240
ОТВЕТЫ К УПРАЖНЕНИЯМ
ни предсказать генерируемые случайные числа, ни продублировать его работу на своем собственном компьютере. (Отметим глубокий реализм этого примера, который предполагает, что обе страны абсолютно не доверяют друг другу, но в то же время полностью доверяют компьютерам.)
4. Бьерн выбирает случайно элемент р ? V, вычисляет с = f(p) и посылает число с Анюте. Анюта вычисляет два прообраза pi и рг и посылает один из них, скажем, pi, Бьерну. Если pi ф р, то Бьерн может назвать оба прообраза Pl и р2 = р. В этом случае считается, что он выигрывает. В противном случае выигрывает Анюта. Если Анюта выиграла, то она должна предоставить второй прообраз, чтобы Бьерн мог проверить равенство /(рг) = с и удостовериться, что Анюта не смошенничала, выбрав неправильный ключ, для которого с имеет только один прообраз. (Анюте невыгодно выбирать ключ, при котором у каждого с имеется более двух прообразов, так как это уменьшает ее шансы послать Бьерну тот прообраз, который он уже знает.)
§IV.2
1. a) BH A 2AUCAJEAR0. б) 2047 = 23-89 (см. пример 1 в §1.4), dA = 411. в) так как цс(23) и ср(89) имеют небольшое наименьшее общее кратное 88, то любой обратный к 179 по модулю 88 (например, 59) будет действовать как dA.
2. Число н,4 является произведением простого числа Мерсенна 8191 и простого числа Ферма 65537. Это чрезвычайно плохой выбор. Имеем dA = 201934721, «DUMPTHESTOCK».
3. a) STOP PAYMENT, б) (1) 6043; (2) п = 113 • 191.
4. С третьей попытки (t = 152843, 152844, 152845) находим t7 - п = 8042, тогда р = 152845 + 804 = 153649, q = 152845 - 804 = 152041.
5. Чтобы показать невозможность вычисления ассоциированного элемента в V (т. е. элемента, имеющего тот же самый образ, что и данный элемент), предположим, что некто, знающий лишь Ke (т. е. число п, но не его разложение) получил вторую пару ±?2 с тем же квадратом по модулю п, что и ±хх. Показать, что тогда НОД (xi +х?, п) есть либо р, либо q. Другими словами, отыскание одной лишь пары ассоциированных элементов в (Z/raZ)*/ ± 1 равносильно разложению п на множители.
6. Достаточно показать, что ade = a (mod р) для любого целого алкаж до го простого делителя р числа п. Это очевидно, если р\а. В других случаях воспользоваться малой теоремой Ферма (предложение 1.3.2).
7. Если т/2 = (р — 1)/2 (mod р — 1), то а™!"1 = (-), что в половине случаев равно +1, а в другой половине случаев равно —1. В случае (2) при помощи китайской теоремы об остатках показать, что событие, состоящее в том, что элемент в (Z/raZ)* является вычетом по модулю р, и событие, состоящее в том, что он является вычетом по модулю q, не зависят друг от друга. Таким образом, ситуация случая (2) подобна независимому бросанию двух монет.
