46
заданный условием 2, для которого верно Enck (
m) =
c. Тогда ,
Pr[C = c | M = m] = Pr[K = k] = 1/|K| ,
где конечное равенство верно по условию 1. Таким образом ,
Это верно для любого распределения по M.
Таким образом, для любого рас-
пределения по
M, любого
m ∈
M при Pr[
M = m] ƒ= 0 и любого
c ∈
C мы имеем:
и система является абсолютно криптографически стойкой.
А теперь докажем обратную теорему и допустим, что система шифрования яв-
ляется абсолютно стойкой . Покажем, что условия 1 и 2 верны. Зафиксируем про-
извольное
c ∈
C. Должно существовать некоторое сообщение m*, для которого
[EncK (m*) = c] ƒ= 0. Лемма 2.4 тогда подразумевает, что Pr[EncK (m) = c] ƒ= 0
для каждого
m ∈
M. Иными словами, если мы допустим, что M = {m1, m2, . . .},
тогда для каждого
mi ∈
M мы имеем непустое множество ключей Ki ∈ K такое,
что Enck (mi) = c тогда и только тогда, когда k ∈ Ki. Более того, когда i ƒ= j, тогда
Ki и Kj не должны пересекаться, иначе утверждение не верно. Поскольку |K| =
|M| , мы видим, что каждое Ki содержит только один ключ ki, как того и требует
условие 2. Теперь лемма 2.4
показывает, что для любого mi, mj ∈ M мы
имеем
Pr[K = ki] = Pr[EncK (mi) = c] = Pr[EncK (mj ) = c] = Pr[K = kj ].
Поскольку это верно для всех 1 ≤ i, j≤|M| = |K|, и ki ƒ= kj для i ƒ= j, следователь-
но,
каждый ключ, выбран с вероятностью 1/|K|, как того и требует условие 1.
Теорема Шеннона полезна для принятия решения о абсолютной криптогра-
фической стойкости заданной системы. Условие 1 легко проверяется, а условие
2 может быть подтверждено (или опровергнуто) без необходимости вычислять
все вероятности (по сравнению с непосредственной работой по определению
2.3). Например, совершенная стойкость шифра Вернама обычно доказывается с
помощью теоремы Шеннона. Однако обращаем ваше внимание на то, что тео-
рема
применяется, когда |M| = |K| = |C|.
Достарыңызбен бөлісу: