Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
l-m
то есть если первые 1 — т знаков последовательности V рав ны нулю, а следующий за ними отличен от нуля.
Для многочлена G(x) є Р\х] степени т и последова
тельности и введем параметры Iu(G) и ku(G) = = Iu (G) - т є N и {0,+оо}, где Iu (G) — число знаков после довательности w, вырабатываемых многочленом G(x). Ясно что ku(G) — максимальное число первых подряд идущю нулей в последовательности G(x) • и (либо оо).
Будем индуктивно строить последовательность много
членов Gq(х), Gj (х), ... неубывающих степенеї
0 = т0 < т{ < т2 <... .
Начальные условия: G0 (х) = е, т0 = 0.
Этап 1. Если
G0(x)-u = и = U0 =(0^^0,1/0(^),...), k0=ku(G), то полагаем
G1(X) = xk°+l -и0(к0 4-І)*u0(k0)~l -хк° *G0(x), yyix = к0 +1.
Если G1 (х) • и = 0, то есть если ки (G1) = оо, то G1 (х) — искомый минимальный многочлен ЛРП и. В противном слу чае строим G2 (х).
Этап 14-І. Пусть многочлены G0(x),...,Gt(x) уже по строены, и степень deg Gj (х) многочлена Gj (х) равна TYij
причем 0 = YYl0 < YYlx <... < mt. Пусть выполняются соотноше ния
26
Глава 9
Gj (X)-U=Uj = (Ou2O, Uj (к j ),...) ,
kJ *0
kJ =ku(Gj)<co,
Iu (iGj ) = к j + т j < +00 .
Определим число s = s(t) так, чтобы выполнялись условия mt = mt] =... - ms+l > ms (такое s найдется, так как тх > т0). Положим
Q = Jg/ (х) - хк$~к‘ ¦ Ut (kt) • Us (ks )_1 • Gs (л;), если kt < ks, \xkt~ks • Gt(x)-ut(kt)• us(ks)-1 • Gs(*), если kt >ks.
Если Gt+l(x) • и — 0, то нужный многочлен построен. В противном случае строим Gt+2(х) .
Теорема 2. Если и — линейная рекуррентная последовательность над полем P с минимальным многочленом F(x) степени т, то F(x) = Gt (х) для некоторого подходящего значения т < 2т -1 — к0.
Доказательство теоремы носит технический характер и заключается в непосредственной проверке двух условий: каждый следующий многочлен в предложенном алгоритме вырабатывает больше знаков последовательности и, чем предшествующий; любой многочлен, вырабатывающий столько же знаков последовательности и, что и многочлен Gj (х), имеет
степень не меньше, чем степень многочлена Gj (х) .
264
I !оточные системы шифрования
§ 9.6. Усложнение линейных рекуррентных последовательностей
Алгоритм Берлекемпа—Месси позволяет для каждой ли нейной рекуррентной последовательности построить выраба тывающий ее линейный регистр сдвига минимальной длины Однако при создании стойких криптографических алгоритмої необходимо гарантировать определенную величину линейноі сложности не для одной конкретной ЛРП, а для целого классі псевдослучайных последовательностей, получаемых при раз личных ключах. При этом, как правило, мощность класса рас сматриваемых последовательностей бывает настолько велика что применить алгоритм Берлекемпа—Месси к каждой после довательности не представляется возможным. Поэтому важ ной криптографической задачей является построение целы: классов псевдослучайных последовательностей с высокой ли нейной сложностью.
Описанные выше свойства линейных регистров сдвиг показывают, что, несмотря на достаточно большой период і хорошие статистические качества, линейные рекуррентные последовательности имеют очень простое строение. Поэтом; в криптографических приложениях используют различны способы усложнения аналитического строения линейных ре куррент.
Фильтрующие генераторы
Первый способ заключается в применении к элемента! линейной рекуррентной последовательности некоторой функ ции f (см. рис. 37) (F(x) — характеристический многочлеь определяющий закон рекурсии ЛРС).
It
Глава 9
P JlPC F(x)
Рис. 37
В литературе подобные узлы усложнения ЛРП получили название фильтрующих генераторов. Их результирующей последовательностью является нелинейно “фильтрованное” содержимое регистра сдвига. “Фильтрующая” функция / должна выбираться так, чтобы выходная последовательность имела распределение, близкое к равномерному распределению, и высокую линейную сложность.
Известно [Лид88], что любая функция над конечным полем может быть задана некоторым полиномом. Поэтому при изучении фильтрующих генераторов достаточно рассмотреть только полиномиальные усложнения линейных рекуррент.
Пусть и — линейная рекуррентная последовательность над полем Pmq элементов с характеристическим многочленом F(x) степени т , и функция /(х\,...,хт) имеет вид:
Тогда выходная последовательность фильтрующего генератора определяется следующим равенством:
0< zj<...</5< т 0< kj< q-1
О < s < т
266
I юточные системы шифрования
y(i) = + т)) =
Y J uO+ h -у)к' u(i + is-\)ks (5)
0</|< <is<m 0< кj<q-1 \<s<m
Рассмотрим случай, наиболее интересный с практической точки зрения, когда F(x) — примитивный многочлен степени т над полем P. Поскольку, согласно (5), усложненная последовательность является суммой произведений некоторых линейных рекуррентных последовательностей, отличающихся друг от друга сдвигами, продемонстрируем методику изучения строения таких последовательностей на примере доказанной А. А. Нечаевым теоремы о произведении линейной рекуррентной последовательности на ее сдвиг.
