Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии

/юточные системы шифрования

Рис. 35

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

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

—использование только простейших операций сложения

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

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

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

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

Последовательностью над полем Р будем называть лю­

бую функцию и: N 9 -> Р , заданную на множестве целых не­

отрицательных чисел и принимающую значения в поле.

251

Глава 9

Последовательность и называют линейной рекуррентной последовательностью (ЛРП) порядка т> 0 над полем Р , если существуют константы / 09—9/ т-\ € Р такие, что

«(/ + т)= Ё / • и(/ + у ),/ > 0 .

7=0

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

Рис. 36

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

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

Равенство, выражающее зависимость между знаками ли­ нейной рекуррентной последовательности, называют законом

252

/юточные системы шифрования

= (и(0),...,и(т —1))— начальным вектором ЛРП (или на­

чальным заполнением ЛРС).

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

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

Периодом последовательности и называется наименьшее натуральное число для которого существует натуральное число Л> О такое, что для всех / > 0 справедливо равенство

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

гистра длины т равно д т.

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

Значения периодов линейных рекуррентных последова­ тельностей определяются свойствами их минимальных мно­ гочленов. В частности, для того чтобы линейная рекуррентная последовательность порядка т над полем из ^ элементов имела максимальный период, необходимо и достаточно, что­ бы ее минимальный многочлен был примитивным многочле­ ном [Лид88]. Так называется неприводимый многочлен, ко­ рень которого имеет в мультипликативной группе поля раз­

ложения порядок д т - 1 .

253

Гпава 9

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

Для конечного поля из ^ элементов будем использовать

стандартное обозначение С Р (д ) .

Утверждение 1 . Если Р(х) — неприводимый многочлен над

полем С Р{2) степени т , и 2т—1 — простое число, то

Р(х) — примитивныймногочлен.

Доказательство. Из неприводимости многочлена Р(х) сле­

дует, что единица поля СР( 2 т ) (которое является его полем

разложения) не является корнем этого многочлена. Так как по ус­

ловию (2т ~ 1) — простое число, все элементы поля СР( 2 м) ,

отличные от единицы, имеют в мультипликативной группе этого

поля порядок 2т- 1 . Следовательно, Р(х) — примитивный

многочлен.

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

Утверждение 2. Неприводимый многочлен Р(х) примити­

вен в том и только в том случае, когда для любого простого чис-

лю многочлена Р (х ) .

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

254

/юточные системы шифрования

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

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

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

щееся расширением поля Р . Тогда функцией “след” из поля

т

<2 в поле Р называется отображение 1г^ (а) :() -* Р вида

В силу свойств конечных полей справедливы равенства

(1Гд ( Х )У' = 1гд (х ) .

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

Лемма 1 . Для любого ненулевого а е Р и любого Ье Р

т

число решений уравнения Iг^ (а- х ) - Ъ равно фп .

Д оказательство. Обозначим через N ь число решений

рассматриваемого уравнения. Тогда для любого Ь е Р выпол­

няется неравенство Ыь < ц т~х, так как ц т~х — степень мно­

255

иметь корней больше, чем его степень. С другой стороны, для

любого Ъ) может выполняться только в том случае, если для

поле О . Тогда для ЛРП {^(0} с характеристическим много­

Д оказательство. То, что последовательность элементов поля, заданная формулой (4), является линейной рекуррент­ ной последовательностью с характеристическим многочленом Р(х) , следует из равенств

256

I юточные системы шифрования

т-1 т-1

= /г* (а -0 '-ет) = и(1 + т).

Заметим, что число всех линейных рекуррентных после­ довательностей с характеристическим многочленом Р(х)

равно ^ т . Ровно столько же существует и различных кон­ стант из поля ^ . Из количественных соображений для завер­ шения доказательства теоремы достаточно показать, что при разных константах а из поля ^ будут получаться различные последовательности.

Если для двух различных констант ах и а2 выполняется равенство

то, пользуясь линейностью функции след, получаем соотно­ шение

т

*гЦ ((°1 ~о2)'в ) = 0, />о,

которое противоречит лемме 1. Теорема доказана.

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

257

/юточные системы шифрования

Пусть 8 {,...,ет — базис поля ^ , рассматриваемого как

векторное пространство над полем Р . Тогда последняя сис­ тема эквивалентна следующей системе линейных уравнений от т переменных над полем Р :

(в} •ев) = а] ,

‘^=1

у = 1,к.

Покажем, что ранг этой системы линейных уравнений ра­ вен к . Предположим, что между строками матрицы системы существует нетривиальное линейное соотношение с коэффи­

Тогда для любого значения 5 = 19т выполняется соотноше­ ние

( е , - ^ с г в 1) = 0.

/=1

к

Обозначим 2 = ^ ^ с ( - в 1 . Тогда для любого набора

1=1

с1\,..., с1т получаем равенство

259

Глава 9

тт

Согласно лемме 1, полученное равенство возможно толь­ ко в случае, когда 2 = 0, что, в силу неприводимости много­ члена Р(х) и условия к < т , означает, что сх= ... = ск = 0 .

Таким образом, ранг системы линейных уравнений равен к , и требуемое утверждение вытекает из известных результатов о числе решений систем линейных уравнений над полем. Ут­ верждение доказано.

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

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

260