Взлом криптосистем с открытым ключом с помощью криптоанализа

Можно сказать, что «криптосистема X является стойкой по отношению к атаке Y, но нестойкой по отношению к атаке Z», то есть стойкость криптосистемы зависит от разновидности атаки. Активные атаки можно разделить на три вида.

Атака на основе подобранного открытого текста (chosen – plaintext attack - CPA). Атакующий выбирает исходные сообщения и передает их шифровальщику для получения зашифрованных текстов. Задача атакующего – взломать криптосистему, используя полученные пары открытых и зашифрованных текстов.

Атака на основе подобранного зашифрованного текста (chosen-ciphertext attack - CCA). Атакующий выбирает зашифрованные сообщения и передает их на расшифровку для получения исходных сообщений. Цель атакующего – взломать криптосистему, используя полученные пары открытых и зашифрованных текстов. Атакующий достигает успеха, если он раскрывает ключ и способен в дальнейшем извлекать секретную информацию из зашифрованного текста, не прибегая к посторонней помощи.

Атака на основе адаптивно подобранного зашифрованного текста (adaptive chosen – ciphertext attack – CCA2). Это – развидность атаки CCA, в которой услуги расшифровки доступны для всех зашифрованных текстов, за исключением заданного.

Эти атаки можно описать следующими сценариями.

В атаке на основе подобранного открытого текста атакующий владеет блоком шифрования.

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

В атаке на основе адаптивно подобранного зашифрованного текста атакующий владеет блоком расшифровки сколь угодно долго, однако, как и в предыдущем случае, расшифровка требуемого текста должна выполняться без его помощи. Это условие вполне естественно – иначе атакующему незачем взламывать систему.

Все эти атаки основаны на предположении, что атакующему неизвестен криптографический ключ.

Атаки CPA и CCA изначально предназначались для активного криптоанализа криптосистем с секретным ключом. Целью этого криптоанализа является взлом криптосистемы с помощью пар открытых и зашифрованных сообщений, получаемых в ходе атаки. Затем они были адаптированы для криптоанализа криптосистем с открытым ключом. Следует отметить три особенности криптосистем с открытым ключом.

Услуги шифрования в криптосистеме с открытым ключом доступны любому желающему, поскольку владение открытым ключом обеспечивает полный контроль над алгоритмом шифрования. Иначе говоря, против криптосистем с открытым ключом всегда можно организовать атаку на основе подобранного открытого текста. Итак, любую атаку на криптосистему с открытым ключом, в которой не используется блок расшифровки, можно назвать атакой CPA. Очевидно, что любая криптосистема с открытым ключом должна быть устойчивой к атакам на основе подобранного открытого текста, иначе от нее мало пользы.

Как правило, криптосистемы с открытым ключом имеют стройную алгебраическую структуру, обладающую свойствами замкнутости, ассоциативности, гомоморфизма и т.п. Атакующий может использовать эти свойства и взломать зашифрованный текст с помощью хитроумных вычислений. Если атакующий имеет доступ к блоку расшифровки, его вычисления могут дать представление об исходном тексте и даже взломать всю криптосистему. Следовательно, криптосистемы с открытым ключом особенно уязвимы для атак CCA и CCA2. Исходя из этого можно сформулировать следующее правило, владелец открытого ключа никому не должен предоставлять услуги расшифровки. Это условие должно выполняться во всех криптосистемах с открытым ключом.

На первый взгляд, атака CCA слишком ограничивает возможности атакующего. В приложениях пользователь, подвергающийся атаке (то есть пользователь, к которому обратились за расшифровкой сообщения), на самом деле не знает об этом. Следовательно, пользователю не известно, когда ему следует прекратить расшифровку. Как правило, предполагается, что пользователь слишком наивен и не предполагает о существовании атакующего, а значит, должен предоставлять услуги по расшифровке сообщений постоянно. С другой стороны, любая криптосистема с открытым ключом должна быть устойчивой к атакам CPA, поскольку атакующий может сам зашифровывать подобранные открытые сообщения. По этой причине, в основном, мы будем рассматривать средства защиты от атаки CCA2.

Задача RSA

Средства защиты криптосистемы RSA от атак CPA основаны на сложности вычисления корня e-й степени шифрованного текста c по составному целочисленному модулю n. Это так называемая задача RSA.

Исходные данные:

e: целое число, удовлетворяющее условию НОД(e, (p-1)(q-1)) = 1.

c принадлежит множеству целых чисел по модулю N.

Результат:

Единственное целое число m, принадлежащее множеству целых чисел по модулю N, удовлетворяющее условию m^e ≡c(mod N)

Как и во всех других задачах, обеспечивающих стойкость криптосистем с открытым ключом, сложность задачи RSA зависит от сложности поиска правильных параметров.

Условие неразрешимости задачи RSA. Алгоритмом решения задачи RSA называется вероятностный полиномиальный алгоритм A с преимуществом ε > 0:

ε = P[m←A(N,e, m^e (mod N))],

где входные данные A определены выше.

Пусть имеется генератор вариантов задачи RSA – IG, получающий на вход число 1^k, время работы которого является полином от параметра k, а результатом – 1) 2k – битовый модуль N = pq, где p и q – два разных равномерно распределенных случайных простых числа, состоящих из k бит, и 2) e принадлежит множеству целых чисел по модулю (p-1)(q-1).

Будем говорить, что генератор IG удовлетворяет условиям неразрешимости задачи RSA, если для вариантов IG(1^k) не существует алгоритма решения с преимуществом ε > 0, которое не является пренебрежимо малым по отношению ко всем достаточно большим числам k.

Выполнение условий неразрешимости задачи RSA означает существование однонаправленной хэш-функции. Она является функцией с секретом: существует эффективная процедура, обратная разложению модуля на простые множители.

Следует отметить, что вероятностное пространство в этом условии включает в себя пространство вариантов, пространство исходных сообщений и пространство случайных операций рандомизированного алгоритма решения задачи RSA. Кроме того, в условии неразрешимости задачи RSA на вход предполагаемого алгоритма поступает показатель степени e, используемый при шифровании. Это ясно очерчивает цель атаки: решить задачу RSA при заданном показателе степени e. Существует альтернативная постановка задачи RSA, которая называется сильной задачей RSA. Ее цель – найти некоторый нечетный показатель степени e > 1 и решить задачу RSA для этого показателя. Очевидно, что решить сильную задачу RSA проще, чем обычную задачу RSA, в которой показатель степени e фиксирован. Считается, что сильная задача является трудноразрешимой. Условие трудной разрешимости сильной задачи RSA легло в основу некоторых алгоритмов шифрования и криптографических протоколов.