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

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

ОГЛАВЛЕНИЕ

Следующая >>

15.1.3. Другие концепции стойкости

15.1.3.1. Жесткость. Говорят, что схема шифрования явля­
ется жесткой, если по данной паре (открытый текст, шифротекст)
( т . С) невозможно найти корректный шифротекст С для «связан­
ного» сообш;ения М', не зная М. Заметим, что смысл слова «связан­
ный» здесь не совсем ясен и может варьироваться в зависимости от
целей. Концепция жесткости приобретает важное значение в све­
те результата, который мы докажем неформально, основываясь на
нашем не вполне строгом определении жесткости.

Л е м м а 15.4. Нежесткая схема шифрования нестойка в отношении
адаптивной атаки с выбором шифротекста.
Д о к а з а т е л ь с т в о . Пусть наша схема не является жесткой. Заме­
ним данный нам шифротекст Сь на связанный с ним С'^. При этом
соответствуюш;ие открытые тексты Мъ и М^ тоже должны быть
связанными друг с другом. После этого нападаюш;ий может потре­
бовать от оракула дешифровать С'^ и раскрыть М^, что было разре­
шено в нашей предыдуш;ей игре. Затем, зная М^, нападающий может
узнать и М^. •
Позже мы увидим, что практически все схемы шифрования с
открытым ключом, с которыми мы уже встречались, лишены свой­
ства жесткости. Известно, однако, что жесткая схема в отношении
атаки ССА2 является и полиномиально стойкой относительно нее,
и наоборот.
Глава 15. Определения стойкости

15.1.3.2. Текстозависимость. Свойством текстозависимости
обладают наиболее стойкие схемы. Схема называется текстозав-
исимой, если с вычислительной точки зрения практически невоз­
можно построить корректный шифротекст, не имея под рукой со­
ответствующего открытого текста. Следовательно, текстозависи­
мость схемы влечет, что атака ССА на нее не может достичь успеха.
Поскольку создание шифротекста требует информации об откры­
том тексте. Вам просто нечего будет подать на вход расшифровы­
вающего оракула.
Понятие текстозависимости было определено в контексте модели
случайного оракула. В этой модели предполагается, что существуют
идеализированные хэш-функции, которые являются односторонни­
ми и
- вычисляют значения за полиномиальное время;
- наблюдатель не может их отличить от любых других случай­
ных функций.
К модели случайного оракула прибегают в некоторых доказатель­
ствах стойкости. Эти доказательства ничего нам не говорят о ре­
альной стойкости схемы, которую мы рассматриваем, но показыва­
ют, что любая реальная атака на нее должна использовать фактиче­
ское определение встроенной в схему хэш-функции. Обычная прак­
тика заключается в том, что мы доказываем стойкость протокола
с помощью модели случайного оракула, а затем превращаем его в
реальный протокол, заменяя случайного оракула на хэш-функцию
типа SHA'l или MD5.


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

Для облегчения изложения будем учитывать эквивалентность по­
нятий семантической стойкости и неразличимости шифрования (по­
линомиальной стойкости).

15.2.1. RSA
Лемма 15.5. RSA не обладает полиномиальной стойкостью.
Доказательство. Предположим, атакующий знает, что пользова­
тель зашифровал только одно из двух сообщений.
Ml или М2.
Они могут означать: покупаю или продаю, да или нет, и т. д. Пред­
полагается, что атакующему известен открытый ключ пользовате­
ля, а именно N и Е. Получив шифротекст С, нападающий стремит­
ся определить, с каким из двух сообщений Mi или М2 совпадает
подлежащий открытый текст т. Для решения этой задачи ему до­
статочно лишь вычислить
С = Mf (modTV).
Тогда
- если С = С, то атакующий получает равенство т — Mi;
- если С ф С, то можно заключить, что m — М2. •
Очевидно, проблема связана с доступом противника к шифрую­
щей функции, ведь как-никак, это схема с открытым ключом.
Предположим теперь, что процедура расшифровывания не инъ-
ективна, т. е. каждый открытый текст может соответствовать боль­
шому числу шифротекстов, причем то, какой именно шифротекст
получится из данного сообщения, решается шифрующей функцией
в процессе работы. Тогда описанная выше атака будет неудачной.
Другими словами, в целях обеспечения стойкости природа алгорит­
ма шифрования должна быть вероятностной, а не детерминирован­
ной. Позже мы увидим вариант Д5Л-системы, обладающий таким
свойством. Поэтому описанная выше атака к нему не применима.
Однако детерминированная функция шифрования — не единствен­
ная проблема RSA,
По существу, RSA — нежесткая система ввиду свойства гомо-
морфности.

Определение 15.6. (Свойство гомоморфности.) Имея заши­
фрованные сообщения vfi\ и т 2 , можно определить шифротекст, со­
ответствующий произведению т\ • 7П2, не зная самих сообщений.
384 Глава 15, Определения стойкости

Тот факт, что RSA обладает свойством гомоморфности, выте­
кает из уравнения:

(mi -шз)^ (modiV) = ( ( m f (modJV)) • ( m f (modAT))) (modAT).

Опираясь на это свойство, можно показать, что RSA не стойка в
отношении адаптивной атаки с выбором шифротекста.

Л е м м а 15.7. RSA не является ССА2-стоикои,
Доказательство. Предположим, что Ева намерена взломать ши-
фротекст
С = т^ (modА/-).
Она создает «связанный» шифротекст С = 2^С и требует от своего
оракула расшифровать C^ При этом получается некоторое сообш;е-
ние М', после чего достаточно провести следующие вычисления:




15.2.2. Эль-Гамаль
Напомним, что проблема выбора Диффи-Хеллмана (известная как
ПВДХ) состоит в определении истинности равенства
X'y^z{raod#{G))
по данным элементам G^, G^ и 0^ из циклической группы (G).

Л е м м а 15.8. Если ПВДХ — трудная задача в группе (G), то кри­
птосистема Эль-Гамаль обладает полиномиальной стойкостью от­
носительно пассивного нападения.
Доказательство. Допустим, что у нас есть полиномиальный ал­
горитм А, нарушающий полиномиальную стойкость системы Эль-
Гамаль. Опираясь на алгоритм Л, найдем решение задачи ПВДХ.
Такую технику мы уже применяли раньше, когда использовали ал­
горитм, взламываюп];ий Эль-Гамаль (дешифрующий шифротекст),
для решения вычислительной задачи Диффи-Хеллмана. Сейчас, при
более ограничительном определением стойкости, а именно, полино­
миальной стойкости, мы можем только свести задачу взлома систе­
мы к решению (предположительно) более легкой проблемы.
Напомним, что алгоритм А проходит две стадии:
- Стадия поиска^ имеющая на входе открытый ключ, выдающая
два сообщения и некоторую дополнительную информацию.
15.2, Стойкость актуальных алгоритмов шифрования

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


где к — эфемерный, меняющийся с каждым сообщением, секретный
ключ, а. Н — открытый ключ.
Наш алгоритм, решающий ПВДХ, работает следующим образом:
1. Входными данными служат G^, G^ и G^.
2. Положим Н = G^.
3. {Mo,Mi,S) = А{поиск,Н).
4. Определим Ci — G^.
5. Выберем случайным образом В G {0,1}.
6. Положим С2 — Мв • G^.
7. В^ = А{гипотеза, {Ci, С2), Н,Мо,Ml, S).
8. Если В = В', то напечатать ИСТИНА.
9. В противном случае напечатать Л О Ж Ь .
Чтобы показать, что этот алгоритм действительно решает ПВДХ,
приведем следующие аргументы.
- Если Z — X • у, то зашифрованные данные, поданные на вход
стадии гипотезы алгоритма А, будут представлять сообщение
Мв- Следовательно, если алгоритм А может взломать семан­
тическую стойкость системы Эль-Гамаль, то выходные дан­
ные В^ будут верными и алгоритм напечатает ИСТИНА.
- Предположим теперь, что z ^ х -у. В этом случае на вход ста­
дии гипотеза почти наверняка попадут неверные данные, т. е.
шифротекст не будет соответствовать ни MQ, НИ MI. Следо­
вательно, то, что получится на выходе этой стадии, т.е. В\
никак не будет зависеть от В. Значит, алгоритм после окон­
чания работы напечатает ИСТИНА или Л О Ж Ь с одинаковой
вероятностью.
Повторяя алгоритм несколько раз, мы получим вероятностный по­
линомиальный алгоритм решения ПВДХ. Но мы предположили, что
такого алгоритма не существует. Поэтому и алгоритм А — мисти­
фикация. Таким образом, предположение о сложности ПВДХ влечет
невозможность успешных атак на полиномиальную стойкость Эль-
Гамаль с выбором открытого текста. •
Глава 15, Определения стойкости

Однако, несмотря на семантическую стойкость в отношении атак с
выбором открытого текста, Эль-Гамаль — нежесткая криптосистема.

Лемма 15,9. Эль-Гамаль — нежесткая криптосистема.
Доказательство. Предположим, что Ева видит шифротекст
(Cl,C2) = ( G ^ m • Я ' = ) .
Тогда она может создать удовлетворительный шифротекст, соот­
ветствующий сообщению 2 • ш, не зная ни т , ни эфемерного ключа
к^ ни секретного ключа х. Искомый шифротекст получается про­
стым умножением второй его половины на 2:
(Cl,2•C2)-(G^2.m.Я^). •
Опираясь на это отсутствие жесткости, можно показать, как и
в случае RSA^ что Эль-Гамаль не стоек в отношении адаптивной
атаки с выбором шифротекста.

Лемма 15.10. Эль-Гамаль не является ССЛ.2-стойкой схемой.
Доказательство. Предположим, что Ева намерена взломать ши­
фрованное сообщение
C = ( C l , C 2 ) = (G^m•Я'=).
Тогда она создает связанное сообщение
C" = (Ci,2.C2)
И требует у своего расшифровывающего оракула дешифровать С ,
и получить соответствующий открытый текст M^ После этого Ева
вычисляет
М' _ 2C2Cf ^ _ 2 т Я ^ ( ? - ^ ^ _
Т˜ 2 "" 2 ˜
2mG^^G-^^ 2m
— — _ ^ = т. •
2 2

15.3. Семантически стойкие системы
Мы уже видели, что RSA не является семантически стойкой даже
в отношении пассивной атаки. Хорошо бы теперь привести при­
мер семантически стойкой системы, основанной на чем-то близком
к задаче факторизации целых чисел. Первая такая схема принадле­
жит Гольдвассеру и Микали, хотя ее и не используют в практиче­
ских приложениях. Стойкость этой схемы основывается на сложно-
15.3. Семантически стойкие системы

сти проблемы квадратичных вычетов. Действительно, очень трудно
определить, является ли данное число а квадратичным вычетом по
модулю составного 7V, если не знать разложения последнего на про­
стые множители.
Напомним, что множество квадратов в группе (Z/ATZ)* обозна­
чается через
QN = {х'^ (modiV)l X е (Z/JVZ)*} ,
а символом Jjsf обозначают множество элементов, чей символ Якоби
равен плюс единице, т.е.

J^ = {х Е {Z/NZr\ (^) = l}-
Множество псевдо-квадратов совпадает с разностью JN \ QN- ДЛ^Я.
КЗА-иоррбкых модулей N = p-q число элементов в JN равно ^^˜ ^^^˜ ^ ^
в то время как множество QN насчитывает ^^˜ 2^˜ ^ элементов.
Проблема квадратичных вычетов заключается в следующем: пусть
дан X € Jjv, лежит ли он в QN^ Ответить на вопрос очень трудно,
в то время как убедиться в том, что X е JN ДОВОЛЬНО легко.
Изложим систему шифрования Гольдвассера-Микали.
15.3.0.1. Генерирование ключей. В качестве секретного ключа
выбираются два простых числа р и q и вычисляется открытый мо­
дуль N = р • q. Кроме того, открытый ключ содержит целое число
Y eJN\ QN-
Чтобы найти У, сначала определяются элементы у^ G F* и у^ G F*
удовлетворяющие соотношениям


РУ \Я
а потом Y вычисляется по ур иуд с помощью китайской теоремы об
остатках. Очевидно, что полученный У не будет лежать в QN-, НО
он принадлежит множеству JN^ поскольку




15.3.0.2. Шифрование. В системе Гольдвассера-Микали ши­
фруется один бит информации за один раз. Для шифрования бита
b поступают следующим образом:
- берут произвольный элемент х G {Ъ/МЪУ
- и вычисляют C = Y^x^ (modiV).

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

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

ОГЛАВЛЕНИЕ

Следующая >>