Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ДОКАЗАТЕЛЬСТВО
| ТЕОРЕМА 2.11 (Теорема Шеннона) Пусть (Gen, Enc, Dec) - это система
шифрования с пространством сообщения M, для которого |M| = |K| = |C|. Си- стема шифрования является совершенно криптографически стойкой тогда и только тогда, когда: 1.Каждый ключ k∈K выбран алгоритмом Gen с (равной) вероятностью 1/|K|. 2. Для каждого m ∈ M и каждого c ∈ C существует такой уникальный ключ k ∈ 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 ∈ 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|. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|