Permutation binomials over finite fields. Conditions of existence.pdf Компонентами многих шифров являются S-блоки - векторные булевы функции. В большинстве случаев S-блоки являются перестановками, то есть взаимно однозначными функциями. Для программной и аппаратной реализации S-блока на вычислительных системах хорошо подходит его полиномиальное представление. Например, полиномиальное представление S-блоков используется в AES - современном стандарте симметричного шифрования США. В работе исследуются взаимосвязи между комбинаторным и алгебраическим представлениями взаимно однозначных векторных булевых функций [1]. Рассматриваются взаимно однозначные функции f : F2n - F2n вида f (x) = akx* + xj, где a - примитивный элемент поля; 0 ^ k ^ 2n - 1 и 1= j < i ^ 2n - 1. Теорема 1. Пусть 1 ^ j < i ^ 2n - 1, 1 ^ k ^ 2n - 1, a - примитивный элемент поля F2n. Если функция f : F2n - F2n вида f (y) = aky* + yj взаимно однозначна, то (i - j, 2n - 1) не делит (k, 2n - 1). Теорема 2. Пусть 1 ^ j < i ^ 2n - 1, 1 ^ k ^ 2n - 1, a - примитивный элемент поля F2n. Если 2n - 1 -простое, то взаимно однозначных функций f : F2n - F2n вида f (x) = akx* + xj не существует. Теорема 3. Пусть 1 ^ j < i ^ 2n - 1, 1 ^ k ^ 2n - 1, а - примитивный элемент поля F2n. Если n - составное число, то существует взаимно однозначная функция f : F2n ^ F2n вида f (x) = акxi + xj. Опираясь на результаты [2], доказана n Теорема 4. Если 2n - 1 имеет делитель d < ---- - 1, то существует взаимно 2log2(n) однозначная функция f : F2n ^ F2n вида f (y) = ауг + yj для некоторого а £ F2n, 0 < j < i < 2n - 1. Остался не исследованным вопрос существования взаимно однозначной векторной булевой функции при простом числе n и составном числе 2n - 1, если у него нет n делителя d < ---- - 1. 2 log2 (n) С использованием полученных результатов найдены все взаимно однозначные функции данного вида для всех n ^ 8. При этих же значениях n найдены все взаимно однозначные биномиальные дифференциально 4-равномерные векторные булевы функции. Посчитано количество взаимно однозначных биномиальных функций с максимальной компонентной алгебраической иммунностью при n = 4, 6. При n = 4 таких функций 10, а при n = 6 - 319 [3].

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