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

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

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 203 204 205 206 207 208 < 209 > 210 211 212 213 214 215 .. 311 >> Следующая

Ех (М) = Мех (mod N), Dx(C) = Cdx (modAT).
Поскольку группа RSA является коммутативной, легко видеть, что условие (14.3.1) выполняется. До завершения игры обе стороны сохраняют свои показатели степеней в тайне. Таким образом, никто не может создать зашифрованный текст, идентичный тексту, созданному партнером. Это не позволяет одному партнеру раскрыть карты другого партнера, получив зашифрованный текст. Кроме того, никто не может расшифровать текст, созданный другим партнером. Таким образом, криптосистема действительно является "достаточно стойкой".
Очевидно, что после завершения игры обе партии могут раскрыть свои показатели степеней и убедиться, что шифрование и расшифровка были выполнены правильно. Итак, четвертое правило честной раздачи карт выполнено.
524
Часть V. Методы формального доказательства стойкости
В проведенном анализе использовалось не вполне адекватное и разумное понятие стойкости: "достаточная стойкость" криптосистемы означает, что Злоумышленник не способен создать правильный зашифрованный текст по заданному исходному тексту, не зная правильного ключа шифрования, либо расшифровать текст, не зная правильного ключа расшифровки. Неадекватность и неразумность такого понятия стойкости совершенно очевидны. Липтон (Lipton) [178] доказал, что протокол 14.2, основанный на оригинальной криптосистеме RSA, не обеспечивает честной раздачи карт при игре в мысленный покер. Это происходит потому, что криптосистема RSA не позволяет скрыть определенную априорную информацию об исходных сообщениях. В данном случае априорная информация такова: исходное сообщение является квадратичным вычетом. Как показано в разделе 6.5, число а представляет собой квадратичный вычет по модулю п, если выполняется условие gcd(a, N) = 1 и существует число х < N, такое что
x2 = a(modN).
Следует заметить, что, поскольку число <f>(N) является четным, показатель степени е, используемый при шифровании, и показатель степени d, применяемый при расшифровке, удовлетворяющие уравнению (14.3.2), должны быть нечетными. Следовательно, исходный текст м является квадратичным вычетом по модулю N, т.е. м е QRtv тогда и только тогда, когда соответствуюгдий зашифрованный текст удовлетворяет условию С е qrn, поскольку
С ее Ме = (x2f = (xe)2(mod N)
для некоторого числа х < N. Иначе говоря, шифрование по алгоритму RSA не может отменить тот факт, что исходное сообщение является квадратичным вычетом. Следовательно, зная разложение числа N, легко выбрать зашифрованный текст Се QR.n'. сначала применить операцию деления числа С по модулю, равному каждому простому множителю числа N, затем вычислить символ Лежандра, используя алгоритм 6.2.
Следовательно, если одни исходные тексты принадлежат множеству QR^, а другие — нет, то партнер, знающий трюк Липтона, получит нечестное преимущество в игре: он точно знает, какие карты не были вообще ни разу зашифрованы.
Итак, игра в мысленный покер не является стойкой. Точнее говоря, протокол 14.1 не является стойким по отношению к атаке IND-CPA.
14.3.3 Вероятностное шифрование Голдвассера и Микали
Протокол 14.2 можно защитить от атаки Липтона. Например, все карты можно выбирать из множества QRN. Однако Голдвассер и Микали предложили решить
Глава 14. Определения формальной и сильной стойкости криптосистем... 525
гораздо более сложную проблему, введя более строгое понятие стойкости — семантическую стойкость.
Свойство 14.1 (Семантическая стойкость). Все элементы открытого текста, которые можно эффективно вычислить по заданному зашифрованному тексту, можно эффективно вычислить и без него.
Голдвассер и Микали предложили схему вероятностного шифрования (probabilistic encryption), обладающую этим свойством. Изобретенная ими схема называется криптосистемой GM. Она шифрует все сообщение бит за битом, причем вся сложность, связанная с поиском отдельного зашифрованного бита в тексте с, заключается в проверке, принадлежит число с множеству QR^ или множеству JN(l)\QRN, где JN(l) = {х | х 6 Щ, (§) = 1}.
Криптосистема GM описывается алгоритмом 14.1.
Покажем, что система, определенная алгоритмом 14.1, является криптографической, т.е., выполняя расшифровку, Алиса действительно восстанавливает подлинное исходное сообщение, отправленное Бобом.
Анализируя алгоритм шифрования, легко видеть, что нулевой бит исходного сообщения шифруется числом, принадлежащим множеству QR^.
Если бит исходного текста равен 1, соответствующий зашифрованный текст имеет вид с — ух2. Учитывая, что — —1, и мультипликативное
свойство символа Лежандра (теорема 6.16 из раздела 6.5.2), получаем следующее.
е)-(«?)-®(7)-^—
Следовательно,
Ш=Ш
Иначе говоря, единица в исходном тексте превращается в зашифрованный текст, принадлежащий множеству Ja/-(1)\QRjv-
Алгоритм расшифровки работает правильно, поскольку, зная числа р и q, Алиса может определить, какому множеству принадлежит зашифрованный текст ci: QR^ или J;v(l)\QR^, и правильно восстановить исходное сообщение бит за битом.
Нетрудно убедиться, что для шифрования сообщения, состоящего из ? бит, необходимо выполнить 0(?(\og2 N)2) побитовых операций. Это выражение представляет собой оценку временной сложности алгоритма. Степень расширения
Предыдущая << 1 .. 203 204 205 206 207 208 < 209 > 210 211 212 213 214 215 .. 311 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed