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

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

История

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

Описание

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

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

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

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

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

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

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

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

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

Пример

3-битовый FCSR

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

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

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

Свойства

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

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

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

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

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

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

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

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

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

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

Связь с (LFSR)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. обновляем состояние: ${\displaystyle M\leftarrow (m_{1},\dots ,m_{n-1},xmod2)}$ , ${\displaystyle 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)

Примечания

1. A. Klapper A Survey of Feedback with Carry Shift Registers (недоступная ссылка)
2. A. Klapper and M. Goresky, Feedback Shift Registers, 2-Adic Span, and Combiners With Memory, in Journal of Cryptology vol. 10, pp. 111—147, 1997, [1] (недоступная ссылка)
3. Б. Шнайер, 2013.
4. A. Klapper and M. Goresky, Fibonacci and Galois Representations of Feedback with Carry Shift Registers, 2004, [2] от 23 сентября 2015 на Wayback Machine
5. Francois Arnault, Thierry Berger, C´edric Lauradoux, Marine Minier and Benjamin Pousse, A new approach for FCSRs, [3] от 2 июня 2018 на Wayback Machine

Литература

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