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

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

Определение и формальное описание

Пусть \( S = (s_0, s_1, \dots, s_{N-1}) \) — конечная двоичная последовательность длины \( N \). Линейной сложностью \( L(S) \) называется наименьшее неотрицательное целое число \( L \), для которого существуют коэффициенты \( c_1, c_2, \dots, c_L \in \{0,1\} \) такие, что для всех \( i = L, L+1, \dots, N-1 \) выполняется рекуррентное соотношение:

\[ s_i = c_1 s_{i-1} \oplus c_2 s_{i-2} \oplus \dots \oplus c_L s_{i-L} \]

где \( \oplus \) обозначает сложение по модулю 2 (исключающее ИЛИ). Если такой \( L \) не существует (например, для последовательности, не являющейся линейно рекуррентной), то полагают \( L(S) = N \).

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

Свойства

Линейная сложность обладает рядом важных свойств:

• Монотонность: Для любой последовательности \( S \) длины \( N \) выполняется \( L(S) \leq N \). Если последовательность полностью случайна, то с высокой вероятностью \( L(S) \approx N/2 \).
• Инвариантность относительно сдвига: Линейная сложность не меняется при циклическом сдвиге последовательности.
• Связь с энтропией: Для истинно случайных двоичных последовательностей математическое ожидание линейной сложности равно \( N/2 \), а дисперсия — \( N/4 \).
• Свойство аддитивности: Для суммы по модулю 2 двух последовательностей \( S_1 \) и \( S_2 \) выполняется \( L(S_1 \oplus S_2) \leq L(S_1) + L(S_2) \).

Алгоритм Берлекэмпа — Мэсси

Основным методом вычисления линейной сложности конечной последовательности является алгоритм Берлекэмпа — Мэсси (Berlekamp–Massey algorithm), разработанный Элвином Берлекэмпом в 1968 году и адаптированный Джеймсом Мэсси для криптографических целей в 1969 году. Алгоритм работает итеративно, начиная с пустой последовательности, и для каждого нового символа корректирует минимальный LFSR, если текущий регистр не может предсказать этот символ. Временная сложность алгоритма составляет \( O(N^2) \), где \( N \) — длина последовательности.

Алгоритм Берлекэмпа — Мэсси является ключевым инструментом в криптоанализе поточных шифров, основанных на LFSR, поскольку позволяет определить линейную сложность перехваченной последовательности и, при достаточной длине, восстановить структуру регистра.

Применение в криптографии

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

Критерии безопасности

• Высокая линейная сложность: Для последовательности длины \( N \) желательно, чтобы \( L(S) \approx N/2 \). Значительное отклонение от этого значения указывает на наличие линейной структуры.
• Стабильность линейной сложности: Линейная сложность не должна резко меняться при малых изменениях последовательности (например, при инвертировании одного бита). Это свойство называется профилем линейной сложности.
• Профиль линейной сложности: График зависимости линейной сложности от длины последовательности. Для случайной последовательности профиль должен быть близок к прямой линии с наклоном 1/2.

Примеры уязвимостей

• Генератор на основе одного LFSR: Если поточный шифр использует только один LFSR, то его линейная сложность равна длине регистра. Злоумышленник, перехватив \( 2L \) бит, может восстановить регистр с помощью алгоритма Берлекэмпа — Мэсси.
• Комбинационные генераторы: Шифры, объединяющие выходы нескольких LFSR с помощью нелинейной булевой функции (например, генератор Геффа), имеют линейную сложность, равную сумме длин регистров, что всё ещё может быть недостаточно при малых длинах.

Классификация последовательностей по линейной сложности

Последовательности можно классифицировать на основе их линейной сложности:

• Линейно рекуррентные последовательности: Имеют конечную линейную сложность, не зависящую от длины последовательности. Пример — последовательности, генерируемые LFSR.
• Псевдослучайные последовательности: Линейная сложность растёт линейно с длиной, но с наклоном около 1/2. Типичны для криптографически стойких генераторов.
• Случайные последовательности: Для истинно случайных последовательностей линейная сложность равна \( N/2 \) в среднем, но может варьироваться.
• Последовательности с низкой линейной сложностью: Например, последовательность из одних нулей имеет \( L = 0 \), а последовательность из одних единиц — \( L = 1 \).

Связь с другими понятиями

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

• Минимальным многочленом последовательности: Для периодической последовательности линейная сложность равна степени её минимального многочлена над полем \( GF(2) \).
• Сложностью по Колмогорову: Линейная сложность является более узким понятием, оценивающим только линейные рекуррентные закономерности, в отличие от универсальной колмогоровской сложности.
• Корреляционной сложностью: В криптоанализе также используется понятие корреляционной сложности, учитывающей нелинейные зависимости.

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

Линейная сложность, хотя и является важным показателем, не является единственным критерием криптографической стойкости. Последовательность может иметь высокую линейную сложность, но быть уязвимой для других атак, например:

• Корреляционные атаки: Если выход генератора линейно коррелирован с внутренними состояниями LFSR, злоумышленник может восстановить ключ, не вычисляя полную линейную сложность.
• Атаки на основе алгебраических методов: Для некоторых генераторов (например, на основе фильтрующих функций) линейная сложность может быть высокой, но система может быть решена методами линеаризации.
• Недостаточность для оценки сложности: Линейная сложность не учитывает нелинейные преобразования, которые могут быть использованы в современных шифрах (например, в AES или ChaCha20).

История

Понятие линейной сложности было введено в 1960-х годах в контексте теории кодирования и линейных рекуррентных последовательностей. Алгоритм Берлекэмпа — Мэсси, опубликованный в 1969 году, стал стандартным инструментом для её вычисления. В 1980-х годах линейная сложность была активно исследована в связи с разработкой поточных шифров (например, A5/1, используемый в GSM), где она стала одним из основных критериев оценки. В 1990-х годах были предложены обобщения, такие как линейная сложность с весом и 2-адическая сложность, учитывающие другие типы рекуррентных соотношений.

Источники

• Берлекэмп Э. Р. «Алгебраическая теория кодирования». — М.: Мир, 1971.
• Мэсси Дж. Л. «Shift-register synthesis and BCH decoding» // IEEE Transactions on Information Theory. — 1969. — Vol. 15, No. 1. — P. 122–127.
• Шнайер Б. «Прикладная криптография». — М.: Триумф, 2002.
• Cusick T. W., Ding C., Renvall A. «Stream Ciphers and Number Theory». — North-Holland, 1998.
• Rueppel R. A. «Analysis and Design of Stream Ciphers». — Springer-Verlag, 1986.