Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
В одном из возможных вариантов значение шага выборки меняется в соответствии с некоторой последовательностью периода t. В этом случае удается описать минимальные многочлены получаемых псевдослучайных последовательностей [G0I88].
Теорема 5. Пусть d0,...,dt_х — набор из t> 2 чисел
________ /-1
множества 0,qn — 2 и D = dj . Пусть при і = k-t + г
J=О
элементы последовательности v задаются формулой
г-1
kD+Ydj
v(i) = tr( (с д ),
где с — ненулевой, а в — примитивный элементы поля GF(qn). Пусть, кроме того, простые делители числа t де-
277
Глава 9
лят
q" - і
¦, но не делят (qn -I9Z)). Пусть, наконец,
СЯп-UD)
qn = I (mod 4), если t кратно четырем. Тогда минимальный многочлен Mv (х) последовательности V имеет вид
Му(х) = F(Xt), где F(x) —минимальный многочлен элемента 0°.
т
Доказательство. Пусть F(x) = • Тогда
5=0
F(Xt) = fsXst. Умножая последний многочлен на после-
5=0
довательность v и полагая / = kt -hr, получаем: №')v](o=№')v](fe+r)=
т т
=+st^=I/,**+r+st)=
S=О т
5=0
=2^v((fe+r)+j/)=
5=0
Г-1
kDd ,+sD
171 / .J J
= ^fs-rfw J'° ) =
s=0
Г-1
kn^LiI т = Irf св J-0 (?/s0*°)
s=0
= 0.
278
I юточные системы шифрования
Отсюда следует, что многочлен F(Xt) является характеристическим для последовательности v. Кроме того, в условиях теоремы, он является неприводимым. Это следует из свойств неприводимых многочленов над конечными ПОЛЯМИ
[Лид88]. Таким образом, F(Xt) является минимальным многочленом последовательности V, что и требовалось доказать.
Схемы с элементами памяти
Дополнительные возможности для усложнения ЛРП открывает использование в криптографических алгоритмах элементов памяти.
Один из наиболее широко известных классов датчиков псевдослучайных чисел, построенных с использованием памяти, составляют генераторы Макларена—Марсалъи. Принцип работы таких генераторов в самом общем виде можно сформулировать следующим образом.
Пусть имеются три последовательности и массив памяти. Будем записывать элементы первой последовательности в память по адресам, которые определяются элементами второй последовательности. Элементы выходной последовательности получаются при считывании значений, хранящихся в массиве памяти, в соответствии с элементами третьей последовательности. Таким образом, первая последовательность определяет, какие знаки заносятся в память, вторая последовательность управляет процессом записи этих элементов в память, а третья — процессом считывания из памяти элементов выходной последовательности.
Рассмотрим частный случай, когда процессами записи и считывания управляет одна и та же последовательность. Схема работы такого генератора изображена на рис. 40.
279
Глава 9
Po
t* V
Pi-1
Рис. 40
Пусть и ну — последовательности над полем P, а выходная последовательность у вырабатывается с использованием q ячеек памяти R0,...9Rq_}. Если Rj(i) —заполнение j -й ячейки памяти перед началом і -го такта работы схемы, то преобразование информации в / -м такте описывается формулами
г(0 = Лу(/)(0 >
ГR / (/) , если j * v(l),
R,(i + l) = \ yW J
[«(/), если j — v(/>.
Таким образом, последовательность V определяет адреса, по которым в память записываются элементы последовательности и.
Рассмотрим вопрос о периодах выходных последовательностей генератора Макларена—Марсальи указанного типа.
Пусть последовательность и имеет период т , а адресная последовательность V принимает значения 0,1,...,^-1 и имеет период t. Начальное заполнение памяти /?o(0),...,7?^_j(0) выбирается произвольно.
Пусть /0 — такое наименьшее натуральное число, что для любого к є {0,1,..., q -1} существует / е 0, ^ такое, что 280
/ юточные системы шифрования
V (S) = к . Другими словами, через /0 тактов работы схемы память будет заполнена только элементами последовательности и.
В дальнейших рассуждениях будем рассматривать работу схемы, начиная с такта /0 +1.
Теорема 6. Пусть T — период последовательности U1 / — период последовательности V, причем (г,/) = 1, t<r. Тогда для значения периода T выходной последовательно-
/ -
сти у выполняется равенство T=rs, где s = — и а <ее .
d
Доказательство. Для />/0 определим параметры I1 равенствами
Ii = min{ / є N : v(/-/)=v(/)}.
Тогда /(I) = U(I-Ii). Несложно заметить, что для любых значений / и j выполняются соотношения
y(i+jt)=Rvd+jt) (І+JO=Rvio (і+jt)=и(і л-Jt-Ii).
Таким образом, каждая регулярная выборка с шагом t из последовательности у совпадает с некоторой регулярной выборкой с шагом t из последовательности и. Отсюда и из условия (г,/) = 1 следует, что T делит T .
С другой стороны, для любого і справедливы равенства
y(i + rt) = Rvil^ii + rt) = RHl) (і + Tt) = u(i + Tt-l,) =
= U(I-I1) = Rv(l) (І) = последовательно, T — TS , где S 11.
281
Гпава 9
Пользуясь условием периодичности и определением величин I1, для любого / > Z0 получаем, что
Y(i + jTs) = y(i) = u(i-ll),
Г (і + jГ s) = u(i + jz s- ll+JT s) = u(i - ll+JT s).
