52 Смсташы с открытым ключом Глава 4

Кршпгосксхемы же с открытым ключ<ж могут непосредственно использоваться для шифрования наиболее значимых сообщений. Криптографические системы с открытым ключом во многом подобны криптосистемам с секретным ключом. Они состоят из пространства ключей Ю, и для каждого к Ю, из пространства открытых сообщений Afj, пространства шифртекстов Ск и пары функций Е*:Л<*->С* и Ок.Ск-Мк, таких, что Dk(Ek{m)) = т для любого открытого текста m еЛ<к. Так же как и в криптосистемах с секретным ключом, эффективные алгоритмы для вычисления и fjt, и D, должны легко получаться для каждого ключа к. Мы будем называть алгоритмы, полученные таким образом, естественными алгоритмами. Важной новой отличительной особенностью является то, что Ек должна быть однонаправленной функцией с потайным ходом - необходимо, чтобы было практически невозможно построить никакого эффективного алгоритма для вычисления Dk (но только естественного такого алгоритма), зная описание естественного алгоритма для вычисления Ек- В частности, это означает, что значение к не должно присутствовать в явном виде в естественном алгоритме шифрования.

Криптохрафические системы с открытым ключом используются следзтопщм образом. Каждый пользователь раз и навсегда выбирает для себя некоторый случайный ключ кЕК,. Этот ключ он использует для получения обоих естественных алгоритмов Ек я Dk. Затем он делает публично доступным свой алгоритм шифрования Ек, возможно посредством использования некоторого справочника, но при этом хранит в строгой, тайне свой алгоритм дешифрования Dk- Тогда, если один из пользователей криптосистемы захочет послать другому некоторое сообщение, то он найдет в спргшочнике его открытый алгоритм шифрования и использует этот алгоритм для того, чтобы зашифровать свое сообщение. В этом случае после его пересылки, используя собственный секретный ключ, только законный получатель сможет расшифровать полученный шифртекст. Заметим, что в противоположность криптосистемам с секретным ключом, если Алиса, зашифровав некоторое сообщение т для Боба,, сохранит щнфрхекст с, но потеряет соохветствуюпщй ему открытый текст (или забудет все, что в нем содержалось), то она не будет иметь никаких преимуществ перед нарушителем в раскрытии m из с.

S 3 Теори» крнтгосмстем с открытым ым>чом 53

Также в противоположность крнптосхемам с секретным клютом, если нарушитель, перехватив шифртекст, знает, для кого он был зашифрован, то он может использовать открытый алгоритм шя-фрования для проверки любого конкретного предположения о том, каким может быть соответствующий открытый текст. Возможность фор>шровать шифртексты из открытых сообщений по своему выбору приводит к сокращению числа классических уровней атак, которые обсуждались в связи с криптосистемами с секретным ключом (см. § 3.1). Однако иногда может применяться следующая важная атаха:

• Атака на основе выбранного шифртекста: против определенного пользователя, функциями шифрования и дешифрования которого являются Ек и, соответственно, Dk, криптоаналитик задается выбранными шифртекстами а, с2, с, и подбирает отвечающие им открытые тексты mi = Dfc(ci), тз = Dk{c2), - гщ = Dk(ci) при условии, что такие осмысленные открытые тексты существуют. Его цель заключается в том, чтобы либо определить ключ к, либо построить какой-нибудь эффективный алгоритм вычисления Dk, либо (за неимением и той, и другой возможности) пытаться найти mi+i из некоторого нового шифртекста Ci+i = ffc(m,+i).

Криптосистемы с открытым ключом, в принципе, могут существовать лишь в том случае, если существуют не только просто однонаправленные функции, но а однонаправленные функции с потайным ходом. В самом деле, функции нгафрования должны быть однонаправленными функциями с потгЛным ходом, а процесс, который с помопц>ю ключа обеспечивает естественный алгоритм шифрования, должен реализовывать просто однонаправленную функцию. В результате всего этого получается, что мы не знаем, как доказать существование криптосистем с открытым ключом. Таким образом, все наши рассуждения о них могут быть не более, чем осуществляемый весьма своеобразным способом разговор о пустом множестве, даже несмотря на то, что возможная реализуемость самого понятия криптосистемы с открытым ключом уже была формально продемонстрирована в относительных утверждениях [68, 65, 66].

Поэтому точно так же, как и в случае однонаправленных

функций (с потайным ходом), мы должны быть удовлетворены своими кандидатами на криптосистемы с открытым ключом. Две из наиболее известных криптосистем, претендующих на роль таких кандидатов, были предложены сразу после того, как Диффи и Хеллман ввели понятие криптографии с открытым ключом [157]. Одна из них - это так называемая ранцевая криптосистема Меркля и Хеллмана [266, 214], которая вскоре была раскрыта [150, 161, 317, 3, 88, 245, 89]. И хотя существуют еще нераскрытые варианты оригинальной криптосхемы, этим вариантам, по видимому, не стоит доверять. Брикелл написал очень подробную историю криптоанализа ранцевой криптографической системы [90]. Другая наиболее известная криптосистема с открытым ключом все еще остается несокрушимой, и мы в следующем параграфе опишем ее достаточно детально. Были предложены и другие системы, такие как системы Макэлиса [262] и Эль-Гамаля [166], но мы не будем обсуждать их здесь. По поводу исчерпывающего обзора криптографических систем с открытым ключом обращайтесь к [246, 279]. Захватывающая история создания криптографии с открытым ключом отражена с статье самого Уитфилда Диффи [156].

§ 4. Криптосистема RSA

Самой первой криптографической системой с открытым ключом, из тех что были предложены в открытой литературе вообще, является криптосистема Ривеста, Шамира и Эдлемана [307]. Она стала известна под названием RSA или MIT криптосистемы. Эта криптосистема основывается на вере в то, что модульное возведение в степень при фиксированных экспоненте и модуле является однонаправленной функцией с потайным ходом (см. § 1). Для первоначального ознакомления с этой криптосистемой обращайтесь к статье Мартина Гарднера [185].

Пусть р и q - два больших различных простых числа, п - р • g , а е - некоторое целое, взаимно простое с (р-1)(д-1). Тогда для криптосистемы RSA в качестве личного (секретного) ключа может быть выбрана люб)ая такая тройка k = {p,q,e). Пусть также каждое из соответствуюищх пространств открытых текстов Mh и шифрованных сообщений Сн суть Z п, т.е. множество неотрицательных целых чисел, меньших п. (Если при этом ре-