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

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

История

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

Описание

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

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

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

${\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}$.^[3]

Свойства

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

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

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

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

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

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

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

Максимальный период 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 является примитивным корнем.^[3][1]

Связь с LFSR

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

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

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

Конфигурация Галуа для 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]}$ .^[4][5]

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

Конфигурация Фибоначчи для 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}$ .^[4][5]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Применение

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

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 с. — ISBN 978-5-89392-527-2.