Математические основы криптологии. Галуев Г.А. - 38 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

75
тем, работающих на основе двузначной логики. Все числовые
данные в ЭВМ представляются с помощью элементов двух ти-
пов
0 и 1. Т.е. вся обработка информации осуществляется на ос-
нове элементов простого конечного поля
2
F или его расшире-
ний
N
F
2
. Реализация линейных рекуррентных последовательно-
стей над полем
2
F может быть достаточно просто осуществлена
на основе регистров сдвига с обратной связью. Пусть у нас име-
ется однородное линейное рекуррентное соотношение вида (т.е.
порядка
К=4):
nnnnn
SaSaSaSaS
01122334
+
+
+=
++++
,
1
3210
=
=== aaaa
. Тогда его реализация на основе регистра
сдвига из
К=4 разрядов с обратной связью будет иметь вид:
Если какой либо из коэффициентов
321
,, aaa
равен нулю,
то соответствующий сумматор
⊕ из цепи обратной связи ис-
ключается.
Нетрудно видеть, что под действием тактовых импульсов в
моменты времени
,...2,1
=
n
на выходе регистра происходит гене-
рация последовательности
,...,,
21 ++ nnn
SSS
Вектор
},...,,{
11 −++ knnn
SSS
- это вектор n - го состояния регистра. При
n=0 вектор
},...,,{
110 −k
SSS
- это вектор начального состояния.
Характерной особенностью линейных рекуррентных по-
следовательностей над конечным полем является их периодич-
ность в смысле следующего определения.
Определение. Пусть S - произвольное непустое множество,
и пусть
,...,
10
SS
последовательность элементов из множества S.
Если существуют целые числа
0 n 0
0
>> иr
, такие что,
76
nrn
SS =
+
для всех
0
nn ≥
, то последовательность
,...,
10
SS
на-
зывается
периодической последовательностью, а r - периодом
этой последовательности.
Наименьший из всех возможных периодов называется
ми-
нимальным периодом.
Лемма. Каждый период периодической последовательно-
сти делится на ее минимальный период.
Определение. Периодическая последовательность
,...,
10
SS
с минимальным периодом
r называется чисто периодической,
если равенство
nrn
SS
=
+
выполняется при всех
,...2,1,0
=
n
Рассмотрим теперь основные результаты о свойствах пе-
риодичности линейных рекуррентных последовательностей над
конечными полями, т.к. для криптографических приложений
желательно иметь ЛПР с
max r .
Теорема. Пусть
q
F
- произвольное конечное поле, К - не-
которое натуральное число. Тогда каждая линейная рекуррент-
ная последовательность
К - го порядка над полем
q
F является
периодической. При этом ее минимальный период
r удовлетво-
ряет неравенству
k
qr ≤
, а в случае однородной последователь-
ности
1−≤
k
qr
.
Достаточным (но не необходимым) условием чистой пе-
риодичности ЛРП является следующее:
Теорема. Пусть
,...,
10
SS
- ЛРП над конечным полем, оп-
ределяемая рекуррентным соотношением. Если коэффициент
0
a
равен
0 т.е.
0
0
=
a
, то последовательность
,...,
10
SS
является
чисто периодической.
Из всех однородных линейных рекуррентных последова-
тельностей над полем
q
F удовлетворяющих соотношению К -
го порядка, т.е
nknkknkkn
SaSaSaS
02211
...
+
+
+
=
−+−−+−+
,
можно выделить одну ЛРП с максимальным значением
минимального периода
r, которую называют импульсной функ-

Страницы