Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
2. Попробуйте вскрыть код, в котором используется ключ шифрования (пА, еА) = (536813567, 3602561). Используйте для разложения на множители числа пА компьютер и простейший известный алгоритм, состоящий в делении на все нечетные числа по очереди. Если нельзя воспользоваться компьютером, попробуйте угадать простой делитель пА, пробуя специальные классы простых чисел. После факторизации пА найдите ключ дешифрования. После этого дешифруйте сообщение «BNBPPKZAVQZLBJ» в предположении, что открытый текст состоит из шести-буквенных блоков в обычном 26-буквенном алфавите (преобразуемых в целые от 0
106
ГЛ. IV. ОТКРЫТЫЙ ключ
до 266 —1 обычным способом), а шифртекст состоит из семибуквенных блоков в том же самом алфавите. Из этого упражнения должно стать ясно, что даже 29-битовое число 71,4 слишком мало.
3. Пусть элементы открытого и шифрованного текстов — это триграммы, но открытый текст написан в 27-буквенном алфавите (буквы A-Z и пробел = 26), а шифртекст записан в 28-буквенном алфавите, полученном из 27-буквенного добавлением знака «/» с числовым эквивалентом 27. Предполагается, что каждый пользователь А выбирает па в диапазоне между 273 = 19683 и 283 = 21952, так что триграмма открытого текста в 27-буквенном алфавите соответствует вычету P по модулю па - Тогда С = РЄА (mod па) соответствует триграмме шифртекста в 28-буквенном алфавите.
а) Пусть ваш ключ дешифрования — это Kd = (ті, d) = (21583, 20787). Дешифровать сообщение «YSNAUOZHXXH » (в конце сообщения стоит один пробел).
б) В условиях а) известно, что tp(n) = 21280. Найти: 1) е = d~l (mod ip(n))\ 2) разложение числа га.
4. Показать, что 35-битовое целое 23360947609 является очень плохим вариантом для га = pq из-за того, что два его простых делителя слишком близки друг к другу. Иначе говоря, показать, что п легко разлагается «методом Ферма», состоящим в следующем. Заметим, что если п = pq (скажем, р > q), то га = (^4-2)2 — (^-2-)2. Если р и q близки, то s = (р — q)/2 мало и t = (р + ?)/2 есть
1— 9
целое число, лишь немного большее у/п, причем t — га является полным квадратом. Проверяя подряд целые числа t > у/п, вы довольно быстро найдете такое, для которого га = t2 — s2. Тогда p = t + snq = t — s (см. упражнение Зк§1.2и§3 главы V.)
5. Предположим, что имеется быстрый (вероятностный) алгоритм решения уравнения X2 = a (mod р) при любом простом р и любом квадратичном вычете а. Например, выбирая случайно целые числа и вычисляя символ Лежандра, с большой вероятностью можно найти невычет. Затем можно применить алгоритм, описанный в §11.2. Предположим также, что не существует хорошего алгоритма для решения уравнения х2 = a (mod га), где а является квадратом по модулю га, а га = pq есть произведение двух больших простых чисел, причем разложение числа п на множители неизвестно (при известных множителях можно найти квадратный корень по каждому из модулей и потом воспользоваться китайской теоремой об остатках для нахождения квадратного корня по модулю га). Пусть оба числа р и q не сравнимы с 1 по модулю 4. Положим Ke = га и Kd = {р, я}- Рассмотрим множество P = C = (Z/raZ)*/ ± 1, которое получается из множества вычетов, взаимно простых с га, «склеиванием» противоположных элементов х и —х. Пусть /: V —+ С — это отображение х i—* х2 (mod га). Показать, что это отображение является примером отображения упражнения 4 из предыдущего раздела. Оно дает способ реализации игры в монетку на большом расстоянии.
6. Пусть га — целое число, свободное от квадратов (т. е. произведение различных простых). Пусть d и є — такие положительные целые числа, что de — 1 делится на р — 1 для каждого простого делителя р числа га. (Например, так будет, если de = 1 (mod ip(n)).) Доказать, что ade = a (mod га) для любого целого а (вне зависимости от того, имеет ли оно общие делители с п).
7. Доказать утверждения замечания 2 о вероятностях выполнения различных сравнений в пп. 1) и 2).
§ 3. ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ
107
ЛИТЕРАТУРА к §2 ГЛАВЫ IV
1. Adleman L. Af., Rivest R. L., Shamir A. A method for obtaining digital signatures and public-key cryptosystems. — Comm. ACM, 1978, v. 21, p. 120-126.
2. Rivest R. L. RSA chips (past/present/future). — In: Advances in Cryptology. Proceedings of Eurocrypt 84. Heidelberg etc.: Springer, 1985, p. 159-165.
3. Gordon J.A. Strong primes are easy to find. — In: Advances in Cryptology. Proceedings of Eurocrypt 84. Heidelberg etc.: Springer, 1985, p. 216-223.
§ 3. Дискретное логарифмирование
Обсуждавшаяся в предыдущем разделе система RSA основана на том, что найти и перемножить два больших простых числа значительно проще, чем выполнить обратную операцию (имея п, найти эти два простых числа). Имеются и другие фундаментальные теоретико-числовые процедуры, обладающие, по всей видимости, свойствами однонаправленности или функции с замком. Одной из самых важных таких процедур является возведение в степень в большом конечном поле.
В поле вещественных чисел возведение в степень (нахождение Ьх с заданной точностью) не намного проще обратной операции (нахождения logf, X с заданной точностью). Рассмотрим теперь конечную группу, например, (Z/raZ)* или F* (с умножением в качестве групповой операции). Метод повторного возведения в квадрат (см. §1.3), позволяет вычислить Ьх при больших X сравнительно быстро (за полиномиальное по log X время). Пусть теперь задан элемент у, допускающий представление Ьх (считается, что «основание» Ь задано); как найти степень элемента 6, в которой он равен у, т. е. вычислить х = logb у (здесь «log» имеет отличный от обычного, хотя и близкий, смысл)? Этот вопрос называется «задачей дискретного логарифмирования». Слово «дискретное» подчеркивает отличие случая конечной группы постановки от классического непрерывного случая.
