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

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

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

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

Основные элементы

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

Математическое описание

Состояние LFSR в момент времени t описывается вектором из n битов: \( S_t = (s_{t,0}, s_{t,1}, \dots, s_{t,n-1}) \). Следующее состояние \( S_{t+1} \) вычисляется следующим образом:

Для конфигурации Фибоначчи (наиболее распространённой):

• \( s_{t+1,0} = \bigoplus_{i \in T} s_{t,i} \), где \( T \) — множество индексов отводов, а \( \bigoplus \) — операция XOR.
• \( s_{t+1,j} = s_{t,j-1} \) для \( j = 1, 2, \dots, n-1 \).

Таким образом, каждый новый бит поступает на вход, а все остальные биты сдвигаются на одну позицию вправо. Выходной последовательностью обычно является последовательность битов, вытесняемых из самого правого разряда регистра: \( b_t = s_{t,n-1} \).

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

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

По архитектуре обратной связи

• Конфигурация Фибоначчи (внешняя обратная связь): XOR-сумматоры расположены вне сдвигового регистра, и их выход подаётся на вход регистра. Отводы берутся от выходов отдельных триггеров. Это классическая и наиболее интуитивно понятная схема.
• Конфигурация Галуа (внутренняя обратная связь): XOR-сумматоры встроены в цепь сдвига между триггерами. Входной бит вычисляется как XOR бита с последнего отвода и выходного бита регистра. Эта конфигурация позволяет реализовать более быстродействующие схемы, так как цепь обратной связи имеет меньшую задержку, но математически она эквивалентна конфигурации Фибоначчи при соответствующем выборе отводов.

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

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

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

Работа LFSR тесно связана с понятием примитивного многочлена (полинома) над полем Галуа GF(2). Полином обратной связи, или характеристический полином, имеет вид:

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

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

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

Характеристики и свойства

Период

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

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

Последовательности, генерируемые LFSR с максимальным периодом, обладают хорошими статистическими свойствами, близкими к свойствам идеальной случайной последовательности:

• Сбалансированность: количество единиц и нулей в полном периоде различается ровно на единицу (единиц на одну больше).
• Свойство прогонов (runs): в полном периоде последовательности встречаются прогоны (последовательности одинаковых битов) различной длины. Количество прогонов длины k равно \( 2^{n-k-2} \) для \( k \le n-2 \), и один прогон длины n.
• Автокорреляция: автокорреляционная функция последовательности имеет резкий пик при нулевом сдвиге и малые значения при всех остальных сдвигах.

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

Несмотря на хорошие статистические свойства, LFSR не является криптостойким генератором сам по себе. Линейность обратной связи делает его уязвимым для атаки на основе известного открытого текста (или известной части выходной последовательности). Если злоумышленнику известно \( 2n \) последовательных битов выходной последовательности, он может восстановить начальное состояние и полином обратной связи, решив систему линейных уравнений. Для повышения криптостойкости LFSR комбинируют с нелинейными элементами, например, в генераторах типа «комбинаторный генератор» или «фильтрующий генератор», а также в поточных шифрах, таких как A5/1 (используется в GSM) и Trivium.

Применение

Генерация псевдослучайных чисел (ПСЧ)

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

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

LFSR являются основой многих поточных шифров. Например, шифр A5/1, используемый для шифрования трафика в сети GSM, основан на трёх LFSR разной длины. Шифр Trivium, финалист конкурса eSTREAM, также построен на основе LFSR. Однако, как отмечалось, LFSR в чистом виде не применяются для защиты информации из-за своей линейности.

Тестирование цифровых схем (Built-In Self-Test, BIST)

В микросхемах LFSR используются для генерации тестовых последовательностей (паттернов) и для сжатия выходных сигналов (сигнатурного анализа). С помощью LFSR можно с высокой вероятностью обнаружить неисправности в логических схемах.

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

В системах с расширением спектра (например, в технологии CDMA) LFSR применяются для генерации псевдослучайных последовательностей, используемых для «размазывания» сигнала по широкой полосе частот. Это позволяет нескольким пользователям одновременно передавать данные в одном частотном диапазоне.

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

• Коды коррекции ошибок: LFSR используются для реализации циклических кодов, таких как коды CRC (Cyclic Redundancy Check), которые широко применяются для обнаружения ошибок при передаче данных.
• Сжатие данных: в некоторых алгоритмах сжатия, например, в LZ77, LFSR могут использоваться для генерации скользящего окна.
• Генерация шума: в аудиотехнике и электронике LFSR применяются для создания «белого» или «розового» шума.

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

• Последовательность, генерируемая LFSR с максимальным периодом, называется M-последовательностью (от maximal-length sequence).
• В 1960-х годах компания Bell Labs использовала LFSR для генерации случайных чисел в своих ранних компьютерных системах.
• Некоторые реализации LFSR в аппаратуре могут быть настолько быстрыми, что способны генерировать миллиарды бит в секунду.
• Выбор отводов для LFSR — нетривиальная задача. Неправильный выбор приводит к значительному сокращению периода. Существуют таблицы примитивных многочленов, которые гарантируют максимальный период.

Источники

• Голомб, С. У. (1967). Shift Register Sequences. Holden-Day.
• Шнайер, Б. (1996). Прикладная криптография. John Wiley & Sons.
• Мак-Вильямс, Ф. Дж., Слоэн, Н. Дж. А. (1977). Теория кодов, исправляющих ошибки. North-Holland.
• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
• Статья «Linear-feedback shift register» в англоязычной Википедии (версия от 2023 года).