Загальні властивості двійкового регістра зсуву з лінійним зворотним зв'язком

У криптосхемах потокових шифрів широко застосовуються криптовузли, основані на т.зв. регістрах зсуву зі зворотним зв'язком.

Регістр зсуву зі зворотним зв'язком складається з двох частин: регістра зсуву і функції зворотноьго зв'язку.

Двоичный регістр зсуву – це послідовність бітових комірок. Їхня кількість називається довжиною регістра. Під час роботи вміст комірок змінюється. Початковий стан регістра називається його початковим заповненням. Вміст комірки називається розрядом (з відповідним номером).

У результаті одного такту роботи регістра генерується один біт. Новий біт обчислюється як функція від бітів, які вибіраються з комірок регістра зі заздалегідь визначеними номерами. Зазначені комірки називаються комірками зворотнього зв'язку, а функція – функцією зворотнього зв'язку. Номера комірок зворотнього зв'язку називаються точками знімання зворотнього зв'язку.

У такті роботи обчислюється значення функції зворотнього зв'язку, потім регістр зрушується, скажемо вліво, утрачаючи лівий крайній розряд і звільняючи крайню праву комірку. У цю комірку заноситься значення функції зворотнього зв'язку. Виходом регістра є біт, знятий з фіксованої (звичайно, із крайньої правої) комірки.

У потокових шифрах генератори гами, у більшості випадків, складаються з типових вузлів, основаних на комбінаціях регістрів зсуву і функціях ускладнення.

Найбільш простим вузлом є т.зв. регістр зсуву з лінійним зворотним зв'язком (РЗЛЗЗ), що генерує рекурентну послідовність виду.

Приклад розгортання РЗЛЗЗ з рекурентним законом:

11000 11011101010000100101100111 11000 1101110101000010010

Тут довжина початкового заповнення регістра n=5. Параметри рекуррентного закону 0,2 - точки знімання зворотнього зв'язку регістра.

Безпосередньо для генерації гами РЗЛЗЗ не підходять. На практиці застосовуються комбінації залежних РЗЛЗЗ, що взаємно впливають на формування своїх послідовних заповнень.

У результаті декількох тактів роботи РЗЛЗЗ довжини з точками знімання і початковим заповненням формується рекурентна послідовність, для якої виконується лінійне рекуррентное співвідношення виду,.

Ця послідовність є періодичною. Період не перевершує числа і залежить від довжини і набору точок знімання регістру. Рекуррентную послідовність можна записати через всі елементи поточного заповнення регістра у виді, де, при й в іншому випадку. Таким чином, легко бачити, що кожен елемент рекуррентной послідовності виражається у виді лінійної комбінації елементів початкового заповнення (щодо додавання за модулем два).

Дата добавления: 2014-10-15