Понятие совершенного шифра для других криптоатак

Выше рассматривались условные вероятности   в случае, когда  Рассмотрим подобные величины для множеств  не обязательно имеющих одинаковые мощности. При этом будем рассматривать лишь случай, когда  исходя из естественного предположения о том, что все, что шифруется и передается по линии связи, перехватывается оппонентом.
Пусть   подмножества множества  и   вероятность выбора  из  при условии, что  Обозначим эту вероятность  Она вычисляется по формуле  

                                                       (5.1)
где 

и   множество всех подмножеств множества  
Пусть  причем  Тогда вероятность  того, что получено множество криптограмм    при условии, что на некотором ключе    шифровалось множество открытых текстов, содержащее  вычисляется согласно формуле полной вероятности:

                         (5.2)

где через  обозначена вероятность

Это так, поскольку при заданном подмножестве открытых текстов  получение множества криптограмм  возможно лишь при зашифровании на некотором ключе множества открытых текстов  той же мощности, что и   содержащего  В связи с этим вероятность  следует “взвесить” условной вероятностью 
Можно проверить, что 

В самом деле, в соответствии с (5.2) и (5.1)

где во внешней сумме  пробегает множество значений из 
Условная вероятность  определяется через вероятность  обычным образом. 
Теперь, следуя [Sti88], введем еще одно условие совершенной стойкости шифра.

Определение 5.1. Будем говорить, что шифр  удовлетворяет условию -стойкости (или является -стойким), если при любых  и  таких что  и   выполняется  равенство 

                                                     (5.3)
Буква   в названии условия (которое можно было назвать также совершенной -кратной стойкости по Стинсону) – это первая буква фамилии Stinson.
Ясно, что (5.3) равносильно равенству 

                                                                                       (5.4)

которым бывает удобнее пользоваться.
Непосредственно из введенных определений следует

Лемма 5.2. Если шифр  удовлетворяет условию -стойкости, то он удовлетворяет и условиям - и -стойкости для любого  из интервала 

Заметим, что условие -стойкости, вообще говоря, сильнее условия -стойкости. В самом деле, любой шифр  удовлетворяет условию -стойкости (где ). Это следует из того, что для любого 

При этом мы воспользовались упомянутым в § 4.1 равенством 
Вместе с тем, шифр  не обязан быть -стойким. Чтобы убедиться в этом, достаточно рассмотреть любой не совершенный (по Шеннону) шифр, который, тем самым, не является -стойким, и тем более  -стойким. 
Лемма 5.3. Шифр  удовлетворяет условию -стойкости тогда и только тогда, когда он удовлетворяет условию -стойкости для любого  

Доказательство. Необходимость условия была отмечена в лемме 5.2. Проверим достаточность. Пусть  причем  В соответствии с формулой (5.2), 

Это доказывает достаточность условия леммы. 
Следующее определение вводит условие стойкости шифра для упорядоченных наборов открытых и шифрованных текстов. Пусть 

Определение 5.4. Будем говорить, что шифр  удовлетворяет условию -стойкости, если при любых  выполняется равенство

                                                                                                (5.5)

Отметим, что буква  в этом определении  это первая буква слова Ordered (упорядоченный). 
Ясно, что вместо равенства (5.5) может быть использовано равенство  Очевидно также, что -стойкий шифр обязан обладать свойством транзитивности, согласно которому для любых   должен существовать элемент  такой, что  

Лемма 5.5. Если эндоморфный шифр  удовлетворяет условию -стойкости, то он удовлетворяет и условию -стойкости для любого 

Доказательство. Пусть  и   вектор, полученный добавлением к  дополнительной координаты  где   множество элементов, составляющих вектор  Пусть также   вектор из  полученный аналогичным образом из вектора  Введем обозначение

По условию  для любого  поэтому выполняется равенство 

Выберем произвольный элемент 

Непосредственно проверяется равенство множеств

причем, если  то 

Рассмотрим вероятность  Согласно (4.1.3),

Отсюда следует, что 

Пользуясь условием -стойкости, получаем:

где   любой вектор из 
Пусть  для любого  Тогда, пользуясь свойством транзитивности шифра, получаем равенства

Следовательно, для любых  элементов   выполняется равенство  что и требуется.
По-видимому, лемма 5.5 справедлива и без условия эндоморфности шифра.

Лемма 5.6. Если эндоморфный шифр  удовлетворяет условию -стойкости, то он удовлетворяет и условию -стойкости.
Доказательство. Согласно леммам 5.3 и 5.5, достаточно доказать, что условие -стойкости влечет условие -стойкости. 
Пусть  Рассмотрим вероятность  Непосредственно проверяется, что для любого вектора  такого, что  выполняется соотношение

причем 

если  В силу этого, если  то

что и требуется. Лемма доказана.
Отметим, что, вообще говоря, условие -стойкости сильнее условия -стойкости. Это вытекает из следующего примера.

Пример 5.7. Рассмотрим шифр , для которого

где  Пусть  для любого  
Покажем, что (независимо от распределения вероятностей на ) данный шифр удовлетворяет условию -стойкости, но не удовлетворяет условиям -стойкости и -стойкости. 

Для удобства рассмотрим матрицу зашифрования:

	x0	x1	x2	
e0	y0	y1	y2	
e1	y1	y2	y0	
e2	y2	y0	y1	

В определении 5.1 будем различать три случая: 

В случае 1) надо показать, что  Имеем:

Из условия следует, что найдется единственный элемент  связывающий  и :   Поэтому 

С другой стороны, 

что и требуется. 
Пусть в случае 2) 

Тогда 
Вероятность  вычислим по формуле 

где для любого  

Вычислим  Пусть, например,   Тогда 

поскольку 

Таким образом, 

Пусть в случае 3) 

Тогда 

Тем самым, условие -стойкости для данного шифра выполнено. Вместе с тем, условие -стойкости не выполняется. В самом деле, 

так как 

С другой стороны, 
Несложно проверить, что рассматриваемый шифр не удовлетворяет условию -стойкости.

Определения 4.2.1, 5.1 и 5.4 относились лишь к атакам на основе шифртекста, когда по  данным криптограммам требовалось получить информацию о передаваемых открытых сообщениях. Далее рассмотрим вопрос о совершенной стойкости шифра к атаке на основе известного открытого текста. 

По Мэсси ([God90]) суть такой атаки порядка  состоит в том, чтобы на основании  данных  пар открытых и шифрованных текстов, полученных на одном ключе, определить открытый текст еще одной криптограммы  полученной на том же ключе. Атака считается успешной, если найдется открытый текст  для которого апостериорная вероятность того, что он соответствует  отлична от его априорной вероятности. Такая постановка задачи возникает, например, при использовании блочного шифра в режиме простой замены.
Формализуем сказанное. Пусть   рассматриваемый шифр; 

 данные cовокупности открытых и соответствующих им шифрованных текстов, полученных на некотором одном (неизвестном) ключе;   еще одна данная криптограмма, полученная на том же ключе из некоторого (неизвестного) открытого текста  Пусть  Будем случайно выбирать  и  после чего случайно выбирать  Этот выбор определяет условные вероятности  и  исходя из формул 

где (по аналогии с (5.2)) вероятность  определяется формулой

Определение 5.8. Будем говорить, что шифр  удовлетворяет условию -стойкости (или является -стойким), если для любых указанных выше  и любого  выполняется равенство 

                                                                             (5.6)

Ясно, что равенство (5.6) равносильно равенству

                                                                               (5.6)

Легко видеть, что из условия -стойкости следует условие -стойкости для любого 
Лемма 5.9. Если шифр  удовлетворяет условию -стойкости, то он удовлетворяет и условию -стойкости.
Доказательство. Проверим для подходящих  справедливость равенства (5.6). Согласно условию,  Следовательно,

откуда следует (5.6).

Заметим, что обратное утверждение неверно. Чтобы убедиться в этом, достаточно рассмотреть следующий пример.

Пример 5.10. Пусть шифр  таков, что

причем 

Данный шифр удовлетворяет условиям - и - стойкости, но не удовлетворяет условию -стойкости.
Для проверки свойства -стойкости будем использовать те же обозначения и рассуждения, что и в примере 5.7. Матрица зашифрования имеет следующий вид:
	x0	x1	
e0	y0	y1	
e1	y1	y2	
e2	y2	y0	

В определении 5.1 рассмотрим три случая:    

1)	  2)   3)  

В случае 1) рассуждения те же, что и в примере 5.7. В случае 2) для любого 

Вместе с тем, 

Поэтому 
В случае 3):

Обратимся к проверке условия -стойкости. 
Имеет смысл рассматривать лишь строки  и  длины 2. По условию  и  таковы, что найдутся  и  для которых  Строкой  может быть либо  либо  Если  то  и  Тогда  может быть одной из трех строк:  Аналогично для  получается  и 

Имеем равенства: 

Аналогично можно убедиться в том, что равенство (5.6) выполняется и во всех других случаях.
Как и в примере 5.7, 

хотя  Тем самым, свойство -стойкости и в данном случае не выполняется. 
Подведем некоторые итоги.
Имеет место следующая иерархия различных понятий стойкости шифров к атакам, основанным на совокупности криптограмм, полученных на одном ключе:

Стрелки означают, что одно условие стойкости является следствием другого. Импликации 

  и  

доказаны лишь для эндоморфных шифров. По-видимому, они справедливы и без требования эндоморфности. Импликация  может не выполняться. Далее будут указаны дополнительные условия, при которых она имеет место.