Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Висновки

Пример 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. Як створюються псевдовипадкові послідовності бітів?

 

 

<== предыдущая лекция | следующая лекция ==>
Лемма 3.1 | Джерела
Поделиться с друзьями:


Дата добавления: 2013-12-12; Просмотров: 315; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.