Анализ совершенности и сильной нелинейности алгоритмов блочного шифрования | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/23

Анализ совершенности и сильной нелинейности алгоритмов блочного шифрования

Экспериментально исследованы характеристики итеративных алгоритмов блочного шифрования с раундовой подстановкой на базе регистров сдвига (обобщение петли Фейстеля) из классов R(8, 32, 3), R(15, 32, 5), R(16, 32, 5), R(32, 32, 9) и R(33, 32,11), где R(n, 32, m) -класс автономных регистров сдвига длины n над множеством векторов V32 c m обратными связями (обобщение петли Фейстеля); n > m ^ 1; Vq - множество двоичных q-мерных векторов. Исследованы показатели совершенности и сильной нелинейности, определяемые как наименьшее число раундов, после которого произведение раундовых подстановок является совершенным и сильно нелинейным соответственно. Даны эмпирические оценки этих характеристик для некоторых алгоритмов из указанных классов. С использованием результатов сделаны рекомендации по числу раундов шифрования.

Analysis of the perfection and strong non-linearity of encryption algorithms.pdf К шифрующим подстановкам блочных алгоритмов предъявляется ряд требований, направленных на обеспечение криптографической стойкости шифра. В частности, подстановка должна быть сильно нелинейной (то есть все её координатные функции не должны являться аффинными [1, c. 125]) и совершенной (то есть каждый бит выходного вектора должен существенно зависеть от всех битов входного вектора). Шифрующая подстановка g(h) итеративного h-раундового алгоритма A блочного шифрования построена как произведение раундовых подстановок g(h) = p1.. .ph, где pi - подстановка i-го раунда, i = 1,...,h. Показателем сильной нелинейности алгоритма A (обозначается esn A) назовём наименьшее количество r раундов, при котором подстановка g(r) является сильно нелинейной; показателем совершенности алгоритма A (обозначается epf A) назовём наименьшее количество r раундов, при котором подстановка g(r) является совершенной, 1 < r ^ h. Заметим, что данные характеристики у алгоритма A могут не существовать. Если перемешивающие орграфы раундовых подстановок совпадают и равны Г($), то величина epf A оценивается снизу экспонентом орграфа Г(д) (обозначается exp r(g)) [2, c. 101]. Величины esn A и epf A оцениваются сверху с помощью лемм 1 и 2 соответственно. Обозначим: I(x) -множество номеров единичных компонент вектора x е Vq; gj - j-я координатная функция подстановки g множества Vq, j = 1,... , q. Непосредственно из определений линейности булевой функции и существенной зависимости от переменной следуют леммы 1 и 2 соответственно. Лемма 1. Пусть для некоторой четвёрки векторов а,Ь, с, е из области определения раундовой подстановки g выполнено g^ ф с) ф g(a) ф g(b ф с) ф g(b) = е, тогда функция gj является нелинейной для любого j е I(е). Лемма 2. Пусть а и b - соседние по i-й координате векторы, i = 1,... , q, и для раундовой подстановки g выполнено g(a) ф g(b) = е, тогда функция gj(x1,... ,xq) существенно зависит от xi для любого j е I(е). В ходе исследований были построены алгоритмы блочного шифрования с раундовой подстановкой на основе регистров сдвига из классов R(8, 32, 3),R(15, 32, 5), R(16, 32, 5), R(32, 32, 9) и R(33, 32,11). Из экспериментально проверенных соображений минимизации экспонента перемешивающего орграфа расположение обратных связей взято равноудалённое или близкое к нему, то есть расстояние между соседними точками съёма близко к n/m. Приведём для примера h-раундовый алгоритм 512-5 из класса R(16, 32, 5) (h - параметр). На г-м раунде шифрования реализуется подстановка g, зависящая от раундо-вых ключей ,... , q5 G V32. Обозначим через X = (X0,... , X15) входной блок раунда, Xk G V32, 0 ^ k ^ 15. При ключах q1,... , q5 раундовая подстановка множества V512 (рис. 1) задана формулой g(Xo,...,Xi5) = (Xi,f (S,qi) Ш Х2,Хз ,X4 ,f (S,^) Ш X5, X6, X7, X8, f (S,®) Ш X9, X10, X11, f (S q4) Ш X12, X13, X14, f (S q5) Ш X15, X0) , где S = Xo Ш X1 Ш X3 Ш X4 Ш X6 Ш X7 Ш X8 Ш X10 Ш X11 Ш X13 Ш X14; Ш - сложение по модулю 232. Функция f обратной связи совпадает с функцией алгоритма ГОСТ 28147-89. Рис. 1. Раундовая подстановка алгоритма 512-5 Для оценки показателя сильной нелинейности алгоритма 512-5 генерируем наборы случайных 512-мерных векторов (at, bt, ct), t =1, 2,... , и при r = 2, 3,... , h вычисляем 4r) = g(r)(at) Ф g(r)(bt) Ф g(r)(a Ф C) e g(r) (bt Ф Ct), e(r) G V512. Если при некотором t (из вероятностных соображений взято t ^ 100) вектор V ... V e(r) (покоординатная дизъюнкция) состоит только из единиц, то esn A ^ r. Для оценки показателя совершенности алгоритма генерируем наборы случайных 512-мерных векторов, соседних по координате Xi, и при r = 2, 3,... , h вычисляем значение etr) = g(r)(at) Ф g(r)(bt), etr) G V512. Если при некотором t ^ 100 результат по- (r) (r) координатной дизъюнкции векторов е1 ,... ,et для г = 1,..., 512 состоит только из единиц, то epf A ^ r. С помощью данных экспериментов оцениваем минимальное число раундов, необходимое для обеспечения сильной нелинейности и совершенности алгоритма шифрования. Если при опробовании 100 наборов векторов условие сильной нелинейности или совершенности не выполняется, то делается вероятностный вывод об отсутствии свойства сильной нелинейности и совершенности соответственно. Для каждого алгоритма - представителя указанных классов вида R(n, 32, m) - проведено по 20 экспериментов, в ходе которых посчитан ехрГ(д) и получена оценка показателей сильной нелинейности и совершенности (таблица). Во всех экспериментах полученные оценки совпали для каждого из рассмотренных блочных алгоритмов. Оценки показателей сильной нелинейности и совершенности n m expT(g) esn A epf A 8 3 4 3 7 15 5 4 3 7 16 5 7 4 8 32 9 7 4 8 33 11 4 3 6 Таким образом, при равноудалённом (или приблизительно равноудалённом) размещении обратных связей на регистре сдвига: 1) число раундов для достижения алгоритмом сильной нелинейности (esn A) близко к величине n/m; 2) число раундов для достижения алгоритмом совершенности (epf A) не меньше 7 и не больше 27, где 7 = 2 exp r(g); 3) число раундов шифрования при синтезе шифров данного класса целесообразно установить не меньше 2expT(g).

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

function perfection, exponent of digraph, экспонент графа, strong nonlinearity, совершенность, сильная нелинейность

Авторы

ФИООрганизацияДополнительноE-mail
Мифтахутдинова Альфинур РуслановнаФинансовый университет при Правительстве Российской Федерациистуденткаbonne_foi@mail.ru
Всего: 1

Ссылки

Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. №2(12). С. 101-112.
Фомичёв В. М., Мельников Д. А. Криптографические методы защиты информации. Ч. 1. Математические аспекты: учебник для академического бакалавриата. М.: Юрайт, 2016. 209 с.
 Анализ совершенности и сильной нелинейности алгоритмов блочного шифрования | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/23

Анализ совершенности и сильной нелинейности алгоритмов блочного шифрования | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/23