Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Все эти атаки основаны на предположении, что атакующему не известен криптографический ключ.
Глава 8. Шифрование — асимметричные методы
307
Атаки CPA и ССА изначально предназначались для активного криптоанализа криптосистем с секретным ключом. Целью этого криптоанализа являлся взлом криптосистемы с помощью пар открытых и зашифрованных сообщений, получаемых в ходе атаки [284]. Затем они были адаптированы для криптоанализа криптосистем с открытым ключом. Следует отметить три особенности криптосистем с открытым ключом.
• Услуги шифрования в криптосистеме с открытым ключом доступны любому желающему, поскольку владение открытым ключом обеспечивает полный контроль над алгоритмом шифрования. Иначе говоря, против криптосистем с открытым ключом всегда можно организовать атаку на основе подобранного открытого текста. Итак, любую атаку на криптосистему с открытым ключом, в которой не используется блок расшифровки, можно назвать атакой CPA. Очевидно, что любая криптосистема с открытым ключом должна быть устойчивой к атакам на основе подобранного открытого текста, иначе от нее мало пользы.
• Как правило, криптосистемы с открытым ключом имеют стройную алгебраическую структуру, обладающую свойствами замкнутости, ассоциативности, гомоморфизма и т.п. (см. главу 5). Атакующий может использовать эти свойства и взломать зашифрованный текст с помощью хитроумных вычислений. Если атакующий имеет доступ к блоку расшифровки, его вычисления могут дать представление об исходном тексте и даже взломать всю криптосистему. Следовательно, криптосистемы с открытым ключом особенно уязвимы для атак ССА и ССА2. В главе показано, что все учебные криптосистемы с открытым ключом уязвимы для этих атак. Исходя из этого можно сформулировать следующее правило, основанное на свойстве 8.2.2: владелец открытого ключа никому не должен предоставлять услуги расшифровки. Это условие должно выполняться во всех криптосистемах, описанных в главе. В главе 14 будут рассмотрены более строгие криптосистемы с открытым ключом, не требующие от пользователей особой осторожности.
• На первый взгляд, атака ССА слишком ограничивает возможности атакующего. В приложениях пользователь, подвергающийся атаке (т.е. пользователь, к которому обратились за расшифровкой сообщения), на самом деле не знает об этом. Следовательно, пользователю не известно, когда он должен прекратить расшифровку. Как правило, предполагается, что пользователь слишком наивен и не предполагает о существовании атакующего, а значит, должен предоставлять услуги по расшифровке сообщений постоянно. С другой стороны, любая криптосистема с открытым ключом должна быть устойчивой к атакам CPA, поскольку атакующий может сам зашифровывать подобранные открытые сообщения. По этой причине, в основном, мы будем рассматривать средства защиты от атаки ССА2.
308
Часть III. Основные методы криптографии
8.7 Задача RSA
Средства защиты криптосистемы RSA от атак CPA основаны на сложности вычисления корня е-й степени шифрованного текста с по составному целочислен^ ному модулю п. Это — так называемая задача RSA (RSA problem).
Определение 8.4 (Задача RSA). ИСХОДНЫЕ ДАННЫЕ:
N = pq, где р и q — простые числа;
е: целое число, удовлетворяющее условию gcd(e, (р—1)(д — 1)) = 1.1
ceZ*N.
РЕЗУЛЬТАТ:
Единственное целое число т € Щ^, удовлетворяющее условию те щ = c(modN).
Как и во всех других задачах, обеспечивающих стойкость криптосистем с открытым ключом, сложность задачи RSA зависит от сложности поиска правильный параметров.
Предположение 8.3 (Условия неразрешимости задачи RSA). Алгоритмом рЛ шения задачи RSA называется вероятностный полиномиальный алгоритм Л с преимуществом е > 0:
е = Prob [m <- Л (N, е, me(mod N))],
где входные данные алгоритма Л указаны в определении 8.4.
Пусть TQ — генератор вариантов задачи RSA, получающий на вход число lk,\ время работы которого является полиномом от параметра к, а результатом -§ 1) 2к-бипговый модуль N = pq, где puq — два разных равномерно распределенные случайных простых числа, состоящих из к бит, и 2) е € Щ^-^^-^у
Будем говорить, что генератор TQ удовлетворяет условиям неразрешимост! задачи RSA, если для вариантов TQ(\k) не существует алгоритма решения с пре\ имуществом е > 0, которое не является пренебрежимо малым по отношению к* всем достаточно большим числам к.
Аналогично замечанию 8.1.3 (в разделе 8.4) можно утверждать, что выполне-ние условий неразрешимости задачи RSA означает существование однонаправГ ленной хэш-функции. Как и в замечании 8.1.4, из этого следует, что она являете^ функцией с секретом: существует эффективная процедура, обратная разложении модуля на простые множители.
Следует отметить, что вероятностное пространство в этом условии включает в себя пространство вариантов, пространство исходных сообщений и простран! ство случайных операций рандомизированного алгоритма решения задачи RSA. \
Глава 8. Шифрование — асимметричные методы
309
Кроме того, в условии неразрешимости задачи RSA на вход предполагаемого алгоритма поступает показатель степени е, используемый при шифровании. Это ясно очерчивает цель атаки: решить задачу RSA при заданном показателе степени е. Существует альтернативная постановка задачи RSA, которая называется сильной задачей RSA (strong RSA problem) [85]. Ее цель — найти некоторый нечетный показатель степени е > 1 и решить задачу RSA для этого показателя. Очевидно, что решить сильную задачу RSA легче, чем обычную задачу RSA, в которой показатель степени е фиксирован. Считается, что сильная задача RSA является трудноразрешимой. Условие трудной разрешимости сильной задачи RSA легло в основу некоторых алгоритмов шифрования и криптографических протоколов.
