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

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

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 232 233 234 235 236 237 < 238 > 239 240 241 242 243 244 .. 311 >> Следующая

Глава 15. Доказуемо стойкие и эффективные криптосистемы.
591
Ьввестным только алгоритму А. Поскольку предполагается, что атакующий алго-«тм А является очень хитроумным, то, если (gi, д2, U\, U2) $ D, никогда нельзя выть уверенным, что полученный результат расшифровки как-то связан с зашифрованным окликом. Так как атакующий А убежден в существовании скрытой €вязи, больше нельзя утверждать, что шифрование числа т,ь точно соответствует схеме Крамера-Шоупа в первом варианте или является стойким в теоретико-информационном смысле во втором варианте.
К счастью, если атакующий алгоритм Л снова пошлет зашифрованный текст 1С = (J7i, U2, Е, V), когда (от, д2, U\, U2) ? D, он тут же получит отказ. Это свойство гарантирует теорема 15.1, которую мы вскоре докажем. В частности, будет Доказано, что вероятность отказа не меньше 1 — ^. Обратите внимание на то, что при противоположном событии помощь Саймона атакующему не нужна: с вероятностью ^ он способен самостоятельно угадывать, корректен ли зашифрованный [текст, поскольку размер группы G равен q.
Итак, атакующий алгоритм А не может предотвратить отказ, посылая неправильно зашифрованный текст.
Вероятность успешно пройти проверку, если посланный зашифрованный текст был некорректным, оценивается следующей теоремой.
Теорема 15.1. Пусть (g\,g2,c,d,h,H) — открытый ключ в схеме шифрования Крамера-Шоупа в группе G, имеющей простой порядок q, причем д\ф\ид2ф\. Если [д\, g2,U\,U2) ? D, то вероятность правильно решить следующую задачу равна ^ независимо от применяемого алгоритма. ИСХОДНЫЕ ДАННЫЕ:
Открытый ключ (gi,g2, с, d, h, Н), (Ui, U2, E) G G3. РЕЗУЛЬТАТ:
V EG : (Ui, U2, E, V) — корректный зашифрованный текст, no мнению владельца ключа.
Примечание 15.1. Мы упростили задачу создания корректного зашифрованного текста, сведя ее к вычислению четвертого компонента по заданной тройке (U\,U2,E) и открытому ключу. Обработка компонента V и вычисление одного из трех компонентов зашифрованного текста, по существу, представляют собой одну и ту же задачу. Однако, поскольку число V не является аргументом функции хэширования Н, найти число V проще всего. ?
Доказательство. Для того чтобы создать корректный зашифрованный текст на основе введенных величин, алгоритм должен вычислить значение V е G, удовлетворяющее условию
^1+й«г;?+^ = т/. (15.3.8)
592
Часть V. Методы формального доказательства стойкости
где числа хх,у2,Х2,у2 — закрытый ключ владельца открытого ключа, а а = = H(Ui,U2,E).
Поскольку группа G имеет простой порядок q, число д\ф\ является порождающим элементом группы G (следствие 5.3). Итак, введем обозначение т\ = — logfil Ui, Т2 = logS2 U2, w = logffl p2- Кроме того, для любого элемента V Е G существуют величины logffl d и logffl V. Сочетая формулу (15.3.8) с конструированием компонентов открытого ключа с и d (которые неявно подвергаются проверке при генерации ключа), получаем следующую линейную систему.
/1
О
о 1
T\Ct
W
О
WT2
О \
w
WT20-)
У1
Х2 \У2/
f^ggic\ logffl d
(mod q).
(15.3.9)
Применяя метод Гаусса, приведем матрицу (15.3.9) к следующему виду.
/10 w 0 \
0 10 w
\0 0 w{T2 — Т\) 1Ю0>{Т2 — Т\) J
(mod q).
(15.3.10)
Если («71,52,1/1,1/2) ^ D, выполняется неравенство тх ф r2(mod«7). Кроме того, отметим, что w ф 0(mod«7) (поскольку число «72 Ф 1 также является порождающим элементом группы G). Итак, матрица (15.3.10) имеет полный ранг, равный трем, т.е. три строки являются линейно независимыми. Как известно, это означает, что для любого элемента V Е G существуют (неединственные) решения (x1,y1,x2,y2)(raodq).
Итак, мы доказали, что, если входные данные удовлетворяют условиям теоремы, для всех q элементов группы G существует корректное число V, т.е. при заданных входных данных любой элемент V EG образует корректный зашифрованный текст (Ui,U2,E, V). Однако для владельца ключа среди q возможных вариантов существует только одно число V Е G, согласованное с закрытым ключом {х\,у\,Х2,У2)- (Несмотря на то что для любого фиксированного элемента V Е G существует несколько целочисленных решений системы (15.3.9), совершенно очевидно, что любому элементу V EG может соответствовать только одна фиксированная четверка (х\,у\, Х2, уг)-) Таким образом, установлена вероятность успеха при решении задачи, сформулированной в теореме. ?
Итак, доказательство стойкости криптосистемы Крамера-Шоупа завершено.
Очевидно, что "сведение к противоречию" в этом доказательстве является линейным: атакующие способности алгоритма Л точно соответствуют способности определять, принадлежит ли данная четверка множеству D. Следовательно,
Глава 15. Доказуемо стойкие и эффективные криптосистемы.
593
можно утверждать, что доказательство стойкости криптосистемы Крамера-Шоупа является строгой редукцией.
15.4 Обзор доказуемо стойких гибридных систем
Гибридные криптосистемы были описаны в разделе 8.15. Они стойки к атаке IND-CCA2 и пригодны для применения схем шифрования с открытым ключом. В этом разделе содержится обзор ряда гибридных криптосистем. Поскольку их количество велико, доказательство их стойкости не приводится. Интересующиеся читатели могут найти их в соответствующих работах.
Предыдущая << 1 .. 232 233 234 235 236 237 < 238 > 239 240 241 242 243 244 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed