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

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

ОГЛАВЛЕНИЕ

Следующая >>

щему оракулу, мы получим исходный открытый текст.
Глава 17. Доказуемая стойкость со случайным оракулом

Необходимо доказать, что спроектированный нами дешифрую­
щий оракул достаточно долгое время способен «обманывать» про­
тивника А. Иначе говоря, нам нужно показать, что если оракулу
передается шифротекст, который не был произведен с помощью
предыдущих необходимых хэш-запросов, то получается значение,
согласующееся с работой алгоритма А.
Наконец, нам нужно продемонстрировать, что если противник
А имеет достаточно большие шансы взломать семантическую стой­
кость системы RSA-OAEP^ то существует достаточно большая ве­
роятность частичного обращения функции / .
Эти последние моменты доказываются с помощью тонкого ана­
лиза вероятностей, ассоциированных с некоторым числом частных
случаев. Напомним, что ВА предполагает, что С* = /(5*,t*) — ши­
фрованная версия Мь. Следовательно, должно найтись такое г*, ко­
торое удовлетворяет условиям:
г* = я(5*) е г , Gir"") - 5* е {Мь\\о^').
Сначала доказывают незначительность вероятности неудачной ра­
боты расшифровывающего оракула. Затем, предполагая достаточ­
но высокую вероятность успеха нападающего алгоритма Л, пока­
зывают, что вероятность получения 5* в качестве запроса тоже не
маленькая. Как только поступит хэш-запрос о числе 5*, мы можем
остановить процесс, поскольку цель — частичное инвертирование
функции / — будет достигнута.
К доказательству привлекается сложная техника теории вероят­
ностей, и мы не будем ее здесь излагать. Любознательному читате­
лю можно порекомендовать статью Фуджисаки, Окамото, Пойнт-
чеваля и Стерна, где написано полное доказательство. •

17.3.3. П р е о б р а з о в а н и е с х е м СРА в с х е м ы ССА2
Предположим, что у нас есть схема шифрования с открытым клю­
чом, семантически стойкая в отношении атаки с выбором откры­
того текста, например, Эль-Гамаль. По определению, такая схема
должна быть недетерминированной, поэтому мы записываем ши­
фрующую функцию как
Е{т,г),
где т — предназначенное для шифрования сообп1;ение, а г — случай­
ная дополнительная информация. Расшифровывающую функцию бу­
дем, как обычно, обозначать через D{C). Следовательно, в шифро-
17.3. Стойкость шифрующих алгоритмов

вании Эль-Гамаль имеем
Е{т,г) - ( G ^ m • Я ^ ) .
Фуджисаки и Окамото показали, как превратить такую схему
в криптосистему, семантически стойкую в отношении адаптивного
нападения в модели случайного оракула. Фактически, они доказы­
вают текстозависимость трансформированной схемы. Мы опустим
доказательство вообш;е, но приведем конструкцию трансформации,
которая настолько же проста, насколько элегантна.
Меняем шифрующую функцию следуюп];им образом:
Е'{т,г) = E{m\\r,F{m\\r)),
где F — какая-то хэш-функция. Расшифровывающий алгоритм то­
же несколько видоизменяется. Сначала вычисляют
т' = D{C),
а потом проверяют равенство
C = E(m',F(mO).
Если равенство истинно, то т восстанавливается из т^ = т\\г.
В противном случае делается вывод о некорректности шифротекста.
В частности, для Эль-Гамаль получается шифруюш;ий алгоритм


который лишь немного менее эффективен, чем исходная криптоси­
стема.

К р а т к о е с о д е р ж а н и е главы

- Основной инструмент доказуемой стойкости состоит в исполь­
зовании успешного нападения на криптосистему для решения
предположительно трудной вычислительной задачи. Посколь­
ку мы верим в сложность этой задачи, можно сделать вывод о
невозможности успешной атаки.
- Модель случайного оракула — вычислительная модель, при­
меняемая в доказательствах стойкости. Доказательство стой­
кости системы, полученное в модели случайного оракула, не
означает, что данная криптосистема действительно стойка.
Оно лишь говорит о том, что система может быть стойкой.
- В модели случайного оракула применяется лемма Стерна и
Пойнтчеваля, чтобы показать, что определенная схема, осно-
Глава 17. Доказуемая стойкость со случайным оракулом

ванная на дискретном логарифмировании, стойка. Чтобы по­
лучить доказательство в случае активного противника, ис­
пользуют случайней оракул для моделирования требований
подписи противника.
- Можно показать, что две основные схемы подписи RSA., а имен­
но RSA-FDH и RSA-PSS^ применяемые на практике, стойки в
модели случайного оракула.
- Доказательства стойкости алгоритмов шифрования несколько
более хитрые. Ранние попытки таких доказательств, предпри­
нятые Женгом и Себерри, были основаны на нестандартных
предположениях.
- В модели случайного оракула можно показать, что стандарт­
ный метод шифрования RSA^ а именно, RSA-OAEP^ крипто-
стоек.

Дополнительная литература
Доказуемая стойкость — быстро развиваюш;аяся область крипто­
графии, и число статей, посвященных этой теме, возрастает с ка­
ждым годом. Хорошее описание леммы Стерна и Пойнтчеваля и
ее приложений даны в оригинальной работе Пойнтчеваля и Стер­
на. Модель случайного оракула и некоторые приложения, включая
RSA-FDH и RSA-PSS^ описаны в работе Белларе и Рогавея. Полное
доказательство стойкости системы RSA-OAEP приведено в труде
Фуджисаки и др.
М. Bellare and P. Rogaway. Random oracles are practical: a paradigm
for designing efficient protocols. In Proc. 1st Annual Conf. on Сотр. and
Comms. Security, ACM, 62-73, 1993.
M. Bellare and P. Rogaway. The exact security of digital signatures —
How to sign with RSA and Rabin, In Advances in Cryptology — Euro-
Crypt '96. Springer-Verlag LNCS 1070, 399-416, 1996.
E. Fujisaki, T. Okamoto, D. Pointcheval and J. Stern. RSA-OAEP is se­
cure under the RSA assumption. In Advances in Cryptology — CRYP­
TO 2001, Springer-Verlag LNCS 2139, 260-274, 2001.
D. Pointcheval and J. Stern. Security arguments for digital signatures
and blind signatures, J. Cryptology, 13, 361-396, 2000.

Контрольные вопросы
17.1.1. Что скрывается под термином «достаточно большая вероят­
ность»?
17.3. Стойкость шифрующих алгоритмов 437

17.1.2. Что собой представляет модель случайного оракула и почему
доказательства, полученные в рамках этой модели, не при­
менимы на практике?

17.1.3. Сформулируйте лемму Стерна и Пойнтчеваля. Расскажите,
как она применяется А,ЛЯ доказательства стойкости схемы
подписи Шнорра в модели случайного оракула.

17.1.4. Почему невозможно применить эту лемму р^ля доказатель­
ства стойкости DSA в модели случайного оракула?

17.1.5. Почему в целях обеспечения стойкости шифрующих схем в
отношении активного нападения проектировщики добавля­
ют к шифротексту избыточную случайную информацию?

17.1.6. Какая пополняющая схема используется в RSA-OAEPl

17.1.7. Какое отношение схема пополнения из RSA-OAEP имеет к
шифру Фейстеля?

Упражнения
17.2.1. Насколько легко построить хэш-функцию с множеством зна­
чений {Ъ/МЪУ, применяемую в RSA-FDH1
17.2.2. Выпишите расшифровывающие процедуры второй и третьей
схем Женга и Себерри.

17.2.3. Доказательство стойкости RSA-OAEP исходит из предполо­
жения о том, что функция RSA., отображающая А;-битовые
строки в А;-битовые строки, является односторонней функци­
ей с секретом. Верное ли это предположение? И если оно лож­
но, то можно ли сконструировать успешную атаку на RSA-
OAEP?
ГЛАВА 18
ДОКАЗУЕМАЯ
СТОЙКОСТЬ
БЕЗ СЛУЧАЙНОГО
ОРАКУЛА

Ц е л и главы
• Описать некоторые из наиболее современных схем, чью стой­
кость можно доказать, не прибегая к модели случайного ора­
кула.
• Исследовать сильные предположения RSA и интерактивные
хэш-предположения Диффи-Хеллмана.
• Объяснить алгоритмы подписи GHR и Крамера-Шоупа.
• Рассказать о шифрующем алгоритме Крамера-Шоупа.
• Познакомить с алгоритмом шифрования DHIES.


18.1. Введение
в предыдуш;ей главе мы рассматривали алгоритмы шифрования и
схемы цифровой подписи, чью стойкость можно доказать с помо-
щъю модели случайного оракула. Как уже отмечалось, модель слу­
чайного оракула реально не моделирует вычислений, встречающих­
ся на практике. Доказательства, полученные в рамках этой модели,
говорят лишь о возможной стойкости алгоритмов, применяющих­
ся на практике, но не гарантируют ее. Эти доказательства можно
интерпретировать так, что если существует удачное нападение на
схему, то противник должен воспользоваться специально привлечен­
ной хэш-функцией.
В этой главе приводится краткий обзор последних работ о по­
пытках конструирования алгоритмов подписи и шифрования, не
зависящих от модели случайного оракула. Мы ограничимся толь­
ко теми схемами, которые имеют практическое значение, опустив
18.2. Некоторые новые задачи

при этом подробные доказательства утверждений, но расскажем об
основных моментах рассуждений. Читатель, интересующийся по­
дробными доказательствами или схемами, не вошедшими в книгу,
должен обратиться к разнообразной литературе в этой области.
Мы увидим, что в то время как стойкость естественных шифру­
ющих алгоритмов может быть доказана без случайного оракула, в
отношении схем подписи такого заявления сделать нельзя. Ситуа­
ция здесь противоположна той, которая возникала при привлечении
случайного оракула к моделированию хэш-функций. В предыдущей
главе схемы подписи выглядели более естественными по сравнению
с алгоритмами шифрования. Но это вполне объяснимо: алгоритмы
подписи интенсивно используют хэш-функции для обеспечения сво­
ей стойкости. Следовательно, имеет смысл считать, что они предъ­
являют такие строгие требования к хэш-функциям, что в реальном
мире и не встретишь функций, удовлетворяющих этим требованиям.
Однако отказ от случайного оракула стоит дорого. Теперь нам
нужно делать более строгие предположения, чем те, которые мы
могли себе позволить со случайным оракулом. В следующем пара­
графе речь пойдет о двух таких новых предположениях. Они не­
сомненно имеют близкое отношение к уже встречавшимся нам, на­
пример, трудноразрешимость проблемы выбора Диффи-Хеллмана
или сложность задачи RSA. Но новая формулировка старых задач
менее изучена, нежели уже знакомая Вам. Кроме того, модифициро­
ванные задачи окажутся менее сложными, поэтому предположение
о их трудноразрешимости — более сильное, чем исходные.


18.2. Некоторые новые задачи
18.2.1. Сильные 125^-предположения
Мы уже изучали предположения RSA., которые говорят о трудности
следуюш;ей задачи:

Определение 18.1. (Задача RSA.) Пусть дан модуль N = р • q
алгоритма RSA^ экспонента Е^ взаимно простая с ^{N)^ и случай­
ный элемент С G (Z/iVZ)*. Требуется найти элемент т G (Z/A^Z)*,
для которого
т^ = С (modAT).

Сильное предполоэюение RSA состоит в трудноразрешимости та­
кой задачи:
Глава 18. Доказуемая стойкость без случайного оракула

Определение 18.2. (Слабая задача RSA,) Пусть дан модуль
N = р- q алгоритма RSA и случайный элемент С G (Z/A/'Z)*. Требу­
ется найти число е > 1 и элемент т G (Z/iVZ)*, д^ля которых
т^ = С (modN),

Ясно, что решив задачу RSA^ мы сможем найти решение и сла­
бой задачи RSA, Это означает, что сильные предположения RSA
действительно сильнее исходных предположений в том смысле, что
решив слабую задачу RSA^ мы все еш;е не сможем найти ответ в за­
даче RSA. Тем не менее, на данный момент мы будем гипотетически
считать, что обе версии задачи RSA эквивалентны по сложности.

18.2.2. И н т е р а к т и в н ы е хэ1п-предположения
Д и ф ф и - Хеллмана
Интерактивные хэш-предположения Диффи - Хеллмана состоят в труд-
норазрешимости определенного аналога проблемы выбора Диффи -
Хеллмана. Прежде всего уточним, что мы имеем в виду под хэш-
задачей Диффи-Хеллмана или HDH (от англ. Hash Diffie-Hellman
problem). Предположим, что нам дана конечная циклическая груп­
па Л и хэш-функция L. В хэш-задаче Диффи-Хеллмана требуется
по данным элементам группы G^^ G^ и хэш-значению Н определить,
истинно ли равенство:
Н = LiG'^WG^'y),
Заметим, что эти предположения комбинируют информацию о взаимо­
действии хэш-функции со стандартными предположениями о труд­
ности решения проблемы выбора Диффи-Хеллмана.
Предположим теперь, что нападаюш;ему на задачу HDH разре­
шен доступ к оракулу, который по скрытому значению у выдает
хэш-значение
HDHy{X) = Ь{Х\\ХУ),
Интерактивные Я/)Я-предположения были выведены из предполо­
жений проблемы выбора Диффи-Хеллмана с учетом возможностей
адаптивного активного противника, вытекаюп1;их из доступа по­
следнего к описанному выше оракулу. Ясно, что мы должны воспре­
пятствовать противнику вводить в НВНу'Оракул значение G^, пос­
кольку это прямой запрос на решение хэш-задачи Диффи-Хеллмана.
Поэтому мы ограничим противника, не разрешая тому осуш;ествить
процедуру
HDHyiG"").

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

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

ОГЛАВЛЕНИЕ

Следующая >>