Повышение стойкости двоичной гаммы

Очевидно, что двоичную гамму, порожденную линейной рекуррентой, вскрыть слишком просто, чтобы подобная последовательность оказалась полезной с криптографической точки зрения. Существует ли какой-нибудь способ увеличения стойкости таких последовательностей? Поскольку их слабость заключается в том, что для рекурренты степени k каждый бит является фиксированной линейной комбинацией предыдущих k битов, даже использование рекурренты высокой степени (например, если взять k=103) не обеспечивает необходимой стойкости, потому что для решения системы уравнений достаточно совсем небольшого отрезка гаммы (для k=103 необходимо всего 26 знаков). Вдобавок, получать гамму с помощью рекурренты высокой степени вручную (как пришлось бы поступить шпиону) - занятие довольно утомительное, да и ошибок можно наделать. Очень жаль, ведь гамма, полученная при помощи такой рекурренты, может иметь очень большой период (для k=103 он превосходит 10³⁰). Конечно, большой период весьма желателен, но может быть, этого можно добиться и без использования рекурренты высокой степени, повысив одновременно стойкость? Это действительно можно сделать, комбинируя гамму от двух или более линейных рекуррент, как показано в следующем простом примере.

Пример 8.2

Вычисляя сумму (по модулю 2) двух последовательностей знаков гаммы, порожденных двумя линейными рекуррентами

U_n = U_(n-1) + U_(n-2), U₀=U₁ =1

и

U_n = U_(n-1) + U_(n-3), U₀=U₁=U₂=1,

получить новую последовательность знаков гаммы. Проверить, что она имеет период 21.

Проверка

Первая рекуррента, как мы уже убедились, имеет период 3 и порождает последовательность знаков гаммы

110110110110...

Вторая рекуррента имеет период 7 и порождает последовательность знаков гаммы

111010011101001110100...

Подписав обе эти последовательности друг под другом и сложив их по модулю 2, получим

110110110110110110110110110...

111010011101001110100111010...

Сумма (по модулю 2) 001100101011111000010001100...

Как видно, гамма начинает повторяться после 21-го шага, но не ранее. Поскольку первая последовательность имеет период 3, а вторая имеет период 7, то период комбинированной гаммы не может быть больше 21, так как они обе повторяются через 21 шаг. С другой стороны, так как числа 3 и 7 не имеют общих делителей, то комбинированная гамма не может повториться раньше, чем через 21 шаг.

Нет никакой необходимости ограничиваться использованием только двух линейных рекуррент: можно использовать и три, и больше. Преимущество этого подхода в том, что чем больше рекуррент использовать, тем труднее криптоаналитику будет вскрыть систему. Недостатком же, если работать приходится вручную, является достаточно утомительный способ получения гаммы и высокая вероятность ошибок. Конечно, от этого недостатка можно избавиться, если у нас есть возможность выработать гамму с помощью механического или электронного устройства. Поэтому неудивительно, что появились машины, порождающие последовательности знаков гаммы большого периода, как двоичные (т.е. модуля 2), так и алфавитные (т.е. модуля 26), которые являются комбинациями нескольких более коротких последовательностей. Одной из таких машин была шифрмашина "Хагелин", широко использовавшаяся во время Второй мировой войны целым рядом стран; она вырабатывала последовательность знаков гаммы модуля 26. Другой пример - это "Lorenz SZ42", одна из шифрмашин, использовавшихся в Германии; она вырабатывала последовательность знаков гаммы модуля 2. О них рассказано в главах 10 и 11.