Линейные блочные шифры

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

Следуя [Mas87], введем 

Определение 3.1. Шифр  назовем  линейным над  если 
 (),

и равенство

       			     (3.1)

выполняется для любых элементов  и любых  

Условие (3.1) означает, что  является линейным отображением  на  Нас будет интересовать возможность построения совершенных линейных шифров.

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

                                         			  (3.2)

Так как для линейного шифра  при любом  то 

и
            			    (3.3)

Из (3.2) и (3.3) получаем равенство 

Так как отображение  инъективно и  то при  выполняется неравенство  Следовательно,

Мы получили равенство 

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

Попытаемся построить линейный над  совершенный шифр, изменив в определении 3.1 условия  на условия

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

Так как векторы  линейно независимы в пространстве  матрица 

имеет ранг  и выполняется равенство  Транспонируя его, получаем равенство 

                                                         			           (3.4)

Если  то для минимального совершенного линейного над  шифра выполняются равенства 

Отсюда и из теоремы Шеннона получаем следующее утверждение.

Теорема 3.3.  Минимальный линейный над  шифр  является сильно совершенным тогда и только тогда, когда выполняются условия:
(i)	для любых  существует (и единственный) ключ  удовлетворяющий условию (3.4);
(ii)	распределение  равномерно.

Пример 3.4. Рассмотрим минимальный, линейный над  шифр  при  Пусть  и 

Векторы из  связаны следующими соотношениями:

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

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

Определение 3.5. Линейный шифр  назовем билинейным над  если

для некоторых  и выполняется равенство 

              			       (3.5)

для тех  при которых определены все выражения в данном равенстве.

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

где   -матрица ранга  причем такая, что для любых   выполняется равенство 

        			       (3.7)

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

и, согласно (3.7),

то есть 

Это означает, что каждая функция  линейна по всем своим переменным.

Пример 3.6. Рассмотрим билинейный над полем  шифр  с параметрами  Правило зашифрования для  определяется матрицей

Чтобы проверить корректность определения правила зашифрования, достаточно убедиться  в обратимости преобразования (3.6) для любого  Непосредственно вычисляем:

Каждая из этих матриц невырождена, что и требуется.

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

Конструкция 1
1) Пусть   начальный вектор линейной рекуррентной последовательности (ранга ) максимального периода над полем 
2) Пользуясь законом рекурсии, выразим каждый из следующих  знаков  ЛРП в виде линейных комбинаций переменных 
3) В качестве -й строки матрицы  возьмем вектор  каждая координата  которого записана в виде полученной на этапе 2) линейной комбинации.
 
Пример 3.7. Рассмотрим ЛРП, порожденную линейным регистром сдвига длины 2 над полем  (рис. 3):

                               

                                 k1    k2

Рис. 3

Пользуясь конструкцией 1, получим матрицу  

совпадающую с матрицей из примера 3.6.

Пример 3.8. Рассмотрим ЛПР, порожденную линейным регистром сдвига длины 3 над полем  (рис. 4):

                                                
                                        k1      k2     k3

Рис. 4

Пользуясь конструкцией 1, получим следующую матрицу:

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

	1	2	3	4	5	6	7	
1	1	2	3	4	5	6	7	
2	4	1	5	6	2	7	3	
3	5	3	6	2	7	1	4	
4	6	4	2	7	1	3	5	
5	7	6	1	3	4	5	2	
6	2	5	7	1	3	4	6	
7	3	7	4	5	6	2	1	

Данная матрица является латинским квадратом. В случае когда все ключи равновероятны, рассматриваемый шифр является минимальным сильно совершенным шифром.

Утверждение 3.9. Матрица  полученная с помощью конструкции 1, отвечает правилу зашифрования билинейного над  минимального сильно совершенного шифра в соответствии с формулой (3.6). 

Доказательство. Достаточно проверить, что выполняется условие (ii) утверждения 3.3. 
Известно (см., например, [Глу90]), что матрица  построенная с помощью конструкции 1, обладает следующим свойством. 
При любом фиксированном  вектор  представляет собой состояние регистра, полученное после фиксированного числа  тактов его работы из начального состояния  Пусть   расстояние между векторами  и  на соответствующем цикле линейного преобразования. Тогда упомянутое свойство может быть записано в виде равенства

     		             (3.8)

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

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

или в координатной форме

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

Конструкция 2
1) Пусть   ненулевые элементы поля  представленные в координатной форме.
2) Определим правило зашифрования  в соответствии с соотношением

                                                     			                       (3.9)
в поле 

Пример 3.11. Пусть   базис поля  над  из примера 3.10. Конструкция 2 дает билинейный над  шифр с правилом зашифрования

Этот шифр совпадает с шифром из примера 3.6.

Утверждение 3.12. Конструкция 2 строит минимальный билинейный над  сильно совершенный шифр.

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

Конструкцию 2 можно естественным образом обобщить.

Конструкция 3
1) Пусть   ненулевые элементы поля  представленные в координатной форме.
2) Определим правило зашифрования  в соответствии с соотношением

в поле  Здесь 

а   невырожденные -матрицы над 
Таким образом, для вычисления  следует вычислить  и  перемножить их в координатной форме, и по произведению  вычислить 

Очевидно, что конструкция 3 также дает билинейный над  минимальный сильно совершенный шифр. Такие шифры названы мультипликативными. В [Mas87] сформулирован ряд нерешенных задач:

•	Является ли сильно совершенный билинейный шифр, построенный с помощью конструкции 1, мультипликативным шифром?
•	Является ли любой сильно совершенный билинейный шифр мультипликативным шифром?
•	Является ли любой сильно совершенный линейный шифр билинейным шифром?