Введение в современную криптографию
Ограничения абсолютной стойкости
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ТЕОРЕМА 2.10
- ДОКАЗАТЕЛЬСТВО
| 2.3 Ограничения абсолютной стойкости
Предыдущий раздел мы завершили тем, что отметили некоторые недостатки си- стемы шифрования Вернама. Здесь же мы покажем, что эти недостатки не являются особенностями той системы шифрования, а, напротив, являются неотъемлемыми ограничениями абсолютной стойкости. Более того, мы докажем, что длина про- странства ключа любой абсолютно стойкой системы шифрования должна по край- ней мере совпадать с длиной пространства сообщения. Если все ключи имеют одну 44 длину, а пространство сообщения состоит из всех строк некоторой фиксированной длины, это подразумевает, что ключ имеет по крайней мере такую же длину, что и со- общение. В частности, длина ключа шифра Вернама является оптимальной. (Другое ограничение, а именно однократное использование одного ключа, также является не- отъемлемым требованием совершенной секретности. См. Упражнение 2.13.) ТЕОРЕМА 2.10 Если (Gen, Enc, Dec) является схемой абсолютной крипто- графической стойкостью с пространством сообщения M и пространством ключа K, тогда |K| ≥ |M|. ДОКАЗАТЕЛЬСТВО Покажем, что если |K| < |M|, тогда система не может быть совершенно криптографически надежной. Допустим , |K| < |M|. Рассмо- трим равномерное распределение по M, пусть c ⊕ C - это шифртекст, встречаю- щийся с ненулевой вероятностью. Пусть M(c) - это множество всех возможных сообщений, являющихся возможной расшифровкой c, из чего следует: что def M(c) = {m | m = Deck (c) для некоторого k ∈ K}. Очевидно, |M(c)| ≤ |K|. (Напомним , что мы можем допустить, что алгоритм Dec является детерминированным.) Если |K| < |M|, существует некоторое mr ∈ M такое, что mr ƒ∉ M(c). Но тогда Pr[M = mr | C = c] ≠ 0 ƒ= Pr[M = mr], из чего следует, что система не является абсолютно криптографически стойкой. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|