Русская Википедия:Регистр сдвига с обратной связью по переносу
Регистр сдвига с обратной связью по переносу (Шаблон:Lang-en, Шаблон:Lang-en2) — Шаблон:Iw регистр битовых слов, арифметический аналог регистра сдвига с линейной обратной связью, отличается от него наличием регистра переноса. Применяется для генерации псевдослучайных последовательностей битов, а также использовался для создания потокового шифра F-FCSR.
История
В 1994 регистр сдвига с обратной связью по переносу был изобретен Горески (Шаблон:Lang-en) и Клаппером (Шаблон:Lang-en), а также независимо от них Марсаглией (Шаблон:Lang-en) и Заманом (Шаблон:Lang-en), Кутюром (Шаблон:Lang-en) и Л’Экуером (Шаблон:Lang-en). Причем Клаппер и Горески хотели использовать его для криптоанализа суммирующего генератора. С другой стороны, Марсаглия, Заман, Кутюр, Л’Экуер были нацелены найти хороший генератор случайных чисел для решения таких задач, как использование квази-Монте-Карло метода.[1]
Описание
В FCSR есть сдвиговый регистр, функция обратной связи и регистр переноса. Длина сдвигового регистра — количество битов. Когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на одну позицию.[2]
Вместо выполнения операции XOR над всеми битами отводной последовательности эти биты складываются друг с другом и с содержимым регистра переноса. Результат <math> mod </math> <math>2</math> и становится новым битом. Результат, деленный на <math> 2 </math>, становится новым содержимым регистра переноса.Шаблон:Sfn
<math>m</math> — значение регистра переноса
- <math>\sigma={q_1}{a_{k-1}}+\cdots+{q_k}{a_0}+m</math>
- <math>{a_k}={\sigma} {mod}{2}</math>
- <math>{m^\prime}=[{\sigma}/2]</math>
<math>({a_k},\cdots, {a_1})</math> — новое состояние регистра
<math>m^\prime</math> — новое значение регистра переноса
Пример
Рассмотрим пример 3-битового регистра с ответвлениями в первой и второй позициях. Пусть его начальное значение <math>\left[0,\;0,\;1\right]</math>, а начальное содержимое регистра переноса равно <math>[0]</math>. Выходом будет являться крайний правый бит сдвигового регистра. Дальнейшие состояния регистра приведены в таблице ниже:
| Номер шага | Сдвиговый регистр | Регистр переноса |
|---|---|---|
| 0 | <math>\left[0,\;0,\;1\right] </math> | 0 |
| 1 | <math>\left[1,\;0,\;0\right]</math> | 0 |
| 2 | <math>\left[0,\;1,\;0\right]</math> | 0 |
| 3 | <math>\left[1,\;0,\;1\right]</math> | 0 |
| 4 | <math>\left[1,\;1,\;0\right]</math> | 0 |
| 5 | <math>\left[1,\;1,\;1\right]</math> | 0 |
| 6 | <math>\left[0,\;1,\;1\right]</math> | 1 |
| 7 | <math>\left[1,\;0,\;1\right]</math> | 1 |
| 8 | <math>\left[0,\;1,\;0\right]</math> | 1 |
| 9 | <math>\left[0,\;0,\;1\right]</math> | 1 |
| 10 | <math>\left[0,\;0,\;0\right]</math> | 1 |
| 11 | <math>\left[1,\;0,\;0\right]</math> | 0 |
Конечное внутреннее состояние (включая содержимое регистра переноса) совпадает со вторым внутренним состоянием. С этого момента последовательность циклически повторяется с периодом равным <math>10</math>. Стоит также упомянуть, что регистр переноса является не битом, а числом. Его размер должен быть не меньше <math>\log_2 t</math>, где <math>t</math> — число ответвлений. В примере только три ответвления, поэтому регистр переноса однобитовый. Если бы было четыре ответвления, то регистр переноса состоял бы из двух битов и мог принимать значения <math>0, 1, 2 </math> или <math> 3 </math>.Шаблон:Sfn
Свойства
В отличие от LFSR, для FCSR существует задержка, прежде чем он перейдёт в циклический режим, то есть начнёт генерировать циклически повторяемую последовательность. В зависимости от выбранного начального состояния возможны 4 различных случая:Шаблон:Sfn
- Начальное состояние может оказаться частью максимального периода.
- Начальное состояние может перейти в последовательность максимального периода, после некоторой начальной задержки.
- Начальное состояние может после начальной задержки породить последовательность нулей.
- Начальное состояние может после начальной задержки породить последовательность единиц.
Опытным путём можно проверить, чем закончится конкретное начальное состояние. Нужно запустить FCSR на некоторое время. (Если <math>m</math> — начальный объем памяти, а <math>t</math> — количество ответвлений, то достаточно <math>{~\log_2 t}+{~\log_2 m}+1</math> тактов.) Если выходной поток вырождается в бесконечную последовательность нулей и единиц за <math>n</math> бит, где <math>n</math> — длина FCSR, то не стоит использовать это начальное состояние. Шаблон:Sfn
Также, стоит отметить, что ряд ключей генератора на базе FCSR будут слабыми, так как начальное состояние FCSR соответствует ключу потокового шифра. Шаблон:Sfn
Максимальный период FCSR равен <math>q-1</math> , где <math>q</math> — целое число связи. Это число задает ответвления и определяется как:
<math>q={2q_1}+{{2^2}q_2}+{{2^3}q_3}+\cdots+{{2^n}q_n}-1</math>
<math>q</math> — должно быть простым числом, для которого 2 является примитивным корнем.Шаблон:Sfn[1]
Связь с LFSR
Также, как анализ LFSR основан на сложении примитивных многочленов mod 2, анализ FCSR основан на сложении чисел, называемых 2-adic. В мире 2-adic чисел существуют аналоги для всего. Точно также, как определяется линейная сложность, можно определить 2-adic сложность. Существует 2-adic аналог и для алгоритма Берлекэмпа-Мэсси. Это означает, что число возможных потоковых шифров по крайней мере удвоилось. Все что можно делать с LFSR, можно делать и с FCSR.Шаблон:Sfn
Варианты реализации
Конфигурация Галуа
Конфигурация Галуа состоит из:
- n — битного главного регистра <math>M=(m_0,\cdots,{m_{n-1}})</math> , с некоторыми фиксированными ответвлениями <math>d_0, \cdots, d_{n-1}</math>
- n-1 — битного регистра переноса <math>C=(c_0,\cdots,c_{n-2})</math>
В момент времени t состояние <math>(M,C)</math> изменяется следующим образом:
1. <math> x_i=m_{i+1} + {c_i}{d_i} + {m_0}{d_i}</math> , для всех <math>0 \leq i < n </math> , с <math>m_{n}=0</math> и <math>c_{n-1}=0</math> и где <math>m_0</math> представляет бит обратной связи.
2. обновляется состояние: <math>m_i \leftarrow {x_i}mod2 </math> , для всех <math>i \in [0 \dots n-1] </math> и <math>c_i \leftarrow {x_i}div2 </math> , для всех <math>i \in [0 \dots n-2] </math> .[3][4]
Конфигурация Фибоначчи
Конфигурация Фибоначчи состоит из:
- n — битного главного регистра <math>M=(m_0,\cdots,{m_{n-1}})</math>
- ответвления <math>(d_0, \cdots, d_{n-1})</math> связаны с регистром переноса <math>c</math> , состоящего из <math> w_H(d) </math> битов, где <math> w_H(d) </math> вес Хамминга для <math>d=(1+|q|)/2</math>
Состояние <math>(M,c)</math> изменяется следующим образом:
1. <math> x = c+ \sum^{n-1}_{i=0} {{m_i}{d_{n-1-i}}} </math> ;
2. обновляем состояние: <math> M \leftarrow (m_1, \dots , m_{n-1}, x mod2) </math> , <math> c \leftarrow x div2 </math> .[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
