Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Пример 3. Пусть при шифровании используется преобразование сдвига однобуквенных элементов в 26-буквенном алфавите (см.
UO
ГЛ. IV. ОТКРЫТЫЙ ключ
пример 1 в §111. 1): С = P + В (mod 26). (Мы используем для параметра сдвига обозначение В, чтобы отличить его от символа Ь в предыдущем абзаце.) В качестве В возьмем наименьший неотрицательный вычет по модулю 26 случайного элемента из F53. Пусть д = 2 (это порождающий элемент в F53). Предположим, что Аида выбрала случайно а = 29 и ей известен открытый ключ Бернардо 2Ь, скажем, 12 Є F53. Тогда она находит, что ключом шифрования явля-
29
ется 12 = 21 Є F53, т.е. В = 21. В то же время она публикует
29
свой открытый ключ 2 =45. Поэтому Бернардо тоже может найти ключ В = 21 возведением 45 в степень b (его секретный показатель b = 19). Конечно, система с таким маленьким полем не дает надежной защиты: посторонний может легко найти дискретный логарифм по основанию 2 для 12 или 45 по модулю 53. И уж, во всяком случае, не является надежным шифрование сдвигом для однобуквенных элементов сообщения. Этот пример лишь иллюстрирует механизм данной системы обмена ключами.
Криптосистема Мэсси—Омуры для передачи сообщений.
Предположим, что все согласились использовать конечное поле F9; оно зафиксировано и общеизвестно. Каждый пользователь системы втайне выбирает такое случайное целое є между 0 и q — 1, что НОД (е, g — 1) = 1, и с помощью алгоритма Евклида вычисляет обратное к нему число d = е 1 (mod q - 1), т.е. de = 1 (mod q - 1). Если Алиса (пользователь А) намерена передать сообщение P Бобу, она сначала посылает ему элемент РвА. Это послание для Боба бессодержательно, так как он не знает dA (или ед, что то же самое) и не может восстановить Р. Не пытаясь понять смысл сообщения, Боб возводит его в свою степень ев и отсылает РЄлЄв обратно Алисе. Третий шаг состоит в том, что Алиса несколько «распутывает» сообщение, возводя его в степень d^\ так как ралЄА — р (по предложению II.1.1), то, по сути дела, она отсылает Бобу Рев, который теперь может прочитать сообщение, возведя его в степень dB.
Весьма простая идея этой системы может быть реализована и в схемах, где используются процедуры, отличные от возведения в степень в конечных полях. Однако не все так просто. Прежде всего, отметим, что при использовании системы Мэсси-Омуры абсолютно необходима хорошая схема подписи сообщений. Без нее любое постороннее лицо С, которому сообщение P не предназначено, может представиться Бобом и вернуть Алисе сообщение P А °. Алиса, не зная, что оно прислано самозванцем, пользовавшимся своим ключом ес, продолжит процедуру, возведя сообщение в степень ад, дав тем самым С возможность прочитать сообщение. Поэтому промежуточное сообще-
§ 3. ДИСКРЕТНОЕ ЛОГАРИФМИРОВАНИЕ
111
ниє рЄАЄв от Боба Алисе должно сопровождаться аутентикацией, т. е. некоторым сообщением в схеме подписи, которое может послать только Боб.
Кроме того, важно, чтобы такие пользователи, как В или С, которые после дешифрования различных сообщений P будут знать пары (Р, РЄА), не могли воспользоваться этим для определения ел. Так, если бы Боб мог решать задачу дискретного логарифмирования в F9 и по P и РЄА определять, каким должно быть ед, то он мог бы легко вычислить dA = еА (mod q — 1) и затем перехватывать и читать все дальнейшие сообщения Алисы, кому бы они ни были адресованы.
Криптосистема Эль-Гамаля. Сначала зафиксируем очень большое конечное поле F9 и элемент д Є F9 (желательно, хотя и не обязательно, чтобы он был порождающим). Предположим, что используются элементы открытого текста с численными эквивалентами P в F9. Каждый пользователь А выбирает случайно целое число а = аА, скажем, из диапазона 0 < а < q — 1. Это секретный ключ дешифрования. Открытым ключом шифрования является элемент да Є F9.
Чтобы передать сообщение P пользователю А, мы выбираем случайно целое число к и посылаем А следующую пару элементов из F9:
(9к,Рдак).
Заметим, что вычислить дак можно, не зная а, просто возведя да в степень к. Теперь А, зная а, может по этой паре раскрыть Р, возве-
к
дя первый элемент д в а-ю степень и разделив на результат второй элемент (или, что эквивалентно, возведя дк в степень q — 1 — а и умножив на второй элемент). Другими словами, наше послание состоит
из замаскированного сообщения (P «несет маску» дак) и «ключа», а
к ,
именно, д , которым можно снять маску (но воспользоваться ключом
может лишь тот, кто знает а).
Тот, кто умеет решать задачу дискретного логарифмирования в
F9, вскроет эту криптосистему, определив ключ дешифрования а по
ключу шифрования да. Вообще говоря, может существовать способ
определения дак по дк и да, а значит, и вскрытия шифра, не связанный
с дискретным логарифмированием. Однако, как уже упоминалось при
обсуждении системы Диффи-Хеллмана, считается, что нет способа
получить дак из дк и да, не решив, по существу, задачи дискретного
логарифмирования.
Стандарт цифровой подписи. В 1991 году Национальный институт стандартов и технологий (НИСТ) при правительстве США
