Diffusion properties of generalized quasi-hadamard transformations on finite abelian groups.pdf В ряде алгоритмов блочного шифрования (Safer [1], Hight [2], CS-Cipher [3], Speed [4] и др.) большинство преобразований, составляющих раундовую функцию, реализует побайтовую обработку блоков текста без взаимного влияния байтов с использованием абелевых групп. Наибольшее распространение среди таких «межбайтовых» преобразований получил класс псевдоадамаровых преобразований на двух байтах в алгоритмах семейства Safer. В [5] он обобщён до класса квазиадамаровых преобразований на аддитивных группах Z22m , Z22m, для которых получены формулы нахождения элементов разностной матрицы. В [6] найден показатель рассеивания (branch number) тензорного произведения псевдоадамаровых преобразований алгоритма Safer. Пусть m 2; (X, *) - конечная группа с бинарной операцией *; e - тождественная подстановка; S(X) - симметрическая группа на X; P(X) = {b | b: X X} - симметрическая полугруппа; ag = ag = g(a) -образ элемента a G X при действии на него преобразованием g G P (X); Hom(X) = (v: X X | Vx, y G X (v(x * y) = v(x) * v(y)) } . Для алгоритмов блочного шифрования рассмотрим обобщение к#,ф: X2 X2 ква-зиадамаровых и псевдоадамаровых преобразований на группу (X, *), которое задаётся набором отображений г? = (ik1,ik2), ф = (фъф2), г?,ф G P(X)2б и условием : (ai, «2) (af1 * af2, a^ * a^ . (1) При (X *) G {(Z2m , + ) (Zm, ®)} rb r2 G {0,..., m - l}^ ri = (rii, Г12), Г2 = (Г21, Г22), Г1 = Г2, U G {0, 1} квазиадамарово преобразование иГи)Г2 на X, введённое в [5], является частным случаем обобщения (1). Так, при X = Z 2m оно задаётся условием иГи)Г2: (ai,a2) (2r11 ai + (-1)и2r12a2, 2r21 ai + (-1)u2r22a2) и совпадает с h,, при следующих отображениях: d1: а 2r11 а mod 2m, $2: а (-1)и2r12а mod 2m, ф1: а 2Г21 а mod 2m, ф2: а (-1)и2r22а mod 2m. Отметим, что при чётном r11 > 0, r2 = (0, 0) преобразование U(r11,0),(0,0) : (аЬ а2) (2Г11 а1 + а2- а I + а2) применено в хеш-функции FFT [7]. Кроме того, при rii = 1 преобразование u((r0) ,0),(0,0), известное как псевдоадамарово, используется для улучшения рассеивающих свойств в алгоритмах блочного шифрования Safer, Safer+ [8], Safer++ [9] и Twofish [10]. В данной работе получены условия биективности преобразования h^,. Так, для биективно-сти h,, необходимо, чтобы одно из преобразований G1, $2, ф1, -ф2 было биективным. Отсюда вытекает, что при X = Z2m биективное преобразование h,, принимает вид h^,,: («1,0:2) ^v11 + b1аV2, a • oVl1 + 62для всех («i, а2) G Z^, (2) где {vi, V2} = {1, 2}, /'2 = vi(1, 2), G S(Z2m), a, 61,62 G Z2m, причём b2 - a • 61 = 1 (mod 2). (3) В работе показывается, что условию (2) удовлетворяет биективное квазиадамарово преобразование. Для импримитивной группы G S(X) с системой импримитивности W (т. е. W - нетривиальное разбиение множества X на равномощные блоки, сохраняемое группой G) рассеивание подстановкой g G S(X) системы W, а также расстояние от g до G будем характеризовать посредством матрицы c(W)(g), введённой в [11]. Разбиению W = {W0,... , Wp-1} множества X и подстановке g G G ставится в соответствие матрица c(W) (g) = cj) (g) , где cjXg) = iWg П Wj |, Wf = {вд | в G Wi} , i,j G {0,... ,p - 1}. Для группы (G, *) рассмотрим её правое подстановочное представление ^G: G S(G), заданное условием ^G(k): x x * k для всех x, k G G. Пусть G = ^g(G) = {^G(k) | k G G}. Для d G {0,..., 2m}, t G {0,...,d} положим W{dd} = {Wo(d,t),...,w2^}, где W[d,tt = {j = i (mod 2t) 1 j G Z2d } , i = 0,.. . , 2* - 1 TT Tj7(d,i) Y77(d,d-1) Легко видеть, что W , ...,W -нетривиальные системы импримитивности группы Z2d. Для t1, t2 G {0, . . . , m} положим W,j,t1,t2) = W,(m,t1) X W(m,t2), i = 0,..., 2t1 - 1, j = 0,..., 2t2 - 1, W(m,t1,t2) = [Wj,t1,t2) | i G {0,..., 2t1 - 1},j G {0,..., 2t2 - 1}} . В работе описываются свойства рассеивания преобразованием h#,) систем импримитивности регулярных подстановочных представлений Z2m = Z2m х Z2m и Z22m соответственно двух групп наложения ключа Z2m и Z22m. Легко видеть, что группа Z%m импримитивна, а {w^’| t1,t2 6 {0,..., m}| - множество всех её систем импримитивности. Найдены элементы матрицы c(W ) (h#,)) для преобразования h#,) и системы импримитивности W^ ’ ’ для каждого t 6 6 {0, . . . , m}. Утверждение 1. Пусть преобразование h#,): Z^m Z^m удовлетворяет услови ям (2) и (3), v1 = 1, $х 6 S(Z 2m ). Группа (h#,^, z2 m ) < s(Z2 m ) является примитивной тогда и только тогда, когда примитивна группа ^1, ZS(Z2m). Нетривиальной системой импримитивности группы Z22m является W ’ для каждого t 6 {1,..., 2m - 1}. Преобразование h#,), заданное условием (1), зависит от элемента v1 6 {1, 2}. Утверждение 2. Пусть t 6 {1,... , 2m - 1}, преобразование h#): Z2m Z^m удо влетворяет условиям (2) и (3), v1 = 1, a = 1 (mod 2), ^1 6 S(Z2m). Тогда для каждых fw(2m,t^ г \\ j1,j2 6 {0,... , 2t - 1} элементы матрицы m ' (h#,)) удовлетворяют следующим свойствам: (w (2m

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