<< Предыдущая

стр. 64
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>



Цели главы
• Описать модель случайного оракула.
• Показать, как с помощью модели случайного оракула доказы­
вается стойкость некоторых схем подписи.
• Показать, как из атаки с выбором шифротекста вытекает не­
обходимость снабжать шифротекст некоторой избыточностью.
• Объяснить RSA-OAEP и привести набросок доказательства.
• Описать, как превратить криптосистему Эль-Гамаль в стой­
кую схему шифрования.


17.1. Введение
Современные способы проверки стойкости протоколов основыва­
ются на доказуемой стойкости. Это несколько дезориентирующее
название соответствующей техники, поскольку она реально не до­
казывает криптостойкости в теоретико-информационном смысле,
о котором мы говорили ранее. Сторонники доказуемой стойкости
стремятся показать, что алгоритм успешной атаки на криптосисте­
му можно использовать для создания другого алгоритма, существо­
вание которого считается невозможным.
Специалисты, например, пытаются показать, что атаку с выбо­
ром шифротекста, направленную на семантическую стойкость RSA^
можно использовать для разложения на множители любого нату­
рального числа. Иными словами, такое доказательство — относи­
тельный результат, при котором «доказательство» стойкости при­
вязано к трудноразрешимости задачи факторизации.
17.1, Введение

Главный вклад доказуемой стойкости в криптографию состо­
ит в точном определении понятий стойкого шифрования и стойкой
схемы подписи. Многие из концепций, введенных в этой книге, —
экзистенциальная фальсификация, семантическая стойкость, нераз­
личимость шифрования, адаптивная атака с выбором шифротекста
и т. д., — появились благодаря изучению доказуемой стойкости.
Объясним технику доказуемой стойкости на конкретных при­
мерах. Предположим, что нам дан атакуюш;ий алгоритм, взламы­
вающий некоторую стойкость алгоритма RSA (например, семанти­
ческую) с определенной достаточно большой вероятностью. Однако
сначала необходимо определить, что здесь означает понятие «доста­
точно большая вероятность».
Предположим, что у схемы есть параметр стойкости А;, измеря-
юш;ий, например, количество битов в ключе. В частности, параметр
стойкости алгоритма RSA мог бы равняться числу двоичных знаков
модуля N, Скажем, что противник достигает успеха с достаточ­
но большой вероятностью, если вероятность достижения им своей
цели больше, чем
1
р{кУ
где р{к) — некоторый многочлен, зависящий от к.
Допустим на минуту, что наш противник А пассивен, т.е. не
обращается за помощью к расшифровывающему «черному ящику».
Нам хотелось бы создать новый алгоритм 5 д , имеющий на входе
натуральное число N и вызывающий алгоритм А некоторое число
раз, полиномиально зависящее от fc. Цель нового алгоритма — найти
простые множители числа N с достаточно большой вероятностью.
Существование алгоритма В А показало бы, что наличие пассивного
алгоритма А, взламывающего RSA^ влечет возможность разложения
N на множители за полиномиальное время с достаточно большой
вероятностью. Поскольку мы не верим в изобретение полиномиаль­
ного алгоритма факторизации целых чисел на данном уровне раз­
вития науки, можно сделать вывод, что соответствующий алгоритм
А также неосуществим на сегодняшний день.
Мы уже использовали этот прием, когда показывали, что успеш­
ная пассивная атака на криптосистему Эль-Гамаль дает эффектив­
ный алгоритм решения проблемы выбора Диффи-Хеллмана, или при
демонстрации того, что успех в пассивной атаке на схему Гольдвас-
сера-Микали дает эффективный алгоритм решения задачи о ква­
дратичных вычетах.
Глава 17. Доказуемая стойкость со случайным оракулом

Итак, по данному алгоритму А мы строим новый алгоритм В А-,
использующий А как стандартную процедуру. На вход алгоритму
В А подается трудная математическая задача, которую мы намере­
ны решить, в то время как входными данными алгоритма А служит
некоторая криптографическая задача. Трудности возникают, когда
А моделирует активного противника, имеющего доступ к дешифру­
ющему или подписывающему оракулу, соответствующему данному
открытому ключу. Алгоритм ВА-, использующий А как подпрограм­
му, должен обеспечить А ответами на вопросы, которые тот задает
оракулу. В этой ситуации перед алгоритмом В А возникает несколь­
ко проблем:
- Ответы, поставляемые алгоритму А, должны быть коррект­
ными, т. е. шифротексты необходимо расшифровывать, а под­
писи необходимо проверять. В противном случае алгоритм А
может заметить, что оракул дает лживые ответы. Следова­
тельно, теперь у алгоритма В А нет никаких гарантий в том,
что А достигает успеха с достаточной вероятностью.
- Ответы псевдо-оракула должны быть распределены с той плот­
ностью вероятностей, которую А ожидает от истинного ора­
кула, поскольку в противном случае А заметит подлог.
- Отвечать необходимо на любой вопрос, который алгоритм А
задает оракулу.
- Алгоритм В А должен генерировать ответы, не прибегая к се­
кретному ключу. Например, в случае Д5Л, если ВА нацелен на
поиск множителей числа iV, то он едва ли сможет воспользо­
ваться этими множителями для ответов алгоритму А прежде,
чем определит их.
Последняя из перечисленных проблем наиболее существенна. Факти­
чески, мы требуем от алгоритма В А расшифровать или подписать
сообщение, не опираясь на знание секретного ключа, но именно это
и считается невозможным ввиду криптостойкости схемы.
Для преодоления возникающих трудностей принято использо­
вать так называемую «модель случайного оракула». Случайный ора­
кул — это идеализированная хэш-функция, которая на каждый но­
вый запрос выдает случайный ответ, равномерно распределенный
по области значений, с условием: если один и тот же запрос посту­
пит дважды, то ответ должен быть одинаковым.
В модели случайного оракула предполагается, что противник А
при атаке на схему не пользуется явной хэш-функцией, определен­
ной в этой схеме. Другими словами, противник А достигнет успеха
17.2, Стойкость алгоритмов подписи 417

даже в том случае, если мы заменим настоящую хэш-функцию схемы
случайным оракулом. Алгоритм В А отвечает на запросы противни­
ка А, обманывая последнего «сфабрикованными» случайным ораку­
лом ответами, чтобы удовлетворить свои собственные потребности.
Чтобы увидеть, как это осуществляется на практике, стоит перей­
ти к следующему разделу о доказательстве стойкости алгоритмов
подписи.
Доказательство с моделью случайного оракула носит еще более
относительный характер, чем предыдущие. Такие доказательства
говорят, что в предположении о трудноразрешимости определенной
задачи, например, факторизации, успешного нападения, не исполь­
зующего подлежащей хэш-функции, быть не может. При этом, есте­
ственно, не утверждается, что нет успешных атак, которые имеют
доступ к фактической хэш-функции криптосистемы.
Во всех наших доказательствс1х и определениях мы не слишком
строги. Мы стремимся передать основные идеи и показать их осо­
бенности, не следя за особой математической точностью детального
рассуждения. Читатель, желающий узнать более точные определе­
ния, может обратиться к научным статьям. Однако надо иметь в
виду, что определения этой области могут незначительно меняться
от статьи к статье.


17.2. Стойкость алгоритмов подписи
Сначала мы рассмотрим стойкость алгоритмов цифровой подписи,
поскольку доказательства здесь более просты, чем в алгоритмах
шифрования. Первый основной инструмент, о котором мы будем го­
ворить, — это лемма, принадлежащая Стерну и Пойнтчевалю. Она
применяется к определенному типу схем подписи, которые использу­
ют хэш-функции следующим образом: чтобы подписать сообщение
- производят (возможно пустое) обязательство Ei;
- вычисляют хэш-значение Н = /f(Ei||M);
- находят Е2 — «подпись» на Ei и Н,
Чтобы запомнить запрос к хэш-функции, запишем выходные дан­
ные схемы в виде ( E i , i ? ( S i | | M ) , Ег). Например,
- DSA: El - 0 , Я = Н{М),

Е 2 ^ ( ^ Д , ^ ^ ^ ^ (modQ)
Глава 17. Доказуемая стойкость со случайным оракулом

rfl,eR= (Q'' (modP)) (modQ).
- EC-DSA: El = 0 , Я = H{M),



где R совпадает с координатой x точки [k]G,
- Схема подписи Шнорра: Si = G^, Н = Н{Тч\\М)
Т,2 = хН Л-к (modQ).

Во всех перечисленных схемах предполагают, что хэш-функция при­
нимает значения в Fg.
Напомним, что в модели случайного оракула хэш-функция позво­
ляет алгоритму В А генерировать произвольные ответы на запро­
сы противника А, Предположим, что в модели случайного ораку­
ла нападаюш;ий алгоритм А может генерировать экзистенциальную
фальсификацию для сообп1;ения М с достаточно большой вероятно­
стью. Тогда выходные данные алгоритма А имеют вид:
(М,ЕьЯ,Е2).
Можно считать, что противник создает критический хэш-запрос
Я = Я(Е1||М),
поскольку в противном случае мы можем самостоятельно генериро­
вать запрос нападаюп];его.
Алгоритм В А теперь дважды вызывает подпрограмму против­
ника А, с неизменными случайными входными данными, но слег­
ка измененным случайным оракулом. Противник А выполняет свою
работу за полиномиальное время и при этом выдает полиномиаль­
ное количество хэш-запросов. Если на все хэш-запросы противник
получает тот же самый ответ, то А должен будет выдать неизмен­
ную подпись. Однако алгоритм отвечает на все случайные запросы
нападаюш;его, как и раньше, кроме одного, выбранного случайным
образом, и на него отвечает по-другому. С достаточно большой ве­
роятностью этот «исключительный» запрос окажется критическим
хэш-запросом и поэтому (с достаточно большой вероятностью) про­
тивник В А получит две подписи на одном и том же сообп];ении, ко­
торые имеют разные ответы на хэш-запросы. Иными словами, мы
получим
(М,Е1,Я,Е2) и (М,ЕьЯ',Е^).
Теперь, опираясь на эти два набора выходных данных алгоритма
17.2. Стойкость алгоритмов подписи

А, можно попытаться решить трудную задачу, составляющую цель
алгоритма В А- Подробности и полный разбор этого приема можно
найти в работе Стерна и Пойнтчеваля (точная ссылка приведена в
разделе «Дополнительная литература» в конце этой главы).

17.2.1. Примеры пассивного противника
Рассмотрим некоторые приложения.

17.2.1.1. Схема подписи Шнорра. Лемма Стерна и Пойнтче­
валя позволяет доказать следующую теорему.

Теорема 17.1. Из предположения о трудноразрешимости задачи
дискретного логарифмирования в данной группе вытекает (в моде­
ли случайного оракула), что успешная пассивная атака, направлен­
ная на схему подписи Шнорра с данной группой, невозможна.
Доказательство. Пусть входными данными в алгоритм В А слу­
жит задача дискретного логарифмирования Y = G^., которую мы
намерены решить. Предположим, что мы вызываем процедуру пас­
сивного противника Л, обладаюш;его открытым ключом Y в каче­
стве входных данных, и попытаемся использовать аргументы лем­
мы Стерна и Пойнтчеваля. С достаточно большой вероятностью мы
получим две подписи

( м , Si = G^, Н,Е2=хН + к (mod Q))
и
( м , S; = G^', я ' , Е'2 = хН' + к' (modQ)),

где Н = i?(Ei||M) — ответ случайного оракула при первом проходе
алгоритма А, а Я ' = H{J2[\\M) — при втором.
Цель алгоритма ВА — найти неизвестное число х. Он делает
вывод: к = к'., поскольку Ei = Е^^. Следовательно,
Cx = D (modQ),
где
С = Н -Н' (modQ), 1) = Е2 - Е^ (modQ).
Кроме того, известно, что Л т^ О, поскольку в противном случае
два хэш-значения были бы равны между собой. Следовательно, алго­
ритм В А может решить исходное логарифмическое уравнение, вы­
числяя
x = C-^D (modQ). •
Глава 17. Доказуемая стойкость со случайным оракулом

Позже мы покажем, что схема подписи Шнорра в модели слу­
чайного оракула защищена и от активного нападения.
17.2.L2. DSA-nodnucu. Как мы сейчас покажем, приведенные
в предыдущем разделе рассуждения не применимы для схемы под­
писи DSA.
Пусть входными данными В А является уравнение Y = G^ отно­
сительно неизвестной х^ которое мы намерены решить. Опять будем
вызывать процедуру противника Л, на вход которого подается от­
крытый ключ F , и будем применять лемму Стерна и Пойнтчеваля.
С достаточно большой вероятностью мы получим подписи
(М, S i = 0 , я , Е2 = (R, S)) и (М, Е ; = 0 , я ' , Е^ = {R', S')),
где Н = Н{М) — ответ случайного оракула из первого вызова А, а
Н^ = Н{М) — из второго. Кроме того,
R = G^ (modP) (modg), Д' = G^' (modP) (modQ),
H-hxR . ,^. ^, H^ + xR^
S= 7 (modQ), S= — (modQ).
Цель алгоритма В A — найти x. Однако здесь мы не можем считать,
что к = к\ поскольку мы не знаем, верно ли равенство: R = R', Зна­
чит, прием, сработавший при проверке стойкости схемы подписи
Шнорра, в этой ситуации не применим. Фактически, доказатель­
ство стойкости схемы подписи DSA пока отсутствует.
Можно попытаться подправить доказательство, несколько ви­
доизменив схему ?)5Л, применяя хэш-функцию одновременно к М
и Л, а не только к М . Такое изменение схемы в терминах лем­
мы Стерна и Пойнтчеваля влечет, что Tii = R^ Н = H{M\\R) и
E2 = i i ^ (modQ).
Даже при такой модификации, приближающей схему DSA к схе­
ме Шнорра, мы не сможем доказать ее стойкости. По лемме мы
получим две подписи, в которых
R = G'' (modP) (modQ), R' = G^' (modP) (modQ),

S = ^-±^ (modQ), S' = ^^^4r^ (modQ),
к к'
причем R = R\ Ho мы все еще не сможем сделать вывод о равенстве
к = к\ поскольку оно не вытекает из уравнения

<< Предыдущая

стр. 64
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>