Тема 5. Потокові симетричні шифри

33. Псевдовипадкові числа і послідовності.

Дискретна рівномірно розподілена випадкова послідовність (РРВП) - це послідовність незалежних в сукупності випадкових величин, для яких .

РРСП має наступні властивості :

1) , ;

2) Для усіх будь-яка - мірна впорядкована вибірка (вектор з компонентами ), має рівномірний розподіл з ймовірністю ;

3) Будь-яка підпослідовність послідовності також РРВП;

4) Сума за модулем m РРВП і будь-якій незалежній від неї послідовності також є РРВП;

5) РРВП не може бути передбачувана, тобто для будь-якого натурального n кількість інформації pf Шенноном, що міститься у відрізку про елемент , дорівнює нулю: .

Пристрій, реалізовуюче РРВП, називається генератором РРВП.

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

34. Загальні відомості про потокові шифри

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

Ключовий потік визначається вхідними ключовими даними і номерами тактів шифрування, аж до розглянутого.

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

У криптографічній літературі під потоковим шифром дуже часто розуміють так зиваний двійковий адитивний потоковий шифр, що являє собою шифр гамування за модулем два зі псевдовипадковою гамою.

Для такого шифра ключовий потік можна записати за допомогою нулів і одиниць і безпосередньо використовувати для гамування відкритого тексту.

35. Генерування потоку бітів за допомогою регістра зсуву з лінійним зворотним зв'язком (РЗЛЗЗ).

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

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

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

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

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

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

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

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

1100011011101010000100101100111110001101110101000010010

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

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

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

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

36. Комбінування регістрів зсуву.

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

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

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

Як комбінуючу вибирають булеву функцію, яка дорівнює сумі різних добутків змінних.

Нелінійні фільтр-генератори генерують вихідну послідовність як нелінійну функцію від станів одного і того ж регістра. Функція, що бере участь в схемі фільтр-генератора, називається функцією ускладнення. Для двійкових регістрів зсуву ця функція є булевою.

РЗЛЗЗ 1

РЗЛЗЗ 2

РЗЛЗЗ k

…

гамма

f

гамма

РЗЛЗЗ

f

Комбінуючий генератор Нелінійний фільтр-генератор