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



Pdf көрінісі
бет30/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   26   27   28   29   30   31   32   33   ...   249
Криптография Катц

ТЕОРЕМА 2.11 (Теорема Шеннона) Пусть (Gen, Enc, Dec) - это система 
шифрования с пространством сообщения M, для которого |M| = |K| = |C|. Си-
стема шифрования является совершенно криптографически стойкой тогда и 
только тогда, когда:
1.Каждый ключ kK выбран алгоритмом Gen с (равной) вероятностью 1/|K|.
2. Для каждого m  M и каждого c  C существует такой уникальный ключ 
 K, что Enck (m) выводит c.
ДОКАЗАТЕЛЬСТВО На уровне интуиции доказательство выглядит следующим 
образом: Для понимания того, что заданные условия подразумевают абсолютную
криптографическую стойкость, обратите внимание на то, что условие 2 означает, что 
любой шифртекст c может быть результатом шифрования любого возможного от-
крытого текста m, поскольку существует некоторый ключ k, преобразующий m в c
Поскольку существует такой уникальный ключ, а каждый ключ выбирается с равной 
вероятностью, то совершенная криптографическая стойкость доказывается как и для 
шифра Вернама. И наоборот, совершенная криптографическая стойкость автомати-
чески подразумевает, что для каждого m и c существует по крайней мере один ключ, 
преобразующий m в c. Более того, из |M| = |K| = |C| вытекает вывод, что для каждого m 
и c существует только один такой ключ. Исходя из этого, каждый ключ должен быть 
выбран с равной вероятностью, иначе абсолютная криптографическая стойкость не 
будет достигнута. Формально же доказательство выглядит так:
Для удобства допустим, что алгоритм Enc детерминирован. (Здесь можно го-
ворить об этом без ущерба для общности.) Сначала докажем, что если система 
шифрования удовлетворяет условиям 1 и 2, то она является абсолютно крип-
тографически надежной. В сущности, доказательство такое же, как и доказа-
тельство абсолютной стойкости шифра Вернама, поэтому мы будем довольно 
кратки. Зафиксируем произвольные c ∈ C и m ∈ M. Пусть k - уникальный ключ, 


46
заданный условием 2, для которого верно Enck (m) = c. Тогда ,
Pr[C = c | M = m] = Pr[K = k] = 1/|K| ,
где конечное равенство верно по условию 1. Таким образом ,
Это верно для любого распределения по M. Таким образом, для любого рас-
пределения по M, любого  M при Pr[M = m] ƒ= 0 и любого  C мы имеем:
и система является абсолютно криптографически стойкой.
А теперь докажем обратную теорему и допустим, что система шифрования яв-
ляется абсолютно стойкой . Покажем, что условия 1 и 2 верны. Зафиксируем про-
извольное  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|.


Достарыңызбен бөлісу:
1   ...   26   27   28   29   30   31   32   33   ...   249




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

    Басты бет