Введение в современную криптографию



Pdf көрінісі
бет56/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   52   53   54   55   56   57   58   59   ...   249
Криптография Катц

Дистинктор 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, в которой ут-
верждается, что любая совершенно криптостойкая система шифрования должна 
использовать ключ по крайней мере такой же длины, что и сообщение.


Достарыңызбен бөлісу:
1   ...   52   53   54   55   56   57   58   59   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет