Захист інформації

Таким чином, можна думати, що 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,E'2,E'3...,

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

, (3. 20)

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

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

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

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

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

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

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

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

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

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