Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
• Атака на основе выбранного шифртекста: против определенного пользователя, функциями шифрования и дешифрования которого являются Е/с и, соответственно, D*, криптоаналитик задается выбранными шифртекстами с\, С2, ..., с,- и подбирает отвечающие им открытые тексты mi = D*(ci), m2 = D*(c2), ..., m, = D*(cj) при условии, что такие осмысленные открытые тексты существуют. Его цель заключается в том, чтобы либо определить ключ к, либо построить какой-нибудь эффективный алгоритм вычисления Dk, либо (за неимением и той, и другой возможности) пытаться найти m,-+i из некоторого нового шифртекста ci+i = ^ ]) ¦
Криптосистемы с открытым ключом, в принципе, могут существовать лишь в том случае, если существуют не только просто однонаправленные функции, но и однонаправленные функции с потайным ходом. В самом деле, функции шифрования должны быть однонаправленными функциями с потайным ходом, а процесс, который с помощью ключа обеспечивает естественный алгоритм шифрования, должен реализовывать просто однонаправленную функцию. В результате всего этого получается, что мы не знаем, как доказать существование криптосистем с открытым ключом. Таким образом, все наши рассуждения о них могут быть не более, чем осуществляемый весьма своеобразным способом разговор о пустом множестве, даже несмотря на то, что возможная реализуемость самого понятия криптосистемы с открытым ключом уже была формально продемонстрирована в относительных утверждениях [68, 65, 66].
Поэтому точно так же, как и в случае однонаправленных
54 Системы с открытым ключом
Глава 4
функций (с потайным ходом), мы должны быть удовлетворены своими кандидатами на криптосистемы с открытым ключом. Две из наиболее известных криптосистем, претендующих на роль таких кандидатов, были предложены сразу после того, как Диф-фи и Хеллман ввели понятие криптографии с открытым ключом [157]. Одна из них — это так называемая ранцевая криптосистема Меркля и Хеллмана [266, 214], которая вскоре была раскрыта [150, 161, 317, 3, 88, 245, 89]. И хотя существуют еще нераскрытые варианты оригинальной криптосхемы, этим вариантам, по видимому, не стоит доверять. Брикелл написал очень подробную историю криптоанализа ранцевой криптографической системы [90]. Другая наиболее известная криптосистема с открытым ключом все еще остается несокрушимой, и мы в следующем параграфе опишем ее достаточно детально. Были предложены и другие системы, такие как системы Макэлиса [262] и Эль-Гамаля [166], но мы не будем обсуждать их здесь. По поводу исчерпывающего обзора криптографических систем с открытым ключом обращайтесь к [246, 279]. Захватывающая история создания криптографии с открытым ключом отражена с статье самого Уитфилда Диффи [156].
§ 4. Криптосистема RSA
Самой первой криптографической системой с открытым ключом, из тех что были предложены в открытой литературе вообще, является криптосистема Ривеста, Шамира и Эдлемана [307]. Она стала известна под названием RSA или MIT криптосистемы. Эта криптосистема основывается на вере в то, что модульное возведение в степень при фиксированных экспоненте и модуле является однонаправленной функцией с потайным ходом (см. § 1). Для первоначального ознакомления с этой криптосистемой обращайтесь к статье Мартина Гарднера [185].
Пусть р и q — два больших различных простых числа, п — р ¦ q , а е — некоторое целое, взаимно простое с (р— 1)(</— 1). Тогда для криптосистемы RSA в качестве личного (секретного) ключа может быть выбрана любая такая тройка k = (р, q, е). Пусть также каждое из соответствующих пространств открытых текстов М-к и шифрованных сообщений С к суть Zn, т.е. множество неотрицательных целых чисел, меньших п. (Если при этом ре-
Криптосистема RSA 55
альные сообщения окажутся слишком длинными, чтобы принадлежать Zn, то их необходимо разбивать на части и зашифровать, используя режим шифрования со сцеплением блоков (СВС), который описан в § 3.5). Тогда соответствующая ключу к функция шифрования Ек'.Мк Ск определяется как Ек(т) — те mod п. Для того чтобы полностью определить естественный алгоритм ее вычисления, достаточно записать пиев открытый справочник. Такая пара (п,е) чисел называется открытым ключом. Он легко вычисляется простым перемножением р и q из личного (секретного) ключа (p,q,e).
Вспомним из § 1, что Ек является кандидатом на однонаправленную функцию с потайным ходом, и хотя существует эффективный алгоритм вычисления обратной ей функции D*, но мы не знаем, как получить его эффективно, задаваясь только естественным алгоритмом вычисления ?* (т. е. только при заданных п и е). Тем не менее такой эффективный алгоритм вычисления Dk легко построить, задав дополнительную секретную информацию, а именно — числа р и q, являющиеся множителями числа п. С этой целью, используя обобщений алгоритм Евклида для нахождения наибольшего общего делителя, необходимо вычислить целое число d, такое, что е • d = 1 (mod <р(п)), где <р(п) — (р — 1)(г/ — 1). Тогда по известной теореме Эйлера me d = т (mod п) для каждого целого числа т и, следовательно, me d mod п = т при условии, что О <С m < п, которое обеспечивается, когда тп?Мк- Функция дешифрования Dk'.Ck—^Mk в связи с этим определяется как Dk (с) = md mod п, и для ее вычисления может быть использован также эффективный алгоритм модульного возведения в степень. (Для заданных чисел р и q существует даже более эффективный алгоритм вычисления Dk, который основан на китайской теореме об остатках [292].)
