Свойства - и -стойких шифров

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

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

Доказательство. Пусть  и, как и ранее, 

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

                                (6.1)

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

Любая биекция  отображает некоторое подмножество  на  данное  поэтому  

Из (6.1) и сказанного выше следует, что условие -стойкости влечет равенство 

для любого  Поэтому, во-первых,

и, во-вторых, 

для  любых    Отсюда следует, что  

(  это число различных -подмножеств  из ) Таким образом 
                                                                             (6.2)

что и требуется. 
Достаточность. Пусть для любых  выполняется условие (6.2). Тогда (с учетом того, что  для любых ) 

Отсюда следует (6.1), а также условие -стойкости. Теорема доказана.

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

                                                             (6.3)
 возрастающая последовательность целых чисел.
Доказательство следует из теоремы 6.1 и леммы 5.3. 
Условие (6.3) является, таким образом, необходимым условием  -стойкости шифра с параметрами 

Можно заметить, что для любого  существует  для которого выполнено условие (6.3). Например, в качестве такого  можно взять число 

Рассмотрим более подробно множество подстановок, удовлетворяющих свойству  (ii)  теоремы  4.2.4.
Согласно теореме 6.1, изучение -стойких шифров в случае, когда

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

Лемма 6.3. Если множество подстановок  является -однородным на  то  является также -однородным на 

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

откуда и следует требуемое утверждение.

Лемма 6.4. Если  является -однородным множеством подстановок на , то .

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

 и  

откуда следует требуемое равенство.

Лемма 6.5. Если  является -однородным множеством подстановок на  причем  то  является также -однородным на  для любого  где 

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

Методом индукции по  покажем, что (при ) величина  не зависит от выбора 
Пусть  Рассмотрим такой элемент  что  Выберем  таким, чтобы 

Ясно, что  Дальнейшие рассуждения проиллюстрируем рисунком 6.

               

                                                            

Рис.6 

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

число пар  таких, что

равно 

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

Число способов выбора  совпадает с числом способов выбора  и равно   Для каждой из выбранных пар  имеется (в силу однородности) ровно  подстановок  для которых  Поэтому искомое число пар  равно 

В результате получаем равенство

(Обратим внимание на то, что при этом  так как )
Шаг индукции: предположим, что  и что проверяемое утверждение верно для любого  Подсчитаем число пар  для которых выполняются условия 

                                                      (6.4)

При этом возможны два случая: когда 

и когда  

В первом случае  таково, что  Соответствующее множество  получается дополнением к  одного элемента  такого, что  не лежит ни в   ни в  Поэтому имеется  способов выбора такого 
Ясно, что во втором случае 

Выберем опять  так, чтобы выполнялись условия (6.4). При этом  получается добавлением к  любого одного элемента  такого что  Поэтому всего имеется 

таких подмножеств  Таким образом, имеется в точности

                          (6.5)

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

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

                                                               (6.6)

Получаем равенство (6.5) = (6.6), в котором величина  не зависит от выбора  по предположению индукции. Следовательно, и  также не зависит от выбора   что и требуется.
Положив теперь  получим искомый результат. В самом деле, равенство  выполняется тогда и только тогда, когда  Согласно сказанному выше, число таких подстановок  не зависит от  что свидетельствует об однородности множества  Число  находится применением  леммы 6.4:

откуда следует требуемая формула для    Переходя от  к  и т.д., аналогичным образом получаем формулу для любого  

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

                                                    (6.7)

Тогда  удовлетворяет также условию -стойкости при любом  таком что 

 или 

Доказательство. По теореме 4.2.5  является -однородным множеством подстановок. Согласно лемме 6.5, при выполнении условий (6.7),  является также и -однородным, где  и

Тогда, согласно теореме 6.1,  является -стойким шифром. 
Кроме того, по лемме 6.3  является также -однородным множеством подстановок. Если  то, согласно теореме 6.1,  является -стойким шифром, что и требуется.
В заключение отметим (см. [Sti90]), что для -стойких шифров справедливы все результаты § 4.3 по оценке вероятностей имитации и подмены, которые были сформулированы для -стойких шифров. В дополнение к этому в [Cas98] получена нижняя оценка числа ключей -стойкого шифра, имеющего минимальное значение вероятности 
Теорема 6.7. Если для шифра  выполняется условие -стойкости,  и выполняется равенство

то имеет место оценка