Том 24, номер 2, 2017 г., Стр. 32-52

УДК 519.17
Коренева А. М., Фомичёв В. М.
Перемешивающие свойства модифицированных аддитивных генераторов

Аннотация:
В статье развивается матрично-графовый подход к оценке перемешивающих свойств биективных преобразований регистров сдвига над множеством двоичных векторов. Такие регистры сдвига обобщают, с одной стороны, класс шифров, основанных на сети Фейстеля, а с другой стороны, — класс преобразований множеств состояний аддитивных генераторов (на основе аддитивных генераторов построены алгоритмы Fish, Pike, Mush). Примечательно, что оригинальные схемы аддитивных генераторов признаны нестойкими, в том числе из-за слабых перемешивающих свойств. В статье приведены результаты исследования перемешивающих свойств модифицированных аддитивных генераторов. Для перемешивающего ориентированного графа преобразования множества состояний модифицированного аддитивного генератора определены множества дуг и контуров, получены условия примитивности и дана оценка экспонента. Показано, что при определённых параметрах модифицированного аддитивного генератора полное перемешивание может быть достигнуто за число итераций, существенно меньшее числа вершин перемешивающего орграфа.
Табл. 1, ил. 1, библиогр. 13.

Ключевые слова: аддитивный генератор, модифицированный аддитивный генератор, перемешивающий орграф, примитивный орграф, регистр сдвига, экспонент орграфа.

DOI: 10.17377/daio.2017.24.528

Коренева Алиса Михайловна ¹
Фомичёв Владимир Михайлович ^1,2,3
1. Национальный исследовательский ядерный университет «МИФИ»,
Каширское шоссе, 31, 115409 Москва, Россия
2. Финансовый университет при Правительстве РФ,
пр. Ленинградский, 49, 125993 Москва, Россия
3. Институт проблем информатики ФИЦ ИУ РАН,
ул. Вавилова, 44, корп. 2, 119333 Москва, Россия
е-mail: alisa.koreneva@gmail.com, fomichev@nm.ru

Статья поступила 19 февраля 2016 г.
Исправленный вариант — 25 июля 2016 г.

Литература

[1] Дорохова А. М., Фомичёв В. М. Уточнённые оценки экспонентов перемешивающих графов биективных регистров сдвига над множеством двоичных векторов // Прикл. дискрет. математика. 2014. № 1. С. 77–83.

[2] Когос К. Г., Фомичёв В. М. Положительные свойства неотрицательных матриц // Прикл. дискрет. математика. 2012. № 4. С. 5–13.

[3] Коренева А. М., Фомичёв В. М. Об одном обобщении блочных шифров Фейстеля // Прикл. дискрет. математика. 2012. № 3. С. 34–40.

[4] Кяжин С. Н., Фомичёв В. М. Локальная примитивность графов и неотрицательных матриц // Прикл. дискрет. математика. 2014. № 1. С. 68–80.

[5] Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М.: ТВП, 2000.

[6] Фомичёв В. М. Методы дискретной математики в криптологии. М.: Диалог-МИФИ, 2010. 424 с.

[7] Фомичёв В. М. Свойства путей в графах и в мультиграфах // Прикл. дискрет. математика. 2010. № 1. С. 118–124.

[8] Фомичёв В. М. Оценки экспонентов примитивных графов // Прикл. дискрет. математика. 2011. № 2. С. 101–112.

[9] Фомичёв В. М. Оценка экспонента некоторых графов с помощью чисел Фробениуса для трёх аргументов // Прикл. дискрет. математика. 2014. № 2. С. 88–96.

[10] Шнайер Б. Прикладная криптография. Протоколы, алгоритмы и исходные коды на языке Си. М.: Триумф, 2002. 816 с.

[11] Kim B. M., Song B. C., Hwang W. Nonnegative primitive matrices with exponent 2 // Linear Algebra Appl. 2005. Vol. 407. P. 162–168.

[12] Shader B. L., Suwilo S. Exponents of nonnegative matrix pairs // Linear Algebra Appl. 2003. Vol. 363. P. 275–293.

[13] Wielandt H. Unzerlegbare, nicht negative Matrizen // Math. Z. 1950. Bd. 52. S. 642–648.