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

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

История

править

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

Описание

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

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

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

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

 
 
 

  — новое состояние регистра

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

Пример

править
 
3-битовый FCSR

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

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

Конечное внутреннее состояние (включая содержимое регистра переноса) совпадает со вторым внутренним состоянием. С этого момента последовательность циклически повторяется с периодом равным  . Стоит также упомянуть, что регистр переноса является не битом, а числом. Его размер должен быть не меньше  , где   — число ответвлений. В примере только три ответвления, поэтому регистр переноса однобитовый. Если бы было четыре ответвления, то регистр переноса состоял бы из двух битов и мог принимать значения   или  .[3]

Свойства

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

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

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

Опытным путём можно проверить, чем закончится конкретное начальное состояние. Нужно запустить FCSR на некоторое время. (Если   — начальный объем памяти, а   — количество ответвлений, то достаточно   тактов.) Если выходной поток вырождается в бесконечную последовательность нулей и единиц за   бит, где   — длина FCSR, то не стоит использовать это начальное состояние. [3]

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

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

 

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

Связь с LFSR

править

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

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

править

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

править
 
Конфигурация Галуа для FCSR

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

  • n — битного главного регистра   , с некоторыми фиксированными ответвлениями  
  • n-1 — битного регистра переноса  
 
Сумматор с переносом

В момент времени t состояние   изменяется следующим образом:

1.   , для всех   , с   и   и где   представляет бит обратной связи.

2. обновляется состояние:   , для всех   и   , для всех   .[4][5]

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

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

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

  • n — битного главного регистра  
  • ответвления   связаны с регистром переноса   , состоящего из   битов, где   вес Хамминга для  

Состояние   изменяется следующим образом:

1.   ;

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

См. также

править

Примечания

править
  1. 1 2 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. 1 2 3 4 5 6 7 8 9 10 11 12 13 Б. Шнайер, 2013.
  4. 1 2 A. Klapper and M. Goresky, Fibonacci and Galois Representations of Feedback with Carry Shift Registers, 2004, [2] Архивная копия от 23 сентября 2015 на Wayback Machine
  5. 1 2 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.