On ARX-like ciphers based on different codings of 2-groups with a cyclic subgroup of index 2.pdf В раундовых преобразованиях большинства блочных шифрсистем обычно используются преобразования из аддитивной группы (Vm, +) m-мерного векторного пространства Vm над полем GF(2), реже - из аддитивной группы (Z2m, +) кольца вычетов Z2m. В ряде шифрсистем используются комбинации таких групп (IDEA, SAFER), действующих параллельно или последовательно. Ещё один класс составляют ARX-шифрсистемы (Addition-Rotation-Xor). Они реализуются с помощью большого числа простых преобразований соответственно из подстановочных представлений групп (Z2m , +), (Vm, +) и циклического сдвига координат. Известными представителями ARX-шифрсистем являются TEA, XTEA [1], RC5 [2], RC6 [3], SIMON, SPECK [4]. Естественным развитием этого подхода представляется рассмотрение неабелевых групп, «ближайших» к указанным, а также различных подстановочных представлений таких групп, в том числе связанных с различными кодировками элементов группы. Ранее в работах авторов описаны подстановочные свойства групп с циклической подгруппой индекса 2 [5], классы преобразований на указанных группах [6, 7], а также рассмотрены вопросы марковости [8]. Из теоремы 12.5.1 [9] следует, что неабелевыми группами порядка 2m с циклической подгруппой индекса 2 являются только четыре группы, удовлетворяющие следующим порождающим соотношениям: - группа диэдра D2m, m 3, 2m-1 2 a2 = e, u2 = e, ua = a-iu; - обобщённая группа кватернионов Q2m, m 3, 2m-1 2 2m-2 a = e, u = a , ua = a- u; - модулярная максимально-циклическая группа M2m, m 4, m-1 a2 - = e, 2 i+2m-2 u2 = e, ua = ai+2 - полудиэдральная группа SD2m, m 4, 2m-1 2 i+2m-2 a2 = e, u2 = e, ua = a-i+2 Обозначим через Hm одну из четырёх групп: Hm G {D2m, Q2m, M2m, SD2m}. Элементы группы Hm будем записывать как u£1 a£2, где £i G {0,1}; 2 G {0,... , 2m-:i Пусть ^rr : Hm S(Hm), plr : Hm S(Hm) - соответственно правое и левое регулярные подстановочные представления, заданные для всех i G {0, . . . , 2m-i - 1}, x G Hm условиями prr (a*) : x xai, «rr (ua*) : x xuai, pir (a*) : x a-ix, plr (ua*) : x (ua*)-ix. Пусть Z2+m. V+ - правые подстановочные представления аддитивных групп кольца Z2m и m-мерного векторного пространства Vm над полем GF(2). Напомним (см., например, [10]), что транзитивная группа подстановок G С S(X) называется импримитивной, если существует сохраняемое G нетривиальное разбиение W множества X на равномощные блоки, т. е. g(W) = {g(a)|a G W} G W для всех g G G. W G W. Группа Gm = (V+. импримитивна с r-й системой импримитивности W(r,m) = = |Wo(r,m)..... W2r'-1)}, где Wt(r,m) m -r. Wir,m) = {j G {0..... 2™ - 1} : j = t (mod 2r)} . t = 0.... . 2r - 1. r = 0. ....m. Группа Gm возникает в связи с разными криптографическими приложениями. Её строение описано, например, в [11, 12]. Максимальной подгруппой в S2m, сохраняющей каждое разбиение W(0,m). W(1,m) W(m,m), является силовская 2-подгруппа Pm G G Syl2 (S2 m ), описываемая операцией сплетения Pm = P2 ? Pm-1 и содержащая Gm. Возможны различные способы задания отображения v : Hm {0..... 2m - 1}, кодирующего элементы группы Hm целыми числами из множества {0..... 2m - 1}, которые удобны для использования в криптографических приложениях. Для c G {rr. lr} отображению v сопоставим естественное изоморфное вложение v : ^c(Hm) S2m, такое, что элементу b G ^c(Hm) ставится в соответствие подстановка v(b) G S({0..... 2m - 1}), заданная условием v(b) : v(a) v(b(a)) для всех a G Hm. Тем самым каждому элементу a G Hm и его образу b(a) G Hm сопоставляются соответственно элементы v(a). v(b(a)) G {0 2m - 1}, которые однозначно задают подстановку v(b) на {0..... 2m - 1}. Далее отображение v будем называть кодировкой. Напомним [10], что у импримитивной группы существуют нетривиальные естественные (подстановочные) гомоморфизмы. Кроме того, импримитивность группы, порождённой криптографическими преобразованиями, в частности раундовыми функциями, может привести к уязвимости шифрсистемы относительно метода гомоморфизмов [13, 14]). В связи с этим описание кодировок v, для которых группы, порождённые комбинациями групп v(^rr (Hm)), v(^ir (Hm)) и Z2m, являются примитивными, представляет интерес с точки зрения криптографических приложений, включая синтез ARX-шифрсистем и их вариаций. Пусть c G {lr. rr}. В данной работе приведены необходимые и достаточные условия на отображение V, при которых справедливо включение v(^c (Hm)) С Pm или равенство (Z^ .v(^c (Hm))} = S2 m. Для преобразования обращения s G Hm, s : а а 1, и регулярного представления v(^c(Hm)) получены необходимые и достаточные условия справедливости включения (v(s). v(^c(Hm))) С Pm. Теорема 1. Пусть m 4, Hm G {D 2 m . Q 2 m . M2m. SD2m}, биективные отображения vdm) : Hm ' {0. 1.... . 2m - 1}, d G {1. 2. 3}, заданы условиями: (m ) 2i. если x = ai, 1 2i + 1. если x = uai, 2m) : x i, i + 2 m- 1 если x = ai, если x = uai, 3m) : x если x = ai, если x = uai, где x G Hm, i G {0,1,..., 2m 1 - 1}. Тогда имеют место следующие свойства: 1) Для r'rr (Hm) v1m)(^rr (Hm)) < Pm, v1 \\s),v1 \\^rr (Hm))^ C Pm для Hm G{D2m , Q2m , M2m , SD2m } , v2 (^rr (Hm)) C Pm для Hm G {D2m , M2m } • v1m)(^ir (Hm)) C Pm, 2) Кроме того, а) ^Z^m ,v2m) (^rr б) (z+m ,v2m) (Vrr (Hm))) Hm G {D2m, Q2m, M2m Для ^Ir (Hm) = S2m для каждой Hm G {Q2m = S2m , SD2m}. ^Z+m ,v3m) (^rr(Hm))) SD2m}; = S2m для каждой v1 \\s),v1 \\^lr (Hm))^ C Pm для Hm G {D2m , Q2m , M2m , SD2m } , . (Hm)) C Pm для Hm = M2m , v3m)(^lr (Hm)) C Pm для Hm G {D2m , SD2m } . Кроме того, а) ^Z+m ,v2m) to, (Hm))) = S2m для каждой Hm G {D2m, Q2m, SD2m}; б) I^Z^n, V3 (^ir (Hm)^ = S2m для каждой Hm G {M~2m, Q2m }• Заметим, что группа Z2+m порождена полным циклом (0, . . . , 2m - 1). При доказательстве теоремы 1 использовано свойство, что примитивная группа, содержащая полный 2m-^^, изоморфна симметрической группе S2 m или естественному подстановочному представлению степени 2m проективной группы PGL(2,p), p = 2m - 1 - простое число [15].

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