Обратная связь с регистрами сдвига переноса

При проектировании последовательностей регистр сдвига с обратной связью (или FCSR) является арифметическим или аналогом сдвига сдвигового регистра с линейной обратной связью (LFSR). Если $N>1$ является целым числом, то N -арный FCSR длины $r$ представляет собой конечное устройство с состоянием $(a;z)=(a_{0},a_{1},\dots ,a_{r-1};z)$ состоящий из вектора элементов $a_{i}$ в $\{0,1,\dots ,N-1\}=S$ и целое число $z$. Операция изменения состояния определяется набором коэффициентов $q_{1},\dots ,q_{n}$ и определяется следующим образом: вычислить $s=q_{r}a_{0}+q_{r-1}a_{1}+\dots +q_{1}a_{r-1}+z$. Выразить s как $s=a_{r}+Nz'$ с $a_{r}$ в $S$. Тогда новое состояние $(a_{1},a_{2},\dots ,a_{r};z')$. Повторяя изменение состояния, FCSR генерирует бесконечную, в конечном итоге периодическую последовательность чисел в $S$.

FCSR использовались при разработке потоковых шифров (таких как генератор F-FCSR ), при криптоанализе потокового шифра суммирующего сумматора (причина, по которой Горески и Клэппер изобрели их). ), а также при генерации псевдослучайных чисел для квази-Монте-Карло (под названием генератора Multiply With Carry (MWC), изобретенного Кутюром и Л'Экуйером, ) обобщающий труд Марсальи и Замана .

FCSR анализируются с использованием теории чисел . С FCSR связано целое число соединения. $q=q_{r}N^{r}+\dots +q_{1}N^{1}-1$. С выходной последовательностью связано N-адическое число. $a=a_{0}+a_{1}N+a_{2}N^{2}+\dots$ Фундаментальная теорема FCSR гласит, что существует целое число $u$ так что $a=u/q$, рациональное число. Выходная последовательность является строго периодической тогда и только тогда, когда $u$ находится между $-q$ и $0$. Можно выразить u как простой квадратичный полином, включающий начальное состояние и q _i .

Существует также экспоненциальное представление FCSR: если $g$ является обратным $N{\pmod {q}}$, а выходная последовательность строго периодическая, то $a_{i}=(Ag_{i}{\bmod {q}}){\bmod {N}}$, где $A$ является целым числом. Отсюда следует, что период не превышает порядка N в мультипликативной группе единиц по модулю q . Это максимизируется, когда q является простым, а N является примитивным элементом по модулю q . В этом случае период составляет $q-1$. В этом случае выходная последовательность называется l-последовательностью (от «длинной последовательности»).

l-последовательности обладают множеством отличных статистических свойств. что делает их кандидатами для использования в приложениях, включая почти равномерное распределение подблоков, идеальные арифметические автокорреляции, а также свойство арифметического сдвига и добавления. с переносом Они являются аналогом m-последовательностей или последовательностей максимальной длины .

Существуют эффективные алгоритмы синтеза FCSR. В этом и заключается проблема: учитывая префикс последовательности, построить FCSR минимальной длины, который выводит последовательность. Это можно решить с помощью варианта Малера. и Де Вегера решеточный анализ N-адических чисел, когда $N=2$; по варианту алгоритма Евклида, когда N простое; и в целом адаптацией Сюй алгоритма Берлекэмпа-Месси. Если L — это размер наименьшего FCSR, который выводит последовательность (называемый N-адической сложностью последовательности), то все эти алгоритмы требуют префикса длиной около $2L$ быть успешным и иметь квадратичную временную сложность. Отсюда следует, что, как и в случае с LFSR и линейной сложностью, любой потоковый шифр с низкой N -адической сложностью не должен использоваться для криптографии.

FCSR и LFSR являются частными случаями очень общей алгебраической конструкции генераторов последовательностей, называемых алгебраическими регистрами сдвига с обратной связью (AFSR), в которых целые числа заменяются произвольным кольцом R , а N произвольным неединичным кольцом в R. заменяется Эта книга является общим справочником по LFSR, FCSR и AFSR.