Данная работа посвящена исследованию задачи нахождения k-error линейной сложности бинарной последовательности. Написаны программы нахождения точного решения k-error линейной сложности для частных случаев.

Ключевые слова: бинарная последовательность, линейная сложность, k-error линейная сложность, алгоритм Берлекэмпа — Мэсси, алгоритм Стэмпа и Мартина.

Известно, что такое свойство последовательности, как линейная сложность, значимо в определении криптографически сильных последовательностей. Введем основные определения.

Дана бесконечная последовательность 𝑠 = , , ... (либо конечная последовательность 𝑠 = , , . . . ,) с элементами из поля 𝐾.

Определение 1. Говорят, что 𝑠 является линейной рекуррентной последовательностью порядка 𝐿 (𝐿 > 0), если для членов этой последовательности выполняется соотношение

для любых 𝑗 = 𝐿, 𝐿 + 1, . . . (или для любых 𝑗 = 𝐿, 𝐿 + 1, . . . , 𝑡 – 1 соответственно), где , . . . , ∈ {0, 1}.

Это уравнение называют линейным рекуррентным отношением порядка 𝐿.

Определение 2. Минимальное 𝐿, такое что 𝑠 является линейной рекуррентной последовательностью порядка 𝐿, называется линейной сложностью последовательности 𝑠.

Cуществует эффективный метод нахождения линейной сложности конечной или периодической последовательности, описанный в источнике [1], известный как алгоритм Берлекэмпа — Мэсси (Berlekamp — Massey Algorithm, BMA).

Пример. Рассмотрим 20-периодичную последовательность 𝑠 с циклом

= 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0.

Ее линейная сложность, посчитанная при помощи алгоритма Берлекэмпа-Мэсси, равна 19.

Пусть дана бесконечная двоичная последовательность 𝑠 = , , ... Через обозначим линейную сложность подпоследовательности = , , . . . ,, 𝑁 > 0.

Последовательность , , ... называется профилем линейной сложности последовательности 𝑠. В случае конечной последовательности профиль линейной сложности состоит из , , . . . ,.

Рассмотрим периодическую последовательность , введенную ранее в примере. Ее профиль линейной сложности, имеющий вид: 1, 1, 1, 3, 3, 3, 3, 5, 5, 5, 6, 6, 6, 8, 8, 8, 9, 9, 10, 10,11, 11, 11, 11, 14, 14, 14, 14, 15, 15, 15, 17, 17, 17, 18, 18, 19, 19, 19, 19, ... , изображен на Рис. 1.

Рис. 1.

Понятие линейной сложности было обобщено до 𝑘-error линейной сложности — минимальной линейной сложности последовательности, в которой по крайней мере 𝑘 элементов были изменены. Эта концепция была впервые изложена Ding, Xiao, Shan [2], которые назвали ее весовой сложностью, и получила название 𝑘-error линейной сложности в работе авторов Stamp и Martin [3]. Это свойство последовательности является важным критерием безопасности потоковых шифров и применяется к проблеме идентификации криптостойких псевдослучайных последовательностей.

Пусть 𝑠 = , , ... — бесконечная последовательность периода 𝑁 с элементами из поля 𝐾. Зафиксируем целочисленное значение 𝑘, 0 𝑘 (, . . . , ), где

(, . . . , ) — вес Хэмминга последовательности = (, . . . , ).

Определение 3. Линейная сложность с k-кратной ошибкой (или k-error линейная сложность) бесконечной периодической последовательности 𝑠 определяется как

(𝑠) = {𝐿(𝑠 + 𝑒) | 0 (, . . . , ) 𝑘},

где 𝑒 — периодическая последовательность из поля 𝐾 с периодом 𝑁.

Последовательности 𝑒 называют вектором ошибок.

Определение 4. Последовательность (𝑠), (𝑠), (𝑠), . . . называется профилем 𝑘-error линейной сложности последовательности 𝑠.

Замечание 1. В этой работе в качестве поля 𝐾 будет использоваться поле Галуа 𝐺𝐹(2) с операцией сложения по модулю 2, то есть его элементами будут двоичные последовательности длины 𝑡. Тогда вес Хэмминга некоторой последовательности 𝑠, (𝑠), будет определяться как количество единиц в этой последовательности.

Не существует общего алгоритма для вычисления профиля 𝑘-error линейной сложности произвольной последовательности над произвольным конечным полем, кроме полного перебора.

Точный алгоритм для вычисления 𝑘-error линейной сложности бинарных последовательностей с периодом , 𝑚 > 1, был предложен авторами Stamp и Martin [3]. Этот эффективный алгоритм является расширением алгоритма Games и Chan [4], предназначенным для вычисления линейной сложности таких последовательностей.

В качестве длины последовательности мы будем брать значения, равные степени 2. Такая локализация нужна для того, чтобы можно было вычислить точные значения 𝑘-error линейной сложности при помощи алгоритма Stamp и Martin. В дальнейшем тестирование будет проходить на бесконечных периодических последовательностях с данным полным периодом. Рассмотрим бинарные последовательности с периодом 𝑛 = = 32.

Начиная с 𝑘=0, будем запускать алгоритм, увеличивая значение 𝑘, пока 𝑘-error линейная сложность не станет равна нулю. Таким образом, мы получим профиль 𝑘-error линейной сложности последовательности 𝑠. Мы применяем алгоритм Stamp и Martin для выборки из 10 последовательностей периода 32 с линейной сложностью 32 (таблица 1), результаты которого представлены в таблице 2. Видно, что выполняется основное свойство 𝑘-error линейной сложности: при увеличении 𝑘 линейная сложность последовательностей уменьшается.

Таблица 1

Тестовые последовательности

Таблица 2

Профиль k-error линейной сложности бинарных последовательностей

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

Код, при помощи которого были получены приведенные выше результаты, доступен по ссылке https://github.com/cafecco/k-error-linear-complexity.

Литература:

1. Massey J.L., Serconek S. Linear Complexity of Periodic Sequences // Lecture Notes in Computer Science. New York: Springer, 1996. V. 1109, P. 358–371.
2. Ding C., Xiao C., Shan W. The Stability Theory of Stream Ciphers // Lecture Notes in Computer Science. Heidelberg: Springer-Verlag. 1992.
3. Stamp M., Martin C.F. An Algorithm for the 𝑘-Error Linear Complexity of Binary Sequences with Period 2𝑛 // IEEE Transactions on Information Theory. 1993. V. 39, № 4, P. 1398–1401.
4. Games R.A., Chan A.H. A Fast Algorithm for Determining the Complexity of a Binary Sequence with Period 2𝑛 // IEEE Transactions on Information Theory. 1983. V. 29, № 1, P. 144–146.