Регистры сдвига с нелинейной обратной связью

Одной из важных задач является построение регистров сдвига /?(/) с нелинейной функцией обратной связи /, обладающих заданной цикловой структурой (в частности, обладающих циклом длины 2″ или 2″ - 1).

Наиболее универсальный из известных к настоящему моменту методов построения нелинейных двоичных регистров сдвига с заданной цикловой структурой основан на принципе «склейкирасклейки» циклов исходного регистра сдвига с известной цикловой структурой^[1]. При этом эффект «склейки» двух циклов в один или «расклейки» одного цикла на два достигается путем инвертирования значения функции обратной связи / исходного автомата R (f) на векторах вида (Let) и (0,а), где, а е F?^-1.

Недостатком данного подхода является то, что если число этапов «склейки-расклейки» мало по сравнению с числом 2″ состояний рассматриваемых автоматов, то существенные части циклов исходного и результирующего автоматов будут совпадать. Другими словами, результирующий автомат будет мало отличаться от исходного. В противном же случае фактически будет иметь место табличное задание функции обратной связи результирующего регистра сдвига с необходимостью использования памяти объемом 0(2″) бит.

А. Лемпелем^[2] предложен метод построения полноцикловых регистров R{f) длины m из полноцикловых регистров длины m — 1. Этот метод, однако, не приводит к увеличению числа полноцикловых регистров длины тп по сравнению с исходным числом полноцикловых регистров длины m — 1.

Известны также методы построения полноцикловых регистров на основе достаточно сложных итеративных процедур, которые не приводят к явной аналитической структуре функции обратной связи построенного регистра сдвига^[3].

Перспективным представляется метод описания классов функций обратной связи M (f), при которых соответствующие регистры сдвига обладают одинаковой цикловой структурой (изоморфны заданному регистру сдвига /?(/)). В таком случае для расчета цикловой структуры всего класса регистров достаточно исследовать структуру одного (наиболее удобного для изучения) представителя. К примеру, все двоичные регистры сдвига длины п, обладающие циклом длины 2″ — 1, изоморфны друг другу. При этом, как известно, в данном классе регистров сдвига содержатся и линейные автоматы (с помощью которых вырабатываются линейные рекуррентные последовательности максимального периода).

Вместе с тем описание регистров сдвига, изоморфных заданному регистру R (f), связано со сложной задачей построения специального вида биективных отображений — решений уравнений Коши, соответствующих парам изоморфных регистров сдвига.

Одним из авторов^[4] настоящего учебника получено описание некоторых классов такого сорта биекций, приведших к построению соответствующих классов изоморфных нелинейных автоматов. При этом наиболее мощные из описанных классов имеют мощность 4(п — 2) и отвечают регистрам сдвига с квадратичными функциями обратной связи. Путем исследования на ЭВМ представителей этих классов для п < 27 найдены классы, отвечающие регистрам, которые обладают циклом длины 2^п — 1.

В криптографической литературе известны методы построения генераторов большого периода на основе линейных регистров сдвига относительно небольшой длины. Во многих случаях такого сорта методы позволяют использовать и нелинейные регистры с длиной периода 2^п — 1.

• [1] еСм. Golomb S. W. Shift Register Sequences. San Francisco: Holden-Day, 1967.
• [2] 'Cm. Lempel A. On a homomorphism of the de Bruijn graph and its applicationsto the design of feedback shift registers. — IEEE Transactions Computers, 1970, C-19,p. 1204−1209.
• [3] См. Fredricksen Н. A class of nonlinear de Bruijn cycles. — J. Comb. Theory (A), 1975, N 19, p. 192−199.
• [4] См. Рожков М. И. О некоторых классах нелинейных регистров сдвига, обладающих одинаковой цикловой структурой. — Дискрет, матем., 2010, т. 22, № 2, с.96−119.