В виде коэффициентов многочлена

В виде многочлена

! : 0-

0 i - !

1 i . I x +

о i - ; + x

0 I - j х + х

1 i. 1 х + x + 1 1 i -! х + 1

0 : - j х" + x

1 • . ! х + x + 1

В ычк степени со - im

-ix -ix

x + x x + x +

.(if - i<o"j

Puc. 2.4.2. Соответствие между различными формами представления элементов поля С!") Пусть

р2,п = 4,(р(х)=х+х+х + х+\ - неприводимый над GF{2).

На рис. 2.4.3 показано устройство, соответствующее характеристическому многочлену <!)(д:) =/++ + л: + 1.

, Г"

о о о о

Рис. 2.4.3. LFSR, соответствующий характеристическому многочлену ф(х) = х + х-1-х-1-х+1,и его диаграмма состояний

Диаграмма состояний устройства состоит из трех щклов длиной 5 и одного тривиального Щ1кла, а значит данное устройство, один такт которого суть умножение на х по модулю ф(д:), не может использоваться в качестве генератора элементов поля. Такая сшуащ1Я всегда имеет место, когда ф(д:) - неприводимый, но не примитивный многочлен. Определим структуру устройства (генератора элементов поля), позволяющего сопоставить каждому ненулевому элементу поля соответствующую степень примитивного элемента.

Имеем

ф(д: +1) = (х+ 1)" + {х+ if + (д: + 1) + (д: + 1) -Ы = {х+1) + {х+х + х+1) + {х+1) + {х+1)+1=х* + х + 1=Щх)

Щх) - примитивный многочлен, а значит, соответствие между различными формами

представления элементов GF(2*) можно получить, моделируя работу устройства, показанного на рис. 2.4.4 . Один такт работы этого устройства суть умножение на о) = д: + 1.

J46 Ассемблер в задачах защиты инфор,

1 0 0 0 1

1 1 о о ш

1 о 1 о со

1 1 1 1 ш=

0 1110)*

1 о 1 1 erf

о о о 1 rf

1 1 1 о ш

1 о о 1 о/

о о 1 о irf

о о 1 1 ш»

110 10)"

о 1 о о 0

0 110 0)"

о 1 о 1 0

0 0 0 0 0

Рис. 2.4.4. Генератор элементов поля CFil")

2.4.3. Сложение и умножение в поле GF (2")

Элементами поля GF(2") являются двоичные многочлены степени меньшей к, кото могут быть заданы строкой своих коэффициентов, т. е. в виде п-разрядных двоичных к

Сложение в поле GF(2") - это обычная операция сложения многочленов с испо ванием операции XOR при приведении подобных членов; или операция поразр XOR, если элементы поля представлены в виде строки коэффициентов соответств) многочленов. Например, в поле GF(2), элементами которого являются двоичные члены, степень которых меньше восьми, байту

01010111 (57 в шестнадцатеричной форме)

Глава

2 программирование алгоритмов защиты информации 14

,тветствует многочлен

+х+х + х+ 1.

Пример выполнения сложения в поле GF(2):

57 + 83 = D4

так как

{х + х + х + х+]) + {х + х+1) = х+х + х + х 01010111 +10000011=11010100.

В конечном поле для любого ненулевого элемента а существует обратный аддитив-ный элемент -а, при этом а + (-а) = 0. В GF(2") справедливо а + а = О, т. е. каждый ненулевой элемент является своей собственной аддитивной инверсией.

В конечном поле для любого ненулевого элемента а существует обратный мультипликативный элемент а", при этом аа" = 1. Умножение в поле GF(2") - это обычная one-рация умножения многочленов со взятием результата по модулю некоторого неприводимого двоичного многочлена ф(дг) и-й степени и с использованием операции XOR при приведении подобных членов. Умножение в GF{2") также можно выполнять, рассматривая ненулевые элементы поля как степени некоторого примитивного элемента о).

Профаммная реализация операции умножения двух элементов а и Р поля GF{2") может быть выполнена двумя способами: табличным и вычислением результата аР "на лету".

Если элементы поля а и Р представлены в виде степени примитивного элемента, т. е.

а = ю и р = оУ, то их произведение аР может быть вычислено по формуле

ар = со"»""-).

Именно этот факт используется при реализации умножения табличным способом. Формируются два массива Elem и Addr. Первый массив состоит из 2" - 1 ненулевых элементов поля ("-разрядных двоичных кодов), расположенных в порядке возрастания степеней примитивного элемента. Например, содержимое ячейки массива Elem с адресом О равно (0°= 1, т. е.

Elem [0] = ш°;

одержимое ячейки массива Elem с адресом 1 равно со = (й, т.е.

Elem [1] = ю ИТ. д., - "Одержимое ячейки массива Elem с адресом i равно со.

Второй

£/е/и [/] = со; где / = 0,2"-2.

в массив формируется для ускорения поиска нужного элемента в массиве Elem,

ои 5чейке массива Addr с адресом j содержится адрес элемента поля j в массиве = 1,2"-1,т.е.

Ассемблер в задачах защиты "формац

Elem[i] = а « Addr[a] = /, а е GF(2"), аФО. Процедура определения результата аР умножения двух элементов поля

а = ш и Р = йУ

с использованием массивом Elem и Addr основана на нахождении в массиве Elem элемент; а и считывании результата умножения из ячейки массива Elem, циклически смещенцо, в сторону старших адресов относительно ячейки, содержащей а, нау позиций, т. е.

ар = Elem [(( + j) modi"- 1] = Elem [(Addr[a] + Addr[]) modi"- I].

Рассмотрим поле GFil"), порожденное многочленом (p{x) = + x + 1. Ha рис. 2.4 показан пример умножения двух элементов поля а = 1011 и Р = 0100:

1011 0100= 1010.

На рис. 2.4.6 показан пример умножения двух элементов поля а = 1101 и Р = 1000:

1101 1000 = 0010.

Программная реализация табличного умножения двух ненулевых элементов no.if GF(2*) приведена ниже.

==== Mulgfl - процедура умножения двух ==== ненулевых элементов поля Gf (2*) . =

==== При вызове: DS: ВХ - адрес массива ElemSAddr (рис. 2.4.7), ===

==== АН - первый сомножитель а = а, ===============================

==== AL - второй сомножитель (5 = а. ===============================

==== При возврате: AL - результат умножения. ======================

Mulgfl

Result:

Mulgfl

PROC push xlat

xchg xlat

add jnc sub add xlat

pop ret ENDP

al, ah

al, ah Result al, 255 bx, 256

формируем Б AL адрес элемента p в массиве Elem, AL = j AH = j , AL = a

формируем в AL адрес элемента a в массиве Elem, AL = i

формирование адреса

ячейки массива Elem,

содержащей результат умножения аЗ

DS: ВХ - адрес массива Elem

считывание в AL

результата умножения af>

£1ет

mod 15

Рис. 2.4.5. Пример умножения двух элементов поля CF{2)

Addr

Addr

2-4.6,

mod 15

Пример умножения двух элементов поля CFU")