mov di, Tapl

mov cx, di

add di, bx

mov si, di

dec si ; Вычисление байта обратной связи

mov al, BYTE PTR [bx + Tap2]

add al, BYTE PTR [di] ; Определение нового состояния генератора rep movsb

mov BYTE PTR [bx], al ; Восстановление регистров

pop cx di si es

popf

AddGenl ENDP

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

AddGen2 - аддитивный байтовый генератор (вариант 2),

==== соответствующий многочлену Ф(х) = х" + х + 1.

==== При вызове: массив регистров Regs - текущее состояние ========

==== генератора, DS - сегментный адрес массива Regs, ==============

==== ВХ - относительный адрес массива Regs; при возврате: =========

==== массив регистров Regs - новое состояние генератора, ==========

===== AL - выходной байт. Начальные значения отводов обратной связи:

===== IniTapl = N - 1, IniTap2 = i - 1. ============================

AddGen2 PROC

Сохранение регистров pushf

push si di Восстановление отводов обратной связи

raov di, cs: Tapl

mov si, cs: Tap2 Вычисление байта обратной связи и обновление содержимого элемента массива Regs с индексом DI

mov al, BYTE PTR [bx+di]

add al, BYTE PTR [bx+si]

mov BYTE PTR [bx+di], al Вычисление отводов обратной связи

test di, di

jnz DecremDI

mov di, 8

jmp DecremSI

CecreraDI: dec di

test si, si

jnz DecremSI

raov si, 8

jmp OutOfProc DecreraSI:

dec si OutOfProc: ; Сохранение отводов обратной связи

mov cs: Tapl, di

mov cs: Tap2, si ; Восстановление регистров

pop di si

popf

Tapl DW IniTapl

Tap2 DW IniTap2 AddGen2 ENDP

; окончание такта работы генератора

Тестовая программа для отладки процедуры AddGen2.

. MODEL tiny . CODE ORG

Begin: Regs

QutBytes DB IniTapl EQU IniTap2 EQU Nextlnstr:

NextByte

AddGen2 PROC <ldGen2 ENDP

lOOh

jmp Nextlnstr

DB 0,1,2,3,4,5,6,7,8

10 DUP (?)

mov raov mov eld

call

stosb

loop

cx, 10

di, OFFSET QutBytes bx, OFFSET Regs

AddGenl

NextByte ax, 4c00h 21h

Puc. 2.3.13. Результаты отладки процедуры Дс/сУСеп2

Таким же образом могут быть реализованы генераторы ПСП на основе LFSR, например, аналогичные показанному на рис. 2.3.7, а также генераторы, функционирующие в конечных полях, которые будут рассмотрены в последующих разделах.

2.4.

Конечные поля

2.4.1. Введение

Математический аппарат теории конечных полей (полей Галуа) щироко используется для решения следующих задач:

Ш разработка и исследование свойств кодов, обнаруживающих и исправляющих ошибки; Ш построение СЛС-генераторов и исследование свойств СЛС-кодов, которые являются

всеми признанным идеальным средством контроля целостности информации при

случайных искажениях информации; Ш разработка и реализация поточных криптоалгоритмов, наиболее известный пример -

шифр SOBER и др.;

разработка и реализация блочных криптоалгоритмов, наиболее известный пример блочный шифр RIJNDAEL, принятый в 2000 г. в качестве стандарта криптографической защиты XXI века ~ AES;

т построение криптографических протоколов, наиболее известный пример ~ протокол выработки общего секретного ключа Диффи-Хэллмана;

построение криптосистем с открытым ключом, например криптосистемы, основанно на свойствах эллиптических кривых - ECCS.

2 4,2. Основы теории конечных полей

Поле - это множество элементов, обладающее следующими свойствами: g в нем определены операции сложения, вычитания, умножения и деления; 0 ДЛЯ любых элементов поля а, р и у должны выполняться соотношения (свойств ассоциативности, дистрибутивности и коммутативности)

а -ь р = р -f а, ар = ра, а + (р + у) = (а + р) + г, а(ру) = (аР)у, а(р + у) = ар + ау;

в поле должны существовать такие элементы О, 1, -а и (для аО) а\ что О + а = а, а t (-а) = О, Оа = О, 1а = а, а(а") = 1.

Конечное поле содержит конечное число элементов. Поле из L элементов обозначает ся GF{L) и называется полем Галуа в честь первооткрывателя Эвариста Галуа (1811 1832). Все ненулевые элементы конечного поля могут быть представлены в виде степей некоторого фиксированного элемента поля ю, называемого пргшитивным элементом.

Простейшие поля получаются следующим образом. Пусть р - простое число. Тогд целые числа О, 1, 2,..., (р - 1) образуют поле GF{p), при этом операции сложения, вьт тания, умножения и деления выполняются по модулю р. Более строго, GF{p) - это пол классов вычетов по модулю р, т. е.

GF(p)={0,l,2,...,(p-l)}, где через О обозначаются все числа, кратные р, через 1 - все числа, дающие при делени нар остаток 1, и т. д. С учетом этого вместо (p-l) можно писать - 1. Утверждение а = в GF{p) означает, что а - р делится на р или что а сравнимо с по модулю р, т. е.

а = P(mod р).

Поле, содержащее L= р" элементов, где р - простое число, an - натуральное, не м( *ет быть образовано из совокупности целых чисел по модулю L. Например, в множест! "laccoB вычетов по модулю 4 элемент 2 не имеет обратного, так как 2-2 = 0. Таким обр; м, хотя это множество состоит из 4 элементов, оно совсем не похоже на поле GF{L обы подчеркнуть это различие, обычно вместо GF(4) пишут GF{2).

Элементами поля из р" элементов являются все многочлены степени не более (и - °эффищ5енуаи из поля GF(p). Сложение в GF(p") выполняется по обычным прав1

Результаты отлажш AddGen2 при Ф(д;) = л: + / + 1 представлены на рис. 2.3.13.

Regs

лам сложения многочленов, при этом операции приведения подобных членов осущест ляются по модулю Многочлен с коэффициентами из GF{p) (т. е. многочлен над пол GF{p)), не являющийся произведением двух многочленов меньшей степени, называет, неприводимым. Примитивный многочлен автоматически является неприводимым. ВыГ, рем фиксированный неприводимый многочлен ф(д:) степени п. Тогда произведение дв\ элементов поля получается в результате их перемножения с последующим взятие остатка после деления на ф(д:). Таким образом, поле GF{p") можно представить как пс классов эквивалентности многочленов над GF{p). Два таких многочлена объявляю-эквивалентными, если их разность делится на ф(д:). Конечные поля порядка р" сущест; ют для всех простых р и всех натуральных п. Пусть

/7 = 2, и = 4, ф(д:) = д:+д:+ 1 - примитивный над GF(2). Элементы поля GF(X) имеют вид

О, 1,д:,д:+1, ... , д:Нд: + д:+1.

Так как <${х) - примрггивный, ему соответствует устройство, диаграмма состояний которого состоит из цикла максимальной длины 2" - 1 и одного тривиального цикла, включающего состояние 0000, переходящее само в себя (рис. 2.4.1). Таким образом, в качестве со можно взять корень ф(д:), а устройство, для которого ф(д:) =х +х + \ является характеристическим многочленом, объявить генератором ненулевых элементов поля. В результате соответствие между различными представлениями элементов поля (в виде наборов коэффициентов многочлена, в виде многочленов и в виде степеней примитивного элемента) имеет вид, представленный на рис. 2.4.2. Состояния генератора определяют список элементов 0(2") в порядке возрастания степеней ш, т.е. один такт работы устройства, соответствующего характеристическому многочлену ф(д:), суть умножение текущего состояния устройства на о) = д:.

Типичные операции сложения, умножения и деления в поле GF(X) в рассматриваемом случае выглядят следующим образом:

(д: +х+\) + {х + х+\)=х +х

1101 +0111 = 1010; {х + \){х +х) = oj-o) = 0) = хЧ д: + 1

(д: + 1 )(д:-+ д:) = д:" + д:+ д:+ д:(то£/ф(д:)) = д:+ д:+ 1; (д: + д: + 1):(д: + д:) = со°:со* = О)" = д: + 1.

I о о о о

Рис. lAA.LFSR, соответствующий характеристическому многочлену над полем CF(2) ф(х) = х" -Ь X -Ь 1, U его диаграмма состояний