S-boxes algorithmic realization based on modified additive generators.pdf 1. Построение подстановок с помощью МАГ Критически важные узлы замены симметричных итеративных блочных шифров (s-боксы), обеспечивающие нелинейность и полное перемешивание входных данных, задаются, как правило, таблично и реализуют отображения двоичных векторных пространств малой размерности (6 х 4 битов в алгоритме DES, 4х 4 битов в ГОСТ 28147-89, 8 х 8 битов в алгоритме «Кузнечик»). Размер s-боксов ограничен в силу ресурсоёмко-сти их табличной реализации по размеру памяти и времени. Для построения s-боксов использованы МАГ длины 3 с точками съёма 0 и 2 и МАГ длины 4 с точками съёма 0 и 3 [1]. Обозначим: X0,... , Xn_i -знаки начального состояния МАГ длины n (числа кольца вычетов z256; b - биекция, определяющая двоичное 8-разрядное представление числа X Е z256 по правилу: если X = 27х0 +... + 2х6 + х7, то b(X) = X = (х0,..., х7) Е Vg; g - преобразование множества Vg (модификация аддитивного генератора); ф9 - преобразование регистра сдвига длины n над Vg, реализуемое МАГ: ф9(Xо,..., Xra_i) = (Xi,..., Xra_i, bg((Xo + Xra_i) mod 256)). Перемешивающий орграф Г(ф9) преобразования ф9 имеет 8n вершин, где разрядам числа Xi соответствует множество вершин {8i, 8i + 1,..., 8i + 7}, i = 0,..., n - 1. Преобразование ф9 -подстановка, если и только если g - подстановка [1]. Знаки гаммы Xi, генерируемые МАГ, образуются по закону рекурсии (1) Xi = bgb-i((Xi_i + Xi_ra) mod 256), i ^ n. При фиксации переменных X0 = z0,... , Xn_2 = zn_2 реализуемая в соответствии с (1) функция Xn-i ^ Xга_1+г при любом / ^ 1 есть преобразование множества Vg. Для краткости обозначим это преобразование s(l)(z,x), где z = (z0,...,zn-2) G V8(n-1), x = O^ . . . , x7) = Xn-1- Теорема 1. Пусть 0, n - 1 - точки съёма МАГ, g - подстановка. Тогда при l = 1,... ,n - 1 и при любой фиксации z преобразование s(1)(z,x) есть подстановка множества V8. 2. Способ построения подстановок Для построения s-боксов размера 8 х 8 использованы s-боксы 4 х 4 и модификации g(x0,...,x7) = (K(x0 ф x4,x1 ф x5,x2 Ф x6,x3 ф x7),K(x0,x1 , x2,x3)), где K G {K1,..., K8, E1,..., E8,11,..., /8}, K - узлы замены ГОСТ 28147-89 [2], E,, I - узлы шифра Serpent [3], i = 1,... , 8. Каждому узлу замены соответствует 28(n-1) подстановок вида s(1)(z,x), l = 1,...,n - 1. Перемешивающие свойства подстановок оценены с помощью локального экспонента [4]. Теорема 2. Пустьg(x0,...,x7) = (K(х0фх4, x^x5, х2фх6, х3фх7), K(x0,x1,x2,x3)), где K - совершенный s-бокс 4 х 4; 0 и n - 1 - точки съёма МАГ. Тогда при J = = {8n - 8, 8n - 7,..., 8n - 1} локальный экспонент J2-exp Г = 2. 3. Экспериментальное исследование свойств сгенерированных подстановок С помощью теорем 1 и 2 сделан обоснованный выбор параметра l = 2 при n = 3 и l = 3 при n = 4. С помощью программной реализации МАГ на ЭВМ для каждого узла замены получены все 216 подстановок при n = 3 и 219 подстановок (выборочно) при n = 4. Для каждой подстановки s с координатными функциями s1,... , s8 проверены следующие свойства: 1) совершенность (существенная зависимость функции Sj от переменных x,, i, j = = 1,..., 8; 2) нелинейность всех нетривиальных линейных комбинаций функций s1,... , s8; 3) близость максимальной разностной характеристики к максимальной разностной характеристике случайной подстановки, где = max |{x G V8 : s(x) ф s(x ф a) = в}|. Установлено, что свойства 1, 2 имеют большинство подстановок (при n = 3 не имеют 1088 подстановок, соответствующих узлу /1, и менее 400 - любому другому узлу). Характеристика подстановок при n = 3 принимает значения (10 + 2k)/256, k = = 0,1,... , 15. В табл. 1 приведено число полученных при n = 3 подстановок s, для которых = 10/256. Таблица 1 Число подстановок со свойствами 1, 2 и характеристикой = 10/256, n = 3 Узлы замены Ki K2 К K4 K5 Кб К7 Kg Ei E2 E3 E4 E5 Еб Е7 Eg h /2 /3 I4 I5 /б /7 /8 Число подстановок 44 24 68 100 24 48 84 48 32 12 20 128 152 140 4 64 104 116 8 160 92 124 44 80 При n = 3 посчитано, что обратные подстановки (к каждой подстановке табл. 1) обладают свойствами 1, 2 и их разностная характеристика также равна 10/256. При n = 4 характеристики подстановок принимают значения (8 + 2k)/256, k = = 0, 1, . . . ; в табл. 2 приведены количества подстановок для k = 0 и 1. Сравним характеристики у полученных и известных s-боксов размера 8 х 8 (табл.3). Видим, что характеристики полученных с помощью МАГ подстановок s Т а б л и ц а 2 Число подстановок со свойствами 1, 2 и характеристикой Ps е {8/256,10/256}, n = 4 Ps Узлы замены, использованные в МАГ Ki K2 K3 K4 K5 Кб Кг Kg 8/256 0 2 0 0 0 0 0 2 10/256 18615 19968 20309 19921 20107 18898 18506 19807 близки по порядку к характеристике 6/256 наилучших на сегодняшний день s-боксов [5]. Заметим, что величина ps = 10/256 соответствует большому количеству случайных подстановок степени 256 и не превышает их среднего значения [5, табл. 1]. Т а б л и ц а 3 Сравнение характеристик ps для s-боксов известных алгоритмов Алгоритм «Skipjack» «Кузнечик» s-боксы работы [5] s-боксы табл. 1 и 2 Ps 12/256 8/256 6/256 8/256,10/256 Выводы Алгоритмический подход позволяет построить с использованием МАГ и s-боксов 4 х 4 большое количество s-боксов 8 х 8 с рядом позитивных криптографических свойств. Представляется перспективным совершенствование характеристик s-боксов 8 х 8 за счёт изменения параметров схемы построения и исследование вопросов синтеза s-боксов больших размеров (16 х 16, 32 х 32 и др.).

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