Inversion

Mult

loop

ENDP

Next2 cx

======= Один такт работы генератора элементов поля

Mult

Next3:

FB = IBh Mult

PROC push mov

shl jnc xor

pop ret

ENDP

bl, al

al, 1 Next3 al, FB

al, bl bx

; Сохраняем исходное значение ; элемента поля а

Получили результат умножения а на X

Получили результат умножения а на X + 1

В заключение приведем список многочленов, неприводимых над GF(2), N<9. М-гочлены заданы набором их коэффициентов о/ а-ь-а/.-аг «1 «яо, например, набор 1 соответствует многочлену дг + х + 1. В скобках указан показатель многочлена, т. е. i меньшее положительное число е, при котором x-l делится на данный многочлен остатка. Многочлены /(х), для которых справедливо соотношение/(х) = д-х" ), где - многочлен степени Л, уже имеющийся в списке, не приводятся.

N= 1

II (1) N= 2

III (3) N = 3 1011 (7) N= 4

icon (15) 11111 (5) N = 5

100101 (31) 101111 (31) 110111 (31) N = 6

1000011 (63) 1001001 (9) 1010111 (21) 1011011 (63) 1100111 (63) W = 7

10000011 (127) 10001001 (127) 10001111 (127) 10011101 (127) 10100111 (127) 010101011 (127) 10111111 (127) 11001011 (127) 11101111 (127)

W = 8

100011011

100011101

100101011

100101101

100111001

100111111

101001101

101011111

101100011

101110111

101111011

110000111

110001011

110011111

111001111

111010111

(51)

(255)

(255)

(255)

(17)

(85)

(255)

(255)

(255)

(85)

(85)

(255)

(85)

(51)

(255)

(17)

Next2: call

0=1-2-

зависимость контрольного кода не только от всех бит анализируемой информа: ной последовательности, но и от их взаимного расположения;

высокое быстродействие, связанное с получением контрольного кода в pea масштабе времени;

в простота аппаратной реализации и удобство интегрального исполнения; ш простота программной реализации.

К сожалению, простое условие пропуска искажений делает С/?С-коды принципиально не пригодными для защрггы от умышленных искажений информации. По этой же причине следует признать непригодным использование процедуры формирования СКС-тл для хеширования информации.

Сущность процесса контроля целостности с использованием С/?С-кодов закгаочаето в следующем. Генератор СРС-кода инициализируется фиксированным начальным значет ем. Чаще всего в качестве начального заполнения используется либо код "все О", либо ко; "все 1". Учитывая, что от начального состояния генератора достоверность метода не зави сит, все дальнейшие рассуждения выполняются в предположении, что исходное состояв) устройства - нулевое. Анализируемая двоичная последовательность преобразуется в корот кий (обычно шестнадцати- или тридцатидвухразрядный) двоичный код - CRC-коя. Значт ние полученного С/?С-кода сравнивается с эталонным значением, полученным заранее да последовательности без искажений. По результатам сравнения делается вывод о наличк или отсутствии искажений в анализируемой последовательности.

1 о 1

о о о 1 о

Ф-ЕЬФ

Л-vO

1 1 о о о 1 о

1000 0100 1010

0 0 0 1 10 0 0 0 10 0 10 10

1 о о О 1 о

1 V 1 Vo

-°- J-1

о 1

2.5. OfC-коды

2.5.1. Контроль целостности информации с использованием С/?С-кодов

Идеальным средством защиты информации от случайных искажений являются сл коды {cyclic redundancy code). Достоинствами CRC-kojxob являются:

ш высокая достоверность обнаружения искажений, доля Ро обнаруживаемых искажен не зависит от длины массива данных, а определяется только разрядностью N щ трольного кода:

Ассемблер в задачах заЛить! информац,, 2. ПР.?.Р.!.Г.УР*!."Р.™?.°Р.У.™.??..

X* + X + 1

j(6 + / + х + 1

Q(x)

де " отвственно частное и остаток, то коэффициенты многочлена Q

оявляктся на выходе разряда (у-ь а коэффициенты многочлена R{x) остаются в регис цератора после прохождения всей последовательности А. Иначе говоря, СЛС-код j: в т „ости равен коду остатка Л, T.Q.s = R,a s(x) = R{x).

Работа генератора С/?С-кода описывается системой линейных уравнений

R{x)

Рис. 2.5.1. Три варианта схемы генератора CRC-кода, соответствуюиего: а,6,в - характеристическому многочлену ф(х) = х" + х + 1;

г - деление многочлена входной последовательности на характеристический многочлен генератора СУ?С-кода.

R - коэффициенты многочлена-остатка R{x}, Q - коэффициенты многочлена-частного Q(x) Рассмотрим схему генератора СЛС-кода, показанную на рис. 2.5.1, б. Входной зна* зируемой двоичной последовательности

А = а,а,а...а,...а„ ,,а, е {0,1},? = О,(от-1) где т - длина последовательности, можно поставить в соответствие многочлен А{х) ни {т -1)

Тогда процесс получения С/?С-кода эквивалентен делению многочлена А{х) последовательности на характеристический многочлен ф(х) генератора СЛС-кода. Ь

A{x) = i9(x)Q{x) + R{x\

[q, {t + \) = a ,q,., it) @ ?,.,(0, i = lN-l,

где «1 Oa 0№ e {0, 1}, - коэффициенты образующего многочлена, q/t) uq/t+l)- cocn ние;-го разряда, соответственно, в моменты времени tut+l, / = О, m , j = 0,N -I.

Таким образом, для С/?С-генератора справедлив принцип суперпозиции, который г] сит: реакция линейного устройства на сумму двух входных воздействий равна сум. реакций на каждое воздействие в отдельности.

Пусть

А = ao<3i-3m-i

- анализируемая последовательность,

- правильная последовательность (без искажений), е - последовательность, полученн в результате сложения по модулю два соответствующих элементов последовательност Л и В, т. е. для любого элемента последовательности е справедливо

=a,©fc„/ = 0,(w-l).

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

V/ = 0,(w-l),e, = 0.

Пусть А{х), В{х) и е{х) - многочлены; 5,4, и - СйС-коды, соответственно, послед ательностей А, В vie. Искажения в последовательности А будут пропущены, если = i Имеем А = В® е, откуда, применяя принцип суперпозиции, получаем равенство

$А = SB ® Se.

Таким образом, необходимым и достаточным условием пропуска искажений явл равенство Se = О, которое имеет место, когда многочлен е(х) нацело делится i *"<огочлен <р{х).

се сказанное относительно генератора, показанного на рис. 2.5.1, б; справедлш для двух других, так как для всех трех генераторов при еФО справедливо утверждени

тогда и только тогда, когда е{х) нацело делится на (р(х). Все три схемы обеспеч; frl """овУ достоверность контроля, тем не менее предпочтение следует отдали из них, как обеспечивающей наиболее интенсивное "перемещивание" ошибо