О почти совершенных нелинейных преобразованиях и разделяющем свойстве мультимножеств | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/65

О почти совершенных нелинейных преобразованиях и разделяющем свойстве мультимножеств

Рассматриваются некоторые классы APN-преобразований относительно возможности построения интегральных различителей с помощью разделяющего свойства. Проведён вычислительный эксперимент по определению величины \\n/d\\ для выбранных APN-преобразований GF(2n) м GF(2n), где d - алгебраическая степень. Из полученных результатов следует, что не все APN-преобразования имеют наилучшее значение \\n/d\\ = 2. Выделены APN-преобразования с параметрами, наиболее оптимальными для противодействия интегральному анализу с помощью разделяющего свойства.

On APN-functions and division property of multisets.pdf Разностный метод и его обобщения являются одними из основных методов анализа симметричных шифрсистем. Один из этапов разностного метода заключается в нахождении элементов матрицы вероятностей переходов разностей компонент функции зашифрования, включая S-боксы. В работе [1] для противодействия разностному методу при синтезе алгоритмов блочного шифрования в качестве S-бокса предложено использовать APN-преобразование (если оно существует). Определение 1 [1]. Преобразование s : GF(2n) м GF(2n) называется APN-преобразованием, если для каждых ненулевых элементов а, в G GF(2n) уравнение s(x + а) - s(x) = в имеет два или нуль решений. Актуальной задачей является исследование APN-преобразований относительно других методов криптоанализа, в частности относительно интегрального метода. В [2] приводится способ построения интегрального различителя с использованием разделяющего свойства (англ. division property). Пусть Vn - n-мерное векторное пространство над полем GF(2); ||а|| - вес Хэмминга вектора a; ai - i-я координата вектора а = (а1,..., an) G Vn, i G {1,...,n}. Для каждого элемента в G GF(2) положим в1 = в, в0 = 1. Тогда корректно определено отображение п : Vn х Vn м Vn, заданное условием n п : (а,6) м П af, а = (ab ...,an) G Vn, 6 = (61,...,6n) G Vn. i=1 Далее будем рассматривать отображение n(x, 6) только при фиксированном 6 G Vn. Определение 2 [2]. Пусть n G N, k G {1,...,n}, S{kn) = {a G Vn : k ^ ||a||}. Говорят, что мультимножество X с носителем Vn имеет разделяющее свойство D(n), если для каждого 6 G Vn \\ S(n) выполняется равенство ф n(a, 6) = 0. aEX Будем говорить, что мультимножество Y с носителем Vn получено применением векторной булевой функции g : GF(2n) ^ GF(2n) к мультимножеству X с носителем Vn, если элементы Y есть результаты применения функции g к каждому элементу мультимножества X. Теорема 1 [2]. Пусть s : GF(2n) ^ GF(2n) -преобразование алгебраической степени d и мультимножество X с носителем Vn имеет разделяющее свойство D(n), k € {1 ,...,n - 1}. Тогда мультимножество, полученное применением s к X, имеет разделяющее свойство Из теоремы 1 следует, что чем больше значение \\n/dd\\, тем для большего числа раундов существует интегральный различитель, получаемый посредством применения предложенного в работе [2] алгоритма. В настоящей работе проведён вычислительный эксперимент по определению величины \\n/d\\ для некоторых APN-преобразований GF(2n) ^ GF(2n), приведённых в [3]. Из полученных результатов следует, что не все APN-преобразования имеют наилучшее значение \\n/d\\ = 2. Результаты отражены в табл. 1-3 (указаны лучшие параметры, если они найдены). Таблица 1 APN-преобразования и их параметры, при которых \\n/d\\ = 2 Формула и условия Параметры xj, j = 2n - 2, n = 2k + 1 n € {3, 5,..., 11} xj, j = 24 + 2°'5t - 1, если t = 2k,k € n; j = 24 + 21'5t+0'5 - 1, если t = 2k + 1, k € n; n = 2t +1 Для n = 7, t = 3 и n = 11, t = 5 имеем d = 4 и d = 6 соответственно xj, j = 22t - 1, n = 2t + 1, t € n t € {1, ..., 6} xj ,j = 22i - 2® + 1, (i, n) = 1 (n, i) € {(9,4), (9, 5)}, d =5 xj, j = 24® + 23i + 22i + 2®® - 1, n = 5i, i € n i € {1, 2} (x + trn/3 (x2(2i+1) + x4(2i+1)] + +tr(x)trn/s (x2i+1 + x22i(2i+1)))2i+1, n = 3k, k = 21, 1 € n, (i, n) = 1 n = 6 Таблица 2 APN-преобразования и их параметры, при которых \\n/d\\ = 6 Формула и условия Параметры qs 1 и 4, i = sk(mod 3), m = 3i, ord(w) = 22k + 2k + 1 n =12 x2S+1 + wx2ik+2mk+s, n = 4k, k € n, (k, 2) = (s, 2k) = 1, k > 3, i = sk(mod 4), m = 4i, ord(w) = 23k + 22k + 2k + 1 n =12 Таблица 3 APN-преобразования, для которых [n/d] растёт с ростом n Формула и условия Параметры xj, j = 2г + 1, (i,n) = 1 n G {2,..., 12}, d =2 xr+1 + (x2* + x + 1) tr (x2i+1), n > 4, n = 2k +1, k G n, (i, n) = 1 n G {4, 6,..., 12}, d =3 x3 + tr(x9), n > 2p ^ 7 для такого наименьшего p, что p > 1, p = 3 и (p, n) = 1 n G {7, 9,11,12,13}, d =2

Ключевые слова

APN-преобразование, разделяющее свойство, интегральный различитель, интегральный метод, APN-transformations, division property, integral distinguisher, integral crypt-analysis

Авторы

ФИООрганизацияДополнительноE-mail
Сорокин Михаил АртёмовичНИЯУ МИФИстудент кафедры криптологии и кибербезопасностиsorokin.michael.96@yandex.ru
Пудовкина Марина АлександровнаМосковский государственный технический университет им. Н. Э. Бауманадоктор физико-математических наук, профессор кафедры информационной безопасностиmaricap@rambler.ru
Всего: 2

Ссылки

Nyberg K. and Knudsen L.R. Provable security against differential cryptanalysis // CRYPTO 1992. LNCS. 1993. V. 740. P. 566-574.
Todo Y. Structural evaluation by generalized integral property // EUROCRYPT 2015. P.I. LNCS. 2015. V. 9056. P. 287-314.
Тужилин М. Э. Почти совершенные нелинейные функции // Прикладная дискретная математика. 2009. Т. 5. №3. C. 14-20.
 О почти совершенных нелинейных преобразованиях и разделяющем свойстве мультимножеств | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/65

О почти совершенных нелинейных преобразованиях и разделяющем свойстве мультимножеств | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/65