А Я Белецкий - Синтез обобщенных примитивных полиномов - страница 1

Страницы:
1  2  3  4 

ІНФОРМАТИКА

 

 

 

 

 

УДК 512.623.3

СИНТЕЗ ОБОБЩЕННЫХ ПРИМИТИВНЫХ ПОЛИНОМОВ

А.Я. Белецкий, д-р техн. наук, профессор, Национальный авиационный университет, г. Киев

 

Получены аналитические оценки числа образующих элементов, придающих свойство примитивности произвольным неприводимым двоичным полиномам, в том числе и не являющихся примитивными по классическому определению. Показано, что количество таких образующих элементов однозначно определяется лишь степенью неприводимого полинома. Приведен алгоритм синтеза порождающих матриц Галуа и Фибоначчи над обобщенными примитивными полиномами и рассмотрены прикладные аспекты их применения.

Ключевые слова: синтез, произвольный неприводимый двоичный полином, порождающие матрицы Галуа и Фиббоначи.

 

 

ВВЕДЕНИЕ И ПОСТАНОВКА ЗАДАЧИ

В теории полей Галуа, составляющих основу алгебраической теории помехоустойчивого кодирования и современной теории криптографии, ключевым является понятие неприводимого полинома (НП). Исходя из того, что в данной статье мы будем рассматривать переменные и функции,   принадлежащие   исключительно   двоичному пространству,

обозначаемому   в   теории   полей   Галуа   GF(2n) ,   приведем частное,

отвечающее полю GF(2n) , определение НП. Полином

n

Pn(x) = £ an_ixn-i ,     ai є {0, 1} , (1)

i=0

степени n над полем GF(2n) называется неприводимым, если он не делится ни на какой полином меньшей степени над данным полем [1].

Полином (1), записанный в алгебраической форме, может быть однозначно представлен бинарной строкой (двоичным вектором) своих коэффициентов (в бинарной форме)

Pn = {an > an-1  ai        a0 } ,ai Є {0 1} .

Например, бинарному вектору

p8 =100011011 соответствует алгебраическая форма полинома

p8(x) = x8 + x4 + x3 + x + 1 . (2)

Введем одну из главных характеристик НП, называемую показателем полинома.  Показатель  неприводимого  полинома  равен наименьшему

положительному числу e , при котором НП pn (x) делит двучлен xe - 1 без

остатка [2]. Физический смысл такой характеристики состоит в том, что он определяет порядок (иначе называемый мощностью) мультипликативной группы (равный числу элементов группы), образованной степенями примитивного элемента в группы по mod pn .

Множество    неприводимых    полиномов     {pn}     содержит важное

(например, для криптографических приложений, информатики, электроники и других направлений науки и техники) подмножество так называемых примитивных полиномов (ПрП). В алгебре, теории чисел и полей    Галуа    двоичный    полином    pn (x)    степени    n называется

примитивным, обозначим его p*n(x) , если он неприводим, а наименьший

показательe , при которомрП^) делит двучлен Ф(х) = хе -1 без остатка,

определяется выражением e = 2n -1 [2].

Приведем другой (авторский) вариант определения примитивного полинома.   Неприводимый   полином   pn (x)    степени   n    относится к

подмножеству примитивных полиномов p<n°}^(x) при выполнении следующих условий. Во-первых, полином должен быть неприводимым. Во-вторых, последовательность степеней некоторого k - разрядного бинарного   вектора   (тоже   полинома)    о ,   называемого образующим

(примитивным)  элементом,   приведенных  к  остатку  по  модулю   рП°° ,

составляет последовательность максимальной длины (иначе, m - последовательность).

Данное определение можно условно назвать «инженерным», не являющимся математически строгим, но которое послужит в дальнейшем корректной основой построения предлагаемых обобщенных примитивных полиномов.

Второе определение НП математически можно отобразить соотношением GF*(2n) = 0). Здесь GF*(2n) означает полное множество n -битных векторов, за исключением нулевого вектора, т.е. мощность (число   элементов)   этого   множества   равна    e = 2n -1,   а    (а) есть

мультипликативная группа порядка 2n - 1.

В теории полиномов постулируется утверждение, согласно которому все примитивные полиномы являются неприводимыми, тогда как обратное не всегда соблюдается, т. е. совсем не обязательно, чтобы каждый неприводимый полином обладал свойствами примитивности.

Основная задача данного исследования заключается в доказательстве того, что, во-первых, любой НП pn степени n соответствующим подбором образующих элементов а приводится к примитивному полиному рП°0 ; и, во-вторых, число элементов а , доставляющих произвольному неприводимому полиному pn свойство примитивности, есть величина постоянная, определяемая только значением n.

В заключительном разделе работы предлагается достаточно простой алгоритм синтеза образующих матриц Галуа и Фибоначчи, посредством которых формируются m-последовательности n - разрядных двоичных кодовых комбинаций для выбранных примитивных над элементами сополиномов  qfwW. Также кратко обсуждаются возможности применения

обобщенных примитивных полиномовдля построения генераторов бинарных псевдослучайных последовательностей и криптопримитивов нелинейной подстановки (так называемых S-блоков).

ОСНОВНЫЕ СООТНОШЕНИЯ

Приведенное ранее первое определение примитивного полинома <p*n(x) можно отобразить такими эквивалентными соотношениями:

fn (*)| xe -1; (3)

xe = 1 (mod qn(x)) , (4)

при условии, что

min e = 2n - 1. (5)

Предлагаемое обобщение понятия примитивного полинома сводится к

следующему. Заменим основание x одночлена xe в формулах (3) и (5) произвольным полиномом wm (x) степени m такой, что 1 < m < n . Тем самым представим данные выражения в виде

fn (x)|[®m (x)] e - 1; (6)

(x)]e - 1mod f:»(x), (7)

при соблюдении условия (5).

Полином a>m (x) назовем образующим элементом (ОЭ)ПрП, подобный ранее введенному образующему элементу в. Дальнейшие пояснения упростятся, если от алгебраических форм полиномов qn(x) и a>m(x) перейти к их бинарным формам. В классическом варианте (3) или (4) одночлен xe можно записать в виде числового (бинарного) эквивалента (10)e, поскольку основание x есть полином первой степени с минимальным весом,  т.е.   x =10.  В то же время ОЭ a>m   может быть

отличным от полинома x = 10 и принимать значения 11, 110, 101 и др.

Неприводимый полином (2) выбран разработчиками криптографического алгоритма Rijndaelв качестве базового для построения примитива нелинейной подстановкив шифреAES (Advanced Encryption Standard), принятого в качестве американского Стандарта симметричной блочной криптографической защиты информации [3]. Относительно НП (2) можно сказать следующее. Во-первых, этот полином не является примитивным; его показатель равен 51. Во-вторых, как справедливо отмечается в [4], полином f8(x), заданный выражением (2),

является первым НП восьмой степени, упоминающийся в большинстве справочников, т.е. его выбор достаточно произволен.

Как известно, S-блоки могут быть реализованы только на примитивных полиномах. Проблему непримитивности полинома авторы алгоритма Rijndael обошли простой заменой одночлена x двучленом x +1. Такая замена привела к тому, что исходный непримитивный полином показателя 51 приобрел свойство примитивности с показателем

255.

Проведенный краткий анализ неприводимых и примитивных полиномов как раз и подтверждает возможность и целесообразность перехода от классического представления примитивного полинома в видесоотношений (3) или (4) к обобщенному представлению выражениями (6) или (7) соответственно.

ОБРАЗУЮЩИЕ ЭЛЕМЕНТЫ ПРИМИТИВНЫХ ПОЛИНОМОВ Введем ряд обозначений,  необходимых для дальнейших выкладок.

Страницы:
1  2  3  4 


Похожие статьи

А Я Белецкий - Преобразования грея в полях галуа по модулю неприводимого многочлена

А Я Белецкий - Синтез обобщенных примитивных полиномов