Дискретная математика и криптология



СТРУКТУРА И ПЕРИОДЫ ПРЕОБРАЗОВАНИЙ - часть 12


может быть «весьма большой» и достигать величины kn-1, где k – порядок поля Р. Такие линейные преобразования называют преобразованиями максимального периода.

Рассмотрим условия максимальности периода преобразования j пространства Р(n)

линейным регистром сдвига (ЛРС) с функцией обратной связи an-1×хn+...+a1×х2+a0×х1, где a0,a1,…,an-1ÎР. Матрица Аj

преобразования j имеет вид:

Аj =

.

Матрица Аj называется сопровождающей матрицей данного ЛРС. Для реализации преобразования регистра левого сдвига вектор (х1,х2,…,хп) умножается на матрицу Аj слева.

ЛРС длины п

максимального периода обозначим ЛРСmax-п. Особый интерес в криптологии к ЛРСmax-п объясняется удобством их реализации и доказуемостью их высоких периодов (при подходящих п) в отличие от многих нелинейных преобразований. Ведь непосредственное вычисление периода преобразования (см. пример 6.1) может быть выполнено лишь для множеств небольшой мощности.

Преобразование j ЛРС имеет максимальный период в том и только в том случае, если циклическая группа <j> имеет порядок kn-1, или иначе, матрица Аj имеет порядок kn-1 как элемент группы линейных преобразований множества Р(n). Выразим эти условия через характеристики обратной связи.

Функции обратной связи f(x1,x2,…,xn) ЛРС однозначно соответствует многочлен F(l) степени n над полем Р:

F(l)=ln- an-1×ln-1- an-2×ln-2-...- a1×l- a0,

называемый характеристическим многочленом этого ЛРС. Матрица Аj

является корнем многочлена F(l), и если F(l) неприводим над Р, её порядок совпадает с порядком многочлена F(l). Поэтому преобразование j имеет максимальный период тогда и только тогда, когда F(l) - примитивный многочлен, то есть:

1)  F(l) неприводим над полем Р;

2) F(l) делит многочлен 

  и не делит ни один из многочленов вида ld-1, где d/kn-1 и d¹kn-1.

Построение примитивных многочленов в общем случае связано со сложными вычислениями. На практике используются таблицы примитивных многочленов.




Содержание  Назад  Вперед