Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 228

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 222 223 224 225 226 227 < 228 > 229 230 231 232 233 234 .. 311 >> Следующая

т
s\\t = Г1(с), r = t@H(s), || 0fel = seG(r)
(15.2.2) (15.2.3) (15.2.4)
568
Часть V. Методы формального доказательства стойкости
показали, что вероятность неправильной имитации расшифровки на этом этапе крайне незначительна.
Следует подчеркнуть, что все приведенные выше рассуждения основаны лишь на однонаправленности функции /.
15.2.3.3 Неполнота
Шоуп обнаружил, что оригинальное доказательство стойкости схемы ОАЕР к атаке IND-CCA2 содержит пробел [270]. Прежде чем приступить к дальнейшим разъяснениям, подчеркнем, что на самом деле никакого дефекта в конструкции схемы ОАЕР нет. Просто формальное доказательство, приведенное в разделе 15.2.3.2, не является полным. Этот недостаток проявляется в следующем.
Имитация расшифровки, выполняемая Саймоном, является статистически точной, поскольку число s*, определяемое по оклику с* в формуле (15.2.5), не содержится в запросе случайному оракулу Н. Однако статистическая точность исчезает, если число s* содержится в запросе, причем оценка вероятности этого события в доказательстве отсутствует.
Для того чтобы объяснить неполноту доказательства, рассмотрим разные ве-' личины, определяемые по зашифрованному оклику с*. Допустим, что
Величины (s*,r*,mb) определяются по зашифрованному оклику с*, где число Ь является результатом жеребьевки с помошью подбрасывания идеальной монеты! выполняемой Саймоном.
Представим себе, что число s* содержится в запросе случайному оракулу Н.\ Разумеется, это событие является весьма маловероятным, поскольку на "этапе поиска" зашифрованный оклик с* еше не вычислен. Вот почему в разделе 15.2.3.J мы пришли к выводу, что доказательство стойкости схемы /-ОАЕР к атаке INDl CCA является корректным. Однако существует вероятность, что атакующий А угадает число s*, получив оклик с* (т.е. на "этапе угадывания").
Чему равна вероятность этого события? Это никому не известно. Определенно можно утверждать лишь, что, если атакующий Л является достаточно мощным^ эта вероятность не равна нулю. В противном случае почему мы должны предполм гать, что атакующий Л вообще способен угадать бит Ь? (Несмотря на это, можнд оценить условную вероятность угадывания числа s* в запросе. Эта вероятности не равна нулю. Соответствующая оценка приводится в разделе 15.2.3.4.)
s* п е = rV), г* = е © я(я*),
mb|| 0fcl =s*©G(r*).
(15.2.51 (15.2.61 (15.2.71
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
569
Поскольку атакующий Л может угадать число s*, атака содержит противоречие, которое легко обнаружить. Зафиксируем значение г*, вычисленное по формуле (15.2.6). Тогда атакующий Л может послать его в следующем запросе. Вероятность того, что для равномерно распределенной случайной величины G(r*), возвращенной Саймоном, число G(r*) © s* совпадет с каким-либо из подобранных исходных текстов, весьма мала. Следовательно, в этот момент атакующий Л воскликнет: "Прекратите дурачиться!". Он должен воскликнуть именно так, поскольку зашифрованный оклик с* не соответствует ни одному из подобранных исходных текстов.
Разумеется, эта "легкость" слишком дорого стоит: атакующий Л вынужден раскрыть Саймону оба числа s* и t* = г* © H(s*) и помочь ему, таким образом, инвертировать функцию / в точке с* f(s* \\ t*)\
Шоуп нашел этой задаче лучшее применение. Он обнаружил, что для некоторой функции /, например, для перестановки OWTP, способности угадать запрос s* по заданному зашифрованному тексту с* вполне достаточно для создания корректного зашифрованного текста без запроса числа г* у случайного оракула G (фактически вообще без взаимодействия с оракулом G на протяжении всей атаки). Более того, поскольку корректный зашифрованный текст, построенный таким образом, является результатом уязвимости другого корректного зашифрованного текста, схема /-ОАЕР является стойкой к атаке NM-CCA2 и по теореме 14.4 (раздел 14.5.4.2) стойкой к атаке IND-CCA2. Однако метод редукции, описанный в разделе 15.2.3.1, не помогает Саймону инвертировать функцию /, поскольку G-список может быть даже пустым (т.е. атакующий Л еще не посылал ни одного запроса случайному оракулу G).
Шоуп построил в качестве контрпримера А;-битовую OWTP-функцию /. Он предположил, что эта перестановка является "xor-гибкой": по заданным числам f{w\), и>2 со значительным преимуществом можно найти число f(w\@W2). Отметим, что это является вполне разумным предположением. В доказательстве стойкости схемы /-ОАЕР, описанном в разделе 15.2.3.1, мы требовали лишь, чтобы функция / была однонаправленной, и она не обязана была быть стойкой. Помимо всего, как показано в предыдущей главе, учебные алгоритмы шифрования с открытым ключом, лежащие в основе схем OWTP, являются уязвимыми. Именно по этой причине возник метод ОАЕР.
Чтобы прояснить ситуацию, допустим, что функция / вообще не скрывает к —ко старших бит. Тогда эту функцию / можно представить в виде
/(* II t) = s\\f0(t),
где функция /о является "xor-гибкой" (к — А;о)-битовой перестановкой OWTP. Следовательно, по заданным числам /o(*i), <2 со значительным преимуществом можно вычислить значение /о(<1©<2)- Эта функция / остается OWTP-перестанов-кой, обладающей свойством однонаправленности и параметром безопасности ко.
Предыдущая << 1 .. 222 223 224 225 226 227 < 228 > 229 230 231 232 233 234 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed