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

Регистр сдвига с обратной связью по переносу (англ. feedback with carry shift register, FCSR) — сдвиговый регистр битовых слов, арифметический аналог регистра сдвига с линейной обратной связью, отличается от него наличием регистра переноса. Применяется для генерации псевдослучайных последовательностей битов, а также использовался для создания потокового шифра F-FCSR.

История

В 1994 регистр сдвига с обратной связью по переносу был изобретен Горески (англ. Goresky) и Клаппером (англ. Klapper), а также независимо от них Марсаглией (англ. Marsaglia) и Заманом (англ. Zaman), Кутюром (англ. Couture) и Л’Экуером (англ. L’Ecuyer). Причем Клаппер и Горески хотели использовать его для криптоанализа суммирующего генератора. С другой стороны, Марсаглия, Заман, Кутюр, Л’Экуер были нацелены найти хороший генератор случайных чисел для решения таких задач, как использование квази-Монте-Карло метода.

Описание

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

В FCSR есть сдвиговый регистр, функция обратной связи и регистр переноса. Длина сдвигового регистра — количество битов. Когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на одну позицию.

Вместо выполнения операции XOR над всеми битами отводной последовательности эти биты складываются друг с другом и с содержимым регистра переноса. Результат $mod$ $2$ и становится новым битом. Результат, деленный на $2$, становится новым содержимым регистра переноса.

$m$ — значение регистра переноса

$\sigma ={q_{1}}{a_{k-1}}+\cdots +{q_{k}}{a_{0}}+m$

${a_{k}}={\sigma }{mod}{2}$

${m^{\prime }}=[{\sigma }/2]$

$({a_{k}},\cdots ,{a_{1}})$ — новое состояние регистра

$m^{\prime }$ — новое значение регистра переноса

Пример

3-битовый FCSR

Рассмотрим пример 3-битового регистра с ответвлениями в первой и второй позициях. Пусть его начальное значение $\left[0,\;0,\;1\right]$, а начальное содержимое регистра переноса равно $[0]$. Выходом будет являться крайний правый бит сдвигового регистра. Дальнейшие состояния регистра приведены в таблице ниже:

Номер шага	Сдвиговый регистр	Регистр переноса
0	$\left[0,\;0,\;1\right]$	0
1	$\left[1,\;0,\;0\right]$	0
2	$\left[0,\;1,\;0\right]$	0
3	$\left[1,\;0,\;1\right]$	0
4	$\left[1,\;1,\;0\right]$	0
5	$\left[1,\;1,\;1\right]$	0
6	$\left[0,\;1,\;1\right]$	1
7	$\left[1,\;0,\;1\right]$	1
8	$\left[0,\;1,\;0\right]$	1
9	$\left[0,\;0,\;1\right]$	1
10	$\left[0,\;0,\;0\right]$	1
11	$\left[1,\;0,\;0\right]$	0

Конечное внутреннее состояние (включая содержимое регистра переноса) совпадает со вторым внутренним состоянием. С этого момента последовательность циклически повторяется с периодом равным $10$. Стоит также упомянуть, что регистр переноса является не битом, а числом. Его размер должен быть не меньше $\log _{2}t$, где $t$ — число ответвлений. В примере только три ответвления, поэтому регистр переноса однобитовый. Если бы было четыре ответвления, то регистр переноса состоял бы из двух битов и мог принимать значения $0,1,2$ или $3$.

Свойства

Целые значения связи для FCSR с максимальным периодом

Целые значения связи для FCSR с максимальным периодом

Целые значения связи для FCSR с максимальным периодом

В отличие от LFSR, для FCSR существует задержка, прежде чем он перейдёт в циклический режим, то есть начнёт генерировать циклически повторяемую последовательность. В зависимости от выбранного начального состояния возможны 4 различных случая:

• Начальное состояние может оказаться частью максимального периода.
• Начальное состояние может перейти в последовательность максимального периода, после некоторой начальной задержки.
• Начальное состояние может после начальной задержки породить последовательность нулей.
• Начальное состояние может после начальной задержки породить последовательность единиц.

Опытным путём можно проверить, чем закончится конкретное начальное состояние. Нужно запустить FCSR на некоторое время. (Если $m$ — начальный объем памяти, а $t$ — количество ответвлений, то достаточно ${~\log _{2}t}+{~\log _{2}m}+1$ тактов.) Если выходной поток вырождается в бесконечную последовательность нулей и единиц за $n$ бит, где $n$ — длина FCSR, то не стоит использовать это начальное состояние.

Также, стоит отметить, что ряд ключей генератора на базе FCSR будут слабыми, так как начальное состояние FCSR соответствует ключу потокового шифра.

Максимальный период FCSR равен $q-1$ , где $q$ — целое число связи. Это число задает ответвления и определяется как:

$q={2q_{1}}+{{2^{2}}q_{2}}+{{2^{3}}q_{3}}+\cdots +{{2^{n}}q_{n}}-1$

$q$ — должно быть простым числом, для которого 2 является примитивным корнем.

Связь с LFSR

Также, как анализ LFSR основан на сложении примитивных многочленов mod 2, анализ FCSR основан на сложении чисел, называемых 2-adic. В мире 2-adic чисел существуют аналоги для всего. Точно также, как определяется линейная сложность, можно определить 2-adic сложность. Существует 2-adic аналог и для алгоритма Берлекэмпа-Мэсси. Это означает, что число возможных потоковых шифров по крайней мере удвоилось. Все что можно делать с LFSR, можно делать и с FCSR.

Варианты реализации

Конфигурация Галуа

Конфигурация Галуа для FCSR

Конфигурация Галуа состоит из:

• n — битного главного регистра $M=(m_{0},\cdots ,{m_{n-1}})$ , с некоторыми фиксированными ответвлениями $d_{0},\cdots ,d_{n-1}$
• n-1 — битного регистра переноса $C=(c_{0},\cdots ,c_{n-2})$

Сумматор с переносом

В момент времени t состояние $(M,C)$ изменяется следующим образом:

1. $x_{i}=m_{i+1}+{c_{i}}{d_{i}}+{m_{0}}{d_{i}}$ , для всех $0\leq i<n$ , с $m_{n}=0$ и $c_{n-1}=0$ и где $m_{0}$ представляет бит обратной связи.

2. обновляется состояние: $m_{i}\leftarrow {x_{i}}mod2$ , для всех $i\in [0\dots n-1]$ и $c_{i}\leftarrow {x_{i}}div2$ , для всех $i\in [0\dots n-2]$ .

Конфигурация Фибоначчи

Конфигурация Фибоначчи для FCSR

Конфигурация Фибоначчи состоит из:

• n — битного главного регистра $M=(m_{0},\cdots ,{m_{n-1}})$
• ответвления $(d_{0},\cdots ,d_{n-1})$ связаны с регистром переноса $c$ , состоящего из $w_{H}(d)$ битов, где $w_{H}(d)$ вес Хамминга для $d=(1+|q|)/2$

Состояние $(M,c)$ изменяется следующим образом:

1. $x=c+\sum _{i=0}^{n-1}{{m_{i}}{d_{n-1-i}}}$ ;

2. обновляем состояние: $M\leftarrow (m_{1},\dots ,m_{n-1},xmod2)$ , $c\leftarrow xdiv2$ .

Возможные варианты использования в генераторах

Чередующиеся генераторы «стоп-пошёл»

Чередующийся генератор «стоп-пошёл»

Основная статья: Генератор «стоп-пошёл»

В нём используются три регистра сдвига различной длины. Здесь Регистр-1 управляет тактовой частотой 2-го и 3-го регистров, то есть Регистр-2 меняет своё состояние, когда выход Регистра-1 равен единице, а Регистр-3 — когда выход Регстра-1 равен нулю.

Эти регистры используют FCSR вместо некоторых LFSR, и операция XOR может быть заменена сложением с переносом.

• Генератор «стоп-пошёл» FCSR : Регистр-1, Регистр-2, Регистр-3 — это FCSR. Объединяющая функция — XOR.
• Генератор «стоп-пошёл» FCSR/LFSR : Регистр-1 — FCSR; Регистр-2, Регистр-3 — LFSR. Объединяющая функция — сложение с переносом.
• Генератор «стоп-пошёл» FCSR/LFSR : Регистр-1 — LFSR; Регистр-2, Регистр-3 — FCSR. Объединяющая функция — XOR.

Каскадные генераторы

Основная статья: Каскад Голлманна

Данная схема представляет собой улучшенную версию генератора «стоп-пошёл». Он состоит из последовательности регистров, тактирование каждого из которых управляется предыдущим регистром. Если выходом Регистра-1 в момент времени является 1,то тактируется Регистр-2. Если выходом Регистра-2 в момент времени является 1, то тактируется Регистр-3, и так далее. Выход последнего регистра является выходом генератора.

Существует два способа использовать FCSR в каскадных генераторах:

• Каскад FCSR. Каскад Голлманна с FCSR вместо LFSR.
• Каскад FCSR/LFSR. Каскад Голлманна с генераторами, меняющими LFSR на FCSR и наоборот.

Комбинированные генераторы

Комбинированный генератор

Эти генераторы используют переменное количество FCSR и/или LFSR и множество функций, объединяющих регистры. Операция XOR разрушает алгебраические свойства FCSR, поэтому имеет смысл использовать эту операцию для их объединения.

• Генератор четности FCSR. Все регистры — FCSR, а объединяющая функция — XOR.
• Генератор четности LFSR/FCSR. Используется смесь LFSR и FCSR, а объединяющая функция — XOR.
• Пороговый генератор FCSR. Все регистры — FCSR, а объединяющая функция — мажорирование.
• Пороговый генератор LFSR/FCSR. Используется смесь LFSR и FCSR, а объединяющая функция — мажорирование.
• Суммирующий генератор FCSR. Все регистры — FCSR, а объединяющая функция — сложение с переносом.
• Суммирующий генератор LFSR/FCSR. Используется смесь LFSR и FCSR, а объединяющая функция — сложение с переносом.

Применение

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

F-FCSR

Основная статья : F-FCSR .

F-FCSR — семейство поточных шифров, основанное на использовании регистра сдвига с обратной связью по переносу(FCSR) с линейным фильтром на выходе. Идея шифра была предложена Терри Бергером, Франсуа Арно и Седриком Лараду. F-FCSR был представлен на конкурсе eSTREAM, был включен в список победителей конкурса в апреле 2008, но в дальнейшем была выявлена криптографическая слабость и в сентябре 2008 F-FCSR был исключен из списка eSTREAM.

См. также

• Регистр сдвига с линейной обратной связью (LFSR)
• Поточный шифр
• F-FCSR

Литература

• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — Триумф, 2013. — 816 с. — ISBN 978-5-89392-527-2.