О перемешивающих свойствах модифицированных многомерных линейных генераторов | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/41

О перемешивающих свойствах модифицированных многомерных линейных генераторов

Описан новый класс регистров сдвига длины n с r-битовыми ячейками, n > 1, r > 1, названных модифицированными многомерными линейными генераторами (ММЛГ). Проведено экспериментальное исследование перемешивающих свойств регистров сдвига длины 8 над V32 из класса ММЛГ, функция обратной связи которых построена на основе раундовой подстановки низкоресурсного блочного шифра SPECK. Для таких ММЛГ с различными множествами точек съёма D С {0,..., 7} рассчитаны локальные (0,256)-экспоненты перемешивающих матриц, то есть для каждой матрицы M определено наименьшее натуральное число 7, такое, что при любом натуральном t ^ 7 положительны все столбцы матрицы M1 с номерами 1,... ,32. Вычислены показатели 0-совершенности, то есть наименьшие значения степеней регистрового преобразования, при которых каждая координатная функция выхода существенно зависит от всех переменных входа. Для ММЛГ с точками съёма 0 и 7 значения локального экспонента и локального показателя совершенности равны 17. Полученные значения сравниваются с локальными экспонентами и локальными показателями совершенности для конструктивно схожих аналогов, построенных на основе модифицированных аддитивных генераторов. Сравнение показало, что генераторы обладают схожими перемешивающими свойствами, однако в отличие от рассмотренных схем класс ММЛГ представляет интерес для использования в условиях ограниченных ресурсов.

On mixing properties of modified multidimensional linear generators.pdf Введение Одним из важных криптографических свойств итеративных криптографических алгоритмов является перемешивание входных данных. В основе принципа перемешивания лежит свойство существенной зависимости выходных функций от входных переменных. Для функции над двоичным конечномерным векторным пространством существенную зависимость каждого бита выхода от всех битов входа называют свойством полного перемешивания. Функции со свойством полного перемешивания называются совершенными [1]. Одним из методов оценки перемешивающих свойств преобразований является мат-рично-графовый подход (МГП) [2], который заключается в исследовании свойства примитивности и экспонентов для специального класса орграфов (перемешивающих орграфов) и соответствующих матриц смежности вершин этих орграфов (перемешивающих матриц). Неотрицательная матрица M называется примитивной, если M1 не содержит нулевых элементов при некотором t Е N. Наименьшее t с таким свойством называют экспонентом матрицы M. С применением МГП в данной работе исследуется класс преобразований, построенных на основе регистров сдвига с нелинейной комбинирующей обратной связью - ММЛГ. Регистры сдвига над множеством двоичных r-мерных векторов широко используются при построении генераторов раундовых ключей итеративных блочных шифров [3-5]. Экспериментально определены множества точек съёма, при которых перемешивающая матрица преобразования множества состояний ММЛГ примитивна. Для различных множеств точек съёма получены значения y локальных экспонентов перемешивающих матриц, оценивающих число тактов, после которых каждый из 32 разрядов вектора в ячейке с номером 0 может зависеть от всех битов начального заполнения регистра, иначе говоря, все столбцы с номерами 1,... ,32 перемешивающей матрицы в степени y не содержат нулей. С учётом полученных значений локальных экспонентов определён показатель локальной совершенности преобразования ММЛГ, равный наименьшему числу тактов работы генератора, после которых указанная зависимость имеется. 1. Конструкция ММЛГ Рассмотрим многомерный линейный генератор - генератор, построенный на основе регистра сдвига длины n над кольцом вычетов по модулю 2r, r > 1. При i ^ n знак гаммы Xi образуется в соответствии с законом рекурсии (n-1 0 b(ajXj+j-n) j=0 где a1,''',an-1 Е {0,1}; a0 = 1; b - биекция Z2r о Vr, определяющая двоичное r-разрядное представление числа X Е Z2r по правилу: если X = 2r-1x0 + '' '+2xr-2+xr-1, то b(X) = X = x0 ''' xn-1, X Е Vr; b-1 - обратная к b функция. Модифицируем многомерный линейный генератор с помощью преобразования g : Vr ^ Vr, назовём такой генератор ММЛГ, закон рекурсии для выходного знака Xj имеет вид Xj = b-1^g ^0 b(ajXj+j-n) Обозначим через : Vnr ^ преобразование множества состояний ММЛГ ( (xXo,..., xXn-1) = (Xi,..., xXn-1, fg (xXo,..., Xn-1)), где fg(Xo,..., xXn-i) = g(f (Xo,..., Xn-i)) = g ( 0 b(Xfc) ) - функция обратной связи VfcGD / fg : ^ V ММЛГ; D = {d0,..., } С {0,..., n - 1} - множество точек съёма (номеров существенных переменных функции f). Схема ММЛГ приведена на рис. 1, через Q обозначен выход генератора. Рис. 1. Схема функционирования ММЛГ Рассмотрим класс ММЛГ, построенных на основе регистров сдвига длины 8 над V32. В качестве модифицирующего преобразования используем раундовую подстановку низкоресурсного блочного алгоритма шифрования SPECK с блоком длины 32 бита и соответствующими для данного размера блока параметрами алгоритма, описанными в [6]. Обозначим такое модифицирующее преобразование через S>32. Оно обладает рядом позитивных свойств: - экспонент перемешивающей матрицы преобразования S?32 равен 4, что сравнимо со значениями экспонентов других современных низкоресурсных алгоритмов блочного шифрования; - имеет малые показатели ресурсоёмкости в сравнении с другими современными низкоресурсными алгоритмами блочного шифрования, в частности по площади аппаратной реализации. Это свойство особенно полезно с учётом современных тенденций, направленных на построение низкоресурсных алгоритмов. 2. Экспериментальное исследование перемешивающих свойств В ходе эксперимента исследованы ММЛГ, построенные на основе регистров сдвига длины 8 над V32 с модифицирующим преобразованием S>32 и различными множествами точек съёма D С {0,..., 7}. Для каждого регистрового преобразования построена перемешивающая матрица M и определено значение локального (0,256)-экспонента, то есть наименьшее натуральное число 7, такое, что при любом натуральном t ^ 7 положительны все столбцы матрицы Mt с номерами {1,... ,32}. Проведён вычислительный эксперимент по определению показателя 0-совершенности, то есть наименьшего числа тактов работы ММЛГ, после которого каждая координатная функция нулевого блока существенно зависит от всех знаков начального состояния. В табл. 1 представлены значения локальных характеристик перемешивания для некоторых представителей S>32-модификации ММЛГ с различными множествами точек съёма. Исходя из соображений экономичности аппаратной реализации, рассмотрим S>32-модификацию ММЛГ с множеством точек съёма D = {0, 7}. Сравним полученные значения локальных экспонентов и локальных показателей совершенности с аналогичными характеристиками для конструктивно схожих аналогов генератора. Рассмотрим Таблица 1 Значения локальных характеристик перемешивания для £з2-модификаций Мощность Множество Показатель Локальный множества точек съёма 0-совершенности (0,256)-экспонент точек съема 2 {0,7} 17 17 3 {0,3,7} 14 14 4 {0,1,4,7} 13 13 5 {0,1,3,5,7} 12 12 схемы МАГ-^i и МАГ-^2 [6], а также МАГ-£>32 - преобразование аддитивного генератора, модифицированного с использованием SPECK. Сравнение перемешивающих характеристик приведено в табл. 2. Таблица 2 Сравнение перемешивающих характеристик Схема регистра сдвига МАГ-^! МАГ-^2 МАГ-532 ММЛГ-532 (0,256)-экспонент 15 14 15 17 Показатель 0-совершенности 29 16 16 17 Выводы С помощью матрично-графового подхода исследованы перемешивающие свойства нового класса регистровых преобразований - многомерных линейных генераторов, модифицированных с использованием преобразования SPECK. По результатам исследования предложена схема на основе регистра сдвига с двумя точками обратной связи, которая обеспечивает паритет по качеству перемешивающих свойств и площади аппаратной реализации. Значения перемешивающих характеристик для предложенной схемы близки к аналогичным характеристикам для конструктивно схожих схем генераторов, однако, в отличие от рассмотренных схем, ММЛГ представляет интерес для использования в условиях ограниченных ресурсов. Автор выражает благодарность д.ф.-м.н. профессору В. М. Фомичеву и к.ф.-м.н. А. М. Кореневой за постановку задачи и внимание к проводимым исследованиям.

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

модифицированный многомерный линейный генератор, перемешивающие свойства, матрично-графовый подход, перемешивающая матрица, показатель совершенности, регистр сдвига, экспонент, SPECK, modified multidimensional linear generator, mixing properties, matrix-graph approach, mixing matrix, index of perfection, shift register, exponent, SPECK

Авторы

ФИООрганизацияДополнительноE-mail
Хайруллин Ильяс ИльдаровичНИЯУ МИФИстудент кафедры №42 криптологии и кибербезопасностиildar97-97@mail.ru
Всего: 1

Ссылки

Фомичев В. М., Мельников Д. А. Криптографические методы защиты информации. Ч. 1. Математические аспекты. М.: Юрайт, 2017.
Fomichev V. M., Avezova Ya. A., Koreneva A. M., and KyazhinS.N. Primitivity and local primitivity of digraphs and nonnegative matrices // J. Appl. Industr. Math. 2018. V. 12. No. 3. P. 453-469.
Fomichev V. M. and Koreneva A.M. On Efficiency of Block Encryption by Improved Key Schedule. Ярославль, CTCrypt-2016. https://ctcrypt.ru/files/files/2016/12 fomichev.pdf.
Фомичев В. М., Задорожный Д. И., Коренева А. М., Тулебаев А. И. О ключевом расписании на основе модифицированного аддитивного генератора. Москва, РусКрипто-2018. https://www.ruscrypto.ru/resource/archive/rc2018/files/02_Koreneva.pdf.
Дмух А, Трифонов Д., Чухно А. О модификации отечественного низкоресурсного криптографического алгоритма 2-ГОСТ и вопросах его реализации на ПЛИС. Москва, РусКрипто-2018. https://www.ruscrypto.ru/resource/archive/rc2018/files/ 02_Dmukh_Trifonov_Chukhno.pdf.
Beaulieu R., Shors D., Smith J., et al. The SIMON and SPECK families of lightweight block ciphers. https://eprint.iacr.org/2013/404.pdf.
 О перемешивающих свойствах модифицированных многомерных линейных генераторов | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/41

О перемешивающих свойствах модифицированных многомерных линейных генераторов | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/41