Шифры, совершенные по К.Шеннону

В данном параграфе под шифром мы будем понимать модель шифра замены с ограниченным или с неограниченным ключом.
Введем понятие совершенного шифра. Для этого нам потребуются условные вероятности 

  и  

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

Для шифра с ограниченным ключом вероятность  вычисляется по формуле

                                  (2.2.1)

если  и полагается равной нулю, если  где

а  определяется формулой (2.1.13). При этом распределение вероятностей  определяется через априорное распределение  на множестве ключей шифра по формуле (2.1.14).
Для шифра с неограниченным ключом соответствующая вероятность  вычисляется по формуле

              	 (2.2.1)

если  и полагается равной нулю, если  где

а   априорное распределение вероятностей на 
Вероятность  вычисляется стандартным образом:

     	  (2.2.2)

Определение 2.2.1. Шифр называется совершенным, если для любых  и любого натурального числа  выполняется равенство 
                      .             		     (2.2.3)

Часто бывает удобнее пользоваться эквивалентным определением совершенного шифра, которое состоит в условии

                                   		      (2.2.4)

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

Утверждение 2.2.2. Если шифр является совершенным, то для любых  и любого натурального числа  выполняется неравенство  

            		                 (2.2.5)

Доказательство. Предположим противное: пусть  при некоторых   Тогда, согласно (2.2.1) (или (2.2.1)), мы бы имели равенство

а согласно (2.2.2), и равенство 

Из (2.2.3) следует, что вероятность  также оказывается равной нулю, вопреки условию (2.1.9). 

Утверждение 2.2.3. Шифр с ограниченным ключом не является совершенным.

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

что невозможно для любого  поскольку 

где    константа, а 

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

Утверждение 2.2.4. Шифр  с неограниченным ключом является совершенным шифром тогда и только тогда, когда его -й опорный шифр  является совершенным шифром при любом 

Это утверждение позволяет нам при изучении свойств совершенных шифров рассматривать лишь их опорные шифры. В связи с этим далее мы будем понимать под шифром совокупность
,                      (2.2.6)

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

при этом    а также множеств   правил зашифрования  и   правил расшифрования  для каждого  для которых выполняются соотношения 

при любых  и 

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

                           		    (2.2.7)

Заметим, что из общих соображений следует равенство 

которое полезно проверить и непосредственно. Для этого рассмотрим отображение  определенное условием  или, иначе,  для любого  Тогда, поскольку 

Условная вероятность  вычисляется по формуле
    		    (2.2.8)
где

Далее, с целью упрощения записи, нижние индексы в обозначениях

  ,  

будем опускать, и записывать их в виде 

, 

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

Утверждение 2.2.5. Если шифр   совершенный, то справедливы неравенства

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

               		        (2.2.10)

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

Теорема 2.2.6 (К.Шеннона). Пусть   шифр, для которого  Тогда    совершенный шифр тогда и только тогда, когда выполняются два условия:
(i) 	 для любых 
(ii) 	Распределение   равномерно, то есть  для любого ключа 
Доказательство. Пусть шифр   совершенный. Тогда, согласно (2.2.10),

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

        			  (2.2.11)

Так как   совершенный шифр, то   Отсюда и из (2.2.11) получаем равенство  для любого  которое доказывает необходимость условия (ii).
Пусть условия (i) и (ii) выполнены. Тогда, пользуясь для фиксированного элемента  введенной выше нумерацией ключей, имеем, на основании (2.2.7), цепочку равенств:

откуда

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

Матрица зашифрования

		…..		
		……		
…..	…….	…….	……..	
		……		

Поэтому в случае, когда  совершенными являются шифры табличного гаммирования (см. 2.2.7) со случайной равновероятной гаммой, и только они. 
Отметим, что число  латинских квадратов произвольного порядка  до сих пор неизвестно. Приведем некоторые сведения об этом числе ([Рио63]). Если   число латинских квадратов, в которых элементы первой строки и первого столбца записаны в естественном порядке, то 

Ряд известных значений  сведем в таблицу:

n	2	3	4	5	6	7	
ln	1	1	4	56	9408	16942080	

Укажем, например, все латинские квадраты размера 44 (с упорядоченной первой строкой):

1	2	3	4		1	2	3	4	
2	3	4	1		2	1	4	3	
3	4	1	2		3	4	1	2	
4	1	2	3		4	3	2	1	

1	2	3	4		1	2	3	4	
2	1	4	3		2	4	1	3	
3	4	2	1		3	1	4	2	
4	3	1	2		4	3	2	1	

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

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

                                                 		                (2.2.12)

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

                                              		      (2.2.13)

Отметим, что определение совершенного шифра было рассмотрено К.Шенноном применительно к фиксированному распределению  отвечающему частотным характеристикам реального языка. Как нетрудно видеть, утверждение теоремы 2.2.6 остается справедливым для любого распределения  В связи с этим в некоторых работах по криптографии (например, [Mas87]) вводят следующее определение.

Определение 2.2.8. Шифр  называется  сильно совершенным, если он остается совершенным для любого распределения 

Нам понадобится еще одно определение.

Определение 2.2.9. Транзитивный шифр  удовлетворяющий условию  называется минимальным шифром. 

Предыдущее замечание свидетельствует о том, что в теореме 2.2.6 слова “совершенный шифр” можно заменить словами “сильно совершенный шифр”. Таким образом, теорема 2.2.6 дает описание минимальных сильно совершенных шифров. Однако, как мы убедимся далее (теорема 4.2.11), определение 2.2.8 излишне, так как совершенный шифр является также и сильно совершенным. 
Еще одно замечание связано с тем, что в матрице зашифрования переменные  и  можно заменить друг на друга. После такой замены будет рассматриваться шифр с транспонированной матрицей зашифрования (которая остается латинским квадратом). Кроме того, из условий теоремы 2.2.6 следует, что и переменные  и  также взаимозаменяемы. Это свойство наглядно проявляется на примере шифра Вернама, определяемого правилом зашифрования (2.2.13) при  Таким образом, в теореме Шеннона все переменные взаимозаменяемы, то есть каждое из множеств  может служить как множеством открытых текстов, так и множеством ключей или множеством шифрованных текстов сильно совершенного шифра. 
Подчеркнем также, что не только указанные шифры являются совершенными по Шеннону. В качестве примера можно указать следующий неэндоморфный шифр с неравновероятными ключами, являющийся сильно совершенным. 

Пример 2.2.10 

Матрица зашифрования имеет следующий вид:
 
	x1	x2	
k1	1	2	
k2	1	3	
k3	2	1	
k4	2	3	
k5	3	1	
k6	3	2	

Вероятности ключей: