Иванов М.А. КМЗИ сети. Криптографические методы защиты информации
 Скачать 3.04 Mb.
|
|
Приложение 1 Неприводимые многочлены над GF(p), p – простое Примечания: 1. Многочлены заданы набором их коэффициентов a N a N-1 ... a i ... a 2 a 1 a 0 (например, набор 1021 соответствует многочлену x 3 + 2x + 1). 2. В скобках указан показатель многочлена, т.е. наименьшее положительное число e, при котором x e –1 делится на данный многочлен без остатка. 3. Многочлены f *(x), для которых справедливо соотношение f *(x) = x N f (x –1 ), где GF(p), ≠ 0, f (x) – многочлен степени N, уже имею- щийся в списке, не приводятся. Неприводимые многочлены над GF(2): N = 1 11 (1) N = 2 111 (3) N = 3 1011 (7) N = 4 10011 (15) 11111 (5) N = 5 100101 (31) 101111 (31) 110111 (31) N = 6 1000011 (63) 1001001 (9) 1010111 (21) 1011011 (63) 1100111 (63) N = 7 10000011 (127) 10001001 (127) 10001111 (127) 10011101 (127) 10100111 (127) 10101011 (127) 10111111 (127) 11001011 (127) 11101111 (127) N = 8 100011011 (51) 100011101 (255) 100101011 (255) 100101101 (255) 100111001 (17) 100111111 (85) 101001101 (255) 101011111 (255) 101100011 (255) 101110111 (85) 101111011 (85) 110000111 (255) 110001011 (85) 110011111 (51) 111001111 (255) 111010111 (17) 389 Неприводимые многочлены над GF(3): N = 1 11 (2) 12 (1) N = 2 101 (4) 112 (8) N = 3 1021 (26) 1022 (13) 1112 (13) 1121 (26) N = 4 10012 (80) 10022 (80) 10102 (16) 10111 (40) 10121 (40) 11021 (20) 11111 (5) 11122 (80) 12112 (80) 12121 (10) N = 5 100021 (242) 100022 (121) 100112 (121) 100211 (242) 101011 (242) 101012 (121) 101102 (121) 101122 (121) 101201 (242) 101221 (242) 102112 (121) 102122 (11) 102211 (242) 102221 (22) 110012 (121) 110021 (242) 110111 (242) 110122 (121) 111121 (242) 111211 (242) 111212 (121) 120212 (121) 120221 (242) 121112 (121) Неприводимые многочлены над GF(5): N = 1 11 (2) 12 (4) 14 (1) N = 2 102 (8) 111 (3) 112 (24) 123 (24) 124 (12) 141 (6) N = 3 1011 (62) 1014 (31) 1021 (62) 1024 (31) 1032 (124) 1033 (124) 1042 (124) 1043 (124) 1113 (124) 1114 (31) 1131 (62) 1134 (31) 1141 (62) 1143 (124) 1213 (124) 1214 (31) 1223 (124) 1312 (124) 1323 (124) 1341 (62) 390 Неприводимые многочлены над GF(7): N = 1 11 (2) 12 (6) 13 (3) 16 (1) N = 2 101 (4) 102 (12) 113 (48) 114 (24) 116 (16) 123 (48) 125 (48) 131 (8) 136 (16) 141 (8) 145 (48) 152 (24) N = 3 1002 (18) 1003 (9) 1011 (114) 1016 (57) 1021 (38) 1026 (19) 1032 (342) 1035 (171) 1041 (114) 1046 (57) 1052 (342) 1055 (171) 1062 (342) 1065 (171) 1112 (342) 1115 (171) 1124 (342) 1126 (57) 1131 (38) 1135 (171) 1143 (171) 1146 (57) 1151 (114) 1152 (342) 1153 (171) 1154 (342) 1163 (171) 1165 (171) 1214 (342) 1216 (57) 1223 (171) 1226 (57) 1235 (171) 1245 (171) 1251 (114) 1261 (114) 1262 (342) 1264 (342) 1325 (171) 1334 (342) 1336 (19) 1341 (38) 1343 (171) 1352 (342) 1354 (342) 1413 (171) 1416 (19) 1425 (171) 1432 (342) 1434 (342) 1453 (171) 1461 (114) 1513 (171) 1532 (342) 1534 (342) 1552 (342) 391 Неприводимые многочлены над GF(11): N = 1 11 (2) 12 (5) 13 (10) 15 (10) 17 (5) 1А (1) N = 2 101 (4) 103 (20) 105 (20) 111 (3) 114 (60) 116 (40) 117 (120) 118 (120) 124 (30) 125 (60) 126 (120) 12А (24) 136 (120) 138 (120) 139 (15) 13А (8) 147 (120) 148 (40) 149 (60) 151 (12) 152 (120) 153 (15) 157 (40) 15А (24) 161 (12) 172 (120) 175 (30) 183 (60) 192 (40) 1А1 (6) 392 Приложение 2 Примитивные многочлены над GF(2) Примечание: многочлены заданы индексами N, i, 0 своих нену- левых коэффициентов, например, строка 89 38 0 соответствует многочлену x 89 + x 38 + 1. 2 1 0 3 1 0 4 1 0 5 2 0 6 1 0 7 1 0 8 6 5 1 0 9 4 0 10 3 0 11 2 0 12 7 4 3 0 13 4 3 1 0 13 4 3 1 0 14 12 11 1 0 15 1 0 16 5 3 2 0 17 3 0 18 7 0 19 6 5 1 0 20 3 0 21 2 0 22 1 0 23 5 0 24 4 3 1 0 25 3 0 26 8 7 1 0 27 8 7 1 0 28 3 0 29 2 0 30 16 15 1 0 31 3 0 34 15 14 1 0 35 2 0 36 11 0 37 12 10 2 0 38 6 5 1 0 39 4 0 40 21 19 2 0 41 3 0 42 23 22 1 0 43 6 5 1 0 44 27 26 1 0 45 4 3 1 0 46 21 20 1 0 47 5 0 48 28 27 1 0 49 9 0 50 27 26 1 0 51 16 15 1 0 52 3 0 53 16 15 1 0 54 37 36 1 0 55 24 0 56 22 21 1 0 57 7 0 58 19 0 59 22 21 1 0 60 1 0 61 16 15 1 0 62 57 56 1 0 63 1 0 64 4 3 1 0 67 10 9 1 0 68 9 0 69 29 27 2 0 70 16 15 1 0 71 6 0 72 53 47 6 0 73 25 0 74 16 15 1 0 75 11 10 1 0 76 36 35 1 0 77 31 30 1 0 78 20 19 1 0 79 9 0 80 38 37 1 0 81 4 0 82 38 35 3 0 83 46 45 1 0 84 13 0 85 28 27 1 0 86 13 12 1 0 87 13 0 88 72 71 1 0 89 38 0 90 19 18 1 0 91 84 83 1 0 92 13 12 1 0 93 2 0 94 21 0 95 11 0 96 49 47 2 0 97 6 0 393 32 28 27 1 0 33 13 0 65 18 0 66 10 9 1 0 98 11 0 Примитивные многочлены вида x N + x i + 1, где N – число Мерсенна: 17 11 0 17 12 0 17 14 0 31 18 0 31 24 0 31 25 0 31 28 0 89 38 0 127 64 0 127 90 0 127 97 0 127 112 0 127 120 0 521 353 0 521 363 0 521 473 0 521 489 0 607 334 0 607 460 0 607 502 0 1279 861 0 1279 1063 0 2281 1252 0 2281 1366 0 2281 1566 0 3217 2641 0 3217 3150 0 Примитивные многочлены вида x N + x i + 1, где i = 8, 16, 32, 64, 128: 15 8 0 39 8 0 63 32 0 65 32 0 81 16 0 97 64 0 105 16 0 119 8 0 127 64 0 135 16 0 159 128 0 175 16 0 177 8 0 225 32 0 521 320 Примитивные многочлены вида x N + x i + 1, где (i, 2 N –1) = 1: 15 7 0 18 7 0 20 3 0 23 5 0 23 9 0 25 3 0 25 7 0 28 3 0 28 9 0 28 13 0 33 13 0 36 11 0 39 14 0 41 3 0 73 31 0 79 9 0 79 19 0 81 35 0 84 13 0 87 13 0 94 21 0 95 11 0 95 17 0 97 6 0 97 12 0 97 33 0 97 34 0 98 11 0 135 22 0 140 29 0 142 21 0 145 52 0 145 69 0 148 27 0 150 53 0 151 3 0 151 9 0 151 15 0 151 31 0 151 39 0 151 43 0 151 45 0 207 43 0 212 105 0 218 11 0 218 15 0 218 71 0 218 83 0 225 74 0 225 88 0 225 97 0 225 109 0 231 26 0 231 34 0 234 31 0 234 103 0 378 43 0 378 107 0 380 47 0 390 89 0 396 25 0 396 109 0 396 169 0 396 175 0 404 189 0 412 147 0 428 105 0 436 165 0 460 61 0 462 73 0 394 41 20 0 47 5 0 47 14 0 47 20 0 47 21 0 49 9 0 49 12 0 49 15 0 49 22 0 52 19 0 52 21 0 55 24 0 57 7 0 57 22 0 58 19 0 60 11 0 63 5 0 63 31 0 65 18 0 68 9 0 68 33 0 71 6 0 71 9 0 71 18 0 71 20 0 71 35 0 73 25 0 73 28 0 98 27 0 100 37 0 103 9 0 103 13 0 103 30 0 103 31 0 105 17 0 105 37 0 105 43 0 105 52 0 106 15 0 108 31 0 111 10 0 111 49 0 113 9 0 113 15 0 113 30 0 118 33 0 118 45 0 119 38 0 121 18 0 129 5 0 129 31 0 129 46 0 130 8 0 132 29 0 134 57 0 135 11 0 151 51 0 151 63 0 151 66 0 151 67 0 151 70 0 159 31 0 159 34 0 159 40 0 161 18 0 161 39 0 161 60 0 170 23 0 172 7 0 174 13 0 175 6 0 175 18 0 175 57 0 177 22 0 177 88 0 178 87 0 183 56 0 194 87 0 198 65 0 201 14 0 201 17 0 201 59 0 201 79 0 202 55 0 236 5 0 250 103 0 252 67 0 255 52 0 255 55 0 255 82 0 258 83 0 266 47 0 268 25 0 268 61 0 270 53 0 270 133 0 282 35 0 282 43 0 284 119 0 286 69 0 286 73 0 292 97 0 294 61 0 300 7 0 300 73 0 300 91 0 316 135 0 322 67 0 332 123 0 350 53 0 364 67 0 366 29 0 475 15 0 476 141 0 484 105 0 508 109 0 524 167 0 532 37 0 540 179 0 540 211 0 564 163 0 588 151 0 588 253 0 708 278 0 708 301 0 756 119 0 756 349 0 780 299 0 804 295 0 828 205 0 395 Приложение 3 Криптоалгоримы с архитектурой «Куб» Трехмерный блок замены Блоки замены (S-блоки) являются важнейшим элементом криптографических примитивов. Именно от качества исполь- зуемых S-блоков зависят непредсказуемость формируемых псевдослучайных последовательностей и криптостойкость ал- горитмов хеширования, блочного и поточного шифрования. Рассматриваются два новых способа построения S-блоков, бло- ки замены могут быть названы 2D и 3D S-блоками соответст- венно. Алгоритм функционирования 2D S-блока. Представим вход- ные и выходные блоки данных, а также все промежуточные ре- зультаты преобразований в виде квадратного массива битов размерностью N N, где N – разрядность используемых узлов замены. Таким образом, объем ключевой информации, одно- значно определяющей логику работы каждого узла замены, ра- вен N 2 N Последовательность выполнения операции A = SubSquare[A] (или, кратко, A = S sq [A]), замены квадратного массива битов A размерностью N N, имеет следующий вид: 1) разбиение входного массива A на N строк R i длины N, i = 0, 1, …, (N – 1); 2) замена строк SubRows, т.е. преобразование каждого i-го N-разрядного двоичного набора R i с использованием со- ответствующего узла замены S i : R i = S i [R i ]; 3) разбиение получившегося массива A = SubRows[A] на N столбцов C i длины N 4) замена столбцов SubColumns, т.е. преобразование каж- дого i-го N-разрядного двоичного набора C i с использо- ванием соответствующего узла замены S i+N : C i = S i+N [C i ]; 5) результатом замены является A = SubColumns[A]. В частном случае, когда используется только одна таблица замен, т.е. S i = S, получаем следующий алгоритм: 1) разбиение входного массива A на N строк R i длины N; 396 2) замена строк SubRows, т.е. преобразование каждого i-го N-разрядного двоичного набора R i : R i = S[R i ], i = 0, 1, …, (N – 1); 3) разбиение получившегося массива A = SubRows[A] на N столбцов C i длины N; 4) замена столбцов SubColumns,т.е. преобразование каж- дого i-го N-разрядного двоичного набора C i : C i = S[C i ]; 5) результатом замены является A = SubColumns[A]. Алгоритм функционирования 3D S-блока.Представим вход- ные и выходные блоки данных, а также все промежуточные ре- зультаты преобразований в виде кубического массива битов размерностью N N N, где N – разрядность используемых узлов замены. Таким образом, объем ключевой информации, однозначно определяющей логику работы каждого узла заме- ны, равен N 2 N Последовательность выполнения операции замены кубиче- ского массива битов A = SubCube[A] (или кратко, A = S cu [A]) размерностью N N N имеет следующий вид: 1) разбиение входного массива A на N слоев L xi размерно- стью N N вдоль оси x, i = 0, 1, …, (N – 1); 2) замена слоев вдоль оси x SubLayersX, т.е. выполнение преобразования L xi = SubSquare[L xi ] каждого i-го слоя L xi с использованием соответствующих узлов замены; 3) разбиение получившегося массива A = SubLayersX[A] на N слоев L yi размерностью N N вдоль оси y; 4) замена слоев вдоль оси y SubLayersY, т.е. выполнение преобразования L yi = SubSquare[L yi ] каждого i-го слоя L yi с использованием соответствующих узлов замены; 5) разбиение получившегося массива A = SubLayersY[A] на N слоев L zi размерностью N N вдоль оси z; 6) замена слоев вдоль оси z SubLayersZ, т.е. выполнение преобразования L zi = SubSquare[L zi ] каждого i-го слоя L zi с использованием соответствующих узлов замены; 7) результатом замены является A = SubLayersZ [A]. 397 Наиболее очевидное назначение предлагаемых алгоритмов – преобразование N 2 - и N 3 -разрядных блоков данных с использо- ванием таблицы замен размерности N × 2 N Трехмерный итеративный криптоалгоритм DOZEN Рассмотрим 3D преобразование данных с архитектурой «Куб», названное авторами DOZEN (dozen – англ. дюжина; на- звание обусловлено тем, что алгоритм имеет двенадцать основ- ных шагов, как будет раскрыто далее). Основные принципы проекта: представление входных и выходных блоков данных, всех промежуточных результатов преобразований и раундовых ключей (RoundKeys) K 0 , K 1 , K 2 , K 3 в виде кубического мас- сива байтов 4 4 4; определение понятия слоя (Layer) − квадратного массива байтов 4 4; представление i-го раундового ключа в виде четырех под- ключей (RoundSubKeys) K i0 , K i1 , K i2 , K i3 , , 3 , 2 , 1 i каждый из которых суть квадратный массив байтов 4 4; трехмерное преобразование блока данных по слоям вдоль осей x, y, z; включение в состав операции преобразования слоя (T_Layer) четырех шагов – замены байтов (SubBytes), пе- ремешивания строк (МixRows), перемешивания столбцов (MixColumns), сложения (XOR) с раундовым подключом (AddRoundSubKey); использование при выполнении преобразований МixRow и MixColumn о перации, использующейся в криптоалгоритме Rijndael при реализации преобразования MixColumn. Последовательность преобразования блока данных размером 512 бит (4 4 4 8): разбиение блока данных на слои (Layers) L x0 , L x1 , L x2 , L x3 вдоль оси x; первый раунд: стохастическое преобразование слоев (T_Layer) L x0 , L x1 , L x2 , L x3 путем выполнения для каждого 398 слоя L xk шестнадцати (по числу байтов) операций SubByte, четырех (по числу строк) операций МixRow, четырех (по числу столбцов) операций MixColumn и операции AddRoundSubKey; разбиение блока данных на слои L y0 , L y1 , L y2 , L y3 вдоль оси y; второй раунд: стохастическое преобразование слоев L y0 , L y1 , L y2 , L y3 путем выполнения для каждого слоя L yk шестна- дцати (по числу байтов) операций SubByte, четырех (по числу строк) операций МixRow, четырех (по числу столб- цов) операций MixColumn и операции AddRoundKey; разбиение блока данных на слои L z0 , L z1 , L z2 , L z3 вдоль оси z; третий раунд: стохастическое преобразование слоев L z0 , L z1 , L z2 , L z3 путем выполнения для каждого слоя L zk шестнадца- ти (по числу байтов) операций SubByte, четырех (по числу строк) операций МixRow, четырех (по числу столбцов) операций MixColumn и операции AddRoundKey. Окончательно, получаем следующую последовательность 3D-преобразований: Шаг 0. Сложение с раундовым ключом K 0 (AddRoundKey K 0 ). Первый раунд: Шаг 1. Преобразование слоя L x0 (T_Layer L x0 ). Шаг 2. Преобразование слоя L x1 (T_Layer L x1 ). Шаг 3. Преобразование слоя L x2 (T_Layer L x2 ). Шаг 4. Преобразование слоя L x3 (T_Layer L x3 ). Второй раунд: Шаг 5. Преобразование слоя L y0 (T_Layer L y0 ). Шаг 6. Преобразование слоя L y1 (T_Layer L y1 ). Шаг 7. Преобразование слоя L y2 (T_Layer L y2 ). Шаг 8. Преобразование слоя L y3 (T_Layer L y3 ). Третий раунд: Шаг 9. Преобразование слоя L z0 (T_Layer L z0 ). Шаг 10. Преобразование слоя L z1 (T_Layer L z1 ). Шаг 11. Преобразование слоя L z2 (T_Layer L z2 ). Шаг 12. Преобразование слоя L z3 (T_Layer L z3 ). 399 Особенностями предложенного преобразования являются байт-ориентированная структура и высокая степень паралле- лизма на уровне инструкций, позволяющая достичь высокой производительности работы алгоритма для гибридных вычис- лительных систем CPU/GPU. Михаил Александрович Иванов Илья Владимирович Чугунков Криптографические методы защиты информации в компьютерных системах и сетях Учебное пособие Под редакцией М.А. Иванова Редактор Е.Г. Станкевич Оригинал-макет подготовлен М.А. Ивановым Подписано в печать 15.11.2011. Формат 60×84 1/16. Печ. л. 2 5,0. Уч.-изд. л. 20,0. Тираж 130 экз. Изд. № 1/37 Заказ № 3 _________________________________________________________________ Национальный исследовательский ядерный университет «МИФИ». 115409, Москва, Каширское ш., 31 ООО «Полиграфический комплекс «Курчатовский». 144000, Московская область, г. Электросталь, ул. Красная, 42 |