Контрольні питання. Линейные регистры сдвига с обратной связью

Висновки

Пример 3.3

Пример 3.2

Линейные регистры сдвига с обратной связью

Регистры сдвига с обратной связью реализуют очень быстрый способ порождения бинарных (или двоичных) последовательностей. Их общий вид показан на рис. 3.2.

Рис. 3.2. Общий вид регистра сдвига с обратной связью.

Регистр сдвига с обратной связью (FSR — от feedback shift register) длины имеет ячеек памяти, значения которых совместно образуют (начальное) состояние регистра сдвига. Функция отображает в и называется функцией обратной связи регистра. Так как является булевой функцией, она может быть легко построена из элементарных логических функций.

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

Рассмотрим случай, когда задается равенством Исходя из начального состояния, можно легко определить последующие состояния с помощью функций Mod, Do и Print пакета "Mathematica"

Clear[f];

f[x_,y_,z_]:= Mod[x*y + z, 2];

{s0,s1,s2} = {0, 1,1};

Do[{s0,s1,s2}= {s1, s2, f[s0,s1,s2]};

Print [{s0,s1,s2}],{i, 1, 6}]

{1,1,1}

{1,1,0}

{1,0,1}

{0,1,1}

{1,1,1}

{1,1,0}

Частный случай линейной функции:

где все — двоичные цифры, а сложение выполняется по модулю 2.

Общий вид линейного регистра сдвига с обратной связью (кратко LFSR) показан на рис. 3.3.

Рис. 3.3. Общий вид линейного регистра сдвига.

Выходная последовательность такого LFSR может быть описана посредством начального состояния и линейного рекуррентного соотношения

(3.2)

или, эквивалентно,

(3.3)

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

(3.4)

Коэффициенты в (3.2) и на рис. 3.3 называются коэффициентами обратной связи регистра. Если, то соответствующий переключатель на рис. 3.3 разомкнут, а если, то замкнут. Предположим, что всегда. Следствием данного предположения является то, что любое состояние LFSR имеет не только единственное следующее состояние, что естественно, но и единственного предшественника. В самом деле, для любого значение однозначно определяется по посредством (3.2).

При,, получаем LFSR на рис. 3.4.

Рис. 3.4. Пример LFSR при.

Начальное состояние (1,0,0,0) дает следующий список последовательных состояний:

{s0, s1, s2, s3} = {1, 0, 0, 0}

Do[{s0, s1, s2, s3} = {s1, s2, s3, Mod[s0 + s1, 2]};

Print [i, " ", {s0, s1, s2, s3}], {i, 15}]

|| {1, 0, 0, 0}

1 {0,0,0,1} 2 {0,0,1,0} 3 {0,1,0,0} 4 {1,0,0,1} 5 {0,0,1,1}

6 {0,1,1,0} 7 {1,1,0,1} 8 {1,0,1,0} 9 {0,1,0,1} 10 {1,0,1,1}

11 {0,1,1,1} 12 {1,1,1,1} 13 {1,1,1,0} 14 {1,1,0,0} 15 {1,0,0,0}

Заметим, что состояние в момент идентично состоянию в момент, так что выходная последовательность имеет период 15.

Выходную последовательность регистра можно легко определить с помощью функций Table, Mod и Do пакета "Mathematica"

Clear[s]; {s[0], s[1], s[2], s[3]} = {1, 0, 0, 0};

s[j_]:= Mod[s[j-4] + s[j-3], 2];

Table[s[j], {j, 0, 15}]

|| {1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1}

Состояние называется нулевым, если все его компоненты равны 0.

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

1. Як визначається ентропія випадкової величини та які її властивості?

2. Як визначається надлишковість тексту і як ця характеристика впливає на шифрування?

3. Як визначається відстань одиничності криптосистеми і як ця характеристика впливає на шифрування?

4. Як визначається умовна ентропія та взаємна інформація у контексті шифрування?

5. Яким чином отримують визначення безумовно безпечної криптосистеми?

6. Якими є ознаки випадковості у послідовності бітів?

7. Як створюються псевдовипадкові послідовності бітів?

Дата добавления: 2013-12-12