Вариации ортоморфизмов и псевдоадамаровых преобразований на неабелевой группе | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/6

Вариации ортоморфизмов и псевдоадамаровых преобразований на неабелевой группе

В криптографии ортоморфизмы на абелевой группе используются как S-боксы в схемах Лея - Месси, квази-Фейстеля, в блочной шифрсистеме FOX, в режиме блочного шифрования Дэвиса - Мейера, а также в кодах аутентификации. В работе рассматриваются ортоморфизмы, полные преобразования и их вариации на конечной неабелевой группе (X, ·) наложения ключа. В алгоритме блочного шифрования SAFER для обеспечения принципа рассеивания используется псевдоада-марово преобразование. Предложено десять аналогов псевдоадамарова преобразования, задаваемых подстановкой s на неабелевой группе (X, ·). Доказано, что биективность аналогов псевдоадамарова преобразования равносильна справедливости следующего условия: подстановка s является ортоморфизмом, полным преобразованием или их вариацией.

Variations of orthomorphisms and pseudo-hadamard transformations on nonabelian groups.pdf Пусть S(X) -симметрическая группа на конечном множестве X, g(a) -образ элемента a £ X при действии на него подстановкой g £ S(X), ag = ag = g(a). Рассмотрим произвольную конечную неабелеву группу (X, ■). Каждой подстановке s £ S(X) поставим в соответствие преобразования n(s) : X M X, i = 1,... , 4, заданные условиями (s) -1 s (s) s (s) s -1 (s) s П : a M a a , n2 : a M aa , П3 : a M a a , П4 : a M a a. Определение 1. Пусть s £ S(X), тогда 1) если n(s) £ S(X), то s называется ортоморфизмом [1]; 2) если n2s) £ S(X), то s называется полным преобразованием [1]; 3) если n3s) £ S(X), то s называется левым ортоморфизмом; 4) если n4s) £ S(X), то s называется полным левым преобразованием. Очевидно, что для коммутативной группы n(s) = n(s), n2s) = n4s). В этом случае говорят, что -ортоморфизм, а n2s) -полное преобразование. Заметим, что для неабелевой группы n(s) можно называть правым ортоморфизм, а n2s) - полным правым преобразованием. В дискретной математике ортоморфизмы и полные преобразования находят применение, например, при построении систем ортогональных латинских квадратов, квазигрупп [2-4]. В настоящее время открытым является вопрос полной классификации всех ортоморфизмов и полных преобразований на произвольной конечной группе. В криптографии ортоморфизмы используются как S-боксы [5], компоненты функции шифрования в схемах Лея - Месси [6], квази-Фейстеля [7], в алгоритме блочного шифрования FOX [8], в режиме блочного шифрования Дэвиса - Мейера [9], а также в кодах аутентификации. Известно [1], что каждому ортоморфизму s £ S (X) соответствует полное преобразование n(s). Наоборот, каждому полному преобразованию s £ S(X) соответствует ортоморфизм n(s). Аналогичная связь существует между левым ортоморфизмом и полным левым преобразованием. В алгоритме блочного шифрования SAFER [10] для обеспечения принципа рассеивания используется псевдоадамарово преобразование h : Z|56 M Z|56, заданное условием h : (ai, a2) M (2ai + a2, ai + a2), (ab a2) £ Z256. Очевидно, что h - подстановка на Z|56. При этом преобразование x M 2x mod 256 не является биективным ортоморфизмом. Для подстановки s £ S (X) и каждого a £ X положим A(s)(a) = {a, a-i, as, (as)-i} . Пусть d = , d2i), d^2), d22^ -набор отображений, удовлетворяющих условиям dj) : X2 M X, d(j)(ai, a2) £ A(s)(ai)UA(s)(a2) для каждой пары (ai,a2) £ X2, i, j = 1, 2. Обозначим через множество всех таких наборов отображений. Для алгоритма блочного шифрования с неабелевой группой наложения ключа (X, •) рассмотрим аналог псевдоадамарова преобразования h(s'd) : X2 M X2, d £ D(s), заданного условием h(s'd) : (ai,a2) M ^d^a^ a2)d2i)(ai, a2), di2)(ai, a2)d22)(ai, a2)j . X2 M X2 при i = 1,..., 10, заданные Для s £ S (X) рассмотрим преобразования h условиями hi h( h5 h7 h( Очевидно, что his) £ {h(M) : d £ D(s)} для i = 1, » » (s) (s) : (ai,a2) M (aja2, aia2), h2s) : (ai,a2) M (aia-i, a2ai), (s) 3 : (ai,a2) M (a^a2, aia-i), h4s) : (ai,a2) M (aia-i, aia-i), (s) 5 : (ai,a2) M ((а^)-ia2, aia2), hf : (ai,a2) M ((ai)-ia-i, aia-i), (s) 7 : (ai,a2) M (aia2, aia2), h8s) : (ai,a2) M (ai(a2)-i, aia2), (s) 9 : (ai,a2) M (aia2, aia-i), : (ai,a2) M (ai(a2)-i, aia-i). 10. Получен критерий биективности преобразования h(s) для каждого j £ {1,..., 10} Теорема 1. Пусть s £ S (X). 1. Для каждого j £ {1, 4} тогда и только тогда hjs) £ S(X2), когда £ S(X). 2. Для каждого j £ {2, 3, 8} тогда и только тогда hjs) £ S(X2), когда п^ £ S(X). 3. Для каждого j £ {5, 6, 9} тогда и только тогда hjs) £ S(X2), когда n(s) £ S(X). 4. Для каждого j £ {7,10} тогда и только тогда h(s) £ S(X2), когда n(s) £ S(X). Кроме того, пусть Aut(X) -группа автоморфизмов. Доказано, что если s £ Aut(X), то для каждого {i, j} £ {{1, 3}, {2, 4}} условия n(s) £ S(X) и njs) £ S(X) равносильны.

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

ортоморфизм, полное преобразование, конечная неабеле-ва группа, псевдоадамарово преобразование, алгоритм блочного шифрования SAFER, orthomorphism, complete mapping, nonabelian group, pseudo-Hadamard transformation, SAFER block cipher

Авторы

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

Ссылки

Evans A. Orthomorphisms Graphs and Groups. Berlin: Springer Verlag, 1992.
Johnson D. M., DulmageA.L., and Mendelsohn N. S. Orthomorphisms of groups and orthogonal Latin squares // Canad. J. Math. 1961. V. 13. P. 356-372.
Глухов М. М. О применениях квазигрупп в криптографии // Прикладная дискретная математика. 2008. Т. 2. №2. С. 28-32.
Глухов М. М. О методах построения систем ортогональных квазигрупп с использованием групп // Математические вопросы криптографии. 2011. Т. 2. №4. С. 5-24.
Mittenthal L. Block substitutions using orthomorphic mappings // Adv. Appl. Math. 1995. V. 16. No. 1. P. 59-71.
Vaudenay S. On the Lai - Massey schemes // ASIACRYPT'99. LNCS. 1999. V. 1716. P. 8-19.
YunA., ParkJ., and Lee J. On Lai - Massey and quasi-Feistel ciphers // Des. Codes Cryptogr. 2011. V. 58. P. 45-72. r(s)
Junod P. and Vaudenay S. FOX: A new family of block ciphers // Selected Areas in Cryptography'04. LNCS. 2005. V.3357. P. 114-129.
Gilboa S. and Gueron S. Balanced permutations Even-Mansour ciphers // Cryptology ePrint Archive. 2014. Report 2014/642.
Massey J.L. SAFER K-64: a byte-oriented block-ciphering algorithm // FSE'94. LNCS. 1994. V. 809. P. 1-17.
 Вариации ортоморфизмов и псевдоадамаровых преобразований на неабелевой группе | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/6

Вариации ортоморфизмов и псевдоадамаровых преобразований на неабелевой группе | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/6