Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| ТЕОРЕМА 2.9 Система шифрования Вернама обладает абсолютной крип-
тографической стойкостью . ДОКАЗАТЕЛЬСТВО Сначала вычислим Pr[C = c | M = mr] для произволь- ных c ∈ 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 ∈ C, мы имеем: где сумма превышает mr ∈ M при Pr[M = mr] ƒ= 0 . Из теоремы Байеса имеем: Мы приходим к выводу, что шифр Вернама обладает абсолютной криптогра- фической стойкостью. В середине XX века разведывательное управления некоторых стран исполь- зовали шифр Вернама для шифрования особо важных сообщений. Вероятно, 43 наиболее известным применением шифра Вернама является защищенная с его помощью «горячая линия» между Вашингтоном и Москвой времен «холодной войны», когда правительства США и СССР обменивались невероятно длинны- ми ключами, перевозимыми надежными курьерами в портфелях, полных до- кументов с записанными в них случайными символами. Несмотря на вышесказанное, шифр Вернама используется редко из-за количества его недостатков. Самым существенным его недостатком является то, что длина ключа должна совпадать с длиной сообщения.² Таким образом ограничивается эффектив- ность системы при пересылке очень длинных сообщений (сложно безопасно пере- дать и хранить очень длинный ключ) и создает определенные трудности, когда сторо- ны не могут заранее предсказать (верхнюю границу), какой длины будет сообщение. Кроме того, шифр Вернама, как следует из его другого названия (одноразо- вый блокнот), безопасен, только когда используется один раз (с одним клю- чом). И хотя мы еще не дали определение криптографической стойкости при шифровании нескольких сообщений, легко заметить, что шифрование более чем одного сообщения одним ключом приводит к большой утечке информации. В частности, скажем , два сообщения m, mr зашифрованы с использованием од- ного ключа k. Противник, получивший c = m⊕ k и cr = mr⊕ k, может вычислить c ⊕ cr = (m ⊕ k) ⊕ (mr ⊕ k) = m⊕ mr и таким образом узнает «исключающее ИЛИ» двух сообщений или, что равно- значно, различия между двумя сообщениями. Хотя это может показаться не очень существенным, но этого достаточно, чтобы исключить любую возмож- ность считать систему шифрования двух сообщений одним и тем же ключом совершенно криптографически надежной. Более того, если сообщения соответ- ствуют тексту на естественном языке, то получив «исключающее ИЛИ» двух достаточно длинных сообщений, можно провести частотный анализ (сложнее, чем описанный в предыдущей главе) и восстановить сами сообщения. Интерес- ным историческим примером для нас служит проект «Венона» (VENONA), в ходе которого разведка США и Соединенного Королевства сумела расшифро- вать шифровки Советского Союза, по ошибке зашифровываемые повторяющи- мися ключами шифра Вернама на протяжении нескольких десятилетий. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|