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

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

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

Основу LFSR составляет регистр сдвига — последовательность из n триггеров (битов), каждый из которых хранит одно двоичное значение (0 или 1). На каждом такте синхросигнала содержимое регистра сдвигается на одну позицию в сторону старших разрядов, а освободившийся младший разряд заполняется новым значением, вычисленным как линейная функция (обычно сумма по модулю 2, то есть XOR) от определённых битов текущего состояния регистра. Эти биты называются отводами (taps) и задают полином обратной связи.

Математически работа LFSR описывается линейным рекуррентным уравнением над полем GF(2):

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

где \( b_t \) — значение бита в момент времени t, \( c_i \) — коэффициенты обратной связи (0 или 1), а n — длина регистра. Полином обратной связи \( P(x) = x^n + c_{n-1}x^{n-1} + \dots + c_1x + c_0 \) определяет свойства последовательности.

Типы и классификация

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

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

По длине и полиному

• Примитивные полиномы — обеспечивают максимальный период последовательности \( 2^n - 1 \) (для n-битного регистра). Примеры: \( x^3 + x + 1 \) (n=3), \( x^4 + x + 1 \) (n=4), \( x^8 + x^4 + x^3 + x^2 + 1 \) (n=8).
• Непрмитивные полиномы — дают меньший период, используются в специализированных задачах.

По конфигурации

• Однородные LFSR — все отводы имеют одинаковую задержку.
• Неоднородные LFSR — отводы с разными задержками, усложняют анализ.

Математические свойства

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

Максимальная длина выходной последовательности LFSR длины n составляет \( 2^n - 1 \) (все ненулевые состояния). Это достигается при использовании примитивного полинома обратной связи. Нулевое состояние (все биты равны 0) является вырожденным — регистр остаётся в нём навсегда, поэтому его обычно исключают из рассмотрения.

Линейная сложность

Последовательность, генерируемая LFSR, имеет линейную сложность, равную длине регистра n. Это означает, что для её восстановления достаточно знать 2n последовательных битов и решить систему линейных уравнений. Данное свойство делает LFSR уязвимым для криптоанализа.

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

Последовательности LFSR обладают хорошими статистическими характеристиками: равномерным распределением 0 и 1, отсутствием длинных серий и низкой автокорреляцией. Они проходят многие тесты на случайность (например, тесты NIST).

Применение

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

LFSR используется как основной компонент в поточных шифрах (например, A5/1 для GSM, E0 для Bluetooth). Однако из-за линейной сложности LFSR редко применяется в чистом виде — обычно комбинируется с нелинейными функциями (фильтрующие генераторы, комбинирующие генераторы) или используется в составе более сложных систем (например, в шифре Trivium).

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

LFSR применяется для генерации тестовых последовательностей (псевдослучайных тестовых векторов) и для сжатия выходных данных (сигнатурный анализ) в автоматизированных системах тестирования (Built-In Self-Test, BIST).

Теория кодирования

На основе LFSR строятся циклические коды, в частности коды БЧХ и Рида-Соломона. Регистр реализует операцию деления полиномов, что используется для кодирования и декодирования.

Системы связи

LFSR применяется для скремблирования данных (перемешивания битов для устранения длинных последовательностей одинаковых символов) и для расширения спектра в системах с прямым расширением (DSSS), например, в GPS.

Генерация случайных чисел

В микроконтроллерах и FPGA LFSR часто используется для аппаратной генерации псевдослучайных чисел, например, в игровых автоматах, симуляторах и системах моделирования.

Достоинства и недостатки

Достоинства

• Простота аппаратной реализации (требуются только триггеры и элементы XOR).
• Высокая скорость работы (один такт на бит).
• Предсказуемый и максимальный период при правильном выборе полинома.
• Хорошие статистические свойства.

Недостатки

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

Криптоанализ

Основной метод атаки на LFSR — атака по известному открытому тексту. Если известны 2n последовательных битов выходной последовательности, можно составить систему линейных уравнений и найти коэффициенты обратной связи (полином) и начальное состояние регистра. Для противодействия этому применяются нелинейные фильтры, комбинирование нескольких LFSR (например, в генераторе Геффа) или использование нелинейной обратной связи (NLFSR).

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

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

Наиболее эффективно LFSR реализуется на программируемых логических интегральных схемах (ПЛИС, FPGA) или в виде специализированных микросхем. В микроконтроллерах часто используется программная эмуляция.

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

Пример на языке C для 8-битного LFSR с полиномом \( x^8 + x^4 + x^3 + x^2 + 1 \) (отводы 8, 4, 3, 2):

```c unsigned char lfsr = 0x01; // начальное состояние (ненулевое) unsigned char tap = 0x1C; // маска отводов (00011100) unsigned char bit;

for (int i = 0; i < 255; i++) { bit = ((lfsr >> 0) ^ (lfsr >> 1) ^ (lfsr >> 2) ^ (lfsr >> 4)) & 1; lfsr = (lfsr >> 1) | (bit << 7); // вывод lfsr } ```

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

• LFSR был впервые описан в 1950-х годах в работах по теории кодирования и криптографии.
• В шифре A5/1, используемом в стандарте GSM, применяются три LFSR длиной 19, 22 и 23 бита.
• Максимальный период для 64-битного LFSR составляет \( 2^{64} - 1 \approx 1.84 \times 10^{19} \) тактов, что при частоте 1 ГГц соответствует более 580 годам непрерывной работы.

Источники

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