Сдвиговый регистр с обратной связью

Сдвиговый регистр с обратной связью (Linear Feedback Shift Register, LFSR) — это устройство или алгоритм, реализующий последовательность двоичных значений, в котором значение нового бита, вдвигаемого в регистр, вычисляется как линейная функция (обычно «исключающее ИЛИ», XOR) от значений определённых разрядов текущего состояния регистра. Относится к классу генераторов псевдослучайных последовательностей и находит широкое применение в цифровой электронике, криптографии, телекоммуникациях и вычислительной технике.

Принцип действия

Сдвиговый регистр с обратной связью представляет собой цепочку из n триггеров (разрядов), каждый из которых хранит один бит информации. В каждом такте работы содержимое всех разрядов сдвигается на одну позицию в сторону старших (или младших) разрядов. Освободившийся разряд заполняется значением, вычисленным как сумма по модулю 2 (XOR) значений определённых «отводных» разрядов — так называемых точек отбора обратной связи.

Математически состояние регистра описывается рекуррентным соотношением:

\[ x_{i+n} = \sum_{j=0}^{n-1} c_j \cdot x_{i+j} \pmod{2} \]

где \(x_i\) — значение i-го бита последовательности, \(c_j\) — коэффициенты обратной связи (0 или 1), а \(n\) — длина регистра. Коэффициент \(c_0\) всегда равен 1, так как обратная связь обязательно включает младший разряд.

Полином обратной связи

Набор отводных разрядов задаётся полиномом обратной связи (или характеристическим полиномом) степени n:

\[ P(x) = x^n + c_{n-1}x^{n-1} + \dots + c_1x + 1 \]

где коэффициенты \(c_j\) соответствуют наличию (1) или отсутствию (0) отвода от j-го разряда. Полином определяет все свойства последовательности, генерируемой регистром.

Классификация

По типу обратной связи

• Линейный сдвиговый регистр с обратной связью (LFSR) — обратная связь реализуется только через операцию XOR (сумма по модулю 2). Последовательность описывается линейным рекуррентным соотношением.
• Нелинейный сдвиговый регистр с обратной связью (NLFSR) — в обратной связи используются нелинейные функции (например, AND, OR, комбинации логических элементов). Такие регистры сложнее анализировать, но они обладают лучшими криптографическими свойствами.

По архитектуре

• Архитектура Фибоначчи — обратная связь подаётся на вход регистра от нескольких отводных разрядов через сумматор. Новый бит вычисляется как XOR отобранных разрядов и вдвигается в младший разряд.
• Архитектура Галуа — обратная связь встроена внутрь регистра: отводные разряды модифицируются XOR с выходным битом до сдвига. Эта архитектура позволяет реализовать более быстродействующие схемы, особенно при аппаратной реализации.

Свойства и характеристики

Период последовательности

Последовательность, генерируемая LFSR, является периодической. Максимальный период для регистра длины n составляет \(2^n - 1\) (все возможные ненулевые состояния). Такая последовательность называется последовательностью максимальной длины (m-последовательностью). Для достижения максимального периода полином обратной связи должен быть примитивным — неприводимым многочленом, корни которого являются примитивными элементами поля Галуа GF(2^n).

Статистические свойства

Последовательности LFSR обладают хорошими статистическими характеристиками:

• Распределение нулей и единиц примерно равномерное (на периоде количество единиц на одну больше, чем нулей).
• Автокорреляционная функция близка к дельта-функции (для m-последовательностей).
• Последовательности проходят многие статистические тесты на случайность (например, тесты NIST).

Криптографическая стойкость

Несмотря на хорошие статистические свойства, LFSR не является криптостойким генератором. При известной длине регистра n и известных 2n битах последовательности можно восстановить полином обратной связи и начальное состояние с помощью алгоритма Берлекэмпа — Мэсси. Поэтому в криптографии LFSR обычно используются в комбинации с нелинейными элементами (например, в поточных шифрах A5/1, Trivium, Grain).

Применение

Генерация псевдослучайных чисел

LFSR широко применяются в качестве генераторов псевдослучайных чисел в симуляциях, тестировании, компьютерных играх и математических расчётах. Простота аппаратной реализации позволяет интегрировать их в микроконтроллеры и ПЛИС.

Криптография

В поточных шифрах LFSR используется как основной компонент для генерации ключевого потока. Примеры:

• A5/1 — шифрование в стандарте GSM (мобильная связь 2G).
• E0 — шифрование в Bluetooth.
• Trivium — финалист конкурса eSTREAM.
• Grain — семейство поточных шифров.

Телекоммуникации и связь

• Формирование скремблирующих последовательностей — для устранения длинных последовательностей одинаковых битов в цифровых каналах связи.
• Коды с циклическим избыточным кодом (CRC) — LFSR используется для вычисления контрольных сумм в протоколах передачи данных (Ethernet, USB, Wi-Fi).
• Системы расширения спектра — в CDMA и GPS для генерации кодовых последовательностей.

Цифровая электроника

• Счётчики с псевдослучайным перебором состояний — используются в тестировании цифровых схем (BIST, Built-In Self-Test).
• Генераторы тестовых последовательностей — для проверки работы логических схем.
• Синтезаторы частот — в составе цифровых фазовых автоподстроек (DDS).

Другие области

• Кодирование и сжатие данных — в некоторых алгоритмах сжатия (например, LZSS).
• Игровая индустрия — для генерации случайных карт, событий, поведения NPC.
• Научные расчёты — в методах Монте-Карло и моделировании случайных процессов.

Примеры реализации

Аппаратная реализация

В цифровых микросхемах LFSR реализуется на D-триггерах и логических элементах XOR. Для регистра длины 8 с полиномом \(x^8 + x^4 + x^3 + x^2 + 1\) (примитивный полином) схема содержит 8 триггеров и 4 элемента XOR. Тактовая частота может достигать сотен мегагерц.

Программная реализация (на C)

```c uint16_t lfsr = 0xACE1u; // начальное состояние (ненулевое) unsigned bit; unsigned period = 0;

do { bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1; lfsr = (lfsr >> 1) | (bit << 15); ++period; } while (lfsr != 0xACE1u); ```

В этом примере полином обратной связи: \(x^{16} + x^{14} + x^{13} + x^{11} + 1\).

Интересные факты

• LFSR был изобретён в 1950-х годах и первоначально использовался в военных системах связи.
• Последовательности максимальной длины (m-последовательности) обладают свойством «окна»: любой ненулевой набор из n последовательных битов встречается ровно один раз за период.
• LFSR может быть реализован как на сдвиговом регистре, так и на основе циклического кода — математически эти модели эквивалентны.
• В криптографии комбинация нескольких LFSR с нелинейной функцией фильтрации позволяет создавать стойкие поточные шифры, устойчивые к атакам на основе линейной сложности.

Источники

• Голомб С. У. «Сдвиговые регистры с обратной связью и их приложения». — М.: Мир, 1968.
• Шнайер Б. «Прикладная криптография». — 2-е изд. — М.: Триумф, 2002.
• Menezes A., van Oorschot P., Vanstone S. «Handbook of Applied Cryptography». — CRC Press, 1996.
• Лидл Р., Нидеррайтер Г. «Конечные поля». — М.: Мир, 1988.
• Стандарт IEEE 802.11 (Wi-Fi) — описание использования LFSR для скремблирования.