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


Ограничения абсолютной стойкости



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

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


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




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

    Басты бет