Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Будем говорить, что исследуемая криптосистема устойчива по отношению к игровой атаке, описанной протоколом 14.1, если эксперимент ^ы(^о) неотличим от эксперимента ?fcd(mi). В соответствии с определением 4.15 (раздел 4.7) это означает, что при любом значимом преимуществе Adv не должно существовать ни одного полиномиального алгоритма распознавания. Иначе говоря, преимущество, с которым Злоумышленник может различать результаты шифрования, должно быть пренебрежимо малой величиной по сравнению с параметром безопасности схемы шифрования, которым, как правило, является длина ключа шифрования. Можно считать, что преимущество любого полиномиального алгоритма распознавания, применяемого Злоумышленником, задается медленно растущей функцией, зависящей от объема вычислительных ресурсов. Здесь термин "медленно растущая" означает, что, даже если Злоумышленник резко увеличит объем своих вычислительных ресурсов, преимущество увеличится крайне незначительно. Именно это мы имели в виду, когда в начале главы указывали, что Злоумышленник не должен взламывать криптосистему слишком часто или слишком быстро.
Из аргумента, сопровождающего определение полиномиально неразличимых ансамблей (определение 4.15), следует, что введенное выше понятие стойкости можно назвать полиномиальной неразличимостью шифрования (poli-nornial inditinguishability of encryption). Более того, поскольку оба исходных текста, подобранных Злоумышленником, являются неразличимыми, точное название формулируется так: стойкость к атаке на основе полиномиально неразличимых подобранных исходных текстов (security against polynomially indinguihable
520
Часть V. Методы формального доказательства стойкости
chosen-plaintext attack, IND-SPA), или сокращенно: стойкость IND-CPA (security IND-CPA).
Несмотря на то что в рамках протокола 14.1 Злоумышленник свободен в вы-. боре исходных сообщений, основную трудность при взломе криптосистемы по принципу "все или ничего" представляет однобитовый ответ на вопрос о подобранном зашифрованном тексте: "Какое сообщение содержится в зашифрованном тексте: m-о или mi?". Действительно, все учебные алгоритмы шифрования с открытым ключом, рассмотренные до сих пор, уязвимы для атаки IND-CPA. Легко проверить, что это относится и к криптосистемам RSA и Рабина, поскольку они являются детерминированными и, следовательно, позволяют Злоумышленику восстановить сообщения то и mi путем повторного шифрования. В разделе 14.3.5 будет показано, что криптосистема Эль-Гамаля, предусматривающая вероятностный алгоритм шифрования, также уязвима для атаки IND-CPA.
По мере роста вычислительных ресурсов и упрощения способов атаки стой-4 кость криптосистемы следует увеличивать. Методы повышения стойкости криптосистем излагаются в следующей главе.
14.3 Семантическая стойкость — введение в теорию доказуемой стойкости
Понятие стойкости по отношению к атаке IND-CPA впервые было предложено Голдвассером и Микали [125]. Они назвали это понятие семантической стойкостью (semantic security). Оно заключается в том, что зашифрованный текст не допускает никакой утечки полезной информации об исходном тексте (если не считать полезной информацией длину самого исходного текста) ни одному взломщику, обладающему полиномиально ограниченными вычислительными ресурсами. Голдвассер и Микали обнаружили, что во многих приложениях сообщения могут содержать априорную информацию, полезную для организации атак. Например, зашифрованный текст может содержать только одну простую инструкцию, скажем, "ПОКУПАТЬ" или "ПРОДАВАТЬ", либо имя одного из нескольких кандидатов при голосовании. Голдвассер и Микали указали на то, что криптосистемы с открытым ключом, основанные на непосредственном применении однонаправленных функций с секретом, как правило, очень слабо скрывают такие сообщения. В дальнейшем будет показано, что их критика относится и к системам, описанным в главе 8.
Назрела необходимость ввести более строгое понятие стойкости. Отказ протокола "мысленного покера" является хорошей иллюстрацией слабости криптосистем с открытым ключом, основанных на применении однонаправленных функций с открытым ключом. Для начала рассмотрим протокол мысленного покера, предложенный Шамиром, Ривестом и Адлеманом [261].
Глава 14. Определения формальной и сильной стойкости криптосистем... 521
14.3.1 Протокол мысленного покера SRA
Предположим, что Алиса живет в Нью-Йорке, а Боб — в Лондоне. Они никогда не встречались, но желают сыграть в покер, оставаясь в своих городах. Это стало возможным благодаря изобретателям алгоритма RSA — Шамиру, Ривесту и Адлеману, предложившим "протокол мысленного покера SRA" [261].
В мысленный покер играют по тем же правилам, что и в обычный, однако карты кодируются в сообщениях, поэтому в мысленный покер можно играть с помощью средств связи. Для того чтобы сыграть в покер, Алиса и Боб сначала должны честно раздать карты. Слово "честно" означает, что при раздаче карт Алиса и Боб должны придерживаться четырех правил.
1. Все карты должны раздаваться с одинаковой вероятностью (т.е. равномерно), причем одна и та же карта не должна оказаться у двух разных игроков одновременно.
