On the construction of s-boxes of 4 X 4 size.pdf Введение Нелинейные преобразования векторных пространств, получившие название s-бок-сов, являются важнейшим элементом раундовых преобразований симметричных блочных шифров. Размер s-бокса, реализующего преобразование множества n-мерных векторов, равен n хп. Отечественные и зарубежные учёные активно проводят исследование свойств s-боксов и методов их построения [1, см. библиографию]. В работе представлен алгоритм построения всех s-боксов размера 4х4, обладающих рядом позитивных криптографических свойств. К таким свойствам относятся: подстановочность, нелинейность, совершенность, небольшая величина разностной характеристики. Изложены результаты выполненного на персональном компьютере экспериментального исследования множества s-боксов размера 4х4, в том числе используемых в некоторых известных блочных шифрах. Алгоритм построения всех s-боксов размера 4х4. Обозначим s1,s2,s3,s4 систему булевых координатных функций s-бокса s, VW = {0,1}w. Алгоритм состоит из следующих шагов: 1. Построение множества F4 всех булевых функций от четырёх переменных со свойствами: функция зависит существенно от всех переменных; функция сбалансирована (равновероятна); степень нелинейности равна 2 или 3. 2. Перебор всех возможных систем четырёх булевых функций из множества функций F4 и проверка преобразований, соответствующих построенным системам, на наличие таких криптографических свойств, как: 1) биективность; 2) отсутствие неподвижных точек, то есть s(a) = а для любого а Е V4; 3) нелинейность всех нетривиальных линейных комбинаций вида ф a2s2 Ф ^з Ф ^4, a Е {0,1} , i = 1,..., 4; 4) значение разностной характеристики ps подстановки s не более 4/16, где ps = 2-W max | {x Е VW : s(x ф а) ф s(x) = в} |. Для распознавания биективности использован критерий [2, с. 116]: s - подстановка тогда и только тогда, когда равновероятна любая нетривиальная линейная комбинация её координатных функций. Заметим, что при построении раундовой подстановки предпочтение отдается биективным s-боксам как функциям, усложняющим применение криптоаналитических атак типа метода статаналогов и др. Полученные результаты. Из всех булевых функций от четырёх переменных (65 536 функций) в множество F4 отобраны 12 618 (п. 1 алгоритма). Составлен список s-боксов (систем четырёх функций) со свойствами 1-4, размер списка 383 084314 s-боксов. Определение характеристик s-боксов DES и ГОСТ 28147-89. Созданное программное обеспечение использовано для определения характеристик s-боксов алгоритмов DES и ГОСТ 28147-89. Каждый из восьми s-боксов размера 6х4 алгоритма DES можно представить как 32 s-бокса размера 4х4 с помощью фиксаций битов ai и а6, управляющих выбором одной из четырёх подстановок степени 16 s-бокса, где ai, а2,... , - биты входного набора s-бокса. При фиксации других битов биективность s-бокса не обеспечена. Установлено, что 6 s-боксов не обладают свойством 2 (наличие неподвижных точек). Ряд s-боксов не обладают свойством 4: у 16 s-боксов = 8/16, у 14- = 6/16, и имеется по одному s-боксу, у которых = 4/16 и 10/16. В алгоритме ГОСТ 28147-89 используется 8 s-боксов размера 4х4, имеются рекомендации по их выбору [3]. Установлено, что из восьми s-боксов три не обладают свойством 2 (наличие неподвижных точек); у всех s-боксов = 4/16. Выводы 1. Построенное множество s-боксов размера 4х4, обладающее рядом позитивных свойств, может быть использовано при решении задач синтеза перспективных криптографических алгоритмов. 2. Созданное программное обеспечение может быть использовано для исследования s-боксов размера 4х4, используемых в различных действующих и перспективных криптографических системах.

Скачать электронную версию публикации