Линейные регистры сдвига

Широкое распространение в криптографических приложениях инейных регистров сдвига над конечными полями и кольцами обусловлено целым рядом факторов. Среди них:

— использование только простейших операций сложения и умножения, аппаратно реализованных практически на всех вычислительных средствах;

— высокое быстродействие создаваемых на их основе криптографических алгоритмов;

— большое количество теоретических исследований свойств линейных рекуррентных последовательностей (ЛРП), свидетельствующих об их удовлетворительных криптографических свойствах.

Введем ряд определений.

Последовательностью над полем Р будем называть любую функцию u: N ₀® P, заданную на множестве целых неотрицательных чисел и принимающую значения в поле.

Последовательность u называют линейной рекуррентной последовательностью (ЛРП) порядка m > 0 над полем Р, если существуют константы f ₀, …, f_{m -1}Î P такие, что

ЛРП реализуется схемой линейного регистра сдвига, изображенной на рис. 1.

 

 

Рис.1 Линейный рекуррентный регистр

 

В очередном такте работы регистра значения, содержащиеся в ячейках его накопителя, умножаются на соответствующие коэффициенты (f_j) и суммируются, после чего происходит (левый) сдвиг информации в регистре, а в освободившуюся крайнюю ячейку записывается вычисленное значение суммы. Заметим при этом, что операции сложения и умножения выполняются в поле Р.

Равенство, выражающее зависимость между знаками линейной рекуррентной последовательности, называют законом рекурсии, многочлен — характеристическим многочленом ЛРП u, а вектор — начальным вектором ЛРП (или начальным заполнением ЛРР).

Характеристический многочлен ЛРП u, имеющий наименьшую степень, называется ее минимальным многочленом, а степень минимального многочлена — линейной сложностью ЛРП u.

Линейная сложность ЛРП определяет минимальную длину линейного регистра сдвига, реализующего данную последовательность.

Периодом последовательности и называется наименьшее натуральное число t, для которого существует натуральное число l > 0 такое, что для всех справедливо равенство u (l+i+t)= u (l+i).

Из вида закона рекурсии следует, что в случае, когда Р — конечное поле из q элементов, максимальное значение периода ЛРП порядка t равно q^m - 1.

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

Значения периодов линейных рекуррентных последовательностей определяются свойствами их минимальных многочленов. В частности, для того чтобы линейная рекуррентная последовательность порядка t над полем из q элементов имела максимальный период, необходимо и достаточно, что­бы ее минимальный многочлен был примитивным многочленом [6]. Так называется неприводимый многочлен, корень которого имеет в мультипликативной группе поля разложения порядок q^m - 1.

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

Для конечного поля из q элементов будем использовать стандартное обозначение GF (q).

Утверждение 1. Если F (x) — неприводимый многочлен над полем GF (2) степени t, и 2 ^m -1 — простое число, то F (x) —примитивный многочлен.

Утверждение 2. Неприводимый многочлен F (x) примитивен в том и только в том случае, когда для любого простого числа р, делящего q ^m -1, многочлен не сравним с 1 по модулю многочлена F (x).

Построение примитивных многочленов представляет собой сложную задачу, решение которой даже в частных случаях сопряжено со значительными трудностями вычислительного характера. На практике используются таблицы неприводимых и примитивных многочленов над конечными полями (см., например, [6]).

Закон рекурсии дает удобный способ вычисления очередного знака ЛРП через предыдущие, но при изучении ее свойств более предпочтительной формой задания является формула общего члена последовательности, представляющая собой аналитическое выражение члена последовательности в виде функции от его номера.

Линейные рекуррентные последовательности над полем позволяют обеспечить первые два из трех требовании к псевдослучайным последовательностям, используемым при построении управляющих блоков поточных шифрсистем. За счет выбора закона рекурсии можно гарантировать достаточную величину периода получаемой псевдослучайной последовательности и хорошие статистические качества. В самом деле, её период совпадает с числом всех ненулевых векторов длины, равной степени минимального многочлена ЛРП, и каждый их этих векторов встречается на периоде последовательности в точности один раз.

Вместе с тем, аналитическое строение ЛРП оказывается очень простым. Для определения начального вектора по некоторому отрезку последовательности достаточно решить несложную систему линейных уравнений. Поэтому при использовании линейных регистров сдвига в криптографических приложениях необходимо предусматривать процедуры, повышающие сложность аналитического строения вырабатываемых ими рекуррентных последовательностей.