Имитостойкие совершенные шифры

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

где 

Обозначим эту вероятность через  
Шансы на успех в попытке имитации для противника, использующего оптимальную стратегию, определяются величиной 

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

где

Наибольшие шансы на успех для противника определяются вероятностью

Усредняя эту вероятность по всевозможным  сообщениям , полагаем по определению

Введем обозначения  для основных параметров шифра 

Теорема 2.3.1. Для любого шифра  справедливо неравенство 

                                                 			            (2.3.1)

Равенство в (2.3.1) имеет место тогда и только тогда, когда для любого  выполняется соотношение

Доказательство. Справедливы следующие равенства: 

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

(равная ) содержит  слагаемых, поэтому максимальное слагаемое не может быть меньше  откуда следует неравенство (2.3.1). Ясно также, что равенство  выполняется лишь в случае, если  для любого 

Теорема 2.3.2. Для любого шифра  справедливо неравенство
                                              			           (2.3.2)  

Равенство в (2.3.2) имеет место тогда и только тогда, когда для любых  выполняется соотношение

                   		        (2.3.3)

Доказательство. Из цепочки равенств

следует, что для любого  имеет место равенство

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

                          			                (2.3.5)
и

откуда мы получаем (2.3.2). 
Пусть  Если для некоторого  

то, в силу (2.3.5), выполнялись бы соотношения

вопреки условию. Тем самым, 

для любого  и поэтому 

                              		           (2.3.6)

для любых  
Если для некоторых  выполнялось бы строгое неравенство

то, в силу (2.3.6), это привело бы к неравенству

вопреки (2.3.4). Таким образом, 

при любых  что и требуется.
Представляют интерес совершенные шифры с минимальным числом ключей, для которых вероятности  минимальны. Имеет место следующий результат ([Sti88]), для формулировки которого нам понадобится определить еще одно понятие.

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

Теорема 2.3.4. Если для шифра  выполняется равенство  то 

                                          			             (2.3.7)

Равенство в (2.3.7) имеет место тогда и только тогда, когда строки матрицы зашифрования, рассматриваемые как подмножества элементов из  образуют -схему. Если при этом  то распределения  и    равномерные. 
Доказательство. Из условия и теоремы 2.3.2 следует, что выполняется равенство (2.3.3), откуда  для любых шифртекстов 
Очевидно, что для любых различных упорядоченных пар открытых текстов  верно соотношение

где 

Тогда, с одной стороны,

С другой стороны, поскольку 

для любых различных пар 

Таким образом,  откуда следует (2.3.7). 
Рассмотрим семейство  множеств шифртекстов, содержащихся в строках матрицы зашифрования. Каждое множество этого семейства имеет мощность  Число множеств семейства  содержащих выбранные шифртексты  и  равно  Поэтому равенство 

возможно в том и только том случае, когда для любых  и   Это равносильно тому, что пара  является -схемой.
Установим теперь равномерность распределений  и  Так как  то, согласно (2.3.3), для любых  ,

 (2.3.8)

Как отмечено выше, 

Поэтому если  то из (2.3.8) следует, что

Это означает, что в сумме 

все слагаемые одинаковы. Выделяя одно из них, получаем равенство

из которого 

                              			            (2.3.9)

Величина  есть число блоков построенной -схемы, содержащих . Известно ([Хол70]), что это число не зависит от  и равно 

Отсюда и из (2.3.9) получаем в случае, когда  формулу

          		  (2.3.10)

Зафиксируем  и воспользуемся условием  Согласно теореме 2.3.1 и равенству (2.3.10),

 			       (2.3.11)

В этой цепочке равенств мы воспользовались тем, что 

 и 

Переход от одной двойной суммы к другой объясняется тем, что в строках матрицы зашифрования, отвечающих ключам из  должен встретиться любой элемент  Последнее обстоятельство опять-таки следует из того, что 
Из соотношения (2.3.11) находим  Учитывая, что  выбиралось произвольно, и, подставляя значение  в (2.3.11), получаем для любого 

Наконец, с учетом (2.3.9), для любого 

Теорема 2.3.5. Если существует -схема, то существует и шифр , для которого

и распределения    равномерные. 
Доказательство. Пусть пара  является -схемой. Пусть   произвольное множество из  элементов. Каждому множеству  семейства  поставим в соответствие отображение 

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

.

По теореме 2.3.1 получаем равенство 
В -схеме любая пара  содержится лишь в одном блоке, поэтому  Отсюда получаем:

.

По теореме 2.3.2 

Теорема 2.3.6. Совершенный шифр  обладающий параметрами 
 ,

существует тогда и только тогда, когда выполняется соотношение
                        			                  (2.3.12)  

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

          			        (2.3.13)

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

и поэтому 

Величина  как мы знаем, равна числу блоков схемы, содержащих элемент  причем 

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

откуда следует (2.3.12).
Достаточность.  Пусть имеется -схема  и  выполняется  соотношение (2.3.12). Тогда (по теореме 2.3.6) существует шифр  с равномерными распределениями  имеющий следующие параметры

 , 

Для этого шифра блоки схемы образуют множества элементов строк матрицы зашифрования. Из условия (2.3.12), для некоторого натурального числа  выполняются равенства  и 

Покажем, что элементы в блоках можно упорядочить таким образом, чтобы в каждом столбце получившейся матрицы зашифрования любой элемент  встречался бы ровно  раз. Для этого заметим, что  Это значит, что  должен встретиться в  строках матрицы. Упорядочим некоторым образом элементы из  и разместим их в строках матрицы зашифрования с помощью следующей индуктивной процедуры. 
Возьмем любой элемент  входящий в первый блок, и поместим его в начало первой строки матрицы. Затем находим следующий блок, содержащий  и также помещаем этот элемент в начало соответствующей строки матрицы. Так мы поступим  раз. Затем следующие  вхождений  располагаем на вторые позиции соответствующих строк матрицы и т.д. В результате этой процедуры в каждом столбце матрицы  будет встречаться ровно  раз. После расстановки  остается  незанятых мест в каждом столбце. 
Далее берем элемент  Располагаем  из имеющихся вхождений  в начала строк и т.д. Это возможно, так как имеется  вхождений  в блоки, не содержащие  (есть лишь один блок, содержащий  и  одновременно). 
В результате мы построим матрицу зашифрования шифра  с нужными значениями параметров и равномерными распределениями  Кроме того, для любых  и  справедливы равенства

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

Теорема 2.3.7. Если для шифра  выполняется равенство  и  то 

Доказательство. Введем в рассмотрение матрицы  размеров  с неотрицательными элементами, строки которых занумерованы элементами  а столбцы  элементами  Пусть 

где 

Пусть  Поскольку 

то достаточно показать, что 
Имеем:

Согласно теореме 2.3.2,

По той же теореме для любого 

                                      (2.3.14)

Умножив строку матрицы  с номером  на величину, обратную к (1), получим матрицу  эквивалентную 

Поскольку определитель  отличен от нуля, то  Теорема доказана.

Шифр , удовлетворяющий условиям

называется экстремальным. В [Re96] получен результат о совершенных экстремальных шифрах. Приведем его без доказательства.

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

В качестве следствия этого утверждения в [Re96] приводится также следующая

Теорема 2.3.9. Для любого числа  являющегося степенью простого числа, существует совершенный экстремальный шифр  с параметрами