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

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

ОГЛАВЛЕНИЕ

Следующая >>

Глава 15. Определения стойкости

Шифротекстом служит число С Обратите внимание на то, что ал­
горитм весьма неэффективен, поскольку отдельный бит открытого
текста занимает log2 N бит в шифротексте.

15.3,0.3. Расшифровывание. Отметим, что любой шифротекст
С принадлежит множеству J^v- Причем если бит Ъ сообщения ра­
вен О, то С будет квадратичным вычетом, в противном случае —
квадратичным невычетом. Таким образом, для дешифрования сооб­
щения необходимо уметь решать проблему квадратичных вычетов
по модулю N. Законный пользователь, естественно, знает разложе­
ние N на простые множители. Поэтому он может вычислить символ
Лежандра ( ^ )• Если найденный символ равен -Ы, то С — квадра­
тичный вычет и соответствующий бит открытого сообщения равен
0. Если же символ равен —1, то С — квадратичный невычет и со­
ответствующий бит равен -fl.

15.3.0.4- Доказательство стойкости. Здесь мы хотим по­
казать, что система шифрования Гольдвассера-Микали защищена
от пассивного нападения, если задача о квадратичных вычетах по
модулю N является трудной.

Лемма 15.11. Если задача о квадратичных вычетах по модулю
N трудная, то криптосистема Гольдвассера-Микали полиномиально
стойка в отношении пассивного нападения.
Доказательство. Пусть у нас есть алгоритм Л, атакующий нашу
криптосистему. Покажем, что с его помощью можно решить задачу
о квадратичных вычетах.
Допустим, нам дан элемент L G JAT и мы хотим определить, явля­
ется ли он квадратичным вычетом, т.е. справедливо ли включение
L G QTV? Поскольку наша криптосистема шифрует отдельные биты
сообщения, на стадии поиска атакующий алгоритм А по открытому
ключу (У, N) создаст два сообщения
Мо = О и Ml = 1.
Сформируем шифротекст
C = L.
Заметим, что если L — квадратичный вычет, то шифротекст С
будет соответствовать сообщению MQ, В противном случае С кор­
ректно отражает сообщение Mi. На стадии гипотезы можно потре­
бовать от алгоритма А определить, какому именно сообщению из
Mi соответствует шифротекст С, и по ответу на этот вопрос мы
15,4- Стойкость подписей

легко можем установить, принадлежит элемент L множеству Q^
или нет. •

15.3.0.5. Адаптивные противники. Заметим, что приведен­
ные выше рассуждения ничего не говорят о том, является ли шифру­
ющая схема Гольдвассера-Микали стойкой в отношении адаптив­
ных нападений. Сейчас мы покажем, что она не обладает таким
свойством.

Л е м м а 15.12. Схема шифрования Гольдвассера-Микали не стойка
по отношению к адаптивной атаке с выбором шифротекста.
Д о к а з а т е л ь с т в о . Пусть С — тестовый шифротекст, и мы хотим
определить тот бит Ь, чьей шифрованной версией он является. На­
помним, что
C = y V (modiV).
Правила игры запрещают нам обрап1;аться к расшифровывающему
оракулу ^\ля дешифрования С, но мы можем потребовать от него
расшифровать любой другой шифротекст по нашему выбору. Со­
здадим новый шифротекст


при некотором произвольном Z ф Q. Легко видеть, что С — ши­
фротекст того же самого бита Ь. Значит, обращаясь к оракулу на
законном основании, можно расшифровать С и получить тот же
открытый текст, что и ^^^ля С. Ш



15.4. Стойкость подписей
Существует много возможных понятий стойкости схем подписи.
Как и в случае со стандартной собственноручной подписью, мы за­
интересованы в том, чтобы подпись нельзя было подделать. Назо­
вем три основных типа фальсификации подписи.
- Полное раскрытие. В этой ситуации злоумышленник может
ставить подписи так же, как законный обладатель ключа. Та­
кая ситуация, фактически, возникает при взломе секретного
ключа и соответствует аналогичному взлому алгоритма ши­
фрования.
- Селективная фальсификация. Здесь нападающий способен под­
делать подпись на единственном сообщении по его выбору.
Глава 15. Определения стойкости

Это аналогично ситуации, когда атакующий алгоритм шифро­
вания может дешифровать одно из сообщений, но не взломать
секретный ключ.
- Экзистенциальная фальсификация. Противник способен под­
делать подпись на единственном сообщении, которое может
быть только случайной строкой битов. Такую ситуацию можно
отождествить с семантической стойкостью криптосистемы.
На практике нас обычно волнуют селективные фальсификации.
Поэтому мы стремимся к тому, чтобы подпись была стойкой имен­
но в отношении селективной подделки. Однако нам неизвестно, как
именно будет использоваться схема подписи. Не исключено, что она
будет работать в протоколах запрос-ответ, где случайная строка би­
тов подписывается различными сторонами. Следовательно, разумно
настаивать на том, чтобы любая схема подписи была стойкой в от­
ношении экзистенциальной фальсификации.
В соответствии с типом фальсификации возникают типы атак.
Наиболее слабая атака производится пассивным противником, ко­
торый, имея открытый ключ, пытается осуществить селективную
или экзистенциальную подделку. Более сильная атака возникает со
стороны адаптивного активного противника, имеющего доступ к
оракулу, производящему законные подписи для данного открыто­
го ключа. Цель активного противника самостоятельно подписать
данное сообщение, не обращаясь р^ля этого конкретного действия к
подписывающему оракулу.

Определение 15.13. Схему подписи считают стойкой, если ада­
птивный противник не способен осуществить ее экзистенциальную
фальсификацию.
Уже отмечалось, что критическим моментом в схемах подписи
является использование хэш-функций. Это можно увидеть вновь,
рассматривая грубый Д5Л-алгоритм подписи, определенный как
S = M^ (modTV).
Осуществить здесь экзистенциальную фальсификацию с помощью
пассивной атаки — дело тривиальное. Противник выбирает случай­
ное значение S и вычисляет
M = S^ (modTV).
Таким образом атакующий получает подпись S на сообщении М.
С другой стороны, активный противник легко сделает селектив­
ную фальсификацию в этой схеме. Допустим, он намерен поставить
15.4' Стойкость подписей

«законную» подпись S на сообщении М. С этой целью противник
генерирует случайное число Mi G (Z/iVZ)* и находит

Ml
Затем атакующий требует от оракула подписать сообщения Mi
и М2. В результате он станет обладателем подписей ^i и 52, причем
Si = Mf (modiV).
Наконец, вычисляя произведение
5 = 5 i - 5 2 (modiV),
атакующий обретает долгожданную подпись, поскольку

5 = 5i • 52 (modiV) - Mf • М^ (modTV) =
= {Ml • М2У (mod AT) = M^ (modAT).

Краткое содержание главы
- Определение стойкости схемы может отличаться от наивного
предположения.
- На сегодняшний день семантическая стойкость де-факто счи­
тается стандартным определением криптостойкости схем ши­
фрования.
- Наличие семантической стойкости трудно доказать, но она
имеет близкое отношение к более легко проверяемому свой­
ству полиномиальной стойкости, часто называемой неразли­
чимостью шифрования.
- При исследовании стойкости необходимо учитывать возмож­
ности противника. Нападения на схемы шифрования разделе­
ны на три типа: атака с выбором открытого текста, атака с
выбором шифротекста и адаптивная атака с выбором шифро-
текста.
- Некоторые схемы, в частности, Эль-Гамаль и система Гольд-
вассера-Микали, полиномиально стойки в отношении пассив­
ного нападения, однако не защищены в отношении активного
адаптивного противника. Другие, например RSA^ не облада­
ют полиномиальной стойкостью даже в отношении пассивного
нападения.
- Стойкость в отношении адаптивной атаки тесно связана с жест­
костью криптосистемы.
Глава 15. Определения стойкости

- Аналогичные подходы применимы к понятиям стойкости схем
подписи, где нас в первую очередь интересует понятие экзи­
стенциальной фальсификации в результате активной атаки.

Дополнительная литература
Хорошее введение в теорию доказуемой стойкости и ее обобщения,
как и фундаментальные идеи доказательств с нулевым разглаше­
нием, можно найти в книге Гольдрайха. С обзором оригинальных
работ, написанных на эти темы вплоть до 1990 г., можно познако­
мится в статье Гольдвассера.
О. Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudo-
randomness. Springer-Verlag, 1999.
S. Goldwasser. The Search for Provable Secure Cryptosystems. In Cryp-
tology and Computational Number Theory^ Proc. Symposia in Applied
Maths, Volume 42, 1990.

Контрольные вопросы
15.1.1. Что означает термин «семантическая стойкость» и какое от­
ношение он имеет к абсолютной стойкости?

15.1.2. Дайте определение полиномиальной стойкости.

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

15.1.4. Назовите две проблемы, связанные с шифрованием RSA^ ко­
торые были описаны в предыдуш;их главах.

15.1.5. В контексте схемы шифрования Гольдвассера-Микали пока­
жите, что если С — корректная шифрограмма бита Ь, то та­
ким же свойством обладает любой шифротекст, полученный
по формуле:
С' = C'Z^ (modN) VZ^O.

15.1.6. Назовите три основные цели, которые пытается достичь на-
падаюш;ий на схемы цифровой подписи.
ГЛАВА 16
ТЕОРЕТИЧЕСКАЯ
СЛОЖНОСТЬ

Ц е л и главы
• Ввести концепции теории сложности, необходимые для изуче­
ния криптографии.
• Объяснить, почему теория сложности не может самостоятель­
но подвести к созданию стойких криптографических систем.
• Объяснить систему Меркля-Хеллмана и причины ее слабости.
• Ввести понятие битовой стойкости.
• Ввести идею случайной саморедукции.


16.1. Классы полиномиальной сложности
Наиболее распространенной ошибкой при проектировании новых
криптографических схем является выбор проблемы, вся трудность
которой проявляется лишь в частных случаях, вместо такой задачи,
которая была бы сложной в средней ситуации. Чтобы разобраться в
этом замечании более подробно, нам необходимо усвоить некоторые
из основных идей теории сложности.
Напомним, что проблемой выбора или задачей принятия реше­
ний {W) называется задача о выборе положительного или отрица­
тельного ответа на вопрос / (который обычно называют запросом)^
закодированный каким-либо способом (например, как строка битов
определенного размера п). Часто имеют в виду некоторое множе­
ство S и задают вопрос вида: верно ли, что I Е S? Например:
- / — целое число, а S — множество всех простых чисел. В этой
ситуации проблема выбора звучит так: является ли данное чи­
сло простым или нет?
- / — граф, а 5 — множество всех графов, которые можно рас­
красить только к красками. Здесь проблема выбора сводится
к выяснению: можно ли данный граф раскрасить по опреде­
ленным правилам, используя ровно к красок? Напомним, что
Глава 16. Теоретическая слоэюностъ

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

Определение 16.1. (Проблема выбора в задаче о рюкзаке.)
Пусть дан набор из N предметов, каждый из которых имеет опреде­
ленный вес Wi. Можно ли сложить некоторые из предметов в рюкзак
так, чтобы общий вес рюкзака составил S? Иными словами, моэю-
но ли найти последовательность {6^}, состоящую из нулей и единиц,
для которой
S = biWi + b2W2 + • • • + bNWN^

Заметим, что время, требуемое на решение задачи о рюкзаке, в
наихудшем случае растет как экспонента от числа предметов N.
Как было отмечено, задача о рюкзаке является проблемой вы­
бора. А что если нам потребуется алгоритм вычисления элементов
последовательности hi?

Определение 16.2. (Задача о рюкзаке.) Пусть дан набор из N
предметов, каждый из которых имеет определенный вес Wi. Требу­
ется сложить некоторые из предметов в рюкзак так, чтобы общий
вес рюкзака составил S. Иными словами, нуэюно найти последова­
тельность {bi}^ состоящую из нулей и единиц, для которой
S = biWi + b2W2 + • • • + ЬлгИ^лг?
Предполагается, что если такая последовательность и существует,
то только одна.
Имея оракула, решающего проблему выбора в задаче о рюкза­

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

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

ОГЛАВЛЕНИЕ

Следующая >>