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

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

Исследованы локальные характеристики подстановок множества состояний модифицированных аддитивных генераторов (МАГ), построенных на основе регистров сдвига длины 8 над множеством двоичных 32-мерных векторов, для трёх вариантов множества точек съёма (обратной связи) и двух вариантов модифицирующего преобразования. К исследованным характеристикам подстановок относятся: а) локальный (0, 256)-экспонент перемешивающей матрицы M порядка 256, то есть наименьшее натуральное число 70, такое, что при любом натуральном t ^ 70 положительны все столбцы матрицы M1 с номерами 0,1,..., 31; б) показатель 0-совершенности, то есть наименьшее число тактов работы генератора, после которых каждая координатная функция 0-го блока зависит существенно от всех битов начального состояния; в) показатель 0-сильной нелинейности, то есть наименьшее число тактов работы генератора, после которых каждая координатная функция 0-го блока является нелинейной. Вычисленные значения характеристик варьируются от 8 до 29. Полученные результаты могут быть использованы при построении криптографических алгоритмов на основе МАГ, в частности алгоритмов ключевого расписания блочных шифров, обеспечивающих сложную нелинейную взаимосвязь битов основного и раундовых ключей.

On mixing and nonlinear properties of modified additive generators.pdf Введение В основе принципа перемешивания, важного для многих криптографических алгоритмов, лежит существенная нелинейная зависимость выходных данных от элементов входа. Эти свойства важны для оценки эффективности атак на системы защиты информации, таких, например, как последовательное опробование частей секретного параметра системы. Исследованы криптографические свойства степеней преобразования модифицированного аддитивного генератора для двух модификаций аддитивного генератора и трёх вариантов множества точек съёма. С помощью матрично-графово-го подхода [1-3] исследованы перемешивающие свойства преобразований генераторов, получены значения локальных экспонентов их перемешивающих матриц. Проведены вычислительные эксперименты по определению степеней преобразований МАГ, при которых каждая координатная функция определённого выходного блока является нелинейной и совершенной, т. е. существенно зависит от всех битов начального состояния генератора. 1. Конструкция МАГ Обозначим: m = 232; V32 - множество 32-мерных двоичных векторов; Zm - кольцо вычетов по модулю m; b - биективное отображение Zm ^ V32, определяющее двоичное 32-разрядное представление числа X е Zm по правилу: если X = 231x0 + ... + 2x30 + + x31, Xi е {0,1}, i = 0,1,..., 31, то b(X) = X = (x0,..., x31) е V32; Ш - операция сложения в кольце вычетов Zm; МАГ-/ - аддитивный генератор, модифицированный с использованием преобразования / множества V32. Пусть (X0,... , X7) - начальное состояние МАГ-/, где X0,... , X7 е Zm. При i ^ 0 закон рекурсии состояний МАГ-/ имеет вид (в записи bjb-1 отображения применяются слева направо) 1 32 Xi+7 = b/b-1 Xi+^ mod 23 где D = d0,... ,dq - множество точек съёма функции обратной связи, D С {0,... , 7}, 0 < q, 0 = d0 < ... < dq. Обозначим через преобразование множества V256, реализуемое МАГ-/ : ^(X0, ...,X7) = (X 1,...,Хб, f(X0,..., ~X 7)). (1) Схема генератора МАГ-j с множеством точек съёма {0,1, 3, 5, 7} приведена на рис. 1, его выходная последовательность есть Xi, i ^ 0. Рис. 1. Схема генератора МАГ-^ 2. Оценки перемешивающих свойств МАГ Перемешивающие свойства МАГ-/ близки к наилучшим, если перемешивающий орграф преобразования является примитивным. Необходимое условие это го [2, с. 225] - достижимость вершины 31 из вершины 0 в перемешивающем орграфе Г(/) преобразования / (множество вершин есть {0,1,... , 31}). В качестве модификации / исследованы: 1) подстановка т циклического сдвига на 1 шаг: т(y0,... , y30,y31) = (y1,... , y31, y0); 2) преобразование в множества V32 следующего вида: %0,...,y30,y31) = ((y4,...,y7) 0 S (yо,Уl,У2,Уз), (у8,...,уИ) 0 S (y0 ,У1,У2,У3^ ..., (y28,. . . ,У31) 0 S(y0,y1,y2,y3),S(У0,У1,У2,Уз)), где S - функция одного из s-боксов алгоритма ГОСТ 28147-89, определённых в [4]. _ _ Обозначим: ^„+32fc(X0,...,X7) -координатные булевы функции преобразования /«- координатные булевы функции обратной связи регистра МАГ-^; ^«(y0,... , y31) - координатные булевы функции преобразования u = 0,..., 31, E(/) - множество номеров существенных переменных булевой функции /. Для обеих модификаций при различных множествах точек съёма D1 = {0, 7}, D2 = {0,1, 3, 5, 7}, D3 = {0,1,..., 7} построены перемешивающий орграф с множеством вершин {0,1,..., 255} и перемешивающая матрица M ) размера 256 х 256. При u = 0,..., 31 и k = 0,1,..., 6 выполнено E(^«+32fc) = {u + 32(k + 1)}. При k = 7 множества E(^„+32fc) и E(/«t(X0,... , X7)) равны, из формулы (1) следует, что /„(X0,... , X7) = ^b ^ ^ Xfc^ mod 232^ . Множество E(

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

nonlinear functions, shift registers, modified additive generator, essential arguments, mixing properties, существенная переменная, регистр сдвига, перемешивающие свойства, нелинейные функции, модифицированный аддитивный генератор

Авторы

ФИООрганизацияДополнительноE-mail
Коренева Алиса МихайловнаООО «Код Безопасности»системный аналитикalisa.koreneva@gmail.com
Всего: 1

Ссылки

МР 26.2.003-2013 «Информационная технология. Криптографическая защита информации. Задание узлов замены блока подстановки алгоритма шифрования ГОСТ 28147-89». М.: ТК 26, 2013.
Фомичёв В. М., Кяжин С. Н. Локальная примитивность матриц и графов // Дискретный анализ и исследование операций. 2017. Т. 24. №1. С. 97-119.
Фомичёв В. М., Мельников Д. А. Криптографические методы защиты информации. Ч. 1. Математические аспекты: учебник для академического бакалавриата. М.: Юрайт, 2016. 209 с.
Fomichev V. M. and Koreneva, A. M. Mixing properties of Modified Additive Generators // J. Appl. Indust. Math. 2017. V. 11. No. 2. P. 215-226.
 О перемешивающих и нелинейных свойствах модифицированных аддитивных генераторов | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/20

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