О неабелевых группах наложения ключа и марковости алгоритмов блочного шифрования | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/25

О неабелевых группах наложения ключа и марковости алгоритмов блочного шифрования

Для абелевой группы наложения ключа (X, *) и разбиения W = {Wo,..., Wr-i} множества X ранее авторами рассматривались *w-марковские преобразования и *-^-марковские алгоритмы, частным случаем которых являются *-марковские алгоритмы блочного шифрования, представленные на конференции EUROCRYPT в 1991 г. В данной работе для неабелевой группы (X, *) описываются свойства *-^-марковских алгоритмов и преобразований. Получены ограничения на строения групп (X, *), (gfc |k е X), а также на блоки Wo, ...,Wr-i, вытекающие из условия сохранения частичной раундовой функцией gk : X ^ X нетривиального разбиения W для каждого k е X. Для всех неабелевых групп порядка 2m, имеющих циклическую подгруппу индекса два, приведены примеры *w-марковских подстановок.

On nonabelian key addition groups and markovian block ciphers.pdf Пусть (X, *) -произвольная группа на множестве X с бинарной операцией * и единичным элементом e; ab = ab = b(a) -образ элемента а е X при действии на него подстановкой b е S(X). Рассмотрим /-раундовый алгоритм блочного шифрования Q(*,b), у которого раундовая функция g : X2 ^ X, определяемая подстановкой b е S (X), задана условием g : (x, k) ^ (x * k)b для всех (x, k) е X2. Раундовой функции g соответствуют частичные функции gk : X ^ X, где g(x, k) = = gk(x) для каждых (x, k) е X2. Заметим, что к данному классу относятся XSL-алгоритмы блочного шифрования, у которых b = sh, где s - преобразование слоя перемешивания (s-боксы); h - преобразование линейного слоя. Неабелевость группы наложения ключа позволяет в некоторых случаях повышать стойкость алгоритмов блочного шифрования относительно линейного и разностного методов. Пусть K - множество всех раундовых ключей итерационного алгоритма блочного шифрования (в данной работе K = X). Для в,е е X положим 1 Зафиксируем произвольное нетривиальное разбиение W = {W0,... , Wr-1} множества X, e е W0. Положим Pe,wc(b)= E Po,o>(b), в е X, с е {0,... ,r - 1}. e'ewc В [1] введено понятие *-марковского алгоритма блочного шифрования, а в [2] - *^-марковского алгоритма блочного шифрования и *w-марковского преобразования. Определение 1. Преобразование b е S(X) называется *W-марковским для разбиения W = {W0,..., Wr-1}, |X| ^ r ^ 2, если pe,wc (b) = aj;C для каждых (j, с) е е {0,..., r - 1}2, в е Wj и некоторых aj,c, 0 ^ aj,c ^ 1. Условие *w-марковости алгоритма Ci(*,b) равносильно *w-марковости подстановки b. Рассмотрим преобразование ak е S (X), заданное условием ak : x ^ x * k для каждого k е X, и группу X * = (ak |k е X). Пусть р : X ^ S (X) - правое регулярное представление группы (X, *). Очевидно, что p(X) = X* и p(k) = ak для каждого k е X; gk = akb для каждого k е X. Будем говорить, что раундовая функция g сохраняет разбиение W справа, если Wgk G W для всех (W, k) G W х X. Получены ограничения на группы (X, *), G = (b,X*), а также на блоки W0,... , Wr-1, вытекающие из условия сохранения раундовой функцией нетривиального разбиения W. Доказано, что W - система импримитивности группы G. Кроме того, показано, что (W0, *) -подгруппа группы (X, *), причём Wj - j-й правый смежный класс группы (X, *) по (W0, *) для j = 0,... , r - 1. Из импримитивности группы G следуют включения b G IGw, (gk|k G X) ^ IGw, где IGw - максимальная подгруппа группы S(X), сохраняющая разбиение W. Если группа G = (b, X* ) импримитивна с системой импримитивности W, то существует естественный гомоморфизм : G ^ S({0,... , r - 1}), 1 = (e). Доказано, что если (Wo, *) нормальна в (X, *) ((Wo, *) < (X, *) ), W - множество всех смежных классов группы (X, *) по (W0, *), то условие *w-марковости алгоритма Q(*,b) эквивалентно существованию у него гомоморфизма, задаваемого отображением

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

difference distribution table, imprimitive group, homomorphism, dihedral group, generalized quaternion group, markovian cipher, матрица разностей переходов, импримитивная группа, обобщённая группа кватернионов, группа диэдра, гомоморфизм, марковский алгоритм блочного шифрования

Авторы

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

Ссылки

Lai X., Massey J. L., and Murphy S. Markov ciphers and differential cryptanalysis // EUROCRYPT 1991. LNCS. 1991. V. 547. P. 17-38.
Погорелов Б. А., Пудовкина М. А. Разбиения на биграммах и марковость алгоритмов блочного шифрования // Математические вопросы криптографии. 2017. Т. 8. №1. С. 107142.
Холл М. Теория групп. М.: ИЛ, 1962. 468с.
 О неабелевых группах наложения ключа и марковости алгоритмов блочного шифрования | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/25

О неабелевых группах наложения ключа и марковости алгоритмов блочного шифрования | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/25