Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Prob[.4wins П Bad] + Prob[Bad] ^ - + Adv. (15.2.14) i
Учитывая формулу (15.2.11), неравенство (15.2.14) можно переписать следующю| образом.
^(1 - Prob[Bad]) + Prob[Bad] > ]- + Adv,
т.е.
Prob[Bad] > Adv. (15.2.15|
Поскольку Bad — AskG U AskH U DBad, получаем
Prob[Bad] ^ Prob[AskG U AskH] + Prob[DBad] = (15.2.16)
= Prob[AskH] + Prob[AskG П AskH] + Prob[DBad] ^ (15.2.11\ ^ Prob[AskH] + Prob[AskG | AskH] + Prob[DBad]. (15.2.181
Формула (15.2.6) справедлива по первому правилу сложения вероятностей, формула (15.2.7) вытекает из утверждений, доказанных в примере 3.3, а формула (15.2.18) следует из определения условной вероятности и того факта, что вероятность никогда не превышает единицу.
В заключение отметим, что равномерное распределение случайных величин, генерируемых оракулом Н, и условное событие AskG | AskH (т.е. число г* содержится в запросе, а число s* — нет) могут возникать с вероятностью 2~к°. Кроме
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
573
того, из формулы (15.12.9) следует, что вероятность события DBad также равна 2~к° + 2~kl. Из неравенств (15.2.15)-( 15.2.18) явствует, что
Prob[AskH] ^ Adv-(2~feo+1 + 2~fcl).
Следовательно, если преимущество Adv не является пренебрежимо малым по сравнению с параметром к, вероятность Prob[AskH] также является существенной.
Итак, совершенно ясно, что если атакующий способен взломать криптосистему с помощью атаки IND-CCA2, а криптосистема RSA-OAEP реализована с помощью случайных оракулов, то атакующий может частично инвертировать функцию RSA, найдя число s* с тем же самым преимуществом. Частичная инверсия (partial inversion) функции RSA может привести к полной инверсии. Рассмотрим ситуацию, в которой это возможно.
15.2.4 Исправленный вариант схемы RSA-OAEP
Математические выкладки, приведенные в разделе 15.2.3.4, играют важную роль в процессе исправления схемы RSA-OAEP. Однако первая попытка исправить схему не использовала эти рассуждения.
15.2.4.1 Первая попытка Шоупа
К счастью, свойство гибкости функции RSA не похоже на свойство гибкости шифра Файстеля, основанного на ОАЕР-преобразовании (см. рис. 15.2 и обсуждение различий между алгебраическими свойствами этих двух структур). Ирония судьбы заключается в том, что значительная разница между алгебраическими свойствами этих двух структур позволила Шоупу доказать, что схема RSA-OAEP является стойкой к атаке IND-CCA2 при условии, что показатель степени в схеме шифрования RSA чрезвычайно мал: если N — это модуль RSA, то в доказательстве Шоупа требуется, чтобы выполнялось следующее неравенство.
Попробуем разобраться, зачем нужно это условие.
Напомним, что в результате анализа мы пришли к выводу, что если число s*, определенное зашифрованным окликом с* в формуле (15.2.5), не содержится в запросе, посланном оракулу Н, то редукция является статистически корректной. Единственная ситуация, когда редукция оказывается некорректной, возникает тогда, когда число s* содержится в запросе, посланном оракулу Н. В этой ситуации поведение Саймона становится неопределенным.
Шоуп обнаружил, что, если число s* предста&тяет собой строку, состоящую из к—ко бит, и содержится в Я-списке, Саймон может решить следующее уравнение:
к0^ (1оё2Л0/е.
(15.2.19)
(15.2.20)
574
Часть V. Методы формального доказательства стойкости
где 1(х) — целое число, заданное строкой х. Если X < N1^, это уравнение можно решить за время, полиномиально зависящее от числа N, используя алгоритм Коп-персмита [82]. Если число X сравнимо с числом 2ка, и справедливо ограничение (15.2.19), то условие X < N1^ выполняется.
Итак, если Саймон получит для расшифровки текст с и не сможет его рас-1 шифровать, используя метод, описанный в разделе 15.2.3.1, он должен попытаться решить уравнение (15.2.20) относительно величины X, используя каждый элемент из своего Д-списка. Если все попытки окончатся неудачей, Саймон должен отвергнуть зашифрованный текст с. В противном случае решением уравнения является величина X = /(?*). Зная числа s* и ?*, Саймон должен расшифровать текст с, как обычно.
Таким образом, для схемы RSA-OAEP, показатель степени которой удовлетворяет условию (15.2.20), запрос s*, посланный оракулу Н, помогает Саймону инвертировать число с*. Вопрос заключается в следующем: какова величина числа с*, удовлетворяющего условию (15.2.20)? Для стандартного параметра безопасности, применяемого в схеме RSA-OAEP, должны выполняться условия N > 21024 и fco = 160 (для того, чтобы число 2~ко было пренебрежимо малым). Следовательно, е ^ ^jj4- — 6,4. Итак, в стандартном варианте е = 3 или е = 5 — единственно возможные варианты показателя степени (число е должно быть взаимно простым с числом $(Af), которое является четным). Несмотря на то, что эти малые значения показателей степени позволяют обеспечить доказуемую стойкость схемы RSA-OAEP, после появления работы Копперсмита считается, что применять их для шифрования не следует.
Поскольку стандартные установки параметра безопасности ко близки к нижней границе, а число N невозможно резко увеличить, маловероятно, что применение метода редукции к более высоким значениям показателя е приведет к успеху.
