POSSIBLE OPTIONS TO IMPROVE CRYPTOGRAPHIC RELIABILITY OF ALGORITHMS BASED ON NYBERG CONSTRUCTION

Full Text

Введение. Применительно к формированию таб- лиц замен можно выделить три основных подхода в разработке алгоритмов шифрования [1]. Одним из решений является выбор таблиц замен в процессе разработки стандарта и открытое опубликование полученных таблиц, одинаковых для всех пользователей данного алгоритма. Такой подход был реализован в алгоритме DES, а в 2015 году применен в алгоритме «Кузнечик», ставшем стандартом Рос- сийской Федерации с 2016 года [2]. Применяются также алгоритмы, в которых табли- цы замен не определены однозначно, а выбираются каждым пользователем самостоятельно. Такой подход реализован, например, в алгоритме ГОСТ 28147-89 [3; 4], долгое время являвшемся стандартом СССР и позднее многих стран СНГ. Отметим, что при над- лежащем уровне квалификации пользователь имеет возможность выбрать качественные блоки замен, притом известные только этому пользователю, что можно трактовать как дополнительное повышение стойкости шифрования. Блочный шифр Rijndael. Наиболее характерным примером третьего подхода может служить также считающийся стойким алгоритм Rijndael [5], в кото- ром блок замен полностью определяется заданием неприводимого полинома над полем Галуа [6]. В Rijndael использована конструкция Ниберг, пред- ставляющая собой отображение в виде мультипликативно обратных элементов поля Галуа GF (2k ) : На данный момент подробно исследованы нелинейные преобразования конструкции Ниберг на основе всех изоморфных и автоморфных представлений полей GF (2k ) для k £ 8 : выписаны все неприводимые полиномы над полями, вычислены криптографические показатели качества определяе- мых этими полиномами S-блоков. Таким образом, полином из (1) является не единственно возможным для построения шифра. Возможность же выбора неприводимого полинома (одного из множества в определенном смысле эквивалентных) имеет практи- ческое значение. Поэтому появилась возможность соединить плюсы подходов ГОСТа и Rijndael. В работе [5] приведена таблица криптографиче- ских характеристик S-блоков на базе полного класса неприводимых полиномов степени 8. Данные этой таблицы свидетельствуют о разнообразии выбора полиномов для использования в блочных шифрах в соответствии с решением использования того или y = x-1 modd[f (z), p], y, x ÎGF (2k ), (1) иного критерия. В связи с этим представляется актуальным расскомбинированная вместе с аффинным преобразова- нием смотрение конструкции, аналогичной AES [15], однако либо с использованием композиции неприводимых полиномов, либо с использованием в разных раундах b = A× y + a, a, b Î GF (2k ), (2) различных полиномов или их композиций, что можно считать одним из возможных вариантов повышения где f (z) = z8 + z4 + z 2 + z + 1 - неприводимый над полем GF (28 ) полином; А - невырожденная матрица стойкости алгоритма, аналогичного AES. В данной статье проведены вычисления и получены все возможные таблицы замен на основе композиции аффинного преобразования; а - вектор сдвига; p = 2 - неприводимых полиномов над GF(28). Композицией характеристика расширенного поля Галуа; 0-1 º 0 - по определению; a,b, x, y - элементы расширенного поля Галуа GF (2k ) ; рассматриваются как десятич- ные числа либо двоичные векторы, либо полиномы степени k -1 . Количественные характеристики блоков замен. Показателями качества блока замен [7-9] наиболее часто предлагаются следующие: - максимум из модулей элементов матрицы коэф- фициентов корреляции входных и выходных битов; - количество нулей в матрице коэффициентов корреляции; - нелинейность как расстояние до множества аффинных функций [10-13]; - алгебраическая степень нелинейности [14]; - период возврата подстановочной конструкции в исходное состояние. неприводимых полиномов считается последователь- ное выполнение двух операций SubBytes в каждом раунде. Определены пары полиномов, обеспечиваю- щих таблицы замен с близкими к оптимальным свой- ствами корреляционной матрицы. Табл. 1 представляет собой данные по криптогра- фическим характеристикам S-блоков, полученных в результате выполнения операции SubBytes для всех возможных неприводимых полиномов над GF(28), где сам полином записан в виде десятичных эквивалентов. Аналогичные данные были получены для компо- зиций неприводимых полиномов (в графе «Компози- ция» полиномы записаны в порядке выполнения опе- рации SubBytes). Ввиду большого объема полученных данных в данной статье хотелось бы заострить вни- мание на тех композициях, корреляционная матрица которых обладает наиболее примечательными крипто- графическими характеристиками. Полученные данные приведены в табл. 2-4. Таблица 1 Криптографические характеристики S-блоков неприводимых полиномов № п/п Полином Максимум модуля Количество нулей Степень нелинейности 1 283 0,125 4 112 112 112 112 112 112 112 112 2 285 0,125 5 112 112 112 112 112 112 112 112 3 299 0,125 10 112 112 112 112 112 112 112 112 4 301 0,125 2 112 112 112 112 112 112 112 112 5 313 0,125 7 112 112 112 112 112 112 112 112 Окончание табл. 1 № п/п Полином Максимум модуля Количество нулей Степень нелинейности 6 319 0,109375 6 112 112 112 112 112 112 112 112 7 333 0,125 7 112 112 112 112 112 112 112 112 8 351 0,125 2 112 112 112 112 112 112 112 112 9 355 0,109375 2 112 112 112 112 112 112 112 112 10 357 0,09375 6 112 112 112 112 112 112 112 112 11 361 0,125 4 112 112 112 112 112 112 112 112 12 369 0,125 5 112 112 112 112 112 112 112 112 13 375 0,109375 2 112 112 112 112 112 112 112 112 14 379 0,125 3 112 112 112 112 112 112 112 112 15 391 0,125 5 112 112 112 112 112 112 112 112 16 395 0,125 5 112 112 112 112 112 112 112 112 17 397 0,109375 5 112 112 112 112 112 112 112 112 18 415 0,109375 3 112 112 112 112 112 112 112 112 19 419 0,109375 11 112 112 112 112 112 112 112 112 20 425 0,109375 3 112 112 112 112 112 112 112 112 21 433 0,109375 2 112 112 112 112 112 112 112 112 22 463 0,125 3 112 112 112 112 112 112 112 112 23 445 0,125 0 112 112 112 112 112 112 112 112 24 451 0,109375 3 112 112 112 112 112 112 112 112 25 471 0,125 3 112 112 112 112 112 112 112 112 26 477 0,125 4 112 112 112 112 112 112 112 112 27 487 0,125 3 112 112 112 112 112 112 112 112 28 499 0,125 7 112 112 112 112 112 112 112 112 29 501 0,109375 4 112 112 112 112 112 112 112 112 30 505 0,125 8 112 112 112 112 112 112 112 112 Таблица 2 Композиции с максимальным и минимальным значением максимума модуля корреляционной матрицы № п/п Композиция Максимум модуля Количество нулей Степень нелинейности 1 301-477 0,109375 6 102 102 106 106 102 98 102 108 2 319-477 0,296875 6 102 94 106 100 104 102 104 96 3 357-433 0,109375 7 106 104 104 104 104 108 104 100 4 361-351 0,109375 4 104 106 102 102 106 106 106 102 5 369-361 0,109375 7 106 102 102 108 106 102 106 102 6 369-375 0,109375 10 104 104 108 104 104 102 104 104 7 369-395 0,109375 4 108 106 102 102 106 102 106 106 8 391-283 0,109375 3 104 104 102 104 104 104 104 104 9 391-433 0,109375 7 104 100 104 104 106 106 106 104 10 425-313 0,109375 8 104 104 104 102 106 100 106 104 11 463-357 0,109375 4 104 104 102 102 102 98 102 102 12 445-333 0,109375 13 104 104 106 106 106 102 106 100 13 451-369 0,109375 10 102 98 104 104 106 106 106 106 14 471-375 0,109375 10 100 98 104 102 106 104 106 106 15 501-425 0,109375 6 102 102 104 104 106 108 106 104 Таблица 3 Композиции с максимальным и минимальным значением нелинейности № п/п Композиция Максимум модуля Количество нулей Степень нелинейности 1 283-351 0,203125 9 104 102 102 104 110 102 110 106 2 299-285 0,171875 8 110 104 102 102 104 102 104 102 3 299-445 0,140625 5 104 104 104 106 110 108 110 106 4 301-285 0,15625 9 100 98 104 106 110 106 110 104 5 301-375 0,125 7 106 106 106 106 106 110 106 102 6 319-499 0,140625 4 110 108 106 102 108 106 108 100 7 351-299 0,171875 5 106 106 110 104 106 106 106 108 8 351-357 0,140625 4 102 102 104 106 110 104 110 102 9 355-471 0,171875 5 106 104 104 110 106 104 106 106 10 361-299 0,15625 4 106 102 104 88 102 100 102 104 11 361-477 0,125 7 110 106 104 104 106 106 106 102 12 379-415 0,1875 5 108 102 110 100 104 104 104 108 13 419-471 0,1875 7 106 106 104 110 102 96 102 104 14 425-299 0,140625 6 104 108 96 104 106 110 106 106 15 433-357 0,203125 6 110 102 106 104 104 106 104 104 16 451-319 0,140625 7 102 106 104 96 104 98 104 110 17 451-451 0,203125 8 100 102 104 100 108 106 108 110 18 451-505 0,15625 4 102 106 110 104 100 98 100 98 19 487-299 0,15625 5 104 106 104 102 106 100 106 110 20 505-283 0,125 2 106 104 102 106 104 104 104 88 21 505-285 0,171875 6 102 106 108 110 108 104 108 108 22 505-301 0,171875 6 110 104 98 106 96 104 96 106 23 505-499 0,15625 2 106 108 104 102 106 104 106 110 Таблица 4 Композиции с максимальным и минимальным количеством нулевых значений корреляционной матрицы № п/п Композиция Максимум модуля Количество нулей Степень нелинейности 1 283-445 0,171875 15 106 104 98 106 108 104 108 108 2 379-391 0,234375 15 98 104 98 102 96 104 96 108 3 487-361 0,203125 0 108 102 102 100 104 108 104 102 Таким образом, мы видим, что для обеспечения равномерной минимизации матрицы коэффициентов корреляции (согласно табл. 1) целесообразнее всего использовать полином для обращения элементов с минимальным количеством нулей, например, поли- ном 445. Применение данного полинома позволит затруднить линейную аппроксимацию шифра аффин- ными булевыми функциями, увеличивая его сопро- тивляемость атакам дифференциального криптоанализа. Эти полиномы обладают лучшими (минимальными) значениями корреляции векторов выхода и входа S-блока подстановки по сравнению с полиномом, применяемым в алгоритме Rijndael, в то же время при использовании композиции полиномов (согласно табл. 4) наиболее подходящей в этом случае окажется композиция полиномов 487-361 либо композиции полиномов 285-471, 299-369, 313-395, 319-379, 351- 477, 357-397, 361-313, 361-487, 391-379, 477-463 с количеством нулей корреляционной матрицы, рав- ным одному. Для обеспечения отсутствия корреляции векторов выхода и входа наиболее предпочтительным будет полином 419 либо композиции 283-445, 379-391 с наибольшим количеством нулей, а также 46 различных композиций, количество нулей корреляционной матрицы которых варьируется от 11 до 14. Они обла- дают наибольшим количеством нулей в матрицах коэффициентов корреляции входа и выхода, что затруднит корреляционный криптоанализ, однако уп- ростит аппроксимацию шифра аффинными булевыми функциями за счет большего количества единичных значений элементов в полной матрице коэффициентов корреляции со всеми аффинными функциями. Заключение. Полученные результаты позволяют сделать вывод о том, что большинство композиций неприводимых полиномов над GF(28) обладают более интересными криптографическими характеристиками в зависимости от потребностей использующего шифр как в части максимума модуля корреляционной матрицы, так и в количестве нулей корреляционной матрицы, но в то же время расстояние композиций до множества аффинных функций уменьшилось и варьи- руется от 88 до 110. Множество композиций неприводимых полиномов может использоваться как более обширный источник S-блоков для шифра Rijndael. К примеру, множество композиций неприводимых полиномов, максимум модуля корреляционных матриц которых превышает 0,125 (максимальное значение максимума модуля корреляционной матрицы неприводимого полинома), насчитывает 795 штук из 900 возможных. Дальнейшее изучение возможных вариантов повы- шения стойкости алгоритма Rijndael будет основы- ваться на полученных характеристиках блоков замен, а также включать в себя оценку криптостойкости алгоритма в случае применения полученных резуль- татов, а именно, использование различных полиномов или их композиций в различных раундах.

About the authors

M. A. Dmitriev

Siberian Federal University

Email: makcmad@mail.ru
79, Svobodny Av., Krasnoyarsk, 660041, Russian Federation

References

Supplementary files