Двоичные линейные последовательности как генераторы гаммы

При построении двоичной последовательности с помощью линейной рекурренты степени k получается последовательность нулей и единиц. Может ли она продолжаться до бесконечности, не повторяясь? Ответ будет "нет", поскольку каждый следующий элемент зависит только от значений k предыдущих элементов, а поскольку элементы принимают только значения 0 и 1, то всего существует только 2^k различных вариантов. Следовательно, не более чем через 2^k шагов какое-то множество из k последовательных двоичных элементов обязательно повторится. Например, последовательность чисел Фибоначчи, приведенная по модулю 2, выглядит так:

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

Видно, что эта двоичная последовательность состоит просто из тройки 011, повторенной бесконечное число раз. Поскольку последовательность чисел Фибоначчи порождена при помощи линейной рекурренты степени 2, то в данном случае имеем k=2, и поэтому двоичная форма этой последовательности обязана повториться не далее, чем через 2²=4 шага. На самом деле она повторяется через 3 шага, и это, в действительности, максимально возможное число, поскольку одна из четырех возможных пар последовательных двоичных элементов равна 00, а эта пара порождает последовательность, состоящую из одних нулей. Наоборот, никакая другая двоичная последовательность не может содержать пары 00. Поэтому максимально возможное число двоичных элементов, которое может встретиться, прежде чем последовательность начнет повторяться, равно 3, а не 4. По этой же причине максимальное число элементов в линейной рекурренте степени k до начала ее повторения равно 2^k-1, а не 2^k. Поэтому, несмотря на свой скромный вид, двоичная последовательность Фибоначчи имеет максимальный период.

Ясно, что двоичная последовательность с максимальным периодом, равным 3, для криптографов интереса не представляет. А что можно сказать о двоичных последовательностях более высоких степеней? Для начала рассмотрим утверждение, которое легко проверить непосредственно: последовательность степени 4 может иметь период 15, то есть 2⁴-1. Если отбросить тривиальный случай, когда все четыре коэффициента равны нулю, то всего существует 15 возможных вариантов линейных рекуррент степени 4. Даст ли какая-нибудь из них последовательность максимального периода 15? Таких последовательностей две, это

U_n = U_(n-3) + U_(n-4)

и

U_n = U_(n-1) + U_(n-4).

Пример 8.1

проверить. Что двоичная линейная рекуррента четвертой степени

U_n = U_(n-3) + U_(n-4)

порождает последовательность максимального периода 15.

Проверка

Начиная с U₀=U₁=U₂=U₃=1, будем вычислять каждый следующий элемент, складывая между собой элементы, отстоящие от него на 3 и 4 позиции, и записывая 0 или 1 в зависимости от того, является ли сумма четной или нечетной. В результате получаем такую последовательность:

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

Видно, что она начинает повторяться, начиная с элемента U₁₅, но не ранее.

(Заметим, что если двоичная последовательность, порожденная линейной рекуррентой порядка k, имеет максимальный период, то она должна содержать все из 2^k возможных двоичных последовательностей длины k, кроме той, которая состоит из одних нулей. Таким образом, в этом случае можно выбрать любые начальные значения, кроме 00..00, и период все равно останется максимальным в любом случае. Если же период не максимальный, то различные начальные значения могут дать различные последовательности.)

Задача 8.1

Проверить, что двоичная рекуррента

U_n = U_(n-1) + U_(n-4)

также порождает последовательность периода 15, а рекуррента

U_n = U_(n-1) + U_(n-2) + U_(n-3) + U_(n-4)

имеет другой период.

А что же будет для последовательностей более высоких степеней? Например, последовательность степени 12 может иметь период, ни много ни мало, 2¹²-1, то есть 4095. Существует ли линейная рекуррента степени 12, дающая двоичную последовательность такого (максимального) периода? В результате довольно изящного применения высшей математики была получена формула, позволяющая подсчитать, сколько именно двоичных линейных рекуррент степени k дают последовательности максимального периода. Для случая рекуррент степени 12 по этой формуле получаем, что 144 двоичных линейных рекурренты степени 12 порождают двоичные последовательности периода 4095. (То, что 144=1212, в данном случае просто совпадение!) Для оставшихся 3952 рекуррент период будет меньше. Эти 144 рекурренты не могут быть получены непосредственно с помощью методов математического анализа, для этого необходимо применить алгоритм, схожий с методом поиска простых чисел. В качестве альтернативы можно протестировать все 4095 возможных рекуррент на компьютере, отсеивая все те, которые начинают повторяться ранее 4096-го знака. Если проделать все это, то первой обнаруженной последовательностью будет

U_n = U_(n-6) + U_(n-8) + U_(n-11) + U_(n-12)

"Первой" она является в том смысле, что если выписать справа от рекурренты нулевые и единичные коэффициенты при всех 12-ти ее членах, то эта последовательность будет иметь 12-битовое представление

000001010011,

которое, если его интерпретировать как двоичную запись целого числа, равно

64 + 16 + 2 + 1 = 83.

Никакая другая последовательность с числовым представлением, меньшим 83, не имеет максимального периода 4095. Некоторые математические факты, лежащие в основе этой теории, содержатся в приложении M11.

Выбрав достаточно большую степень и найдя линейную рекурренту максимального периода, можно получить последовательность знаков гаммы, которая, по-видимому, будет псевдослучайной двоичной последовательностью и может быть использована для шифрования. Например, можно показать, что 356960 линейных рекуррент степени 23 дают последовательности знаков гаммы максимального периода, который превосходит 8000000 (см. M11). Можно было бы предположить, что, поскольку начальные значения также будут иметь более 8000000 вариантов, то такая гамма станет для криптоаналитика трудноразрешимой проблемой. Так и будет, но лишь поначалу. К несчастью для криптографов, полученная таким способом гамма имеет фатальный недостаток: при наличии совсем небольшого отрезка последовательности можно восстановить и вид линейной рекурренты, с помощью которой он получен, и его начальные значения. Это вытекает из следующего утверждения.