Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
/(X1 ...X, ) = Х Z ch ..Jk 'xh xIk •
k=\ 1</| <...<(? <t
272
/ юточные системы шифрования
Теорема 4. Пусть Ut — ЛРП максимального пе-
риода с примитивными характеристическими многочленами F\(x\...,Ft(x) над полем GF(q) попарно взаимно простых
степеней: ns =degFs(x), (ns,rij) = I для j, s,j = 1,/.
Тогда для функции усложнения вида (7) линейная сложность последовательности V вида
40 = Ащ (і),и2 (І),-,Ut (і)), і > 0
равна
Y S ^
k=I 1</j<...</?</ I=I
_ f0, если Ch =0, где С, , = , J1"* л
1~* ]\,если Q1 Jk *0.
Доказательство. Согласно (7), последовательность V представляется в виде суммы последовательностей вида
^A-Jk ' uJl (0 ‘ и.І2 ‘ uj/c (О» C71. Jk *0, (9)
где 1 < к < t, 1< j\ <...< jk <t.
Если в произведение (9) вместо элементов линейных рекуррентных последовательностей подставить их выражения через функцию “след”, то получится представление в виде
, Qix Qik J
суммы последовательностей вида с (аДч ¦ ...-CCjk4 ) , где CCj— корень многочлена Fj (х) в поле GF(qm), пг = «j • «2 ’•••'ns , 0 < Zs < rij , s = ІД , с — некоторая константа из поля GF(qm ) .
273
fлава 9
Отсюда следует, что корни минимального многочлена
*1 1к
произведения (9) имеют вид a, О < is <nJs,
s = I, к . Непосредственно проверяется, что все такие элементы являются попарно различными и могут быть представлены
г
в виде (ад *...•ccJk)q при подходящем значении г. В силу
свойств многочленов над конечными полями отсюда следует, что минимальный многочлен произведения (9) является неприводимым многочленом степени Uj^ •rij2 '...'Yljk .
Можно заметить, что при различных наборах индексов
I < j\ <...< Jfi </, I <k<t, минимальные многочлены для последовательностей вида (9) попарно взаимно просты, поскольку они неприводимы и имеют различные степени. Таким образом, минимальный многочлен последовательности v равен произведению этих неприводимых многочленов, а линейная сложность последовательности V описывается формулой (6). Теорема доказана.
Композиции линейных регистров сдвига
Рассмотрим еще один тип генераторов, представляющий собой композицию линейных регистров сдвига. Так называется схема, в которой выход одного из регистров подается на вход другого регистра (см. рис. 39).
F(X)
G(X)
Рис.39
274
I юточные системы шифрования
Функционирование такой схемы описывается следующим образом. Пусть V — ЛРП, вырабатываемая первым регистром сдвига, закон рекурсии которого определяется характеристическим многочленом F(x).
Пусть задано начальное состояние второго регистра сдвига, закон рекурсии которого определяется характеристиче-
/77-1
ским многочленом G(x) = Xm ~^jgjxJ • Тогда выходная по-
J=о
следовательность композиции регистров сдвига задается соотношением
т-1
w(i + т) = Yj Mi + j)gj + v(i), іїО.
J-O
Непосредственно из определения композиции регистров сдвига вытекает, что минимальный многочлен выходной последовательности делится на минимальный многочлен последовательности V и делит произведение F(x)'G(x) .
Схемы с динамическим изменением закона рекурсии
Рассмотренные способы усложнения линейных рекуррент объединяет общая идея повышения линейной сложности исходных последовательностей за счет применения дополнительных функций усложнения. При этом законы функционирования самих регистров остаются неизменными.
Альтернативный способ усложнения ЛРП состоит в изменении закона рекурсии в процессе работы криптографического алгоритма. Привлекательным представляется использование нелинейной логики в цепи обратной связи регистровых преобразований. Однако общая теория подобных схем еще недостаточно разработана, в связи с чем трудно гарантировать необходимые свойства соответствующих последовательностей.
275
_____ _______f пава 9
Один из путей построения подобных схем основан на динамическом изменении закона рекурсии линейного регистра сдвига.
Рассмотрим, например, вопрос о строении псевдослучайной последовательности, получаемой с помощью линейного регистра сдвига, закон функционирования которого меняется в зависимости от четности номера вырабатываемого знака.
Рассмотрим два многочлена А(х) -хт +y^alXj9
В(х) -хт + Ък хк степени т и последовательность V, удовлетворяющую условиям:
W-I
v(2t + т) = -]Г а} • v(21 + j),
J= о
W-I
v(21 +1 + пі) = v(2f+i+*),/>o.
к=о
Ясно, что в четных тактах закон рекурсии последовательности у определяется характеристическим многочленом
А(х), а в нечетных тактах -ном В(х).
Образуем многочлены следующим образом:
Л(0)(*) = Yj02J Xlj ’
B{0\x) = Yb2jX2j, J* О
- характеристическим многочле-А(0)(х), Л0)(х), Bw(X), В{1)(х)
(X) = YaI j+\x2j+X,
J^ О
B(~X\x) = Yb2J+\x'2j+X-
276
/ юточные системы шифрования
Несложно проверить, что получаемая в результате последовательность V является линейной рекуррентной последовательностью с характеристическим многочленом
Н(х) = А{1)(х)В{1)(х)-А{0)(х)В{()\х).
К классу генераторов с динамическим изменением закона рекурсии относятся также линейные регистры сдвига с неравномерным движением информации. Так называются регистры, для которых число тактов работы до получения (/-hi)-го знака выходной последовательности зависит либо от значения числа і, либо от состояния регистра в такте і. Получаемая в результате последовательность будет некоторой выборкой с переменным шагом из исходной ЛРП, вырабатываемой линейным регистром сдвига.
