Криптоанализ линейной рекурренты

Если известны 2k последовательных бита гаммы, порожденной двоичной линейной рекуррентой степени k, то можно построить и решить систему из k линейных уравнений относительно k неизвестных коэффициентов при членах рекурренты.

Если криптоаналитик имеет основания предполагать использование гаммы, полученного с помощью линейной рекурренты, то ему следует действовать так:

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

2. задать значение k, то есть степень линейной рекурренты;

3. по известным 2k последовательным разрядам гаммы составить k линейных уравнения относительно k неизвестных коэффициентов рекурренты; если рекуррента на самом деле имеет степень k, то система имеет решение, в котором все коэффициенты - целые числа (их надо интерпретировать по модулю 2, то есть как четные и нечетные); возможно, что решение для степени k будет не единственным, или, напротив, решения может вовсе не быть, в последнем случае следует попробовать другое значение k.

Итак, если символы представлены 8-разрядными байтами, а последовательность знаков гаммы порождена с помощью двоичной линейной рекурренты степени 23, то для решения системы понадобится всего 46 двоичных разрядов гаммы . Так как в 6 знаках сообщения 48 битов, то система может быть легко решена, если, например, сообщения обычно начинаются с букв TO THE!

Примеры, в которых рассматриваются варианты решения системы, разобраны в приложении M12.