On the way of constructing differentially 25-uniform permutations over F22m.pdf Исследование способов построение нелинейных биективных преобразований с заданными криптографическими характеристиками является актуальной и сложной задачей. Одним из известных подходов, позволяющих строить нелинейные преобразования с достаточно высокими криптографическими характеристиками и допускающие эффективную программную и аппаратную реализацию, является использование подстановок, имеющих декомпозицию. Пусть F2 = {0,1} -поле из двух элементов с операциями сложения «+» и умножения «•»; (Fn, +) = {(a0, a1,..., an-1) : ai G F2,i = 0, ...,n - 1} - арифметическое векторное пространство размерности n. Задав специальным образом операцию умножения на множестве F2n, можно определить поле F2n, состоящее из 2n элементов. Везде далее считаем, что фиксирована биекция между F2n и F2n. Произвольную функцию F: Fn Fm будем называть (n, те^-функцией. Тогда (n, 1)-функция есть булева функция, биективная (n, ^-функция- подстановка. Определение 1 [1]. Пусть F - (n, те.)-функция, 1 С t С min(n,m), xi,yi G F2, x2 G Fn-t, y2 G Fm-t, x = xi||x2 G Fn, y = yi ||y2 G Fm. Тогда если существуют такие функции T: F2 х Fn-t F2, U: Fn-t х F2 Fm-t, что при фиксации х2 произвольным значением T(xi, x2) есть биекция по переменной xi и функция F представима в виде F(x) = F(Х1ЦХ2) = T(xi,X2)||U (X2,T(xi,X2)), (1) то такое представление функции F в виде (1) будем называть TU-представлением. Замечание 1. Известно [2], что в случае m = n функция F является подстановкой, если функция U(x2, xi) является подстановкой по x2 при фиксации xi. Определение 2. Для F: Fn Fm и произвольных a G Fn \\ {0}, b G Fm положим 5aFb = |{x G Fn: F(x + a) + F(x) = b}|. Будем говорить, что F является дифференциально OF-равномерной функцией, если Of = a,b max OF , aGFn\\{0}, F bGFm значение OF будем называть показателем дифференциальной равномерности функции F. Использование нелинейных преобразований с меньшим показателем дифференциальной O-равномерности при синтезе криптографических примитивов позволяет гарантировать стойкость последнего к разностному методу криптографического анализа. Известно достаточно много примеров подстановок, обладающих высокими криптографическими характеристиками и имеющих TU-представление: - подстановка, CCZ-эквивалентная подстановке Диллона, -единственная известная в настоящий момент 2-равномерная подстановка на F2m [3]; - подстановка, линейно эквивалентная подстановке алгоритмов ГОСТ Р 34.11-2012 и «Кузнечик» (ГОСТ Р 34.12-2018) [2]; - подстановки из работ [4-7]. Для a G F2n-t обозначим: - OT,a - показатель дифференциальной O-равномерности подстановки, которую задаёт функция T(xi, x2) при фиксации x2 = a; Aai,a2,0i *-> та -количество решений уравнения T(xi,a) + T(xi + ai,a + «2) = в1, ai, в1 G Fn t, а2 G F2 \\ {0}. Получен следующий критерий дифференциальной O-равномерности функции F, имеющей TU-представление. Теорема 1. Пусть у функции F имеется TU-представление (1). Тогда показатель дифференциальной O-равномерности функции F меньше либо равен значению 2t • max aeF2 max ai,eieFn-t a26F‘\\{0} \\ai,a.2,Pi I ^T,a ( Доказательство теоремы следует из того факта, что при каждой из 2t фиксаций x2 значением a2 уравнения вида T(xi, a2) + T(xi + «i, a2 + a2) = в1 являются следствием уравнений F(xi, a2) + F(xi + «i, a2 + a2) = в1 ||в2- Теорема 1 позволяет строить дифференциально 25-равномерные преобразования, а замечание 1 гарантирует биективность этого преобразования. Следствие 1. Пусть в условиях теоремы 1 t =1 и 5т,а С 5 для всех a G F2. Тогда функция F, имеющая TU-представление (1), не более чем дифференциально 25-равномерна тогда и только тогда, когда max AT'-l)1^ С 5. «1,в1 CX' 1 Для доказательства следствия необходимо отметить, что Аа10,1,в1 = Аа'|1,в| для всех ai,ei G Fn-i. Тогда, согласно следствию 1, задача построения дифференциально 25-равномерных подстановок сводится к поиску двух подстановок п0,п1 G S (Fn_i), таких, что количество решений уравнений no(x) + ni(x + ai) = ei (2) при всевозможных значениях ai, в1 G Fn-i не больше 2. Действительно, если T(x1, i) = = ni(xi), i G {0,1}, U(x2,xi) - линейная по x2 функция при произвольной фиксации xi, то с использованием формулы (1) получим подстановку с показателем дифференциальной равномерности 25. В качестве п0,п1 можно взять произвольную дифференциально 2-равномерную подстановку. В этом случае, c учётом следствия 1 и замечания 1, функция F является подстановкой с показателем дифференциальной равномерности большим либо равным 4. При этом если максимальное количество решений (2) равно двум, то подстановка будет дифференциально 4-равномерной, иначе показатель её дифференциальной равномерности будет определяться удвоенным максимальным количеством решений уравнений вида (2). Теорема 2. Пусть xi G F2n-i, n чётное, n > 6, x2 G F2, f - произвольная булева функция от n - 1 переменной, c G F2n-1\\{0, 1}, T: F2n-i x F2 F2n-i, T(xi,x2) = x-1 • cx2, U: F2 x F2n-1 F2, U(x2,xi) = f (xi) + x2. Тогда формула (1) задаёт подстановку F, при этом 1) если tr(c) = tr(c-i) = 1, то 5F = 4; 2) иначе 5F = 6. Замечание 2. Результат п. 1 теоремы 2 доказан в [8], однако следствие 1 позволяет проводить доказательство с более общих позиций. Теорема 3. Пусть x1 G F2n-i, n чётное, n > 6, x2 G F2, f - произвольная булева функция от n - 1 переменной, c G F2n -i\\{0, 1}, T: Fn_i x F2 Fn_i, T(xi,x2) = x3 • cx2, U: F2 x F2n-i F2, U(x2, xi) = f (xi) + x2. Тогда формула (1) задаёт подстановку F, при этом 5F = 6. Напомним, что две (n, т)-функции g и f называются расширенно аффинно-эквивалентными, если существуют аффинные подстановки а и b пространств F2n и F2m соответственно и аффинная (n, т)-функция с, что f (x) = (b ◦ g ◦ a) (x) + c(x) [1]. Расширенно аффинно-эквивалентные функции, очевидно, имеют одинаковый показатель дифференциальной равномерности. В доказательстве теоремы 3 используется тот факт, что уравнение третьей степени не может иметь больше трёх решений. Естественно предположить, что если взять в качестве T(x1, i) = x3 + aix2 + bix1 - функции, расширенно аффинно-эквивалентные 2-равномерной подстановке x3, то можно построить 4-рав-номерные подстановки F с использованием формулы (1). Следующее утверждение показывает, что это не так. Утверждение 1. Пусть x1 G F2n-i, n чётное, n > 6, x2 G F2, f - произвольная булева функция от n - 1 переменной, a, b G F2n-i, T: Fn-1 x F2 Fn-1, T (x1,0) = xf, T (x1,1) = x3 + a • x1 + b • x1, U: F2 x Fn-1 F2, U(x2,xi) = f (xi) + x2. Тогда существуют «1,в1 G F2n-i, такие, что количество решений уравнения T(x1 + + ai,0) + T(x1, 1) = ef равно 2n-1, либо T(x1, 1) не является подстановкой. Приведём ещё несколько результатов, полученных применением теоремы 1. Утверждение 2. Пусть x1 G F2n-i, n чётное, n > 6, x2 G F2, f - произвольная булева функция от n - 1 переменной, T: F2n-i x F2 F2n-i, T (x1, 0) = x3, T (x1, 1) = x-1, U: F2 x Fn-1 F2, U (x2,xx) = f (xj + x2. Тогда формула (1) задаёт подстановку F, при этом 6F = 8. Утверждение 3. Пусть t = 2, x1 G F2n-t, x2 G Ft2. Тогда существуют такие cx2, x2 G F22, cx'2 = cx" при x2 = x^, что подстановка F, задаваемая формулой (1), дифференциально 8-равномерна, где T: Fn-t x F| Fn-1, T (x^) = x-1 • Cx2, U: F* x Fn-t Ft,, при фиксации произвольного x1 функция U (x2,x1) является подстановкой по переменной x2.

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