Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Дистинктор D:
На входе D задана строка w ∈ {0, 1}A(n). (Мы допускаем, что n может быть определено из A(n).) 1. Запустить A(1n), чтобы получить пару сообщений m0, m1∈{0, 1}A(n). 2. Выбрать единообразный бит b∈{0, 1}. Задать c := w⊕mb. 3. Передать c A и получить выходные данные br. Вывести 1, если br = b, и 0 в противном случае. Очевидно, что D работает в полиномиальном времени (предполагается, что A работает в полиномиальном времени). Прежде чем анализировать поведение D, мы определим измененную систему шифрования Π˜ = (G˜en, E˜nc, D˜ec), которая с точностью соответствует системе шифрования Вернама за исключение того, что мы теперь включаем параметр 80 безопасности, который определяет длину зашифрованного сообщения. Иными словами, G˜en(1n) выводит унифицированный ключ k длиной A(n), и шифрова- ние сообщения m∈ 2A(n) с использованием k∈{0, 1}A(n) является шифртекстом c := k⊕m. (Расшифрование может осуществляться как обычно, но для нас это сейчас не так важно.) Совершенная стойкость шифра Вернама подразумевает Чтобы проанализировать поведение D, проведем следующие основные на- блюдения: 1. Если w равномерно выбрана из {0, 1}A(n), тогда вид A, когда он работа- ет в качестве подпрограммы D, распределен идентично виду A в эксперимен- те . Это происходит из-за того, что когда A запускается в качестве подпрограммы D(w) в этом случае, A задается шифртекст c = w⊕mb, где w∈{0, 1}A(n) является однородной. Поскольку D выводит 1 точно тогда, когда A до- бивается успеха в своем подслушивающем эксперименте, вследствие этого мы имеем (см. уравнение (3.3)) (Индекс первой вероятности явно обозначает, что w выбирается равномерно из {0, 1}A(n).) 2. Если w, напротив, генерируется выбором однородного k∈{0, 1}n и после- дующим заданием w := tt(k), вид A, работающего в качестве подпрограммы D, распределяется идентично виду A в эксперименте . Это из-за того, что A, работающему в качестве подпрограммы D, теперь задан шифртекст c = w⊕mb, где w = tt(k) для однородного k∈{0, 1}n. Таким образом, Поскольку tt - псевдослучайный генератор (и D работает в полиномиальном времени), мы знаем, что существует такая пренебрежимо малая функция negl, что Используя уравнения (3.4) и (3.5), мы видим, что которая подразумевает Поскольку A явля- ется произвольным противником, это завершает доказательство того, что П об- ладает неразличимым шифрованием при наличии подслушивающей стороны. Легко запутаться в подробностях доказательства и задаваться вопросом, по- лучилось ли что-нибудь в сравнении с шифром Вернама, не стоит забывать, что 81 шифр Вернама также шифрует A-битные сообщения с помощью операции XOR по отношению к A-битным строкам! Смысл конструкции, конечно, заключается в том, что A-битные строки tt(k) могут быть значительно длиннее секретного ключа k. В частности, вышеупомянутая система позволяет зашифровать файл размером 1 Мб с помощью всего лишь 128-битного ключа. Полагаясь на вычислительную стойкость, мы таким образом обошли невозможность теоремы 2.10, в которой ут- верждается, что любая совершенно криптостойкая система шифрования должна использовать ключ по крайней мере такой же длины, что и сообщение. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|