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



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

ТЕОРЕМА 2.9 Система шифрования Вернама обладает абсолютной крип-
тографической стойкостью .
ДОКАЗАТЕЛЬСТВО  Сначала вычислим Pr[C = c | M = mr] для произволь-
ных  C и mr  M. Для шифра Вернама
Pr[C=c|M = mr] =Pr[EncK(mr)=c]= r[mr  K = c] = Pr[K = mr  c] = 2−A,
где конечное равенство верно, поскольку ключ K является равномерно распре-
деленной строкой A-битов. Зафиксируем любое распределение по M. Для всех 
 C, мы имеем:
где сумма превышает mr  M при Pr[M = mr] ƒ= 0 . Из теоремы Байеса имеем:
Мы приходим к выводу, что шифр Вернама обладает абсолютной криптогра-
фической стойкостью.
В середине XX века разведывательное управления некоторых стран исполь-
зовали шифр Вернама для шифрования особо важных сообщений. Вероятно, 


43
наиболее известным применением шифра Вернама является защищенная с его 
помощью «горячая линия» между Вашингтоном и Москвой времен «холодной 
войны», когда правительства США и СССР обменивались невероятно длинны-
ми ключами, перевозимыми надежными курьерами в портфелях, полных до-
кументов с записанными в них случайными символами.
Несмотря на вышесказанное, шифр Вернама используется редко из-за количества 
его недостатков. Самым существенным его недостатком является то, что длина ключа 
должна совпадать с длиной сообщения.² Таким образом ограничивается эффектив-
ность системы при пересылке очень длинных сообщений (сложно безопасно пере-
дать и хранить очень длинный ключ) и создает определенные трудности, когда сторо-
ны не могут заранее предсказать (верхнюю границу), какой длины будет сообщение.
Кроме того, шифр Вернама, как следует из его другого названия (одноразо-
вый блокнот), безопасен, только когда используется один раз (с одним клю-
чом). И хотя мы еще не дали определение криптографической стойкости при 
шифровании нескольких сообщений, легко заметить, что шифрование более 
чем одного сообщения одним ключом приводит к большой утечке информации. 
В частности, скажем , два сообщения m, mr зашифрованы с использованием од-
ного ключа k. Противник, получивший c = m k и cr = mr k, может вычислить
 cr = (m  k)  (mr  k) = m mr 
и таким образом узнает «исключающее ИЛИ» двух сообщений или, что равно-
значно, различия между двумя сообщениями. Хотя это может показаться не 
очень существенным, но этого достаточно, чтобы исключить любую возмож-
ность считать систему шифрования двух сообщений одним и тем же ключом 
совершенно криптографически надежной. Более того, если сообщения соответ-
ствуют тексту на естественном языке, то получив «исключающее ИЛИ» двух 
достаточно длинных сообщений, можно провести частотный анализ (сложнее, 
чем описанный в предыдущей главе) и восстановить сами сообщения. Интерес-
ным историческим примером для нас служит проект «Венона» (VENONA), в 
ходе которого разведка США и Соединенного Королевства сумела расшифро-
вать шифровки Советского Союза, по ошибке зашифровываемые повторяющи-
мися ключами шифра Вернама на протяжении нескольких десятилетий.


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




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

    Басты бет