Ссылки и дополнительная литература

47
запатентовавшему его Вернаму [172], однако, недавние исторические исследова-
ния [25] показали, что шифр был изобретен примерно на 35 лет раньше. Анализ 
шифра Вернама пришлось отложить до появления новаторской работы Шенно-
на [154], который ввел понятие абсолютной криптографической стойкости. В 
настоящей главе мы рассмотрели абсолютную криптографическую стойкость . 
Некоторые другие криптографические задачи могут также решаться с помощью 
«абсолютной» безопасности . Важнейшим примером может служить задача ау-
тентификации сообщения, целью которой является предотвратить (неопределяе-
мое) изменение противником сообщения, направленного одной стороной другой. 
Более подробно мы рассмотрим эту проблему в разделе 4.6 главы 4 в ходе об-
суждения «абсолютно криптографически стойких» аутентификаций сообщения.
Упражнения 
Докажите, что при переопределении пространства ключа мы можем допу-
стить, что алгоритм генерации ключей Gen выбирает ключ равномерно произ-
вольно из пространства ключей без изменения Pr[C = c | M = m] для любых m, c.
Подсказка: Определите, что пространство ключей - это множество всех воз-
можных случайных лент для случайного алгоритма Gen.
Докажите, что при переопределении пространства ключа мы можем допу-
стить, что алгоритм Enc является детерминированным без изменения Pr[C = c | 
M = m] для любых m, c.
Докажите или опровергните: Система шифрования с пространством сообще-
ния M является совершенно криптографически надежной тогда и только тогда, 
когда для каждого распределения вероятности по M и каждого c0, c1 ∈ C мы 
имеем Pr[C = c0] = Pr[C = c1].
Докажите утверждение, обратное лемме 2.4.
Докажите лемму 2.6.
Определите, является ли каждая из приведенных систем шифрования совер-
шенно криптографически надежной. Обоснуйте свой ответ в каждом из случаев.
(a) Пространство сообщения M={0, ..., 4}. Алгоритм Gen выбирает унифи-
цированный ключ из пространства ключей {0, . . . , 5}. Enck (m) выдает [k + m 
mod 5], а Deck (c) выдает [c − k mod 5].
(b) Пространство сообщения M = {m ∈ {0, 1}A | последний бит m равен 0}. 
Алгоритм Gen унифицированный ключ из {0, 1}A−1. Enck (m) выдает шифр-
текст m ⊕ (k''0), а Deck (c) выводит c ⊕ (k''0).
При использовании шифра Вернама с ключом k = 0A , мы имеем Enck (m) = k 
⊕
m = m и отправляется незашифрованное сообщение! В следствие этого было 
предложено изменить шифр Вернама, используя для шифрования k ƒ= 0A (т. е. 

48
заставить алгоритм Gen равномерно выбирать k из множества ненулевых ключей 
длиной A). Повлияло ли это на совершенную надежность системы? Объясните.
Пусть Π обозначает шифр Виженера, где пространство сообщения состоит из 
всех трехсимвольных строк (английский алфавит), а ключ сгенерирован путем 
равномерного выбора периода t из {1, 2, 3}, после чего допускалось, что ключ - 
это равномерная строка длиной t.
(a) Определите A следующим образом: A выводит m0 = aab и m1 = abb. После 
задания шифртекста c A выводит 0, если первый символ c совпадает со вторым 
символом c, иначе выводит 1. Вычислите Pr 
(b) Создайте и проанализируйте противника Ar, для которого Pr 
больше вашего ответа из части (a).
В данном упражнении мы рассматриваем разные условия, при которых шиф-
ры сдвига, моноалфавитной подстановки и шифр Виженера являются совер-
шенно криптографически надежными:
(a) Докажите, что если зашифровать один символ, тогда сдвиговый шифр яв-
ляется совершенно криптографически надежным.
(b) Каково же наибольшее значение пространства сообщения M, для которого 
моноалфавитный шифр подстановки обеспечит совершенную стойкость?
(c) Докажите, что шифр Виженера, использующий (фиксированный) период 
t, является абсолютно стойким при шифровании сообщения длиной t.
Согласуйте это с атаками, представленными в предыдущей главе.
Докажите, что система, удовлетворяющая определению 2.5, должна иметь |K| 
≥ |M| без использования леммы 2.4. В частности, пусть Π - это произвольная 
система шифрования с |K| < |M|. Представьте A, для которого Pr
Подсказка: Возможно, легче допустить, что A случайна .
Допустим, нам только требуется, чтобы система шифрования (Gen, Enc, Dec) 
с пространством сообщения M удовлетворяла следующему условию: Для всех 
m ∈ M, мы имеем Pr[DecK (EncK (m)) = m] ≥ 2−t. (Данная вероятность перено-
сится на выбор ключа таким же образом, как и любая произвольность, исполь-
зованная во время шифрования.) Покажите , что совершенная стойкость может 
быть достигнута при |K| < |M|, когда t ≥ 1. Докажите существование нижней 
границы размера K исходя из t.
Пусть ε ≥ 0 будет постоянным. Предположим, что система шифрования явля-
ется ε-абсолютно стойкой , если для каждого противника A верно:
(Сравните с определением 2.5) Покажите, что ε-абсолютная стойкость может 

49
быть достигнута при |K| < |M|, когда ε > 0. Докажите существование нижней 
границы размера K исходя из ε 
В данной задаче мы рассматриваем определения совершенной стойкости си-
стемы для шифрования двух сообщений с использованием одного ключа. Здесь 
мы рассматриваем распределение по парам сообщений из пространства сооб-
щения M. Пусть M1, M2 - произвольные переменные, определяющие первое и 
второе сообщение соответственно. (Подчеркиваем, что мы не допускаем того, 
что эти произвольные переменные независимы.) Генерируем (один) ключ k, от-
бираем пару сообщений (m1, m2) в соответствии с заданным распределением, 
после чего вычисляем шифртексты c1 ← Enck (m1) и c2 ← Enck (m2), что об-
уславливает распределение по парам шифртекстов, пусть C1, C2 – соответству-
ющие произвольные переменные.
(a) Скажем, система шифрования (Gen, Enc, Dec) является абсолютно стойкой
для двух сообщений, если для всех распределений по M × M все m1, m2 ∈ M и 
все шифртексты c1, c2 ∈ C при Pr[C1 = c1 ٨ C2 = c2] > 0:
Pr [M1 = m1 ٨ M2 = m2 | C1 = c1 ٨ C2 = c2] = Pr[M1 = m1 ٨ M2 = m2].
Докажите, что ни одна система шифрования не соответствует данному опре-
делению.

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

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