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

Регистр сдвига с обратной связью по переносу (Шаблон:Lang-en, Шаблон:Lang-en2) — Шаблон:Iw регистр битовых слов, арифметический аналог регистра сдвига с линейной обратной связью, отличается от него наличием регистра переноса. Применяется для генерации псевдослучайных последовательностей битов, а также использовался для создания потокового шифра F-FCSR.

История

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

Описание

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

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

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

σ = q_{1} a_{k - 1} + \dots + q_{k} a_{0} + m

a_{k} = σ m o d 2

m^{'} = [σ / 2]

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

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

Пример

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

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

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

Свойства

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

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

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

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

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

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

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

$q$ — должно быть простым числом, для которого 2 является примитивным корнем.Шаблон:Sfn^[1]

Связь с LFSR

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

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

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

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

n — битного главного регистра $M = (m_{0}, \dots, m_{n - 1})$ , с некоторыми фиксированными ответвлениями $d_{0}, \dots, d_{n - 1}$
n-1 — битного регистра переноса $C = (c_{0}, \dots, 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} m o d 2$ , для всех $i \in [0 \dots n - 1]$ и $c_{i} \leftarrow x_{i} d i v 2$ , для всех $i \in [0 \dots n - 2]$ .^[3]^[4]

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

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

n — битного главного регистра $M = (m_{0}, \dots, m_{n - 1})$
ответвления $(d_{0}, \dots, 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}, x m o d 2)$ , $c \leftarrow x d i v 2$ .^[3]^[4]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Применение

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

F-FCSR

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

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

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Книга

↑ ^1,0 ^1,1 A. Klapper A Survey of Feedback with Carry Shift RegistersШаблон:Недоступная ссылка
↑ 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,0 ^3,1 A. Klapper and M. Goresky, Fibonacci and Galois Representations of Feedback with Carry Shift Registers, 2004, [2] Шаблон:Wayback
↑ ^4,0 ^4,1 Francois Arnault, Thierry Berger, C´edric Lauradoux, Marine Minier and Benjamin Pousse, A new approach for FCSRs, [3] Шаблон:Wayback

[FCSR1-1] 1,0 ^1,1 A. Klapper A Survey of Feedback with Carry Shift RegistersШаблон:Недоступная ссылка

[FCSR2-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]Шаблон:Недоступная ссылка

[FCSR3-3] 3,0 ^3,1 A. Klapper and M. Goresky, Fibonacci and Galois Representations of Feedback with Carry Shift Registers, 2004, [2] Шаблон:Wayback

[FCSR4-4] 4,0 ^4,1 Francois Arnault, Thierry Berger, C´edric Lauradoux, Marine Minier and Benjamin Pousse, A new approach for FCSRs, [3] Шаблон:Wayback

[1]

[2]

[3]

[4]

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

Содержание

История