Широкое распространение в криптографических приложениях линейных регистров сдвига над конечными полями и кольцами обусловлено целым рядом факторов. Среди них можно отметить:
– пользование только простейших операций сложения и умножения, аппаратно реализованных практически на всех вычислительных средствах;
– высокое быстродействие создаваемых наих основе криптографических алгоритмов;
– большое количество теоретических исследований свойств рекуррентных последовательностей (ЛРП), свидетельствующих об их удовлетворительных криптографических свойствах.
Введем ряд определений.
Последовательностью над полем Р будем называть любую функцию и:n0—>Р, заданную на множестве целых неотрицательных чисел и принимающую значения в поле.
Последовательность и называют линейной рекуррентной последовательностью (ЛРП) порядка т>0 над полем Р, если существуют константы f0,...,fт -1ÎP такие, что
u(i+m)=
ЛРП реализуется схемой линейного регистра сдвига.
В очередном такте работы регистра значения, содержащиеся в ячейках его накопителя, умножаются на соответствующие коэффициенты (fj) и суммируются, после чего происходит (левый) сдвиг информации в регистре, а в освободившуюся крайнюю ячейку записывается вычисленное значение суммы. Заметим при этом, что операции сложения и умножения выполняются в поле Р.
Равенство, выражающее зависимость между знаками линейной рекуррентной последовательности, называют законом рекурсии, многочлен
Характеристический многочлен ЛРП и, имеющий наименьшую степень, называется ее минимальным многочленом, а степень минимального многочлена – линейной сложностью ЛПР и.
Линейная сложность ЛРП определяет минимальную длину линейного регистра сдвига, реализующего данную последовательность.
Периодом последовательности и называется наименьшее натуральное число t, для которого существует натуральное число l > 0 такое, что для всех i >0 справедливо равенство u(l+i+t)=u(l +i).
Из вида закона рекурсии следует, что в случае, когда Р – конечное поле из q элементов, максимальное значение периода ЛРП порядка т равно qm –1. В самом деле, нулевой начальный вектор порождает последовательность, состоящую из одних нулей, а число различных заполнений регистра длины т равно qm.
Последовательности, имеющие максимально возможный период, получили название линейных рекуррентных последовательностей максимального периода или просто максимальныx рекуррентных последовательностей.
Значения периодов линейных рекуррентных последовательностей определяются свойствами их минимальных многочленов. В частности, для того чтобы линейная рекуррентная последовательность порядка т над полем из q элементов имела максимальный период, необходимо и достаточно, чтобы минимальный многочлен был примитивным многочленом. Так называется неприводимый многочлен, корень которого имеет в мультипликативной группе поля разложения порядок qm –1.
Несмотря на то, что имеется достаточно много критериев проверки неприводимости многочленов над конечными полями и методов их построения, доказать то, что заданный неприводимый многочлен примитивен, удается в исключительных случаях.
Для конечного поля из q элементов будем использовать стандартное обозначение GF(q) .
Утверждение 1.Если F(x) – неприводимый многочлен над полем GF(2) степени т, и 2m –1 – простое число, то F(x) – примитивный многочлен.
Общий подход к построению примитивных многочленов состоит в построении неприводимых многочленов и непосредственном вычислении их периодов. Проверка максимальности периода неприводимого многочлена может быть осуществлена с помощью следующего утверждения:
Утверждение 2. Неприводимый многочлен F(x) примитивен в том и только в том случае, когда для любого простого числа р , делящего qm–1, многочлен не сравним с 1 по модулю многочлена F(x).
Построение примитивных многочленов представляет собой сложную задачу, решение которой даже в частных случаям сопряжено со значительными трудностями вычислительного характера. На практике используются таблицы неприводимых и примитивных многочленов над конечными полями.
Закон рекурсии дает удобный способ вычисления очередного знака ЛРП через предыдущие, но при изучении ее свойств более предпочтительной формой задания является формула общего члена последовательности, представляющая собой аналитическое выражение члена последовательности в виде функции от его номера. Рассмотрим этот способ представления на примере ЛРП над конечными полями с неприводимыми характеристическими многочленами.
Пусть P=GF(q) и Q –поле из qm элементов, являющееся расширением поля Р. Тогда функцией "след" из поля Q в поле Р называется отображение
вида
В силу свойств конечных полей справедливы равенства
означающие, что функция "след" является линейным отображением над полем Р.
лемма 1.Для любого ненулевого а Î Р и любого bÎ Р число решений уравнения равно qm-1.
Теорема 1.Пусть – неприводимый многочлен над
полем Р степени т, Q —корень F(x) в поле Q. Тогда для ЛРП {u(i)} с характеристическим многочленом F(x) существует единственная константа а Î Р, такая, что
Пусть и – ЛРП максимального периода над полем Р и
v(a1,…,ak) — число решений системы уравнений
то-есть число появлений мультиграммы a1,…,ak на периоде последовательности и.
Утверждение 3.Пусть F(x) – примитивный многочлен степени т над полем Р и Q – корень F(x) в поле Q. Тогда любая ненулевая мультиграмма (a1,…,ak) встречается на периоде ЛРП и ровно
v(a1,…,ak)=qm-k
раз, а число вхождений нулевой мультиграммы на единицу меньше.
Представленные результаты показывают, что линейные рекуррентные последовательности над полем позволяют обеспечить первые два из трех требований к псевдослучайным последовательностям, используемым при построении управляющих блоков поточных шифрсистем. За счет выбора закона рекурсии можно гарантировать достаточную величину периода получаемой псевдослучайной последовательности и хорошие статистические качества. В самом деле, ее период совпадает с числом всех ненулевых векторов длины, равной степени минимального многочлена ЛРП, и каждый из этих векторов встречается на периоде последовательности в точности один раз.
Вместе с тем аналитическое строение ЛРП оказывается очень простым. Для определения начального вектора по некоторому отрезку последовательности достаточно решить несложную систему линейных уравнений. Поэтому при использовании линейных регистров сдвига в криптографических приложениях необходимо предусматривать процедуры, повышающие сложность аналитического строения вырабатываемых ими рекуррентных последовательностей.
Последовательность и называют линейной рекуррентной последовательностью (ЛРП) порядка т>0 над полем Р, если существуют константы f0,...,fт -1ÎP такие, что
Равенство, выражающее зависимость между знаками линейной рекуррентной последовательности, называют законом рекурсии, многочлен
Утверждение 2. Неприводимый многочлен F(x) примитивен в том и только в том случае, когда для любого простого числа р , делящего qm –1, многочлен не сравним с 1 по модулю многочлена F(x).
Пусть P=GF(q) и Q –поле из q m элементов, являющееся расширением поля Р. Тогда функцией "след" из поля Q в поле Р называется отображение
вида
В силу свойств конечных полей справедливы равенства
Пусть и – ЛРП максимального периода над полем Р и
v(a1,…,ak) — число решений системы уравнений