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

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

Дискретна рівномірно розподілена випадкова послідовність (РРВП) Тема 5. Потокові симетричні шифри - №1 - открытая онлайн библиотека - це послідовність незалежних в сукупності випадкових величин, для яких Тема 5. Потокові симетричні шифри - №2 - открытая онлайн библиотека Тема 5. Потокові симетричні шифри - №3 - открытая онлайн библиотека .

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

1) Тема 5. Потокові симетричні шифри - №4 - открытая онлайн библиотека , Тема 5. Потокові симетричні шифри - №5 - открытая онлайн библиотека ;

2) Для усіх Тема 5. Потокові симетричні шифри - №6 - открытая онлайн библиотека будь-яка Тема 5. Потокові симетричні шифри - №7 - открытая онлайн библиотека - мірна впорядкована вибірка (вектор з компонентами Тема 5. Потокові симетричні шифри - №8 - открытая онлайн библиотека ), має рівномірний розподіл з ймовірністю Тема 5. Потокові симетричні шифри - №9 - открытая онлайн библиотека ;

3) Будь-яка підпослідовність послідовності Тема 5. Потокові симетричні шифри - №10 - открытая онлайн библиотека також РРВП;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Найбільш простим вузлом є т.зв. регістр зсуву з лінійним зворотним зв'язком (РЗЛЗЗ), що генерує рекурентну послідовність виду Тема 5. Потокові симетричні шифри - №14 - открытая онлайн библиотека .

Приклад розгортання РЗЛЗЗ з рекурентним законом Тема 5. Потокові симетричні шифри - №15 - открытая онлайн библиотека :

1100011011101010000100101100111110001101110101000010010

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

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

У результаті декількох тактів роботи РЗЛЗЗ довжини Тема 5. Потокові симетричні шифри - №16 - открытая онлайн библиотека з точками знімання Тема 5. Потокові симетричні шифри - №17 - открытая онлайн библиотека і початковим заповненням Тема 5. Потокові симетричні шифри - №18 - открытая онлайн библиотека формується рекурентна послідовність Тема 5. Потокові симетричні шифри - №19 - открытая онлайн библиотека , для якої виконується лінійне рекурентне співвідношення виду Тема 5. Потокові симетричні шифри - №20 - открытая онлайн библиотека , Тема 5. Потокові симетричні шифри - №21 - открытая онлайн библиотека .

Ця послідовність є періодичною. Період не перевершує числа Тема 5. Потокові симетричні шифри - №22 - открытая онлайн библиотека і залежить від довжини і набору точок знімання регістра. Рекурентну послідовність можна записати через всі елементи поточного заповнення регістра у виді Тема 5. Потокові симетричні шифри - №23 - открытая онлайн библиотека , де Тема 5. Потокові симетричні шифри - №24 - открытая онлайн библиотека , при Тема 5. Потокові симетричні шифри - №25 - открытая онлайн библиотека й Тема 5. Потокові симетричні шифри - №26 - открытая онлайн библиотека в іншому випадку. Таким чином, легко бачити, що кожен елемент рекурентної послідовності виражається у виді лінійної комбінації елементів початкового заповнення (щодо додавання за модулем два).

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

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

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

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

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

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

РЗЛЗЗ 1
РЗЛЗЗ 2
РЗЛЗЗ k
гамма
f

гамма
РЗЛЗЗ
f

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