О классе степенных кусочно-аффинных подстановок на неабелевой группе порядка 2m, обладающей циклической подгруппой индекса два | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/7

О классе степенных кусочно-аффинных подстановок на неабелевой группе порядка 2m, обладающей циклической подгруппой индекса два

Четыре неабелевы группы порядка 2m, m ^ 4, имеют циклические подгруппы индекса два. Примерами являются широко известная группа диэдра и обобщённая группа кватернионов. Произвольная неабелева группа G порядка 2m, обладающая циклической подгруппой индекса два, в определённом смысле близка к встречающейся в качестве группы наложения ключа аддитивной абелевой группе кольца вычетов Z2m. В данной работе на группе G задаются два класса преобразований, названных степенными кусочно-аффинными, для которых доказаны критерии би-ективности. Они позволят далее провести полную классификацию ортоморфизмов, полных преобразований и их вариаций во множестве всех степенных кусочно-аффинных подстановок.

On a class of power piecewise affine permutations on nonabelian groups of order 2m with cyclic subgroups of index 2.pdf В ARX-шифрсистемах используются просто реализуемые операции сложения в кольце вычетов, в векторном пространстве над полем GF(2), а также циклический сдвиг. Возникает вопрос о переходе к просто реализуемой группе наложения ключа, относительно которой вместе с некоторым преобразованием g могут эффективно обеспечиваться перемешивающие и рассеивающие свойства. Неабелевы группы порядка 2m, обладающие циклической подгруппой индекса два, в определенном смысле преемственны широко встречающимся в качестве групп наложения ключа аддитивным абелевым группами m-мерного векторного пространства Vm(2) над полем GF(2) и кольца вычетов Z2m. В [1] описана связь между неабелевостью группы наложения ключа и свойством марковости алгоритмов блочного шифрования. Из теоремы 12.5.1 [2] следует, что неабелевыми группами порядка 2m, имеющими циклическую подгруппу индекса два, являются только четыре группы с двумя образующим a, u, удовлетворяющими следующим определяющим соотношениям: 1) обобщённая группа кватернионов Q2m, m ^ 3, 2m-1 2 2m-2 -i a = e, u = a , ua = a u; 2) группа диэдра D2m-i, m ^ 3, 2m-1 2 -i a = e, u = e, ua = a- u; 3) m ^ 4, 2m-1 2 i+2m-2 a = e, u = e, ua = a + u; 4) m > 4, 1 _i_om - 2 a u. m - 1 2 2 a e, u e, ua На произвольной неабелевой группе G = (a,u) порядка 2m, имеющей циклическую подгруппу (a) индекса два, рассмотрим преобразования двух видов Г2■ G ^ G и ^(с1 c2 b 1 b2) ■ G ^ G, заданные условиями если i G {0,..., 2m-2 - 1}, если i G {2m-2,..., 2m-i - 1}, ,Г11+С1 в, , , 1 ■ a ь-> ar2i+c2 u, a91'+b1 u, 2m-2 - 1}, ..., 2m-i - 1}, если i G {0,... если i G {2m-2 (r1,r2,91,92) . ■ a u H> и (C1 ,C2,b1,b2) 92i+b2 a если i G {0,..., 2m-2 - 1}, , 2m-i - 1}, ,r-1i+c! ^(^1,^2,91,92) ■ (c1,c2,b1,b2) ■ a' i->ar2i+c2 u, если i G {2m-2 2m-2 - 1}, .., 2m-i - 1}, 2m-i - 1}. (Ci c2'91 ь2) будем называть степенными кусочно- Далее преобразования U((c1,c2,b1,b2) аффинными. Для каждого из этих преобразований получены критерии биективности. Приведём критерий для преобразования в(Г1 с^ь!^). Теорема 1. Пусть m ^ 4, G = (a,u), G - неабелева группа порядка 2m с циклической подгруппой (a) индекса два. Преобразование в^^ ^ ■ G ^ G является подстановкой тогда и только тогда, когда элементы bi,b2,ci,c2 G {0,..., 2m-i - 1}, ri,r2,qi,q2 G {0,... , 2m-i - 1} удовлетворяют одному из следующих условий: 1. Если ri = r2 = 1 (mod 2), то a91'+b1 a92i+b2 u если i G {0,... если i G {2m-2, ^(r1,r2,91,92) (C1,C2,b1,b2) a u н> где 6i,b2,ci,c2 G {0,... , 2m-i - 1}, ri,r2,qi,q2 G {0, 3 (r1 ,Г2,91,92) и U(r1,r2,91,92) 2m-i - qi, ci = 62, 6i - c2 + 2m-2 = qi (mod 2m-i); 2m-i - q2, C2 = 6i, 62 - ci + 2m-2 = q2 (mod 2m-i); 1.4. r2 = 2m-i-qi, ri = 2m-i-q2, 6i-c2+2m-2 = qi ( mod 2m-i), 62-ci+2m-2 = = q2 (mod 2m-i). 2. Если ri = 1 (mod 2), r2 = qi = 2 (mod 4), то 2.1. ri = q2, ci = 62, 6i + C2 = 1 (mod 2); 2.2. ri = 2m-i - q2, 6i + C2 = 1 (mod 2), 62 - ci + 2m-2 = q2 (mod 2m-i). 3. Если r2 = 1 (mod 2), ri = q2 = 2 (mod 4), то 3.1. r2 = qi, c2 = 6i, 62 + ci = 1 (mod 2); 3.2. r2 = 2m-i - qi, ci = 62, 6i + c2 = 1 (mod 2). 4. Если ri = r2 = 2 (mod 4), то 4.1. qi = q2 = 2 (mod 4), 6i + c2 = 1 (mod 2), 62 + ci = 1 (mod 2). Полученные критерии биективности в дальнейшем позволят для каждой из четырёх неабелевых групп порядка 2m, обладающих циклической подгруппой индекса два, классифицировать ортоморфизмы, полные преобразования, а также левые орто-моризмы и полные левые преобразования [3] в множестве всех степенных кусочно-аффинных подстановок в((™£$, в™-)1. 1.1. ri = q2, r2 = qi, ci = 62, C2 = 6i; 1.2. ri 1.3. r2 q2, r2 qi, ri mi

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

неабелева группа, группа диэдра, обобщённая группа кватернионов, критерий биективности, ортоморфизм, nonabelian group, dihedral group, generalized quaternion group, bijection criterion, orthomorphism

Авторы

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

Ссылки

Погорелое Б. А., Пудовкина М. А. О неабелевых группах наложения ключа и марковости алгоритмов блочного шифрования // Прикладная дискретная математика. Приложение. 2018. №11. С. 79-81.
Холл М. Теория групп. М.: ИЛ, 1962. 468с.
Погорелое Б. А., Пудовкина М. А. Вариации ортоморфизмов и псевдоадамаровых преобразований на неабелевой группе // Прикладная дискретная математика. Приложение. 2019. №12. С. 24-27.
 О классе степенных кусочно-аффинных подстановок на неабелевой группе порядка 2<sup>m</sup>, обладающей циклической подгруппой индекса два | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/7

О классе степенных кусочно-аффинных подстановок на неабелевой группе порядка 2m, обладающей циклической подгруппой индекса два | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/7