Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ПРЕДПОЛОЖЕНИЕ 3.20
- ДОКАЗАТЕЛЬСТВО
| ОПРЕДЕЛЕНИЕ 3.19 Система шифрования с закрытым ключом Π = (Gen,
Enc, Dec) обладает неразличимым многократным шифрованием при наличии под- слушивающей стороны, если для всех вероятностных полиномиально-временных противников A существует такая пренебрежимо малая функция negl, что где вероятность вычисляется по случайности, используемой A, и случайности, используемой в эксперименте. Любая система шифрования, обладающая неразличимостью многократного шифрования при наличии подслушивающей стороны, очевидно, также соот- ветствует определению 3.8, поскольку эксперимент PrivKeav соответствует особому случаю PrivKmult, где противник выводит два списка, в каждом из ко- торых содержится только одно сообщение. Фактически, наше новое определе- ние строго сильнее определения 3.8, как это показано далее. ПРЕДПОЛОЖЕНИЕ 3.20 Существует система шифрования с закрытым клю- чом, обладающая неразличимостью при наличии подслушивающей стороны, но раз- личимая при многократном шифровании при наличии подслушивающей стороны. ДОКАЗАТЕЛЬСТВО Нам не нужно долго искать пример системы шифрования, соответствующей предположению. Шифр Вернама совершенно надежен, а также об- ладает неразличимым шифрованием при наличии подслушивающей стороны. Мы покажем, что он не надежен в смысле определения 3.19. (Мы уже обсудили эту атаку в главе 2. Здесь же мы просто проанализируем атаку с учетом определения 3.19.) Точнее, рассмотрим следующего противника A, атакующего систему (в смыс- ле, определенном экспериментом PrivKmult): A выводит M˙ 0 = (0A, 0A) и M1 = (0A, 1A ). (Первый содержит два одинаковых открытых текста, второй два разных сообщения.) Пусть C˙= (c1, c2) - это список шифртекстов, полученных A. Если c1 = c2, тогда A выводит br = 0; иначе, A выводит br = 1. Теперь мы анализи- руем вероятность того, что br = b. Важно то, что шифр Вернама детерминирован, таким образом, шифрование одного и того же сообщения (с помощью одного и того же ключа) приводит к появлению одного и того же шифртекста. Итак, если b = 0, тогда c1 = c2, и A в этом случае выводит 0. С другой стороны, если b = 1, тогда каждый раз зашифровывается другое сообщение; следовательно, c1 ƒ= c2, и A вы- водит 1. Делаем вывод, что A правильно выводит br = b с вероятностью 1, таким образом, система шифрования не является надежной с учетом определения 3.19. _____________________________________________________________ 4 .В разделе 3.6.1 мы увидим, что если система шифрования отслеживает состояние, тогда возмож- но надежно зашифровать несколько сообщений даже в случае детерминированного шифрования. |