ЛЕММА 2.6 Система шифрования Π является совершенной тогда и только  тогда, когда является совершенно неразличимой. Пример 2.7

41
= 1/2 • Pr[A выводит 0 | b = 0] + 1/2 • Pr[A выводит 1 | b = 1], (2.2)
где b - единообразный бит, определяющий, какое сообщение будет зашифро-
вано. A выводит 0 тогда и только тогда, когда два символа шифртекста c = c1c2 
равны. Когда b = 0 (значит зашифровано m0 = aa), тогда c1 = c2, если (1) выбран 
ключ периода 1 или (2) выбран ключ периода 2, и оба символа ключа равны.
Первое происходит с вероятностью 1/2, а последнее происходит с вероятно-
стью 1/2 • 1/26. Таким образом,
Pr[A выводит 0 | b = 0] = 1/2 + 1/2 • 1/26 ≈ 0,52.
Если b = 1, тогда c1 = c2 только если выбран ключ периода 2 и первый символ 
ключа на единицу больше второго символа ключа, что происходит с вероятно-
стью 1/2 • 1/26. Таким образом,
Pr[A выводит 1 | b = 1] = 1 − Pr[A выводит 0 | b = 1] = 1 − 1/2 • 1/26 ≈ 0,98.
Подставляем в уравнение (2.2) и получаем:
и система не является совершенно неразличимой. 
♦
2.2 Шифр Вернама 
В 1917 году Гилберт Вернам запатентовал абсолютную криптографическую 
стойкость, названную шифром Вернама (или одноразовым блокнотом). Ког-
да Вернам предложил свою систему, доказательств ее абсолютной стойкости 
не существовало, впрочем, как и самого понятия абсолютной стойкости. Тем 
не менее, примерно 25 лет спустя Клод Шеннон ввел определение абсолютной
стойкости и продемонстрировал, что шифр Вернама достигает такого уровня 
безопасности.

42
Схема шифрования Вернама.
Для описания системы пусть a ⊕ b означает побитовое исключающее ИЛИ
(XOR) двух двоичных последовательностей a и b (т.е ., если a = a1 • • • aA и b 
= b1 • • • bA являются строками A-битов, тогда a ⊕ b является строкой A-битов, 
заданных a1 ⊕ b1 • • • aA⊕ bA). Кл юч в системе шифрования Вернама - это 
равномерная строка той же длины, что и сообщение , а шифртекст вычисляет-
ся путем простого объединения ключа и сообщения операцией исключающего 
ИЛИ. Формальное определение дано в Конструкции 2.8. Перед обсуждением 
стойкости системы мы проверим ее корректность: для каждого ключа k и каж-
дого сообщения m верно, что Deck (Enck (m)) = k⊕ k⊕ m = m, таким образом, 
шифр Вернама представляет собой надежную систему шифрования.
Опираясь на лемму 2.4 и тот факт, что шифртекст равномерно распределен 
вне зависимости от зашифрованного сообщения, можно с легкостью доказать 
абсолютную стойкость шифра Вернама. Приведем доказательство, основан-
ное непосредственно на первоначальном определении.

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: