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

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

Принцип работы

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

Линейная обратная связь

Линейная обратная связь реализуется с помощью набора отводов (taps) — определённых позиций регистра, биты которых суммируются по модулю 2 (операция XOR). Результат этой суммы и становится новым входным битом. Математически это описывается как:

\[ b_{n} = \sum_{i=1}^{n} c_i \cdot b_{n-i} \mod 2 \]

где \(b_n\) — новый бит, \(c_i\) — коэффициенты обратной связи (0 или 1), \(b_{n-i}\) — биты на предыдущих тактах. Если \(c_i = 1\), то соответствующая позиция участвует в обратной связи; если \(c_i = 0\) — не участвует.

Тактирование

РСЛОС работает синхронно с тактовым сигналом. На каждом такте:

1. Вычисляется новый бит по правилу обратной связи.
2. Все биты регистра сдвигаются на одну позицию.
3. Новый бит записывается в освободившуюся ячейку.
4. Бит, вытесненный из регистра, становится очередным элементом выходной последовательности.

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

Работа РСЛОС полностью описывается полиномом обратной связи (или характеристическим полиномом) над полем GF(2). Полином имеет вид:

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

где \(n\) — длина регистра, а коэффициенты \(c_i\) соответствуют наличию отводов. Например, для 4-битного РСЛОС с отводами на позициях 4 и 1 (считая от 1) полином будет \(x^4 + x + 1\).

Примитивные полиномы

Максимальный период выходной последовательности РСЛОС длины n составляет \(2^n - 1\) (все возможные ненулевые состояния регистра). Такой период достигается, если полином обратной связи является примитивным — то есть неприводимым и порождающим все ненулевые элементы поля GF(2^n). Примитивные полиномы существуют для любой длины n, но их количество ограничено. Например, для n=3 примитивным является полином \(x^3 + x + 1\), для n=4 — \(x^4 + x + 1\), для n=5 — \(x^5 + x^2 + 1\).

Если полином не является примитивным, период последовательности будет меньше максимального и может зависеть от начального состояния регистра.

Классификация РСЛОС

РСЛОС классифицируются по нескольким признакам.

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

• Внутренняя обратная связь (Galois LFSR) — отводы подключены к XOR-элементам, встроенным между ячейками регистра. Новый бит вычисляется на основе текущего состояния регистра и сразу же влияет на сдвиг. Эта архитектура более быстродействующая, так как XOR-операции выполняются параллельно.
• Внешняя обратная связь (Fibonacci LFSR) — отводы подключены к одному общему XOR-элементу на входе регистра. Новый бит вычисляется на основе состояния регистра до сдвига. Эта архитектура проще для понимания, но медленнее из-за последовательной обработки.

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

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

По длине регистра

• Короткие (n ≤ 16) — используются в простых генераторах, тестировании.
• Средние (16 < n ≤ 64) — применяются в криптографии, системах связи.
• Длинные (n > 64) — используются в генераторах псевдослучайных чисел для научных и инженерных задач.

Применение

РСЛОС находят применение в различных областях цифровой техники и информатики.

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

РСЛОС является простым и быстрым способом генерации последовательностей, близких к случайным. Однако для криптографических целей требуется дополнительная обработка, так как линейная структура делает РСЛОС уязвимым для атак (например, атаки Берлекампа — Мэсси).

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

В криптографии РСЛОС используются как компоненты поточных шифров. Классические примеры:

• Шифр A5/1 — использовался в стандарте GSM для шифрования голосового трафика. Основан на трёх РСЛОС длиной 19, 22 и 23 бита с нелинейной комбинацией выходов.
• Шифр E0 — применялся в Bluetooth.
• Шифр Trivium — современный поточный шифр, основанный на комбинации трёх РСЛОС.

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

Цифровая связь

В системах связи РСЛОС применяются для:

• Скремблирования — перемешивания данных для устранения длинных последовательностей одинаковых битов.
• Формирования шумоподобных сигналов — в системах с расширением спектра (CDMA, GPS).
• Кодирования — в циклических кодах (CRC, BCH, Рида — Соломона) для вычисления контрольных сумм и коррекции ошибок.

Тестирование цифровых схем

РСЛОС используются в генераторах тестовых последовательностей (Built-In Self-Test, BIST) для проверки цифровых микросхем. Они позволяют сформировать псевдослучайные тестовые векторы, покрывающие большинство возможных состояний схемы.

Моделирование и научные расчёты

В симуляциях, требующих случайных чисел (метод Монте-Карло, моделирование физических процессов), РСЛОС применяются как быстрые генераторы, уступающие по качеству более сложным алгоритмам (например, Mersenne Twister), но превосходящие их по скорости на простых аппаратных платформах.

Криптоанализ и уязвимости

Основная уязвимость РСЛОС — его линейность. Если известны 2n последовательных битов выходной последовательности (где n — длина регистра), то с помощью алгоритма Берлекампа — Мэсси можно восстановить полином обратной связи и начальное состояние регистра. Это делает РСЛОС непригодным для криптографического использования без дополнительной защиты.

Методы защиты:

• Нелинейная фильтрация — выход РСЛОС пропускается через нелинейную булеву функцию.
• Комбинирование нескольких РСЛОС — выходы нескольких регистров объединяются нелинейной функцией (например, в шифре A5/1).
• Чередование тактов — регистры тактируются неравномерно, что затрудняет восстановление последовательности.

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

Простейший 4-битный РСЛОС с полиномом \(x^4 + x + 1\) (отводы на позициях 4 и 1) может быть реализован на языке C:

```c

include <stdint.h>

uint8_t lfsr = 0x01; // начальное состояние (ненулевое) uint8_t bit;

uint8_t lfsr_next() { bit = ((lfsr >> 3) ^ (lfsr >> 0)) & 1; // XOR битов 4 и 1 lfsr = (lfsr >> 1) | (bit << 3); // сдвиг вправо return lfsr & 1; // выходной бит } ```

В этом примере регистр сдвигается вправо, а новый бит вычисляется как XOR битов на позициях 4 (старший) и 1 (младший). Начальное состояние 0x01 (0001) гарантирует, что регистр никогда не обнулится (иначе последовательность зациклится на нуле).

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

• РСЛОС является одним из самых старых алгоритмов генерации псевдослучайных чисел — первые упоминания относятся к 1950-м годам.
• В некоторых аппаратных реализациях РСЛОС используется всего один XOR-элемент, что делает его крайне экономичным для встраиваемых систем.
• Максимальный период РСЛОС длины n равен \(2^n - 1\), что для n=64 составляет около \(1.8 \times 10^{19}\) тактов — при частоте 1 ГГц это более 570 лет непрерывной работы.
• В криптографии существуют атаки на РСЛОС, использующие корреляционные методы (корреляционная атака), которые позволяют восстанавливать состояние регистра даже при наличии нелинейной фильтрации.

Источники

• Шнайер Б. Прикладная криптография. — М.: Триумф, 2002. — Глава 16.
• Голомб С. Сдвиговые регистры с линейной обратной связью. — М.: Мир, 1968.
• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996. — Chapter 6.
• Кнут Д. Искусство программирования. Том 2. Получисленные алгоритмы. — М.: Вильямс, 2007. — Раздел 3.2.2.