О свойствах максимального элемента матрицы вероятностей переходов разностей биективного отображения относительно различных групповых операций | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/57

О свойствах максимального элемента матрицы вероятностей переходов разностей биективного отображения относительно различных групповых операций

Рассматриваются конечные группы (G1, 0), (G2, 0) с бинарными операциями 0 и 0. На практике G1,G2 обычно равны аддитивной группе (Vm, Ф) m-мерного векторного пространства Vm над полем GF(2) или аддитивной группе (Z2m, Ш) кольца вычетов Z2m. Среди неабелевых групп порядка 2m аддитивной группе (Z2m, Ш) кольца вычетов в определённом смысле ближе всего группы, содержащие циклическую подгруппу индекса 2. Такими группами являются группа диэдра (D2(m-1), о) и обобщённая группа кватернионов (Q2m, И). В разностном методе и его обобщениях биективному отображению ставится в соответствие матрица вероятностей переходов разностей. В работе для всех 0, 0 Е {Ф, Ш, И, о} экспериментально исследуется случайная величина q(®,0), равная |G1|p(®,Q), где p(®,0) - наибольший элемент матрицы вероятностей переходов разностей случайного биективного отображения s : G1 ^ G2.

On properties of the largest probability for difference transition under a random bijec-tive group mapping.pdf Пусть (G1, 0), (G2, 0) - конечные группы с бинарными операциями 0, 0 и нейтральными элементами e1, e2 соответственно, Gf = Gi \\ {ei} для i =1, 2. В симметричных шифрсистемах группа G1 часто интерпретируется как группа наложения ключа, а на группе G2 задаются отображения, реализующие неформально сформулированные К. Шенноном принципы рассеивания или перемешивания. На практике группы G1, G2 обычно равны аддитивной группе (Vm, ф) m-мерного векторного пространства Vm над полем GF(2) или аддитивной группе (Z2m, Ш) кольца вычетов Z2m. Произвольному биективному отображению s : G1 ^ G2 поставим в соответ ствие матрицу переходов разностей q(0,0)(s) = q^,0)(s) £ Е Gf, 8 Е Gf заданы условием qg,0)(s) = |{а Е G1 : s(a 0 £) = s(a) 0 8}|. Посредством матрицы q(0,0) (s) определяется матрица вероятностей переходов разностей р(0,0)(s) = |G1|-1q(0,0)(s) отображения s. Один из этапов разностного метода и его обобщений заключается в оценках элементов матрицы q(0,0)(s). Все элементы матрицы q(0,0)(s) удаётся вычислить только при небольшом порядке группы G1, например 16 или 256. Если группа G1 большого порядка, например |G1| Е {264, 2128}, то, элементы которой для всех как правило, ищутся нетривиальные нижние или верхние оценки некоторых элементов матрицы q(0'0)(s). Одной из величин, характеризующей матрицу q(0>0) (s) в целом, является ее максимальный элемент. Положим q(®,©) (s) = max { qg>0) (5) : e е G*,6 Е G2x } . Через величину q(0'0)(s) задаются классы криптографических отображений. Так, отображение g : G1 ^ G2 называется разностно d-равномерным, если d = q(0'0)(s) [1]. Если d = 2, то g - APN-отображение [2]. Для противодействия разностному методу при синтезе XSL-алгоритмов блочного шифрования в качестве S-бокса, как правило, выбирается отображение g : G1 ^ G2 с наименьшим значением q(0'0)(g) среди всех отображений (часто биективных) из G1 в G2. В работах [3, 4] приведены примеры биективных отображений, для которых достигаются равенства q(®>e) (s) = 2 и q(ffl'ffl)(s) = 2 соответственно. Пусть F(G1, G2) -множество всех биективных отображений из G1 в G2. Если подстановка s выбирается из множества F(G1, G2) случайно и равновероятно, то q(0'0)(s) является случайной величиной, которую будем обозначать через q(0'0). Для криптографии представляет интерес нахождение распределения случайной величины q(0>0), а также ее различных моментов. В [5] статистически исследована случайная величина q(0'0) для следующих пар групповых операций: (®, ©) Е {(ф, ф), (Ш, Ш), (И, □)}, □ - умножение в Zgm+1, где 2m + 1 -простое. В [5] при фиксированном m Е {4,... , 8} для нескольких тысяч случайным образом сгенерированных m-битных подстановок получена выборка случайной величины q(0>0) и найдено ее выборочное среднее. Показано, что выборочное среднее q(®,e) больше, чем каждое из выборочных средних q(ffl,ffl) и q(0>0). Среди неабелевых групп порядка 2m аддитивной группе (Z2m, Ш) кольца вычетов в определенном смысле ближе всего группы, содержащие циклическую подгруппу индекса 2. Такими группами являются обобщенная группа кватернионов (Q2m, И) и группа диэдра с двумя образующими и, а и циклической подгруппой (а) индекса 2 [6]. В настоящей работе для каждого m Е {4,..., 8} с использованием классического способа [7] сгенерированы 10000 псевдослучайных m-битных подстановок. Для всех ®, © Е {ф, Ш, И, о} получена выборка случайной величины q(0>0) и найдено ее выборочное среднее. Результаты приведены в табл. 1 для ®, © Е {ф, Ш, И}. Таблица 1 Выборочное среднее выборки случайной величины q(®>0) для псевдослучайных m-битных подстановок m (ф, ф) (ф, ш) (ф, и) (ш, ф) (ш, ш) (ш, и) (и, ф) (и, ш) (и, и) 4 6,69896 4,74291 4,72011 4,73179 4,42389 4,47999 4,72041 4,4844 4,42092 5 7,94352 5,53062 5,5322 5,53519 5,17748 5,21568 5,5268 5,21399 5,19629 6 9,10926 6,24734 6,24682 6,24594 5,89826 5,91497 6,25189 5,91757 5,911 7 10,31922 6,88711 6,88434 6,88417 6,58556 6,59382 6,88643 6,59206 6,59326 8 11,34672 7,62034 7,62162 7,62201 7,26284 7,27024 7,62459 7,26751 7,26852 В работе использовалась кодировка v : {0,... , 2m - 1} ^ Q2 m элементов аддитивной группы кольца вычетов (Z2m, Ш) элементами обобщенной группы кватернионов (Q2m, И), заданная условием a Li/2J, если г четно v : г ^ ,L*/2J aL' Ju, если г нечетно. Аналогичная кодировка применена для диэдральной группы. Для 8-битных подстановок S-боксов алгоритмов блочного шифрования Aes, Anubis, Belt, Crypton, Fantomas, iScream, Kalyna, Khazad, Kuznyechik, Picaro, Safer, Scream, Zorro и 4-битных подстановок алгоритмов Gift, Panda, Pride, Prince, Prost, Klein, Noekeon, Piccolo вычислена q(0,0) (s) для всех 0, 0 Е {Ф, Ш, И, о}. Результаты приведены в табл. 2 для 0, 0 Е {ф, Ш, И}. Та б л и ц а 2 q(0,0)(s) для некоторых S-боксов S-боксы (Ф, Ф) (Ф, ш) (Ф, и) (ш, Ф) (ш, ш) (ш, и) (и, Ф) (и, ш) (и, и) Aes 4 6 7 7 7 7 6 7 8 Anubis 8 8 8 8 8 6 8 7 6 Belt 8 6 6 3 7 6 4 7 7 Crypton S0 10 7 7 8 9 7 9 9 8 Crypton S1 10 8 7 8 9 10 9 9 10 Crypton S2 10 8 7 7 9 7 6 9 8 Crypton S3 10 8 7 8 9 8 7 9 8 Fantomas 16 16 16 20 12 13 16 12 13 iScream 16 16 16 16 11 14 16 11 14 Kalyna pi0 8 6 6 6 8 6 7 8 7 Kalyna pi1 8 6 7 7 6 7 6 7 7 Kalyna pi2 8 7 8 7 7 7 6 7 6 Kalyna pi3 8 7 7 7 7 7 7 6 7 Khazad 8 8 8 8 8 8 8 8 7 Kuznyechik 8 7 6 7 7 7 8 8 6 Picaro 4 7 7 7 8 7 6 8 7 Safer 128 10 10 128 2 4 128 4 8 Scream 8 10 12 12 11 12 10 10 12 Zorro 10 8 8 7 6 7 8 8 7 Prost 4 4 4 4 4 4 4 4 5 PRINCE 4 4 4 4 5 4 4 4 4 Pride 4 4 4 4 4 4 4 4 5 Gift 6 4 4 4 3 4 4 3 4 Panda 4 4 4 4 4 3 4 4 3 Klein 4 3 4 3 5 4 3 4 4 Noekeon 4 4 4 4 4 4 4 4 3 Piccolo 4 4 4 4 6 5 4 4 5

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

матрица вероятностей переходов разностей, разностно d-равномерные отображения, S-боксы, обобщённая группа кватернионов, группа диэдра, differences table, differentially d-uniform mapping, S-boxes, generalized quaternion group, dihedral group

Авторы

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

Ссылки

Canteaut A., Duval S., and Leurent G. Construction of lightweight S-boxes using Feistel and Misty structures // SAC'2015. LNSC. 2016. V.9566. P. 373-393.
Nyberg K. and Knudsen L. R. Provable security against differential cryptanalysis // CRYPTO'92. LNCS. 1993. V. 740. P. 566-574.
Nyberg K. Differential uniform mappings for cryptography // EUROCRYPT'93. LNCS. 1993. V. 765. P. 55-64.
Massey J. L. SAFER K-64: A byte-oriented block ciphering algorithm // FSE'93. LNCS. 1994. V. 809. P. 1-16.
Hawkes P. and O'Connor L. XOR and Non-XOR differential probabilities // EURO-CRYPT'99. LNCS. 1999. V. 1592. P. 272-285.
Холл М. Теория групп. М.: ИЛ, 1962.
Knuth D. The Art of Computer Programming. V. 2. Addison-Wesley, 1981.
 О свойствах максимального элемента матрицы вероятностей переходов разностей биективного отображения относительно различных групповых операций | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/57

О свойствах максимального элемента матрицы вероятностей переходов разностей биективного отображения относительно различных групповых операций | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/57