Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
а) Определить ключ шифрования.
б) Какой элемент из Fg6i вы должны послать вашему другу для того, чтобы он мог определить этот ключ?
в) Найти преобразование дешифрования.
г) Прочитать сообщение «BUVCFIWOUJTZ1H».
4. Вы получили шифртекст «VHNHDOAM», зашифрованный с помощью матрицы размера (2 X 2)
применяемой к биграммам обычного 26-буквенного алфавита. Эта матрица шифрования была построена с помощью обмена ключами по методу Диффи-Хеллмана следующим образом. Имеется простое поле из 3602561 элементов. Ваш корреспондент послал вам gb = 983776. Вы выбрали случайно показатель а — 1082389. Наконец, вы договорились получать матрицу из ключевого числа Ke Є F3602561, выражая наименьший неотрицательный вычет Ke по модулю 264 в форме о-263 + b ¦ 262 + с ¦ 26 + d, где a,b,c,d — содержимое разрядов в записи вычета в системе счисления по основанию 26. Если полученная таким образом матрица необратима по модулю 26, то заменяем Ke на Ke + 1 и повторяем процесс построения снова. В качестве матрицы шифрования возьмем первую обратимую матрицу, встретившуюся среди построенных.
а) Воспользоваться имеющейся информацией для определения матрицы шифрования.
б) Найти матрицу дешифрования и прочитать сообщение.
5. Пусть каждый пользователь А имеет секретную пару преобразований /д и /^1 из V в V, где V — заданное множество элементов открытого текста. Для защиты информации используется метод Мэсси-Омуры, а именно, пользователь
§ 3. ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ
121
А посылает пользователю В сообщение /а(Р), получает от В назад Jb(Ia(P)) и т.д. Указать условия на совокупность /а, необходимые для работоспособности этой системы.
6. Пусть р — простое число Ферма 65537 и д = 5. Вы приняли сообщение (29095, 23846), которое построено с помощью криптосистемы Эль-Гамаля в F* и вашего открытого ключа д". Ваш секретный ключ для дешифрования а = 13908. Вы договорились преобразовывать целые из Fp в триграммы 31-буквенного алфавита из упражнения 3, записывая их в системе счисления по основанию 31 и принимая содержимое разрядов в этой записи (от старшего разряда к младшему) в качестве числовых эквивалентов букв триграммы. Дешифровать принятое сообщение.
7. а) Показать, что выбор Fp с простым числом Ферма р = 22 +1 является исключительно неудачным, построив алгоритм, производящий дискретное логарифмирование в F* за полиномиальное по log р время. Пусть д — порождающий элемент (например, 5 или 7, как показано в упражнении 15 к § П. 2) и для заданного а требуется найти такое х, что 0 ^ х <. р — 1= 22* Hj1Eo (mod р). Записать X в двоичной системе и построить алгоритм по образцу алгоритма извлечения квадратного корня по модулю р, описанному в конце § П. 2.
б) Найти оценку вида О-большое (в терминах р) для числа двоичных операций, необходимых для нахождения х с помощью алгоритма пункта а).
в) Использовать алгоритм пункта а) для нахождения величины к в упражнении 6.
8. Пусть элементами открытого текста являются 18-буквенные блоки обычного 26-буквенного алфавита, числовыми эквивалентами которых являются 18-разрядные -- в системе счисления по основанию 26 — целые числа (разряды записываются в порядке убывания степеней основания). Получено сообщение
(82746592004375034872957717, 164063768437915425954819351),
зашифрованное с помощью криптосистемы Эль-Гамаля в простом поле из 297262705009139006771611927 элементов и вашего открытого ключа да. Ваш секретный ключ а = 10384756843984756438549809. Дешифровать полученное сообщение.
9. Ниже описана схема (также предложенная Эль-Гамалем) посылки подписи, использующая большое простое конечное поле Fp. Объяснить, почему Алиса может выполнить все необходимые для пересылки подписи шаги за полиномиальное по log р время, почему Боб может проверить, что это именно Алиса послала свою подпись, и почему эта система не дает защиты от злоумышленника, если он может решать задачу дискретного логарифмирования в F*.
Пусть зафиксированы и общеизвестны р и элемент j E FJ. Каждый пользователь А выбирает случайно и сохраняет в секрете целое а .4,0 < а а < P — 1, а публикует у а = д"А¦
Для посылки своей подписи, состоящей из элементов с числовыми эквивалентами S из диапазона 0 ^ S < р— 1, Алиса сначала выбирает случайно целое число к, взаимно простое с р — 1. Она вычисляет г = дк (mod р) и после этого решает сравнение gs = y\rx (mod р) относительно х. Затем она посылает пару (г, х) Бобу вместе со своей подписью S. Борис проверяет, что в самом деле gs = yrArx (mod р). Убедившись в этом, он может быть вполне уверен, что именно Алиса прислала сообщение S.
Lit
ГЛ. IV. ОТКРЫТЫЙ ключ
10. Используя алгоритм Силвера-Полига-Хеллмана, найти дискретный логарифм числа 153 по основанию 2 в F181 (2 — порождающий элемент в F181).
11. а) Какова вероятность (в процентах) того, что случайный многочлен над F2 степени 10 разлагается в произведение многочленов степени не выше второй? Какова вероятность (в процентах) того, что случайный ненулевой многочлен над F2 степени не выше 10 разлагается в такое произведение?
