Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Глава 14. Определения формальной и сильной стойкости криптосистем.
533
следовательно, также имеет равномерное распределение. Итак, он не позволяет Злоумышленнику извлечь ни априорную, ни апостериорную информацию об исходном тексте.
Алгоритм шифрования RSA представляет собой перестановку в пространстве сообщений. Алгоритм шифрования Рабина можно представить в виде перестановки во множестве QR^, если N — число Блюма (см. теорему 6.19.4 в разделе 6.7). Итак, эти алгоритмы можно считать подходящими кандидатами на роль алгоритма SPk-
Далее, благодаря силе генератора CSPRB псевдослучайная строка ps, сгенерированная на основе начального числа s, играет роль внутренней случайной операции в схеме шифрования. Следовательно, применение оператора исключающего ИЛИ к сообщению т и строке ps является семантически стойким.
В эффективной схеме шифрования Блюма-Голдвассера, основанной на применении генератора CSPRB (BG cryptosystem [45]), блок с\ в формуле (14.3.3) равен s2*(modN), где г = [^0g°k^™mj + 1. а псевдослучайная строка битов ps генерируется по числу s с помощью датчика псевдослучайных чисел BBS (9.3.1) блок за блоком: каждый блок состоит из log2 log2 N младших значащих битов элемента, представляющего собой степень 2? числа s по модулю N(j = 1,2, ...,г — 1). Следует учесть, что первый элемент в паре зашифрованного текста, по существу, является результатом шифрования строки s с помощью алгоритма Рабина.
Поскольку задача одновременного извлечения log2 log2 N младших значащих битов исходного текста, зашифрованного по схеме Рабина, эквивалентна решению задачи о разложении числа N на простые множители (см. замечание 9.1. в разделе 9.3.1), семантическая стойкость криптосистемы BG эквивалентна сложности факторизации модуля N.
14.4 Неадекватность семантической стойкости
Понятие семантической стойкости (определение 14.1 и свойство 14.1) формализует интуитивное предположение, что любой полиномиально ограниченный Злоумышленник не должен иметь возможность извлекать априорную информацию об исходном тексте из зашифрованного текста. Однако это гарантирует секретность, только если атакущий ведет себя пассивно, т.е. просто перлюстрирует переписку.
В разделах 8.6 и 8.14 указано, что многие криптосистемы с открытым ключом особенно уязвимы для атак на основе подобранного зашифрованного текста (chosen-ciphertext attack) (CCA и ССА2). В ходе атак ССА и ССА2 Злоумышленник может получать помощь при расшифровке, т.е. иметь определенный уровень доступа к "блоку расшифровки" и читать некоторые зашифрованные тексты, даже не владея ключом расшифровки. Такую помощь мы назвали "обучением крипто-
534
Часть V. Методы формального доказательства стойкости
анализу". Атаки на основе подобранного зашифрованного текста, особенно атака ССА2, часто встречаются в реальных приложениях. Например, некоторые протоколы требуют, чтобы пользователь выполнял операцию расшифровки случайного оклика, т.е. участвовал в работе механизма "оклик-отзыв". В других случаях получатель зашифрованного электронного письма может раскрыть исходные сообщения в ходе последующего открытого обсуждения.
Криптосистемы с открытым ключом особенно уязвимы для атак ССА и ССА2 из-за алгебраических свойств, лежащих в их основе. Злоумышленник может использовать эти свойства и создать зашифрованный текст путем сложных вычислений. Если Злоумышленник получает помощь при расшифровке, то в его распоряжение могут попасть сообщения, которые должны были быть недоступными.
В примере 8.9 продемонстрирована уязвимость криптосистемы Эль-Гамаля к атаке ССА2. Очевидно, что эта атака опасна и для семантически стойких криптосистем, даже если они используют генератор CSPRB. В ходе таких атак блок с2 в формуле (14.3.3) заменяется выражением с'2 = г © с2, где г — строка, состоящая из i бит, играющая роль случайного числа т в примере 8.9.
Продемонстрируем уязвимость криптосистемы GM для атаки ССА2.
Пример 14.2. Пусть Злоумышленник имеет ограниченный доступ к блоку расшифровки, принадлежащему Алисе. Это условие вполне "разумно": если результат расшифровки текста, полученного от Злоумышленника, выглядит как случайный набор чисел, то Алиса должна вернуть Злоумышленнику исходный текст. I Предположим, что зашифрованный текст С = (ст, с2,..., q) содержит исходный текст В = (pi,b2, -¦ ¦ ,bg), отправленный Алисой кому-нибудь (за исключением Злоумышленника!). Злоумышленник перехватывает сообщение С и желает восстановить текст В. Для этого он посылает Алисе следующий "хитроумный зашифрованный текст".
В ходе этой атаки Злоумышленник использует следующее алгебраическое свойство.
Это свойство непосредственно следует из критерия Эйлера (теорема 6.13 в разде-1 ле 6.5.1).
Итак, поскольку у G Ja^I^QR^, можно убедиться, что число у шифрует единичный бит. Затем, применяя атаку "путем умножения на у" ("multiplying-' у attack") к шифрованному тексту (14.4.1), Злоумышленник переключает биты
С = (yci,yc2,yc?)(mod N).
(14.4.11
Глава 14. Определения формальной и сильной стойкости криптосистем... 535
fy, г = 1,2,..., ?, т.е. в результате расшифровки Алиса получит исходный текст
