Захист інформації - курс лекций

Мал. 3.1. Блокове шифрування.

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

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

Мал. 3.2. Потокове шифрування.

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

,(3.1)

де - i-ий символ гами залежачий функціонально від ключа K Відновлення повідомлення відбувається по аналогічному прийомі:

(3.2)

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

Мал. 3.3. Потокове шифрування гамуванням.

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

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

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

Мал. 3.4. Перетворення спектра: а) інверсія б) перестановка смуг.

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

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

Для надійного шифрування мовного сигналу його потрібно перетворити в цифрову форму, потім використовувати стійкі шифри пристосовані для шифрування для дискретних повідомлень, наприклад потокові шифри. Проте при перетворенні розмови в цифрову форму за допомогою імпульсно-кодової модуляції або дельта-модуляції істотно розширюється необхідна смуга частот каналу звязку, що призводить до необхідності використовувати більш широкополосні канали. Для того щоб передати зашифрований сигнал у тієї ж смузі частот (0,3-3,4 kГц), що використовується звичайно для передачі вихідного мовного сигналу, застосовуються спеціальні мовоперетворюючі пристрої - вокодери. Ці пристрої вимагають невеликої швидкості передачі, порядку 1200-2400 біт/c, завдяки чому зашифрований сигнал також може бути переданий по каналі ТЧ.

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

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

Блокові симетричні шифри.

Основні принципи побудови блокових симетричних шифрів.

Ще в роботі Шенона "Таємність і терміновість" були сформульовані такі основні принципи перетворення повідомлень, що можуть забезпечити високу стійкість блокового шифрування (мал.3.5):

Переплутування (нелінійне перетворення підстановка) символів.

Перемішування (розосередження, перестановка) символів.

Ітерування (повторення пунктів 1 і 2 багаторазово).

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

Мал.3.5. Побудова блокових шифрів.

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

Найпростішим засобом завдання нелінійного перетворення є табличний засіб, коли двоїчний блок спочатку перетвориться в число, потім це число по таблиці перетвориться в інше і, нарешті, отримане число знову по таблиці перетвориться в двоїчний блок. Наприклад, шифруються блоки довжиною n = 3, яким зіставлені такі числа: 000 - 0, 001 - 1, 010 - 2,..., 111 - 7. Тоді таблиця підстановок може бути задана в такий спосіб:

{0, 1, 2, 3, 4, 5, 6, 7}{4, 2, 6, 7, 0, 5, 1, 3}.

Це означає, що, наприклад, вхідний блок 011 буде перетворений у вихідний блок 111. Складність такого перетворення залежить від довжини таблиці, що дорівнює 2n, де n - довжина блока.

Вигляд нелінійного перетворення звичайно залежить від певних біт розширеного ключа, що виробляється з вихідного ключа. Наприклад, нелінійне перетворення, що залежить від біт розширеного ключа = (K1,K2,K3), може мати вигляд

f(,) = f((K1,K2,K3), (M1,M2,M3)) = = (E1, E2, E3).

E1 = K1K2M1M2, E2 = K2K3M2M3,

E3 = (K1 K2) M1M3, = (E1, E2, E3). (3.3)

Якщо криптограма і повідомлення = (M1, M2, M3) відомі, то при виконанні криптоаналізу можна скласти рівняння щодо елементів розширеного ключа . Це буде система нелінійних рівнянь із невідомими K1, K2, K3, де дії виконуються по модулю два.

У процесі шифрування часто виконується декілька перетворень із двоїчними блоками, при чому, крім лінійної операції додавання по модулю два, використовуються, наприклад, операції додавання по модулю 2n, 2n+1 або множення по модулю 2n+1, де n - довжина блока і т.п. Тому криптоаналіз гарного блокового шифру не зводиться до відомих поліноміальних задач.

Більшість сучасних блокових шифрів реалізується на основі, так називаної, структури Файстеля. Для цього попередньо з вихідного ключа  = 0 за допомогою заданого детермінованого перетворення, що входить в опис алгоритму шифрування, формується послідовність розширених ключів i, i = 1,2,...,d, де d - число ітерацій.

Мал.3.6. Підготовка блоків для шифрування на основі структури Файстеля.

Далі структура Файстеля припускає такий засіб перетворення блоків. Спочатку послідовність двоїчних символів повідомлення розбивається на блоки довжиною n=2n0 (мал.3.6).

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

,

i=2,3,...,d, (3.4)

де 0 і  1 - підблоки першого блока вихідного повідомлення, f(,) - детермінована відкрита нелінійна функція, i-1 - елементи послідовності розширених ключів, сформовані детермінованим способом з основного секретного ключа даної криптосистеми. Криптограма, сформована на останній ітерації d, приймає вигляд

= ( d - 1, d). (3.5)

Наприклад, якщо дано = ( 0, 1), то обчислюємо

2 = 0 f(1, 1),

складаємо (1,2), знову обчисляємо

3 = 1 f( 2, 2),

складаємо (2,3) і т.д.,..., до отримання послідовностей d - 1 і d, із котрих і формується криптограма = (d - 1,d).

Перевага такої структури складається в тому, що по-перше, для неї виконується принцип перемішування між підблоками, по-друге, дуже просто реалізується алгоритм дешифрування при ключі, відомому законному користувачу. При цьому важливо те, що функція f(,) навіть не обовязково повинна мати обернену! Дійсно, коректне дешифрування в даній структурі виконується по тому ж алгоритмі, що і шифрування: Нехай = ( 0, 1) = ( d - 1, d).

Тоді

,..., ,...,

1 = 3 f( 2, 2), 0 = 2 f( 1, 1),

= ( 0, 1), що, як очевидно і збігається з вихідним повідомленням.

Є багато різноманітних блокових шифрів, заснованих на структурі Файстеля, що відрізняються вибором функції f і засобом формування розширених ключів i i=1,2,…,d з основного ключа . Нехай на такий шифр відбувається напад із відомим повідомленням. Тоді, знаючи опис функції f і засіб побудови підключей по основному ключу, опонент може скласти систему нелінійних рівнянь і спробувати її вирішити щодо ключа як невідомого. Стійкість даного типу шифрів грунтується на складності рішення системи нелінійних рівнянь із діями по модулі два. Доведено, що в загальному випадку ця задача відноситься до класу NP - важких задач.

Багатократне шифрування блоків.

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

, . (3.6)

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

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

(3.7)

Для криптоаналізу використовуємо напад із відомим повідомленням, рахуючи, що відомо не менше двох блоків повідомлення і відповідні їм блоки криптограми, наприклад,

11 і 22. (3.8)

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

З співвідношення очевидно, що для дійсно використаних ключів 1 або 2 якийсь елемент Em другого рядка повинний обовязково співпасти з яким-небудь елементом Mn третього рядка. У такий спосіб достатньо знайти збіжні елементи в другому і третьому рядках і вибрати відповідні їм ключі Km і Kn у якості кандидатів у дійсні ключі 1 і 2. Проте збіги можливі і не тільки для істинних ключів, тобто кандидатів може виявитися декілька. Тому потрібно спробувати застосувати знайдені ключі до іншої пари повідомлення-криптограми для перевірки другого співвідношення

. (3.9)

Якщо виповниться і ця рівність то, як правило, знайдені ключі називаються істинними.

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

, . (3.10)

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

Основні параметри і принципи побудови найбільше відомих блокових шифрів.

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

Шифр DES (Федеральний стандарт США).

IDEA - (міжнародний стандарт шифрування).

GOST - (стандарт Російської Федерації).

DES - Федеральний стандарт шифрування для несекретних повідомлень у США. Є першим у світі цілком відкритим алгоритмом. Повсюдно використовується для шифрування даних.

DES являє собою блоковий шифр, заснований на структурі Файстеля з довжиною блоків рівної 64-м бітам і такою же довжиною блока криптограми. Для шифрування використовується ключ довжиною 56 біт + 8 перевірочних біт. Алгоритм реалізується 16-ма ітераціями. На кожній ітерації ключ виробляється з вихідного ключа за допомогою вибірки визначених елементів ключа і їхніх перестановок. Нелінійна функція в кожній ітерації задається за допомогою коротких нелінійних перетворень, так названих S - блоків, і перестановок. Всі перетворення задаються таблицями, що опубліковані у відкритій літературі. Алгоритм виробляє зашифровані дані, кожний біт яких є функцією від усіх біт відкритих даних і від усіх біт ключа. Зміна лише одного біта даних дає рівні можливості зміни для кожного біта криптограми.

Спочатку DES був розроблений фірмою IBM для своїх цілей. Тест по безпеці даної системи шифрування був проведений Агентством Національної Безпеки США, що не виявило в ньому статистичних або математичних вад. Після цього з 1976 DES став стандартом шифрування для несекретних повідомлень у США. Алгоритм опублікований. Вартість апаратної реалізації зі швидкістю шифрування 500 кбіт/c складає 100$. При програмній реалізації швидкість перетворення складає 20-140 кбіт/с.

Основний метод нападу на DES - повний перебір усіх ключів, число яких складає 256. На ПК можна перебрати всі ключі за 2300 років. Якщо сконструювати спеціальну дешифровальную машину, то систему DES можна розкрити протягом 1-го тижня. Це буде коштувати 3,3 млн. $ за даними на 1995 рік. До 2000 року вартість може знизиться до 830 тис. $, а до 2005 року - до 100 тис. $.

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

Наприклад, якщо повний час перебору складає 1 рік, то з можливістю рівної 0,0833 можна знайти ключ за 1 місяць, а з можливістю 0,0192 за тиждень.

Таблиця 3.1. Можливості перебування істинних ключів.

Існували спроби непереборного дешифрування DES на основі диференціального (різницевого), лінійного і статистичного криптоаналізу. Для повного алгоритму DES ці методи виявилися практично негожими. Проте, якщо використовується спрощений алгоритм DES (наприклад, замість 16-ти циклів реалізується тільки 4), то непереборні методи дозволяють розкривати спрощений "DES" без знання ключа за невеликий час.

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

IDEA - міжнародний стандарт шифрування. Це блоковий шифр із довжиною блока рівний 64-м бітам. Довжина ключа складає 128 біт. У якості нелінійних перетворень використовуються такі операції: додавання по модулю два і по модулю 216, а також і множення по модулю 216+1. Загальне число циклів 8. Табличні перестановки не використовуються.

Зручний у програмній реалізації для 16 бітового процесора. Швидкість: при програмній реалізації на 386 процесорі - 880 кбіт/с, при апаратній - 55 Mбіт/c.

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

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

GOST (ДЕРЖСТАНДАРТ 28-147-89) - державний стандарт шифрування Російської Федерації. Обовязковий для застосування у всіх державних і відомчих структурах і у всіх організаціях, повязаних із ними.

Має також відкрито опублікований алгоритм шифрування. Перетворює блоки повідомлення довжиною 64 біта в блоки криптограми такої ж довжини. Ключ складається з 256-ти біт, число циклів дорівнює 32. У якості перетворень використовуються нелінійні табличні підстановки і додавання по модулю 232. Крім ключа довжиною в 256 біт є і довгостроковий ключ із 512-ти біт. Цей ключ декілька змінює структуру алгоритму, тобто структуру S блоків (нелінійних перетворень).

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

Програмна реалізація забезпечує швидкості порядку 600-800 кбіт/c. Апаратна реалізація - до 1 Мбіт/с.

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

Модифіковані алгоритми блокового шифрування.

Необхідність у модифікації блокового шифрування.

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

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

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

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

Таблиця 3.2.

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

Суть нападу з вставкою нескладна. Зловмисник спочатку переводить деяку суму на свій рахунок, що дозволяє йому одержати криптограму свого імені і свого рахунку, а потім заміняє криптограму імені і рахунки будь-якого вкладника на свої.

Для усунення зазначених хиб використовують модифіковані алгоритми (моди) блокового шифрування.

Модифікація з зачепленням блоків.

Схема шифрування і дешифрування для цієї моди подана на мал. 3.7.

Мал. 3.7. Шифрування з зачепленням блоків.

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

, (3.11)

для дешифрування використовується співвідношення:

i=1,2,…,S... (3.12)

Тут E0 = IV - деякі початкові дані (Initial Value) - блок довжини n із двоїчних символів, що вибираються випадково і не секретні.

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

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

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

При використанні моди з зачепленням блоків формули дешифрування, у яких бере участь блок криптограми Ei-1 мають вигляд:

,. (3.13)

З них слідує висновок, що при появі помилок у блоці Ei-1 помилки на блоці повідомлення Mi-1 розмножуються так само, як і у випадку попередньої моди, а на блоці повідомлення Mi розмноження помилок не відбувається, вони виявляються тільки на тих місцях, де відбулися в блоці криптограми Ei-1.

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

Розглянемо дві основні схеми (мал.3.8) взаємодії контролю помилок і шифрування, де під контролем помилок розуміється їхнє виявлення і (або) виправлення.

а)

б)

Мал. 3.8. Взаємодія контролю помилок і шифрування.

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

Модифікація зі зворотнім звязком по криптограмі.

Схема шифрування і дешифрування для цієї моди дана на мал.3.9.

Мал. 3.9. Шифрування зі зворотнім звязком по криптограмі.

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

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

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

Модифікація зі зворотнім звязком по гамі.

Мал. 3.10. Шифрування зі зворотнім звязком по гамі.

Схема шифрування і дешифрування для цієї моди дана на мал.3.3.10. Вона схожа на попередню.

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

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

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

Дійсно, нехай є різні криптограми і , у яких різні повідомлення і засекречені однією і тією ж , тоді4

, . (3.14)

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

(3.15)

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

Щоб виключити можливість розглянутої атаки, необхідно на кожному новому сеансі звязку, при кожному новому запуску, якщо не змінився ключ, змінювати початкове заповнення IV регістра зсуву, передаючи це заповнення на приймальну сторону. Зміни чинять детермінованим або випадковим способом, але так, щоб можливість їхнього збігу при різноманітних пусках була б достатньо малою.

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

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

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

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

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

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

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

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

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

Мал. 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.

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

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

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

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

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

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

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

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

N(n) = (2n-2) /n, (3. 19)

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

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

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

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

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

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

Мал. 3.15. Основні типи нелінійних вузлів ускладнення:

а) схема "і" та б) генератор Джеффа.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

M: M1,M2,..., : 1,2,..., E: E1,E2,... .

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

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

, (3. 20)

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

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

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

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

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

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

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

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

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

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