Cryptographic properties of some vectorial boolean functions compositions.pdf Обозначим через Fn множество всех подстановок на F^ и будем рассматривать следующие подклассы функций из Fn: 1) Kn - функции, полученные из тождественной подстановки с помощью n независимых транспозиций [1]; 2) Sn,k - функции вида F = (fi,... , fn), где (fi,... , fk) е Kk и fi(xi,... , Xn) = Xi 0 0 gi(xi,... ,xi-i), gi - произвольные булевы функции, существенно зависящие от k - 1 переменных, i = k + 1,..., n, k ^ n [2, 3]; 3) пусть k|n; s = n/k; Pn,k - функции F = (fi,...,fn), где ftk+i(xi,... , Xn) = = gi(t+i)(xtk+i,...,X(t+i)k), t = 0,...,s - 1 и i = 1,...,k; (gjj),..., gkj)) е Kk, j = 1,...,s. Приведём определения некоторых криптографических характеристик функций F =(fi ...fn): Fn ^ Fn [4-6]. Компонентой функции F называется булева функция vF = vifi 0 ... 0 vnfn, где v = vi... vn е Fn \\ {0n}; 0n - нулевой вектор длины n. Нелинейностью N(F) и компонентной алгебраической иммунностью AIcomp(F) функции F называются минимальные нелинейность и алгебраическая иммунность её компонент соответственно: N (F) = min N (vF), AIcomp (F) = min AI(vF). Для векторов a,b е Fn обозначим (a,b) = |{x е Fn : F(x) 0 F(x 0 a) = b}|. Показателем дифференциальной равномерности функции F называется = max (a, b). a=0n ,b Проведено экспериментальное исследование этих характеристик, а также алгебраической степени для некоторых композиций функций от 3-10 переменных. Нелинейность, алгебраическая иммунность, дифференциальная равномерность вычислялись по алгоритмам, описанным в [7]; алгебраическая степень - с помощью преобразования Мёбиуса. В ходе экспериментов получены следующие результаты: 1) Если в композиции участвует случайная подстановка F е Fn, то характеристики композиции в среднем совпадают с характеристиками функции F. Это можно объяснить тем, что при композиции любой подстановки со случайной равновероятно выбранной равномерное распределение сохраняется [8]. 2) Композиция H функции F е Kn с функцией G е Sn,k UPn,k (в любом порядке), можно сказать, берёт наилучшие свойства обоих классов: а) deg H и AIcomp(H) сохраняются, как у функции F; б) принимает значения, приблизительно равные , если G е Sn,k, и если G е Pn,k; в) N(H) « N(G). 3) При композиции функций F и G из одного класса, Kn или Pn,k, все рассмотренные свойства в общем ухудшаются: а) принимает худшее значение 2n, а нелинейность - значение 0 (хотя очень редко получаются значения лучше, чем у исходных функций); б) AIcomp(H) принимает значения 1 или 2 (у исходных функций всегда 2); в) deg H часто равна 1 (редко - как у исходных функций). 4) Про композиции функций из разных классов Sn,k и Pn,k и композиции функций одного класса Sn,k нельзя однозначно сказать о поведении свойств функций: а) deg H часто улучшается; б) AIcomp(H) принимает значения 1 или 2 (те же значения, что и у функций класса Sn,k); в) бы в первом случае принимает значения, приблизительно равные 8 функций классов Vn,k (очень редко получаются значения лучше или хуже), а во втором случае сохраняется значение 2n (как у функций класса Sn,k); г) N(H) в обоих случаях может принимать разные значения, в основном они лучше, чем наихудшие значения у функций, используемых в композициях.

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