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

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

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

Полином обратной связи обычно записывается в виде:

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

где \( n \) — длина регистра сдвига (количество ячеек), а коэффициенты \( c_i \) принимают значения 0 или 1 (для двоичных LFSR) или принадлежат полю \( GF(2) \) (полю Галуа из двух элементов). В некоторых приложениях (например, в недвоичных регистрах) коэффициенты могут быть элементами более общего поля \( GF(q) \). Коэффициенты определяют, какие отводы (tap) регистра подключены к сумматору по модулю 2 (или по модулю \( q \)). Если \( c_i = 1 \), то выход i-й ячейки участвует в обратной связи; если \( c_i = 0 \) — не участвует.

Рекуррентное соотношение, соответствующее полиному, имеет вид:

\[ s_{t+n} = c_{n-1}s_{t+n-1} \oplus c_{n-2}s_{t+n-2} \oplus \dots \oplus c_1s_{t+1} \oplus c_0s_t \]

где \( s_t \) — значение в ячейке регистра в момент времени \( t \), а \( \oplus \) — операция сложения по модулю 2 (XOR). Для недвоичных систем операция сложения выполняется по модулю характеристики поля.

Типы полиномов обратной связи

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

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

Примеры примитивных полиномов небольшой степени:

• \( x^3 + x + 1 \) (степень 3, период 7)
• \( x^4 + x + 1 \) (степень 4, период 15)
• \( x^5 + x^2 + 1 \) (степень 5, период 31)
• \( x^7 + x + 1 \) (степень 7, период 127)

Неприводимые полиномы

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

Полиномы с обратной связью по Галуа и Фибоначчи

Существуют две основные архитектуры LFSR, различающиеся способом вычисления обратной связи:

• Архитектура Фибоначчи (внешняя обратная связь): выходы нескольких ячеек (отводы) суммируются и подаются на вход первой ячейки. Полином обратной связи при этом описывает, какие ячейки участвуют в суммировании.
• Архитектура Галуа (внутренняя обратная связь): каждый такт значение из старшей ячейки подаётся на сумматоры, расположенные между ячейками, в соответствии с полиномом. Полином обратной связи для архитектуры Галуа часто записывается в обратном порядке коэффициентов.

Обе архитектуры эквивалентны по своим свойствам, но отличаются скоростью работы и сложностью реализации.

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

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

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

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

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

Коды с исправлением ошибок

Полиномы обратной связи используются в циклических кодах (коды БЧХ, коды Рида — Соломона) для описания порождающих полиномов и полиномов обратной связи в регистрах сдвига, реализующих кодирование и декодирование. Примитивные полиномы лежат в основе построения полей Галуа, необходимых для работы кодов Рида — Соломона.

Системы связи с расширенным спектром

В системах с прямым расширением спектра (DSSS) и с частотными скачками (FHSS) LFSR с примитивным полиномом используются для генерации псевдослучайных последовательностей, управляющих перестройкой частоты или модуляцией. Пример — GPS-сигналы, где используются коды C/A (Coarse/Acquisition), генерируемые LFSR с полиномами \( x^{10} + x^3 + 1 \) и \( x^{10} + x^9 + x^8 + x^6 + x^3 + x^2 + 1 \).

Критерии выбора полинома обратной связи

При выборе полинома обратной связи для LFSR учитываются следующие требования:

• Максимальный период: полином должен быть примитивным, чтобы период последовательности составлял \( 2^n - 1 \).
• Линейная сложность: для криптографических приложений полином должен иметь высокую линейную сложность, чтобы последовательность была устойчива к атакам на основе линейной рекуррентности.
• Количество отводов: полиномы с малым числом ненулевых коэффициентов (маловесные полиномы) проще реализуются аппаратно, но могут быть уязвимы для некоторых атак. Оптимальным считается полином с тремя или пятью ненулевыми коэффициентами (трином или пентаном).
• Статистические свойства: последовательность должна проходить статистические тесты на случайность (например, тесты NIST).

Таблица примитивных полиномов для LFSR

Ниже приведены примеры примитивных полиномов для различных длин регистра (степени \( n \)):

Критика и ограничения

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

Источники

• Голомб, С. У. (1967). Shift Register Sequences. Holden-Day.
• Лидл, Р., Нидеррайтер, Г. (1988). Конечные поля. Мир.
• Мэсси, Дж. Л. (1969). «Shift-register synthesis and BCH decoding». IEEE Transactions on Information Theory.
• Шнайер, Б. (1996). Прикладная криптография. John Wiley & Sons.
• NIST Special Publication 800-22. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications.