Sufficient variables for transition function of a modified additive generator.pdf Введение Работа посвящена исследованию подстановок регистров сдвига длины n над множеством Vr двоичных r-мерных векторов при n, r > 1. Данный класс подстановок (обозначим его R(n, r)) обобщает как класс R(2, r), лежащий в основе сетей Фейстеля, так и подстановки множества состояний аддитивных генераторов (обозначим Rad(n, r) этот подкласс класса R(n,r)). Аддитивные генераторы исследуются с середины XX века. В [1] дан краткий обзор аддитивных генераторов чисел по модулю m, указаны их преимущества и недостатки. Один из первых аддитивных генераторов построен Дж. Ж. Митчелом и Д. Ф. Муром в 1958 г.: последовательность, генерируемая в соответствии с законом рекурсии Xn = (Xn-24 + Xn-55) mod m, n ^ 55, где m - чётное число; X0,...,X54 - произвольные целые не все чётные числа. Выбор чисел 24 и 55 обеспечивает длину периода 255 - 1 последовательности, составленной из младших двоичных разрядов чисел Xn. Позднее на основе аддитивных генераторов были построены криптографические алгоритмы Fish, Pike, Mush [2]. Известно, что аддитивные генераторы по модулю 2r плохо перемешивают входные данные. В связи с этим представляет интерес изучение перемешивающих свойств модификаций аддитивных генераторов по модулю 2r с помощью подстановки, применяемой к функции обратной связи. Заметим, что перемешивающие свойства регистров из R(n, r) исследованы в [3, 4]. В [5] получены условия полного перемешивания для модификации аддитивного генератора с помощью инволютивной перестановки координат векторов из V .В настоящей работе с целью исследования перемешивающих свойств широкого класса модификаций описано множество существенных переменных функции, являющейся композицией функции обратной связи регистра из Rad(n,r) и произвольной подстановки множества V. 1. Определяющие функции аддитивных генераторов и модификаций Рассмотрим аддитивный генератор по модулю 2r (регистр сдвига длины n над кольцом вычетов Z2r), r > 1. Для i ^ n знак Хг образуется в соответствии с законом рекурсии n- 1 Хг = (Е а,Xj+i-n) mod 2r, i ^ n, (1) j=0 где а1,...,ата-1 G {0,1} и а0 = 1. Из закона рекурсии (1) следует, что i-е разряды двоичного представления каждого из чисел Х0,Х1,... ,Xn-1 текущего состояния зависят только от r-го, ... , i-го разрядов чисел предыдущего состояния, i = 1,... , r, что исключает хорошие перемешивающие свойства преобразования множества состояний аддитивного генератора. Модифицируем аддитивный генератор с помощью преобразования g множества V, такой генератор назовем g-модификацией аддитивного генератора. Обозначим через b биекцию Z2r о V, сопоставляющую числу Хг G Z2 r его двоичное представление (b-1 -обратная к b функция). Для g-модификации аддитивного генератора закон рекурсии имеет вид n- 1 X = b-1 (g(b((£ а,-Xj+i-n) mod 2r))), г ^ n. (2) j=0 Обозначим через преобразование множества Vnr, которое реализуется g-моди-фикацией

Скачать электронную версию публикации