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

Нас будут интересовать -стойкие шифры, имеющие наилучшие параметры имитостойкости. Помимо упомянутых в главе 2 параметров  и  рассматривают также вероятность  успеха противника в попытке обмана порядка  Имеется  в виду ситуация, когда противник может наблюдать  различных криптограмм, полученных на одном ключе, и заменять их на некое “поддельное” сообщение по своему усмотрению. 
В [Sti88], [Soe88] получена простая нижняя оценка вероятности 

Теорема 4.3.1. Имеет место достижимая оценка

                                                                                              (4.3.1)

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

                                              (4.3.2)
где 

Аналогично тому, как это делалось в теореме 2.2.3, проверяется равенство 

                                                                      (4.3.3)

из которого следует искомое неравенство: 

Если этот максимум достигается на  то противник выбирает его в своей попытке обмана. 

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

                                                             			      (4.3.4)

В ряде работ (например, [Soe88], [Sti90], [Mitt94], [Cas98]) изучались шифры, одновременно удовлетворяющие условию -стойкости и условию -стойкости к попытке обмана. Наибольшее внимание уделялось случаям, когда  или  Первое сочетание наиболее естественно в случае, когда противник может вставить новое сообщение в канал связи, но не может модифицировать наблюдаемые сообщения. Если же противник может модифицировать сообщения, то естественно изучать второй случай. 

Сформулируем ряд результатов в этом направлении. 
Теорема 4.3.3. Если шифр  удовлетворяет условию -стойкости и условию -стойкости к попытке обмана, то 
Доказательство. Пусть  Предположим, что 
Как и в теореме 4.3.1, вероятность того что при попытке обмана шифртекст  будет принят как аутентичный, при условии что наблюдается множество криптограмм  вычисляется по формуле (4.3.2). Аналогично (4.3.3), справедливо равенство 

причем одно из слагаемых этой суммы   равно нулю. Если бы все остальные слагаемые были не больше отношения 

то их сумма была бы строго меньше  Значит, для некоторого  

и 

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

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

Теорема 4.3.4. Если существует перпендикулярный массив  то существует шифр  для которого 

 и 

причем -стойкий и -стойкий к попытке обмана.

Доказательство. Рассмотрим данный перпендикулярный массив в качестве матрицы зашифрования для  Если строка матрицы с номером  имеет вид  то полагаем  Будем использовать ключ  с вероятностью 

Как и в лемме 4.2.9, при  каждый символ содержится ровно  раз в каждом столбце массива. Отсюда следует, что

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

или, что то же самое, 

Тогда

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

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

Теорема 4.3.5. Если существует перпендикулярный массив  то существует оптимальный -шифр  с параметрами 
Доказательство. Пусть  Построим  так же, как в теореме 4.3.3. Достаточно проверить, что 
Имеем: 

   			       (4.3.5)

Так как  встречается в каждом столбце матрицы  ровно   раз,

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

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

Тем самым, 

что и требуется.

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

Теорема 4.3.6. Пусть  четно,  Тогда существует циклический перпендикулярный массив 

В [Soe88] для построения оптимальных -шифров использованы штейнеровы системы (см. определение 2.3.3) и конечные геометрии. Имеет место, например, следующий результат (который мы приводим без доказательства).
Теорема 4.3.7. Штейнерова система  определяет оптимальный -шифр  с параметрами 

.

В [Soe88] теорема 4.3.2 уточняется следующим образом. 
Теорема 4.3.8. Если шифр  удовлетворяет условию -стойкости и условию -стойкости к попытке обмана, то 
                                                     		            (4.3.6)

Доказательство. Так же как в теореме 4.3.2, доказывается, что
                                                   			  (4.3.7)

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

                                                       		           (4.3.8)   

Заметим, что если  то 

                                			       (4.3.9)

Из (4.3.7)  (4.3.9) следует, что при всех возможных выборах подмножеств  мы получим не менее 

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

откуда следует неравенство (4.3.6).

Отметим в заключение, что для построения имитостойких -стойких шифров помимо циклических перпендикулярных массивов, в [Sti90] использован еще один частный класс перпендикулярных массивов. 

Определение 4.3.9. Перпендикулярный массив  называется аутентификационным перпендикулярным массивом (и обозначается ), если выполняется следующее условие:

“для любого  и любого подмножества элементов  в строках матрицы  содержащих  любое подмножество из  состоящее из  элементов, входит во все возможные подмножества из  столбцов матрицы одинаковое число раз”.

Приведем (без доказательства) обзор некоторых результатов из [Sti90]. 

Теорема 4.3.10. Если существует ортогональный массив , то существует шифр , удовлетворяющий условиям -стойкости, -стойкости к попытке обмана, и имеющий параметры

Доказывается частичное обращение этой теоремы:

Теорема 4.3.11. Если существует шифр  с параметрами 

удовлетворяющий условиям -стойкости и -стойкости к попытке обмана для любого распределения  и  то существует перпендикулярный массив 

Имеется ряд частных результатов о оптимальных - и  -шифрах.

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

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

где 

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

Теорема 4.3.15. Для любого простого числа Ферма  существует оптимальный -шифр с произвольным распределением  имеющий параметры

Дальнейшие результаты о свойствах аутентификационных перпендикулярных массивов , основанные на теории схем и теории групп подстановок, получены в [Bie94], [Tr95] и [Bi96]. В [Tr95] приведена таблица (состоящая из 154 позиций) известных массивов  для 
 
В [Cas98] изучаются, в частности, -стойкие шифры с минимальными значениями вероятностей  и обладающие минимальным (в определенном смысле) числом ключей. Предлагаются конструкции таких шифров на основе ортогональных массивов. В связи с их громоздкостью мы их не приводим. 
В [Cas98] уточняется также теорема 4.2.11:

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