MDS-матрицы, построенные с помощью сопровождающих матриц многочленов и подстановочных матриц | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/59

MDS-матрицы, построенные с помощью сопровождающих матриц многочленов и подстановочных матриц

Предлагается новый метод построения MDS-матриц порядка k = 4, 6 над полем GF(256), основанный на возведении в степень сопровождающих матриц некоторых многочленов и последующим сложением с подстановочной матрицей. Оценивается число операций сложения по модулю 2, необходимых для вычисления образов векторов при действии соответствующих линейных преобразований. Построенные матрицы представляют интерес для использования в шифрсистемах, ориентированных на низкоресурсную реализацию.

Construction methods for mds matrices using companion and permutation matrices for lightweight cryptography.pdf Введение Пусть Q = GF(2n) = GF(2)[x]/g(x) - конечное поле из 2n элементов, где g(x) - неприводимый многочлен степени n над полем GF(2). Множество всех вектор-строк длины k над полем Q обозначим через Qk, а множество всех матриц размера k х k над полем Q - через Qk,k. Определение 1 [1]. Показатель рассеивания р матрицы A G Qfc,fc определяется равенством р(А) = min{w(a) + w(aA)}, a=0 где w(a) -вес Хэмминга вектора a G Qk, то есть количество его ненулевых элементов. Определение 2 [1, 2]. Матрица A G Qk,k называется MDS-матрицей, если р(А) = = k + 1. + afc-1xfc 1 + xk G Q[x]. Определение 3 [2]. Пусть f (x) = a0 + a1x + a2x2 + Матрица Sf G Qk,k, определённая равенством 010 0 0 1 0 0 1 Sf = 000 yao «1 «2 ''' afc-1J называется сопровождающей матрицей многочлена f (x). В [3] предложено оценивать сложность реализации линейного слоя в блочных шифрсистемах подсчётом количества вентилей XOR, необходимых для реализации умножения элемента над полем. Показано, что, в отличие от распространённого мнения, элементы с высоким весом Хэмминга также могут иметь низкую сложность реализации. Будем использовать эту новую характеристику для расчёта сложности реализации линейного слоя. Определение 4 [3]. XOR-сложностью элемента a Е Q в фиксированном базисе назовём количество операций XOR, необходимых для реализации умножения a на произвольный элемент в Е Q. Пример 1 [3]. Пусть GF(23) = GF(2)[x]/(x3 + x + 1) и {1,a,a2} - базис пространства GF(23) над полем GF(2). Умножение элемента a4 = a Ф a2 на произвольный элемент в = 6o ф ^a ф 62a2, где 6 Е GF(2), имеет вид (bo Ф 6ia Ф b2a2)(a ф a2) = (60 Ф 62) Ф (bo Ф bi)a Ф (60 Ф 61 Ф b2)a2. Элемент a4e можно отождествить с элементом из GF(2)3 вида (6o Ф 62, 6o Ф 6i, 6o Ф 6i Ф 62), в котором есть четыре операции XOR. Таким образом, XOR-сложность элемента a4 равна 4. Будем обозначать XOR-сложность элемента a Е Q как XOR(a). Нетрудно проверить, что XOR(O) = XOR(1) = 0. XOR-сложность строки с номером i матрицы M = (mij)kxk можно найти по формуле [3] k £ XOR(mi,j) + (li - 1)n, j=i где /j - количество ненулевых элементов в i-й строке. Тогда можно определить XOR-сложность матрицы M = (m-ij) Е Qk,k по формуле XOR(M) = ^Г ^ XOR(mj,j) + n E (/j - 1). i=ij=i i=i Пусть f (x) = ao + aix + a2x2 + ... + ak-ixk-i + xk и {ci,..., cs} - множество всех различных ненулевых коэффициентов многочлена f (x). В [4] показано, что XOR(Sf ) = Е XOR(cj) + (/f - 1)n; (1) j=i XOR(S}) = r ■ XOR(Sf) (2) для любого r Е N, где /f - количество ненулевых элементов в последней строке матрицы Sf. 1. Построение MDS-отображений Определение 5. Будем говорить, что линейное отображение L : Qk -у Qk, заданное по правилу L(a) = a ■ Ay(L), является MDS-отображением, если p(AY(L)) = k +1, где AY(L) -матрица линейного отображения L в фиксированном базисе 7 пространства Qk. В шифрсистемах, ориентированных на низкоресурсную реализацию, существенное значение имеет XOR-сложность используемых криптографических примитивов. Нахождение MDS-отображений с небольшим значением данного параметра является актуальной проблемой. Предложим способ построения MDS-отображений над полем GF(28) вида C},P : a ^ a(f/2 0 P) \\T (3) где Sf - сопровождающая матрица многочлена f (x) Е GF(28)[x] степени k; P - подстановочная матрица порядка k. С целью эффективной реализации коэффициенты многочлена f (x) выберем из множества {0,1, а, а-1, а2, а3}, где а - произвольный примитивный элемент поля GF(28). Пусть k = 4, A1(x) = x4 + ах3 + а, А2 = x4 + а2х3 + а2, А3 = x4 + ах3 + а А4 = x4 + «3x3 + а3 и /0 0 1 0\\ 10 0 0 0 10 0 \\0 0 0 1/ Тогда L^p (a) = a(S4 0 Pi)T, i = 1,..., 4. Пусть Лг - линейное преобразование, осуществляемое регистром сдвига с характеристическим многочленом Ai(x), i = 1,..., 4. Тогда действие отображения L\\. p на вектор a = (ao, a1 ,а2, а3) Е GF(28)4 можно схематично представить в виде рис. 1. Тогда L£. P2 (a) = a(S£. 0 Р2Г, i =1,..., 4. L L aq ax a2 a^ a2 aQ ax a^ Рис. 1. Действие отображения L4. pi при i = 1, 2, 3, 4 Теорема 1. Для любого i = 1,... , 4 отображение L\\. p является MDS-отображе-нием. Рассмотрим теперь отображения вида (3) в случае k = 6. Пусть а Е GF(28) - корень многочлена x8 + x7 + x6 + x +1, r1(x) = x6 + a-1x5 + «x4 + а, r2(x) = x6 + аx5 + + а-1 x4 + а, r3(x) = x6 + «3x5 + x4 + а, r4(x) = x6 + «3x5 + x4 + а-1 и 1 P1 P2 2= 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1, , 4. Пусть Tj - линейное преобразование, осуществляемое регистром сдвига с характеристическом многочленом Tj(x) для любого i = 1,..., 4. Тогда действие отображения L6. р на вектор a = (а0, «ъ «2, а3, а4, а5) G GF(28)6 можно схематично представить в виде рис. 2. Рис. 2. Действие отображения C^ р2 при i = 1,..., 4 aQ ax a2 a^ a^ a^ aQ a2 a^ a^ a^ Теорема 2. Для любого i = 1,..., 4 отображение L6. P2 является MDS-отображе-нием. 2. XOR-сложность некоторых MDS-отображений Пусть Q = GF(28) = GF(2)[x]/x8 + x7 + x6 + x + 1, в - корень многочлена x8 + x7 + +x6+x + 1. Записи табл. 1 соответствуют XOR-сложности элементов поля Q, заданных в шестнадцатеричном виде. Например, для элемента в = в5 + в2 + в + 1 G GF(28) используется запись 0x27. Тогда XOR(e) = XOR(Ox27) = 28. Таблица 1 XOR-сложность элементов поля Q XOR .0 .1 .2 .3 .4 .5 .6 .7 .8 .9 .a .b .c .d .e .f 0. 0 0 3 9 5 11 10 14 7 11 12 18 14 20 13 21 1. 12 18 11 19 13 17 18 24 17 23 22 26 12 20 23 29 2. 16 22 21 25 11 19 22 28 17 23 16 24 18 22 23 29 3. 20 24 25 31 27 33 26 34 11 19 22 28 24 30 29 33 4. 20 24 23 29 25 31 26 34 11 19 20 26 22 28 29 33 5. 18 24 25 29 15 23 24 30 19 25 20 28 22 26 25 31 6. 24 30 25 33 27 31 30 36 29 35 36 40 26 34 35 41 7. 10 18 19 25 21 27 28 32 25 29 28 34 30 36 31 39 8. 25 21 26 20 24 22 31 27 30 26 33 31 27 21 36 32 9. 11 5 20 16 22 18 25 23 22 20 29 25 31 27 32 26 a. 19 17 26 22 28 24 29 23 14 8 23 19 25 21 28 26 b. 21 17 24 22 18 12 27 23 22 18 23 17 21 19 28 24 c. 27 23 32 30 26 20 33 29 28 24 31 25 29 27 34 30 d. 31 29 36 32 38 34 41 35 26 20 33 29 35 31 40 38 e. 9 3 16 12 18 14 23 21 20 18 25 21 27 23 30 24 f. 25 21 28 22 26 24 31 27 30 26 35 33 29 23 36 32 Используя результаты из табл. 1, рассмотрим отображения из теорем 1 и 2. Для вычисления a(S®.)T ф a(Pi)T = b необходимо 4 • 8 = 32 операции XOR. Аналогично, для вычисления a(S9)T Фa(P2)T = b необходимо 6• 8 = 48 операций XOR. Тогда с помощью равенств (2) получим, что для пары (f P) f(Ai,pi), k = 4, f ) \\(Ti, P2), k = 6 3k справедливо равенство XOR(LkP) = - XOR (Sf) + 8k. f 2 Пусть hi(x) = x4 + в2x3 + x2 + fix +1, hv(x) = x4 + (в + 1)x3 + x2 + вх + 1, h3(x) = x4 + в2x3 + x2 + x + в e GF(2n)[x]. В [5] показано, что при некоторых в е GF(2n) матрица S^. является MDS-матрицей для любого i =1, 2, 3. В работе [2] авторы использовали многочлены g1(x) = x6+2x5+8x4+5x3+8x2+2x+1 и g2(x) = x6 + 4x5 + x4 + 2x3 + x2 + 3x + 2 для построения MDS-матриц размеров 6 x 6, используемых в семействе хэш-функции PHOTON, ориентированных на низкоресурсную реализацию. Они получили, что над полем GF(28) = GF(2)[x]/x8 + x4 + x3 + x + 1 матрица S|. является MDS-матрицей, i = 1, 2. Заметим, что среди многочленов вида g1 (x) = x6 + вx5 + в3x4 + (в2 Ф 1)x3 + в3x2 + вx +1, g2 (x) = x6 + в2x5 + x4 + вx3 + x2 + (в ф 1)x + в для некоторого в е GF(28) найдутся многочлены g1(x) и g2(x) соответственно. С помощью значений из табл. 1 и равенств (1) и (2) при a = в = 0x02 получены результаты, приведённые в табл. 2 и 3. Из таблиц следует, что метод построения MDS-отображений на множествах Qk при k = 4 и 6, предложенный в данной работе, позволяет осуществить менее затратную реализацию, чем с использованием отображений из работ [2, 5]. Таблица 2 Сравнение параметра XOR-сложность для MDS-отображений множества Q4 MDS-отображения C

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

MDS-матрицы, сопровождающие матрицы многочленов, подстановочные матрицы, конечные поля, низкоресурсная криптография, XOR-сложность, MDS-matrices, companion matrices, permutation matrices, LFSR, finite field, lightweight cryptography, XOR-count

Авторы

ФИООрганизацияДополнительноE-mail
Кой Пуэнте ОливерООО «Центр сертификационных исследований»научный сотрудникo.coypuente@gmail.com
Всего: 1

Ссылки

Augot D. and Finiasz M. Direct construction of recursive MDS diffusion layers using shortened BCH codes // LNCS. 2014. V.8540. P. 3-17.
Guo J., Peyrin T., and Poschmann A. The PHOTON family of lightweight hash functions // LNCS. 2011. V. 6841. P. 222-239.
Sarkar S. and Sim S. M. A deeper understanding of the XOR count distribution in the context of lightweight cryptography // LNCS. 2016. V.9646. P. 167-182.
Toh D., Teo J., Khoo K., and Sim S. M. Lightweight MDS serial-type matrices with minimal fixed XOR count // LNCS. 2018. V. 10831. P. 51-71.
Gupta K. C. and Ray I. G. On constructions of MDS matrices from companion matrices for lightweight cryptography // LNCS. 2013. V.8128. P. 29-43.
 MDS-матрицы, построенные с помощью сопровождающих матриц многочленов и подстановочных матриц | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/59

MDS-матрицы, построенные с помощью сопровождающих матриц многочленов и подстановочных матриц | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/59