Потокові шифри

3.4.1.Потокові шифри на основі генераторів псевдовипадкових послідовностей

Мал. 3.11. Потокове шифрування на основі використання ГПВП.

На відміну від потокового шифрування на основі блокового зі зворотнім зв'язком по гамі (мал. 3.10) для одержання потокового шифру на основі використання генераторів псевдовипадкових послідовностей (ГПВП) використовується схема, подана на мал. 3.11.

У якості ГПВП застосовується добре відомий із різноманітних технічних додатків рекурентний метод формування гами на основі

лінійного рекурентного регістра зсуву зі зворотнім зв'язком (ЛРР, LFSR).

3.4.2.Застосування лінійних рекурентних регістрів зсуву

Мал. 3.11. Лінійний рекурентний регістр зсуву зі зворотнім зв'язком.

Схема апаратної реалізації лінійного рекурентного регістра зсуву зі зворотнім зв'язком дана на мал. 3.12.

Лінійний рекурентний регістр зсуву працює по такій програмі:

при j=0,1,…,n-1,

при j=n,n+1,…, (3.16)

сума по mod2. , n - число осередків пам'яті, довжина ЛРР,

hi ,{0,1}, i = 0, 1,..., n - 1, - коефіцієнти, що визначають структуру ЛРР, aj , {0,1}, j = 0, 1,..., n - 1, - початкові стани осередків пам'яті, bj ,{0,1}, - символ на виході ЛРР.

Спочатку провадиться заповнення осередків пам'яті ЛРР елементами початкової двоїчної послідовності a0, a1, ... , an-1. Потім під дією тактових імпульсів, що надходять , (ТІ) виконуються всі зазначені підсумовування по mod2 і посимвольне просування вмісту осередків на вихід. В результаті утвориться вихідна послідовність з символів bj. Відводи підключені не до всіх суматорів, а тільки до тих, для котрих hi = 1. Двоїчна послідовність h1,..., hn , визначає індивідуальні властивості конкретного ЛРР.

Кожному ЛРР можна зіставити степеневий поліном зворотного зв'язку

h(x) = xn + hn-1xn-1 + hn-2xn-2 + ... + h1x + 1, (3.17)

з двоїчними коефіцієнтами hi, де h0 = hn = 1, і, навпаки, по заданому степеневому поліному можна побудувати ЛРР. Наприклад, поліном

h(x) = x4 + x +1

Мал. 3.13. ЛРР, що відповідає поліному h(x) = x4 + x +1.

відповідає лінійний рекурентний регістр зсуву з чотирьох осередків пам'яті, (довжиною n = 4), приведений на мал. 3.13.

З властивостей ЛРР відзначимо такі:

1. Період T вихідної послідовності лі нійного рекурентного регістра зсуву довжиною n обмежений нерівністю T £ 2n - 1.

2. Період T вихідної послідовності лінійного рекурентного регістра зсуву довжиною n визначається рівністю T = 2n - 1 тоді і тільки тоді, коли поліном зворотного зв'язку h(x) є так називаним примітивним поліномом.

Визначення. Поліном h(x) ступеня n c двоїчними коефіцієнтами називається примітивним, якщо він, по-перше, є неприводимим (тобто не представимий у вигляді добутку двох або більш багаточленів із двоїчними коефіцієнтами) і, по-друге, коли поліном ділиться на поліном h(x) без залишку. При цьому всі дії виконуються по модулю 2.

Прикладом примітивного полінома є поліном x4+x+1.

Для будь-якого n, а, отже, і для ЛРР будь-якої довжини існують примітивне поліном, причому число N таких поліномів визначається формулою

N(n) = j(2n-1)/n, (3.18)

де j(x) - функція Ейлера, що визначає число цілих чисел із проміжку від 1 до x-1 взаємно простих із x. Якщо 2n-1 просте число (таке просте число називають числами Мерсена) то,

N(n) = (2n-2)/n, (3.19)

З даних співвідношень очевидно, що при великих значеннях ступеня n число примітивних поліномів дуже велике. В даний час є докладні таблиці примітивних поліномів до великих ступенів включно. Є також регулярні алгоритми, що дозволяють перевірити чи є даний поліном, навіть дуже високого ступеня, примітивним. Таким чином, не існує проблема вибору поліному зворотного зв'язку h(x) для ЛРР достатньо великої довжини n на основі примітивного полінома, що забезпечує період вихідної послідовності T = 2n - 1 для будь-якого початкового заповнення.

Вихідна послідовність лінійного рекурентного регістра зсуву, реалізованого на примітивному поліномі, крім того, що має найбільший період повторення T = 2ⁿ – 1 має властивість «балансу», що полягає в тому, що число нулів на періоді T в точності дорівнює2n - 1 - 1, тоді як число одиниць у точності дорівнює2n - 1 , і властивістю «вікна», яка гарантує, що у всіх 2n - 1 вікнах із n символів, послідовно розташованих в періоді, усі можливі 2n - 1 ненульові двоїчні послідовності з'являться рівно по разу.

Перераховані властивості ЛРР, а також деякі інші призводять до того, що спостерігаючи послідовність на виході ЛРР, цю послідовність можна прийняти за чисто випадкову, що може бути отримана при незалежних киданнях симетричної монети. Проте в дійсності вихідна послідовність ЛРР є суворо детермінована, оскільки вона однозначно задається початковим заповненням aj ,{0,1}, j = 0, 1, ..., n - 1, і поліномом зворотного зв'язку h(x), у силу чого її називають псевдовипадковою послідовністю (ПВС).

З розглянутих властивостей ЛРР виникає питання, чи не можна використовувати ЛРР у якості датчика гами g у потоковому шифраторі , приведеному на мал. 3.14, де ключ K вводиться або в якості початкового заповнення, або коефіцієнтів поліному зворотного зв'язку.

Мал. 3.14. До обговорення придатності ЛРР для потокового шифрування

Проте відповідь на нього заперечна, оскільки ЛРР має таку властивість: якщо відома вихідна послідовність ЛРР довжиною 2n, то однозначно можна обчислити як початкове заповнення, так і поліном зворотного зв'язку, причому складність вирішення цієї задачі має порядок O ( n3), тобто потребує n3 операцій. Після цього стає можливим обчислити ключ K для даного типу шифратора, якщо відомо відкрите повідомлення довжиною 2n біт. Дана властивість є наслідком лінійності ЛРР, що дозволяє звести вирішення даної задачі до розв'язання системи лінійних рівнянь.

Мал. 3.15. Основні типи нелінійних вузлів ускладнення: а) схема «і» та б) генератор Джеффа.

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

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

Використовуючи рiз- номанітні нелінійні вузли і комбінуючи їх багаторазово, одержують можливість виконати складні нелінійні перетворення. Сукупність таких вузлів називають нелінійними вузлами ускладнення (НВУ). Входи НВУ підключають до виходів осередків пам'яті ЛРР, після чого нелінійний вузол ускладнення на своєму виході формує гаму. В результаті структурна схема шифратора на ЛРР може мати вид, поданий на мал. 3. 16. Як усяка цифрова система передачі потоковий шифратор потребує синхронізації між передаючою та прийомною гамою з точністю до біта. Крім того, при кожному черговому запуску необхідно змінювати початковий стан ЛРР, що звичайно досягається використанням випадкової послідовності, що щораз повинна бути передана на приймальну сторону.

Мал. 3.16. Шифратор на ЛРР із нелінійними вузлами ускладнення.

Ще одним прикладом нелінійного перетворення є використання двох ЛРР, причому перший ЛРР служить для другого генератором тактових імпульсів (мал. 3.16). Використання відразу декількох ЛРР і нелінійного вузла ускладнення показане на мал. 3. 17.

Мал. 3.16. Формування гами з використанням двох ЛРР. Мал. 3.17. Потоковий шифратор.

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

3.4.3.Поняття про криптостійкість потокових шифрів

Визначення. Двоїчна послідовність довжини n має лінійну еквівалентну складність d, якщо існує ЛРР довжина d, що може згенерувати цю послідовність при деякому початковому заповненні і при виборі деякого полінома зворотного зв'язку.

Тому нелінійний вузол ускладнення конструюється так, щоб забезпечити велику еквівалентну складність. Наприклад, якщо в якості НВУ вибирається генератор Джеффа з залученими до нього трьома ЛРР, що мають такі довжини: 84 осередки в ЛРР-1, 107 осередків у ЛРР-2 і 61 осередок у ЛРР-3, то лінійна еквівалентна складність d = 109, а число операцій d3 = 1027.

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

В даний час криптоаналіз потокових шифрів розвинений навіть у більшому ступені, чим криптоаналіз блокових шифрів, і запропонований ряд схем потокових шифрів на основі використання ЕОМ, що при відомих зараз методах криптоаналізу не можуть бути розкриті в реальному часі.

Крім більш простого криптоаналізу, потокові шифри мають такі переваги перед блоковими:

1. Простіша апаратна реалізація потокових шифрів.

2. Відсутнє розмноження помилок, що виникають у каналах зв'язку.

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

Проте потокові шифри мають недоліки, і при їхній експлуатації потрібна суттєва увага до слабкостей таких шифрів.

Як було відзначено раніше, при використанні потокового шифру необхідно категорично виключити можливість шифрування однією і тією ж гамою різноманітних повідомлень, оскільки це призводить до швидкого дешифрування без знання ключа. Для того, щоб забезпечити виконання цієї вимоги, потрібно при шифруванні кожного нового повідомлення, при кожному черговому запуску шифратора вибирати від випадкового датчика нове початкове заповнення ЛРР, що повинно передаватися по відкритому каналі на приймальну сторону. Якщо ж початкове заповнення ЛРР визначається ключем K, то при кожному новому пуску потрібно з цим ключем побітно скласти по модулю дві послідовності, отримані від випадкового датчика, і їхню суму взяти як початкове заповнення. Тоді схема потокового шифрування прийме вигляд, поданий на мал.3.18.

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

Мал. 3.18. Схема потокового шифрування.

. Для її виконання достатньо нав'язати законному користувачу хоча б один додатковий біт, вставлений у його попереднє повідомлення. Нехай відповідно повідомлення, гама і криптограма мають вигляд:

M: M1,M2,... , g: g₁,g₂,... , E: E1,E2,... .

Після вставки відомого повідомлення M' ці ж послідовності змінюються в такий спосіб: M: M1, M', M2,... , g: g₁,g₂,... , E:E1,E'2,E'3...,

і вся криптограма за вставкою розкривається за допомогою обчислень:

, (3.20)

Таким чином, потокові шифри на основі ЛРР мають визначені переваги перед блоковими:

1. Мають більш розроблений криптоаналіз.

2. Легше реалізуються апаратно.

3. Не розмножує помилки, що виникнули в каналі зв'язку.

4. Зручні для засекречування оцифрованої промови.

Проте, потокові шифри мають і свої недоліки:

1. Незручні для програмної реалізації.

2. Потребують суворої бітової синхронізації між передачею і прийомом.

3. Потребує зміни гами при кожному новому шифруванні.

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