Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Несмотря на то, что очень большие дискретные логарифмы возможно и являются трудновычислимыми, хотелось бы предупредить читателя, что для их вычисления существуют алгоритмы намного лучшие, чем исчерпывающий поиск. Самые лучшие из известных в настоящее время алгоритмов, когда п является простым числом, описаны в [124], а при вычислениях в GF(2k) — в [281]. При выборе размера ключа такие поля должны тщательно анализироваться. Фирмой Hewlett-Packard однажды бы-
Теория криптосистем с открытым ключом
ла разработана злополучная аппаратная реализация, использующая GF(2127) [368]. Однако ключи в ней были быстро раскрыты с применением методов, которые изложены в [45].
В предположении, что п и д являются стандартными параметрами, интересной альтернативой описанному ранее интерактивному протоколу является организация и использование некоторого единого для всех пользователей каталога. Каждый пользователь записывает в этот каталог свой собственный открытый ключ X, вычисленный как дх mod п в соответствии с личным случайно выбранным секретным ключом х. Это позволяет любым двум пользователям сформировать свой совместный секретный ключ даже до их предварительной договоренности о нем друг с другом. Основной недостаток такого общедоступного каталога состоит в том, что он не поддерживает достаточно частые изменения пользователями личных секретных ключей. Мы намереваемся вернуться к этой теме в § 7.
Другой подход к проблеме распределения ключей обеспечивает предложенная Чарльзом Беннеттом и Жилем Брассаром квантовая криптография [25]. Ее надежность не зависит от недоказанных предположений о вычислительной сложности, основанных на трудности вычислений каких бы то ни было функций. Более того, она остается таковой даже тогда, когда нарушитель имеет неограниченные вычислительные ресурсы, или даже если, все-таки, 'Р = j\l'V [27, 26, 28]. Квантовое открытое распределение ключей описывается в последней, седьмой главе этой книги.
§ 3. Теория криптосистем с открытым ключом
Система открытого распределения ключей, так как она описана в § 2, позволяет двум сторонам сформировать совместную часть некоторой распределенной секретной информации. Однако при этом ни одна из сторон не имеет никакого непосредственного влияния на то, какой окажется эта информация. Если бы Алиса захотела передать Бобу единственное специальное сообщение, то за использованием системы открытого распределения ключей должно было бы последовать использование криптосистемы с секретным ключом, в которой первоначальная совместно сформированная ими информация сохранялась бы в качестве их общего секретного ключа.
52 Системы с открыты ключом
Глава 4
Криптосистемы хе с открытым ключом могут непосредственно использоваться для шифрования наиболее значимых сообщений. Криптографические системы с открытым ключом во многом подобны криптосистемам с секретным ключом. Они состоят из пространства ключей 1C, и для каждого к ? К, из пространства открытых сообщений Мк, пространства шифртек-стов Ск и пары функций ?*: -М* —+Ск и Dk : Ск -+Л4к, таких, что Dk(Ek{m)) = т для любого открытого текста т ? Мк- Так же как и в криптосистемах с секретным ключом, эффективные алгоритмы для вычисления и ?*, и Dk, должны легко получаться для каждого ключа к. Мы будем называть алгоритмы, полученные таким образом, естественными алгоритмами. Важной новой отличительной особенностью является то, что F* должна быть однонаправленной функцией с потайным ходом — необходимо, чтобы было практически невозможно построить никакого эффективного алгоритма для вычисления Ojt (но только естественного такого алгоритма), зная описание естественного алгоритма для вычисления F*. В частности, это означает, что значение к не должно присутствовать в явном виде в естественном алгоритме шифрования.
Криптографические системы с открытым ключом используются следующим образом. Каждый пользователь раз и навсегда выбирает для себя некоторый случайный ключ к (Е 1C. Этот ключ он использует для получения обоих естественных алгоритмов Ек я Dk- Затем он делает публично доступным свой алгоритм шифрования Ек, возможно посредством использования некоторого справочника, но при этом хранит в строгой, тайне свой алгоритм дешифрования Ojt- Тогда, если один из пользователей криптосистемы захочет послать другому некоторое сообщение, то он найдет в справочнике его открытый алгоритм шифрования и использует этот алгоритм для того, чтобы зашифровать свое сообщение. В этом случае после его пересылки, используя собственный секретный ключ, только законный получатель сможет расшифровать полученный шифртекст. Заметим, что в противоположность криптосистемам с секретным ключом, если Алиса, зашифровав некоторое сообщение т для Боба, сохранит шифртекст с, но потеряет соответствующий ему открытый текст (или забудет все, что в нем содержалось), то она не будет иметь никаких преимуществ перед нарушителем в раскрытии ш из с.
Теория криптосистем с открытым ключом 53
Также в противоположность криптосхемам с секретным ключом, если нарушитель, перехватив шифртекст, знает, для кого он был зашифрован, то он может использовать открытый алгоритм шифрования для проверки любого конкретного предположения о том, каким может быть соответствующий открытый текст. Возможность формировать шифртексты из открытых сообщений по своему выбору приводит к сокращению числа классических уровней атак, которые обсуждались в связи с криптосистемами с секретным ключом (см. § 3.1). Однако иногда может применяться следующая важная атака:
