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

Анотація наукової статті з математики, автор наукової роботи - Кой Пуенте Олівер


Construction methods for mds matrices using companion and permutation matrices for lightweight cryptography

In this work, we propose a new construction method of MDS-matrices of dimension k = 4,6 by means of summation of a power r of the companion matrix of a certain polynomial and a fixed permutation matrix over the finite field GF (28). The method is represented by the expression S ^ + P for a polynomial f (x) = = xk + fk-1xk-1 + ... + f1x + f0, where Sf is the companion matrix of the polynomial f (x), P is a permutation matrix, r = 3k / 2, and the coefficients fi? {0,1, a, a-1, a2, a3}. For its effective implementation, it is proposed to apply Sf as a linear feedback shift register with characteristic polynomial f (x) and P as a Feistel network with k entrances. The XOR-count metric is used to show the effectiveness of the proposed method in algorithms that require low implementation cost.


Область наук:

  • Математика

  • Рік видавництва: 2019


    Журнал: Прикладна дискретна математика. додаток


    Наукова стаття на тему 'MDS-МАТРИЦІ, ПОБУДОВАНІ ЗА ДОПОМОГОЮ СУПРОВОДЖУЮЧИХ матриць многочленів і підстановлювальний матриць'

    Текст наукової роботи на тему «MDS-МАТРИЦІ, ПОБУДОВАНІ ЗА ДОПОМОГОЮ СУПРОВОДЖУЮЧИХ матриць многочленів і підстановлювальний матриць»

    ?5. Antony M. Discrete Mathematics of Neural Networks: Selected Topics. SIAM, Philadelphia, 2001..

    621.391: 519.7 Б01 10.17223 / 2226308Х / 12/59

    МБ8-МАТРИЦІ, ПОБУДОВАНІ ЗА ДОПОМОГОЮ СУПРОВОДЖУЮЧИХ матриць многочленів і підстановлювальний матриць

    О. Кой Пуенте

    Пропонується новий метод побудови ИБЯ-матриць порядку до = 4, 6 над полем ОР (256), заснований на зведенні в ступінь супроводжуючих матриць деяких многочленів і подальшим складанням з подстановочной матрицею. Оцінюється число операцій додавання по модулю 2, необхідних для обчислення образів векторів при дії відповідних лінійних перетворень. Побудовані матриці представляють інтерес для використання в шіфрсістемах, орієнтованих на нізкоресурсную реалізацію.

    Ключові слова: ИВБ-матриці, які супроводжують матриці многочленів, підстановочні матриці, кінцеві поля, нізкоресурсная криптографія, КСК-складність.

    Вступ

    Нехай (= ОЕ (2га) = РЄ (2) [х] / д (х) - кінцеве поле з 2П елементів, де д (х) - не приводиться многочлен ступеня п над полем РЄ (2). Безліч всіх вектор-рядків довжини до над полем (позначимо через (до, а безліч всіх матриць розміру до х до над полем (- через (до, до.

    Визначення 1 [1]. Показник розсіювання р матриці А Е (до, до визначається рівністю

    р (А) = тт {-№ (а) + -ЦаА)},

    а = 0

    де '№ (а) -вага Хеммінга вектора а Е (до, тобто кількість його ненульових елементів.

    Визначення 2 [1, 2]. Матриця А € (до, до називається МББ-матрицею, якщо р (А) = = до + 1.

    Визначення 3 [2]. Нехай f (x) = а 0 + a1x + a2x2 + Матриця Sf G Qk, k, певна рівністю

    + Ak-ixk 1 + xk G Q [x].

    Sf =

    / 0 10 0 0 1

    000

    0 0

    1

    yao a \ u2 • • • ak-1J

    називається супроводжує матрицею многочлена f (x).

    В [3] запропоновано оцінювати складність реалізації лінійного шару в блокових шіфрсістемах підрахунком кількості вентилів XOR, необхідних для реалізації

    множення елемента над полем. Показано, що, на відміну від поширеної думки, елементи з високим вагою Хеммінга також можуть мати низьку складність реалізації. Будемо використовувати цю нову характеристику для розрахунку складності реалізації лінійного шару.

    Визначення 4 [3]. Хоі-складністю елемента а Е Q в фіксованому базисі назвемо кількість операцій хоі, необхідних для реалізації множення а на довільний елемент в Е Q.

    Приклад 1 [3]. Нехай ОЕ (23) = ОЕ (2) [х] / (х3 + х + 1) і {1, а, а2} - базис простору ОЕ (23) над полем РЄ (2). Множення елемента а4 = а Ф А2 на довільний елемент в = 6о Ф ^ а Ф 62а2, де 6г € РЄ (2), має вигляд

    (Ьо Ф 61а Ф Ь2а2) (а Ф А2) = (6о Ф 62) Ф (6о Ф 6 ^ а Ф (6о Ф 61 Ф 62) А2.

    Елемент а4в можна ототожнити з елементом з ОЕ (2) 3 види

    (6о Ф 62, 6о Ф 61, 6о Ф 61 Ф 62),

    в якому є чотири операції хоі ,. Таким чином, хоі-складність елемента а4 дорівнює 4.

    Будемо позначати хоі-складність елемента а Е Q як ХО ^ а). Неважко перевірити, що ХОР (О) = ХОЩ1) = 0. хоі-складність рядки з номером г матриці М = (тг, 3) КХК можна знайти за формулою [3]

    до

    Е ХОЩт ^) + (/ г - 1) п,

    3 = 1

    де 1г - кількість ненульових елементів в г-й рядку. Тоді можна визначити хоі-складність матриці М = (тг, з) Е Qk, k за формулою

    ХОР (М) =? ? ХО ^ Шгз) + п? (До - 1).

    г = 13 = 1 г = 1

    Нехай f (х) = ат + а1х + а2х2 + ... + ак-1хк-1 + хк і {с1, ..., С5} - безліч всіх різних ненульових коефіцієнтів многочлена f (х). В [4] показано, що

    ХООД) = Е ХО ^) + (/ - 1) п; (1)

    3 = 1

    ХО ^) = г | ХО ^ /) (2)

    для будь-якого г Е N де / - кількість ненульових елементів в останньому рядку матриці 5 /.

    1. Побудова ИЮВ-відображень Визначення 5. Будемо говорити, що лінійне відображення Ь: Qk -> Qk, заданий за правилом

    Ь (а) = а | А7 (Ь),

    є МВБ-відображенням, якщо р (А7 (Ь)) = до +1, де А7 (Ь) матриця лінійного відображення Ь в фіксованому базисі 7 простору Qk.

    У шіфрсістемах, орієнтованих на нізкоресурсную реалізацію, істотне значення має хоі, -складність використовуваних криптографічних примітивів. Знаходження МВБ-відображень з невеликим значенням даного параметра є актуальною проблемою.

    Запропонуємо спосіб побудови МББ-відображень над полем ОЕ (28) виду

    СКР: а ^ а (^ / 2 0 Р)

    \ Т

    (3)

    де Sf - супроводжує матриця многочлена / (ж) Е ОЕ (28) [ж] ступеня к; Р - підставкова матриця порядку к. З метою ефективної реалізації коефіцієнти многочлена / (ж) виберемо з безлічі {0,1, а, а-1, а 2, а3}, де а - довільний примітивний елемент поля ОЕ (28).

    Нехай к = 4, А1 (ж) = Ж4 + аж3 + а, А2 = Ж4 + а2ж3 + А2, А3 = Ж4 + аж3 + а

    1

    А4 = Ж4 + а3ж3 + а3 і

    Р1

    / 0 0 1 0 \

    10 0 0

    0 10 0

    \ 0 0 0 1 /

    Тоді Сд.р (а) = а ^ 0 А) т, г = 1, ..., 4.

    Нехай Лг - лінійне перетворення, здійснюване регістром зсуву з характеристичним многочленом Аг (ж), г = 1, ..., 4. Тоді дія відображення С4, р на

    вектор а = (а0, а1, а2, а3) Е ОЕ (28) 4 можна схематично представити у вигляді рис. 1.

    і

    ад а ^

    Мал. 1. Дія відображення С \. р1 при г = 1, 2, 3, 4

    Теорема 1. Для будь-якого г = 1, ..., 4 відображення С \. р є МББ-відображена-ням.

    Розглянемо тепер відображення виду (3) в разі к = 6. Нехай а Е ОЕ (28) - корінь многочлена ж8 + Ж7 + Ж6 + ж +1, т1 (ж) = Ж6 + а-1ж5 + аж4 + а, т2 ( ж) = Ж6 + аж5 + + а-1 Ж4 + а, т3 (ж) = Ж6 + а3ж5 + Ж4 + а, Т4 (ж) = Ж6 + а3ж5 + Ж4 + а-1 і

    Р2

    2 =

    Тоді ??. Р2 (а) = 0 Р2) т, г = 1, ..., 4.

    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.

    ад а ^ А2 а ^

    Нехай Т - лінійне перетворення, здійснюване регістром зсуву з характеристичний многочленом ТДХ) для будь-якого r = 1, ..., 4. Тоді дія відображення? р на вектор а = (а0, Я'А2, аз, а4, а5) € ОЕ (28) 6 можна схематично представити у вигляді рис. 2.

    а ^ аз а ^ а ^

    А2 аз а ^ а ^

    Мал. 2. Дія відображення р2 при г = 1, ..., 4

    Теорема 2. Для будь-якого г = 1, ..., 4 відображення Р2 є МББ-відображена-ням.

    2. хоі-складність деяких МЮ8-відображень

    Нехай ф = ОЕ (28) = ОЕ (2) [х] / х8 + х7 + х6 + х + 1, в - корінь многочлена х8 + х7 + + х6 + х + 1. Записи табл. 1 відповідають хоі-якої складності елементів поля ф, заданих в шістнадцятковому вигляді. Наприклад, для елемента в = В5 + В2 + у + 1 € ОЕ (28) використовується запис 0x27. Тоді ХОР (в) = Х0 ^ 0х27) = 28.

    Таблиця 1

    Хоі, -складність елементів поля Q

    ХОР .0 .1 .2 .3 .4 .5 .6 .7 .8 .9 .а .Ь к.с. .а .е

    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

    а. 19 17 26 22 28 24 29 23 14 8 23 19 25 21 28 26

    Ь. 21 17 24 22 18 12 27 23 22 18 23 17 21 19 28 24

    с. 27 23 32 30 26 20 33 29 28 24 31 25 29 27 34 30

    а. 31 29 36 32 38 34 41 35 26 20 33 29 35 31 40 38

    е. 9 3 16 12 18 14 23 21 20 18 25 21 27 23 30 24

    ? 25 21 28 22 26 24 31 27 30 26 35 33 29 23 36 32

    Використовуючи результати з табл. 1, розглянемо відображення з теорем 1 і 2. Для обчислення а ($ д.) Т ф а (Р ^ 1) т = Ь необхідно 4 • 8 = 32 операції хоі. Аналогічно, для обчислення а (? 9) т Фа (Р2) т = Ь необхідно 6 • 8 = 48 операцій хоі ,. Тоді за допомогою рівності (2) отримаємо, що для пари

    (F р) i (Ai, pi), k = 4,) \ (Ti, P2), k = 6

    3k

    справедливо рівність XOR (LkP) = - XOR (Sf) + 8k.

    f 2

    Нехай hi (x) = x4 + в2x3 + x2 + вх +1, h2 (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<4 c<4 c<4 p4 r4 r4 r4 Sh2 Sh3 LAi, PI lA 2, Pl LA 3, Pl LA 4, Pl

    XOR-складність 128 144 128 98 110 116 122

    Таблиця 3 Порівняння параметра XOR-складність для MDS-відображень безлічі Q6

    MDS-відображення q6 Q6 r6 r6 r6 r6 Og'l Sg'2 LTi, P2 LT2, P2 LT3, P2 LT4, P2

    XOR-складність 366 342 246 246 282 282

    висновок

    У роботі запропоновано новий метод побудови MDS-матриці. Отримані MDS-матриці володіють хорошими експлуатаційними характеристиками з точки зору реалізації на обчислювальних платформах з обмеженими ресурсами.

    ЛІТЕРАТУРА

    1. Augot D. and Finiasz M. Direct construction of recursive MDS diffusion layers using shortened BCH codes // LNCS. 2014. V.8540. P. 3-17.

    2. Guo J., Peyrin T., and Poschmann A. The PHOTON family of lightweight hash functions // LNCS. 2011. V. 6841. P. 222-239.

    3. 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.

    4. 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.

    5. 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.

    УДК 519.688 DOI 10.17223 / 2226308X / 12/60

    ОБЧИСЛЮВАЛЬНІ ЕКСПЕРИМЕНТИ В КІНЦЕВИХ ДВУПОРОЖДЁННИХ БЕРНСАЙДОВИХ ГРУПАХ ПЕРІОДУ 5

    А. А. Кузнецов

    Нехай B0 (2, 5) = (ai, a2) - найбільша кінцева двупорождённая бернсайдова група періоду 5, порядок якої дорівнює 534. Для кожного елемента даної групи існує єдине уявлення виду а ^ 1 | а ^ 2 '• • •' аз44, де од? , I = 1, 2, • • •, 34. Тут а1 і а2 - породжують елементи B0 (2, 5), а3, ..., А34 - комутатори, які обчислюються рекурсивно через ai і А2. Визначимо факторгруппу групи Bo (2, 5) наступного вигляду: Bk = B0 (2, 5) / (ak + 1, • • •, a34). Очевидно, що | Bfc | = 5k. На основі проведених обчислювальних експериментів сформульована гіпотеза про діаметрі групи Bk для симетричного породжує безлічі {а1, а1, а2, а1}.

    Ключові слова: функція зростання групи, група Бернсайда.

    Справжня робота продовжує дослідження, розпочаті в [1, 2], які присвячені розробці алгоритмів для дослідження зростання в кінцевих двупорождённих групах періоду 5. В [1] основний упор зроблений на створенні алгоритмів мінімальної обчислювальної складності, а в [2] розроблено ресурсно-ефективний алгоритм, який має низьку просторову складність і зберігає обчислювальну складність на прийнятному рівні.

    Нагадаємо основні визначення [1]. Нехай G = (X). Кулею Ks радіусу s групи G будемо називати безліч всіх її елементів, які можуть бути представлені в алфавіті X у вигляді нескоротних групових слів довжини не більш s. Всі елементи однакової довжини i утворюють сферу Pi радіуса i. Одиниця групи e є порожнім

    s

    словом, довжина якого дорівнює нулю. Згідно з даними визначень, Ks = (J Pj.

    i = 0

    Для кожного цілого невід'ємного i можна визначити (сферичну) функцію зростання групи F (G), яку будемо записувати у вигляді вектора F (G) = = (F0, F1, ..., Fi, ...), де Fi = | Pj |. нехай Fs0 > 0, але Fs0 + 1 = 0, тоді s0 є

    діаметром графа Келі групи G в алфавіті породжують X, який будемо обо__1 so

    значать (G). Середній діаметр (G) дорівнює - E sFs.

    | G | s = 0

    Зауважимо, що рішення деяких завдань теорії кодування і криптографії зводиться до дослідження відповідних графів Келі. Наприклад, відкрита проблема ефективного відновлення вершин в графі Хеммінга є однією з таких завдань [3].

    Коротко опишемо алгоритми з [1, 2].

    Алгоритм 1 обчислює куля Ks фіксованого радіуса s довільної кінцевої групи G, заданої породжує безліччю X. Даний алгоритм має низьку


    Ключові слова: MDS-МАТРИЦІ /Супроводжується МАТРИЦІ многочленів /підстановлювальний МАТРИЦІ /ПРИКІНЦЕВІ ПОЛЯ /НІЗКОРЕСУРСНАЯ криптографії /XOR-Складність /MDS-MATRICES /COMPANION MATRICES /PERMUTATION MATRICES /LFSR /FINITE FIELD /LIGHTWEIGHT CRYPTOGRAPHY /XOR-COUNT

    Завантажити оригінал статті:

    Завантажити