Каждый символ шифротекста Ci является функцией от соответствующих символов исходного текста и ключа:

Ci = Eki(mi) = mi Å ki.

При дешифрации выполняется обратное преобразование D:

Dki(ci) = ci Å ki = ( mi Å ki ) Å ki = mi. mi , ki ,ci {0,1}.

Генераторы M-последовательностей.

При выборе генератора ключа (ГК) необходимо учитывать следующие факторы: аппаратные затраты на реализацию ГК, временные затраты на генерацию ключа. Широкое распространение получили генераторы на основе сдвигового регистра с линейными обратными связями. Они описываются следующим отношением:

ai =Åak ai-k, k=0,1,2, . , (2.1)

где k - номер такта; ak{0,1} - биты формируемой последовательности; ai {0,1} - постоянные коэффициенты; Å - операция суммирования по модулю 2. Генератор, описываемый отношением (2.1), показан на рис. 2.1.

Свойства генерируемой последовательности определяются постоянными коэффициентами ai. Их можно исследовать, анализируя характеристический полином

g(x) = 1 Å a1 x Å a2 x2 Å .Å am-1 xm-1 Å am xm.

При соответствующем выборе коэффициентов генерируемая последовательность { ai } будет иметь максимально возможный период, равный 2m-1, где m - разрядность сдвигового регистра и одновременно старшая степень порождающего полинома. Последовательность максимально возможного периода называется M-последовательностью. Основная задача синтеза генератора рассматриваемого типа - нахождение характеристического полинома, формирующего М-последовательность.

.

m-3 m-2 m-1 m

ak-1 . ak-m+2 ak-m+1 ak-m

Рис. 2.1. ГК на основе сдвигового регистра.

m2 D T D T D T D T

C C C C

C

Рис. 2.2.Функциональная схема четырехразрядного ГК

с порождающим полиномом g(x) = 1 Å x3 Å x4

Таблица 2.1.Примитивные полиномы Таблица 2.2. Функционирование ГК

m g(x) n ГК n ГК

3 1ÅxÅx3 1 1000 9 1010

4 1ÅxÅx4 2 0100 10 1101

5 1Åx2Åx5 3 0010 11 1110

6 1ÅxÅx6 4 1001 12 1111

7 1ÅxÅx7 5 1100 13 0111

8 1ÅxÅx5Åx6Åx8 6 0110 14 0011

9 1Åx4Åx9 7 1011 15 0001

10 1Åx3Åx10 8 0101

11 1Åx 2Åx11

12 1Åx3Åx4Åx7Åx12

13 1ÅxÅx3Åx4Å x13

Полиномы, формирующие последовательность максимального периода, называются примитивными. С ростом m их количество становится очень большим. Среди множества примитивных полиномов степени m можно найти полиномы с наименьшим числом единичных коэффициентов ai. Генераторы, построенные на их основе, имеют наиболее простую техническую реализацию. В табл. 2.1 приведен перечень полиномов с минимальным количеством ненулевых коэффициентов для значений m <=16.

Схема четырехразрядного ГК, описываемого примитивным полиномом g(x)=1Å x3 Å x4, приведена на рис. 2.2; его работа показана в табл. 2.2.

Для формирования M-последовательности наряду с примитивным полиномом g(x) может использоваться и обратный ему полином g-1(x)=xmg(x-1). Полученная в этом случае последовательность максимальной длины будет инверсной по отношению к последовательности, формируемой g(x). Например, для полинома g(x)=1Åx3Åx4 обратным полиномом будет g-1(x) = x4(1Åx-3Åx-4 )=1 Å x Å x4 .

Главное преимущество описываемого метода формирования псевдослучайных последовательностей - простота его реализации. Генератор M-последовательности содержит лишь m-разрядный регистр сдвига и набор сумматоров по модулю два в цепи обратной связи. Регистр сдвига выполняет функции хранения m бит M-последовательности и сдвига m-разрядного кода на один разряд вправо. Сумматоры по модулю два вычисляют очередное значение младшего разряда сдвигового регистра.

Состояние разрядов регистра на каждом такте можно представить в виде m-мерных векторов A(k)=a1(k)a2(k)a3(k) .am(k), где k=0,1,2, . - номер такта, ai(k) - состояние i-го разряда, i=1,m, Тогда будет выполняться следующее соотношение:

a1(k) a1 a2 a3 . am-1 am a1(k-1)

a2(k) 1 0 0 . 0 0 a2(k-1)

a3(k) = 0 1 0 . 0 0 * a3(k-1)

. . . . . . .

am(k) 0 0 0 . 1 0 am(k-1)

или в более компактном виде A(k) = VA(k-1), откуда для произвольного s справедливо равенство

A(k+s) Vs+1= A(k-1), (2.2)

где

a1 a2 a3 . am-1 am

1 0 0 . 0 0

V = 0 1 0 . 0 0

. . . . . .

0 0 0 . 1 0 .

Для М-последовательности, описываемой полиномом g(x)=1Åx3Åx4 , матрица V имеет вид