ТОЧНЫЕ АЛГОРИТМЫ ДЛЯ ВЫЧИСЛЕНИЯ K-ERROR ЛИНЕЙНОЙ СЛОЖНОСТИ БИНАРНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ

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

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

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

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

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

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

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

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

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

Ее линейная сложность, посчитанная при помощи BMA, равна 19.

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

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

Тогда профиль линейной сложности  последовательности  представляется в виде: 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, ... .

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

Пусть s = , , ... — бесконечная последовательность периода N с элементами из поля k. Зафиксируем значение k,  0  k    ( , . . . , ), где ( , . . . , ) — вес Хэмминга последовательности = ( , . . . , ).

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

где e — вектор ошибок, периодическая последовательность с периодом N.

Определение 4. Последовательность L₀ (s), L₁(s), L₂(s), . . . называется профилем k-error линейной сложности последовательности s.

Замечание 1. В этой работе в качестве поля K будет использоваться поле Галуа GF(2) с операцией сложения по модулю 2.

Точный алгоритм для вычисления k-error линейной сложности бинарных последовательностей с периодом 2^m , m > 1, был предложен авторами Stamp и Martin [3]. В качестве длины последовательности мы будем брать значения, равные степени 2. Рассмотрим бинарные последовательности с периодом n = 2⁵  = 32.

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

Таблица 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 k-Error Linear Complexity of Binary Sequences with Period 2n // IEEE Transactions on Information Theory. 1993. V. 39, № 4, P. 1398–1401.