DS:[BX]-

DS:[BX+256]-

Murvi

Массив Addr - адреса Addr; ненулевых элементов поля в массиве Elem

Массив Elem - ненулевые элементы поля в порядке возрааания аепени примитивного элемента поля t

f(em[255]

f uc. 2.4.7. Организация массива Elem&Addr

Пусть, например, для построения поля GF(2*) выбран

ф)=х + х* + х+х+ 1 - неприводимый многочлен показателя 51. Диаграмма состояний соответствующег устройства (рис. 2.4.8, а), один такт работы которого суть умножение на х по мс ф(д:), имеет 5 кодовых колец по 51 состоянию в каждом и один вырожденный триЕ ный цикл, соответствующий состоянию 00, переходящему самому в себя. Опре, структуру устройства (генератора элементов поля), позволяющего сопоставить ка> ненулевому элементу поля соответствующую степень примитивного элемента.

q, Qi Us 1* Ь Яг ?, ?„ Hex

--в- Поле CF(2):

Эаграмма его состояний

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

Имеем

i?(x + 1) = (х + 1) + (х+ ly + (х + 1) + (X + 1) + 1 = = (х* + 1) + (х" + 1) + (х + Х + X + 1) + (х + 1) + 1 = = х + х" + х + х + 1 = ф(х),

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

000 0000 I - •ОГСш" 1) 0000 00 1 1 -03(со) О О О О О 1 О 1 - 05 (ш) О О О О 1 1 11 - OF (со) ООО 1 ООО 1 - 1 ГС©) 00 1 1 00 1 1 -33(ю)

0 10 10 10 1 -55 (со*)

1 1 1 1 1 1 1 1 - FF (со) ООО 1 1 О 1 0-1А(й)) 001011 1 0-2Е(о))

11110 11 l-F7(o))

000000 1 0-02 (О

00000 1 1 0-06 (со)

1 1 О О О 1 1 1 - С? (о))

0 10 1001 0-52 (со")

1 1 1 1 О 1 1 О - F6 (0)").

Работу данного устройства моделирует программа, приведенная ниже.

Генератор элементов поля GF(2 ), когда (р(х) не является ======

примитивным. Один такт работы устройства суть умножение ======

на X + 1 по модулю ф(х). =====================================

.1

==== Программа предназначена для запуска в отладчике ======

==== в пошаговом режиме. AL - состояние генератора. =======

. MODEL tiny . CODE

ORG lOOh

Begin: mov al, Olh

mov cx, 255

; AL = 01

; Число циклов равно количеству ; ненулевых элементов поля

Гдаза 2. Программир 1531

NeXt:

mov rcl Next

xor xor

loop

mov int DB END

ah, al al, 1

al, fb al, ah Step

ax, 4c00h 21h IBh Begin

: копия "старого" ; состояния генератора : сдвиг LFSR и анализ бита обратной связи

если бит обратной связи равен

нулю, коррекции результата

умножения на х не требуется

действие единичного бита обратной связи

AL - "новое" состояние генератора

Если СХ не равно О,

переход на начало следующего

такта работы генератора

Вектор обратных связей

Пример выполнения операции умножения в рассматриваемом поле (х* + х + х + х+1)(хЧх+1) =

, =хЧх"+хЧх« + хЧхЧх+;сЧ1 =

= (хЧхЧ l)mod(i>ix)

(0 = 0)"

57--83= Cl.

а значит, В GF(2*) справедливо

0)"=1,

а значит, ненулевые элементы со и Ф j) являются взаимно обратными тогда и только тогда, когда

Например, т. е.

МНОя

= 255. coV = m=l, ll.B4= 1 (xU 1)(хЧх+х+х)= 1.

*ая произвольный многочлен Учим в общем случае многочлен 8-й степени

Ассемблер в задачах зaщuтьluнфopмaцJJ

Если а-1 = О, мы сразу получаем результат умножения; если а? = 1, необходимо взят), результат по модулю (р(х), что в рассматриваемой ситуации, очевидно, эквивалентно вычитанию из результата ф(х). Таким образом, умножение а{х) на х на байтовом уровц это либо результат циклического сдвига в сторону старших разрядов байта

если a = 0; либо поразрядный XOR результата циклического сдвига байта

(0706050403210)

в сторону старших разрядов с вектором обратной связи 15 (см. рис. 2.4.8, о), если

07=1.

Пусть

хТте{<з)

- операция умножения элемента поля а на х. Тогда умножение на л:" можно осуществнц путем «-кратного повторения операции xTime(a). Например,

57-13= FE,

так как

57-02 = хГ ие(57)=АЕ 57-04 = xf/me(AE)=47 57-08 = л:Г и<47) = 8Е 57-I0 = xf/me(8E)= Ю7

57-13= 57-(01Ф02Ф10)= 57еАЕе07= ТЕ. Ниже приведен пример вычисления "на лету" произведения двух элементов GFC-приведенному выше алгоритму.

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

рГвызовеГм"- первый сомножитель, AL - второй сомножитель,

- ...-..лтттгли ППГГа =--- - -

---- при DDIJVU. л..-----

==== DL - вектор обратных связей генератора элементов поля ==== При возврате: AL - результат умножения. =============

Mulgf2 PROC

test jz

xchg test

al, al Result ah, al al, al Result

Первый сомножитель равен О ? Если да, на выход - результат равен О

Второй сомножитель равен О ? Если да, на выход - результат равен О

Глав 2. .Программирс информации 155

Shift:

mov xor

cx, 8 bl, bl

ah, 1

xTime

bl, al

xTinie:

EndL:

xTime (a), AL = a shl al, 1 jnc EndL xor al, dl

Число повторений цикла

Инициализация регистра,

в котором формируется результат

Анализ очередного бита первого

сомножителя

Если выдвигаемый бит равен нулю, готовимся к следуюшему циклу Формирование в BL промежуточного результата

Result: ret Mulgf2

loop NextShift

mov al, bl ; Результат умножения в AL

pop cx bx

ENDP

2.4.4. Вычисление обратного элемента в поле GF{2")

Как и в случае умножешм элементов поля, задача нахождения обратного элемента

~== Процедура формирования обратного элемента в GF(2), ======

====== ?>(х) = х% х + х + X + 1 - неприводимый ========1======

" элемент поля а, выход: AL - элемент поля а" == = FB - вектор обратных связей, ======================„===

== для заданного ф(х) FB = IBh =============================

srsion

push

bx cx