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],
из чего следует, что система не является абсолютно криптографически стойкой.
Достарыңызбен бөлісу: