Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Теорема 3. Пусть и — линейная рекуррентная последовательность над полем P = GF(q) характеристики р с примитивным характеристическим многочленом F(x) степени т, элементы которой задаются равенством
u(i) ^trfj {а-в1), где 0 —корень F(x) в поле GF(qm) из
qm элементов, а е GF(qm). Тогда элементы последовательности V, задаваемой равенством
v(i) = u(i) • u(i + k\ і > О, удовлетворяют соотношению
v(i)=trf а20квъ + Ytrfs aUqSe{X+qS)l (Ok +0^), і> О,
S=I
267
Глава 9
где Я:
, т.=-
\Л, если т = 2Л, s = Л; ! т в остальных случаях.
Доказательство. Непосредственно проверяется справедливость следующих равенств:
т-1 J т-1 qs
v(i) = u(i)-u(i + k)= ]Г(авl) ]|Г(авкО1) =
t=o
5=0
т-\т-\
S=O t=о
т-\т-\ J
= XZ«^'),V -^) =
5=0/=0
т-1
= j>((a0')l+<? Gkq ).
5=0
Для завершения доказательства теоремы достаточно заметить, что если т = 2Л +1, то
• і. m-s h„m-s tr (,ael)Uq Okq
\
а если т = 2/1, то
JW )1**""
= tr
(ae‘)x+qS .0*1, s = \,Я,
= tr
(ael)X+qS вк
, s = I9Л-1,
при этом справедливо равенство
268
I юточные системы шифрования
trf (ав‘)]+с>Я OkcIx =trf (ав‘)1+чЯ -(Akq* +вк). Теорема доказана.
Следствие. Если в условиях теоремы 0 <к <т, т> 8,
то
Л
5=0
где Ms(x)—минимальный многочлен элемента Q^q над полем GF(q).
Доказательство. Непосредственно проверяется, что при к <т порядок ord Ok элемента 9к удовлетворяет неравенствам
пт _\ Щ
ordek >1------->2(q2 -1),
т
и, следовательно, для всех S = I9 Л выполняется условие Okqs +Ok ф0.
Заметим, что в этом случае линейная сложность последо-
т(т + \) вательности V равна----------.
В общем случае описание строения минимального многочлена линейной рекуррентной последовательности удобно проводить, исходя из свойств его корней.
Для примитивного многочлена F(x) с корнем в обозначим через F^r\x) многочлен вида
F{r)(x)= \\(х-вк),
Wq(k)=r
269
Глава 9
где Wq(k) обозначает g-ичный вес числа к, то есть число ненулевых цифр в q-ичной записи числа к. Положим
к=О
Утверждение 4. Пусть и —линейная рекуррентная последовательность над полем GF{q) с примитивным характеристическим многочленом F(x) степени т, в — корень
F(x) в GF(qm). Тогда ранг последовательности Vy полученной из последовательности и усложнением с помощью функции /(X1Xm ), deg /(х) < г, не превосходит
degF<r>(jc), причем многочлен F<r>(x) является характеристическим многочленом последовательности V.
Доказательство. Рассуждая аналогично доказательству теоремы 3 и подставляя выражения членов последовательно-
/
сти V через функцию “след” в произведение J~~J u{i + **)*,
JM
получаем, что каждый знак указанного произведения представляется в виде суммы значений вида
Ygtjt
с. QqlxW2+-Wd =с.в ^ (6)
где с — некоторая константа из поля GF (qm),
___ /
0 < is < т, s = I,d, d -гJi <г .
k=1
270
I юточные системы шифрования
Следовательно, корни минимального многочлена указанного произведения последовательностей имеют вид:
'1 '2 Ч ^qtjt
eq +q +...+q =q j <jt<q,
m-1
причем jt <d <r. А поскольку последовательность
/=0
1/(0 = f(u(i)9...,u(i + m-1)), I > 0,
представляется в виде суммы последовательностей вида (6), то минимальный многочлен mv(x) делит F<r>(x). Откуда следует оценка ранга ЛРП v .
Таким образом, несмотря на то, что фильтрованную последовательность нельзя получить с помощью сдвигового регистра с линейной обратной связью той же длины, что и исходный регистр, ее всегда можно получить с помощью регистра сдвига большей длины.
Заметим, что степень многочлена F^r\x) равна числу целочисленных наборов (Z0,...,/^,), таких, что 0 <z‘7<gr,
т-\
= г, и представляется в виде
J=O
к> о
Данная величина является верхней оценкой линейной сложности класса выходных последовательностей фильтрующего генератора, полученных при различных начальных заполнениях регистра сдвига. Задача получения нижних оценок ранга усложнений линейных рекуррент представляется существенно более сложной. В частности, даже если ограничиться классом последовательностей, полученных с помощью
271
Гпава 9
функций усложнения фиксированной степени нелинейности, то в этом классе будут содержаться рекурренты, линейная сложность которых меняется в диапазоне от т до
degF<r>(x).
Таким образом, для получения псевдослучайных последовательностей с высоким уровнем линейной сложности функция усложнения фильтрующего генератора должна иметь достаточно высокую степень нелинейности.
Комбинирующие генераторы
Второе направление синтеза псевдослучайных последовательностей с высокой линейной сложностью связано с использованием в одной схеме нескольких линейных регистров сдвига. Генератор псевдослучайных последовательностей, реализующий усложнение нескольких линейных рекуррент с помощью одной общей функции усложнения, получил название комбинирующего генератора (см. рис. 38 ).
Рис. 38
Рассмотрим один частный случай комбинирующего генератора, когда функция усложнения / имеет степень нелинейности t, и ее представление свободно от квадратов:
