Введение в современную криптографию
Совершенная неразличимость для противника
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ОПРЕДЕЛЕНИЕ 2.5
| Совершенная неразличимость для противника. Данный раздел мы закончим,
представив другое равнозначное определение совершенной стойкости. В основе это- го определения лежит эксперимент, в ходе которого противник рассматривает шифр- текст, не пытаясь его проанализировать или раскрыть, после чего пытается угадать, какое из двух возможных сообщений было зашифровано. Мы вводим данное поня- тие, поскольку оно служит отправной точкой для определения вычислительной стой- кости в следующей главе. Действительно, на протяжении всей книги мы часто будет использовать такого рода эксперименты для определения безопасности. В данном контексте мы рассмотрим следующий эксперимент: противник A сначала определяет два противоречащих друг другу сообщения m0, m1 ∈ M. Одно из этих двух сообщений было равномерно выбрано случайным образом и зашифровано с использованием случайного ключа. Получившийся шифртекст был передан A. В конце A выводит «догадку» о том, какое из двух сообщений было зашифровано. A добивается успеха, если догадка оказывается верна. Си- стема шифрования является совершенно неотличимой, если ни один противник A не добьется успеха с вероятностью выше 1/2. (Обратите внимание, что для любой системы шифрования вероятность, что A достигнет успеха, составляет 1/2 при выводе равномерно распределенной догадки. Главное требование: ни один перехватчик не должен справиться лучше.) По дчеркиваем, вычислитель- ные возможности A ничем не ограничиваются. 40 Формально, пусть Π = (Gen, Enc, Dec) является системой шифрования с про- странством сообщения M. Пусть A - это противник, который формально явля- ется лишь алгоритмом (отслеживающим состояние). Обозначим содержание эксперимента следующим образом : Эксперимент совершенной неразличимости для противника : 1. Противник A выводит пару сообщений m0, m1 ∈ M. 2. С помощью алгоритма Gen генерируется ключ k и выбирается единоо- бразный бит b ∈ {0, 1}. Вычисляется шифртекст c ← Enck (mb ), который передается A. Мы рассматриваем c в качестве анализируемого шифртекста. 3. A выводит бит b'. 4. Результатом эксперимента является 1, если b'=b, иначе 0. Пишем P = 1 если результатом является 1, тогда мы говорим, что A добился успеха. Как было отмечено ранее, обычно A достигает успеха с вероятностью 1/2, выводя случайную догадку. Для подтверждения совершенной неразличимости требуется, чтобы ни один A не сумел справиться лучше. ОПРЕДЕЛЕНИЕ 2.5 Система шифрования Π = (Gen, Enc, Dec) с пространством сообщения M является совершенно неразличимой, если для каждого A верно: Следующая лемма утверждает, что Определение 2.5 тождественно Определе- нию 2.3. Доказать лемму требуется в Упражнении 2.5. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|