ABCDEFGHIJKLMNOPQRSTUVWXYZ 2 страница

 

Рисунок 2.1 – Схема секретної системи зв’язку

 

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

 

2.3 Вимоги до реалізації сучасних криптоалгоритмів.

 

Сучасні криптографічні системи можуть бути реалізовані програмним, програмно-апаратним чи апаратним шляхом.

Існують наступні загальні вимоги до реалізації криптографічних алгоритмів:

- криптографічні алгоритми повинні бути адаптовані до новітньої програмно-апаратної бази (наприклад, алгоритми блочного шифрування в програмній реалізації повинні бути адаптовані до операцій з 64-розрядними числами);

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

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

- обсяг повідомлення в ході виконання операцій шифрування повинен зводитися до мінімуму;

- повинно бути виключене явище розмноження помилок.

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

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

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

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

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

До переваг програмної реалізації можна віднести те, що програма, написана під одну операційну систему, може бути модифікована під будь-який тип ОС.

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

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

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

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

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

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

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

 

2.3.1 Параметри сучасних шифрів

 

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

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

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

В якості міри, за допомогою якої оцінюється складність обчислювального процесу під час дешифрування повідомлень, частіше за все використовують кількість елементарних операцій w деякого типу, що виконуються протягом часу дешифрування одного повідомлення, або визначення одного ключа. В кожному окремому випадку обговорюється, що саме включається у термін “ елементарна операція ”. Це може бути або сукупність операцій, що виконуються на конкретній апаратурі за один етап шифрування, або сукупність операцій, що виконується протягом часу однієї спроби підбору ключа, або щось інше. Головне – щоб вибір цієї міри був обґрунтований.

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

В цій ситуації, єдиним способом дешифрування криптограми є перевірка усіх можливих значень ключа. Якщо його довжина дорівнює довжині повідомлення, повна кількість ключів, які треба буде перебрати складає величину 2 ⁿ. Цю величину називають потужністю ключового простору. Підвищення потужності ключового простору, звичайно, збільшує криптографічну стійкість шифру, але не завжди і необов’язково. Наприклад, для шифру простої заміни потужність ключового простору дорівнює величині т!, де т це кількість символів у алфавіті. Хоча при досить великій довжині тексту потужність ключового простору буде непомірно великою, як відомо, шифри простої заміни ламаються статистичними методами досить легко.

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

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

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

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

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

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

4. Потужність обчислювача – число тактів, що виконується за одну секунду.

5. Пам’ять обчислювача – доступна пам’ять, що використовується в процесі обчислення та зберігання даних.

6. Надійність алгоритму дешифрування – імовірність дешифрування, що визначається обраним методом дешифрування та алгоритмом його реалізації.

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

8. Максимально припустима пам’ять – числова величина, що характеризує практичну значимість алгоритму дешифрування.

Нехай М – множина всіх можливих методів аналізу шифру F з імовірністю дешифрування ³ r (мінімальна імовірність практичного дешифрування). Через S визначимо множину всіх алгоритмів дешифрування, що вимагають пам’яті не більше за величину RAM і відповідають множині М. Крім того, нехай С - множина всіх обчислювачів. Тоді визначимо через Q(c,s) важкість дешифрування алгоритму S по відношенню до обчислювача Q для всіх sÎ S та сÎ С.

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

 

 

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

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

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

 

2.3.2 Елементарні криптографічні перетворення

 

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

 

 

 

 

 

Рисунок 2.2 Елементарні криптографічні перетворення

 

 

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

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

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

 

З урахуванням сказаного, множину шифровеличин U можна розглядати як множину слів U_і алфавіту А^*.

 

а множину шифроперетворень V як множину слів V_і алфавіту В^*

Тоді а Якщо кількість символів у алфавітах А і В відповідно дорівнює п і т, тоді загальна кількість шифровеличин U_і повинна складати N > п а загальна кількість шифроперетворень V_і повинна складати М > т.

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

Множину V можна представити як сімейство з r варіантів такого її розподілення

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

 

і кожна з підмножин не повинна бути пустою

 

 

Таким чином, з урахуванням вище сказаного, можна надати наступне визначення шифру заміни.

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

У найпростішому випадку шифровеличини співпадають із символами алфавіту А_т, за допомогою яких утворюються відкриті повідомлення, а шифроперетворення із символів алфавіту В_п, з якого утворюються криптограми. Причому, В_п, частіше за все, є підстановкою на А_т, що утворюється за допомогою відображення . Тоді п = т i N=M. Шифри, які передбачають співпадання довжини шифровеличин та відповідних до них шифроперетворень, називають шифрами рівнозначної заміни. В протилежному випадку мають місце шифри різнозначної заміни.

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

 

 

де k – є ключ до шифру.

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

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

 

 

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

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

Щоб запобігти повному перенесенню статистичних характеристик відкритих повідомлень на відповідні до них криптограми, у минулі часи до складу алфавіту В_п, з якого утворюються закриті криптограми, добавляли додаткові символи так, щоб n < m. Під час зашифрування повідомлень у такий спосіб, кожен символ відкритого тексту можна було замінити на один кількох різних символів заздалегідь визначеної підмножини алфавіту В_п. Цей принцип добре ілюструється рисунком 2.4. Шифри такого типу називають шифрами багатозначної заміни або шифрами пропорційної заміни.

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

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

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

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

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

Для подальшої формалізації перестановочних шифрів надамо визначення перестановки.

Перестановкою s набору цілих чисел від 0 до N-1 будемо називати зміну порядку їх запису. Для того, щоб показати, що символ а_і переставлено з i -тої позиції в позицію s(i), де 0 £ (i) < n, скористаємось таким записом

Загальне число перестановок на множині (0,1,..., N-1) дорівнює

 

 

Далі перестановку набору S={s₀,s₁,..., s_N-1} символів будемо розглядати як взаємно-однозначне відображення на себе

 

Якщо повідомлення, що підлягає зашифруванню сформоване символами алфавіту А, загальна кількість яких дорівнює т, загальна кількість варіантів, що дають змогу утворити перестановку у групі з п символів, дорівнює (mⁿ)!.

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

Довжина блоку визначає потужність ключового простору. Якщо вона складається з бінарних символів і дорівнює п’яти, існує 120 способів її перестановки. Це означає, що для реалізації такого шифру потрібен пристрій, пам’ять якого повинна вміщувати всі 120 таблиць відповідних перестановок, тобто 2880 біт. У разі ж коли довжина блоку складає 128 символів, операція перестановки стає технічно неможливою, хоча потужність ключового простору, що вона забезпечить, буде дорівнювати 2¹²⁸ або 10³⁸. В цьому полягає фундаментальна дилема криптографії – ми знаємо, що є ідеалом, але він для нас практично недосяжний.

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

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

 

 

2.3.3 Будування композиційних шифрів.

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

Першим таким способом є використання операції множення кількох секретних систем. Наприклад, якщо їх дві - R₁ і R₂ (як це показано на рисунку 6), то спочатку повідомлення зашифровується за допомогою системи R₁, а потім, утворена таким чином криптограма, знову підлягає зашифруванню вже за допомогою секретної системи R₂. Ключ загальної системи S, що уявляє собою добуток складових систем і визначається за правилом

 

 

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

 

Таким чином, якщо система R₁ передбачає наявність т ключів, що обираються відповідно з імовірностями

 

 

а система R₂ – п ключів, що обираються відповідно з імовірностями

 

 

загальна секретна система буде мати тп ключів, які обираються з імовірностями р_і р_j^’ відповідно.

Слід пам’ятати, що множення секретних систем у загальному випадку не є комутативним (тобто R₁ R₂ ¹ R₂ R₁), хоча можуть існувати й виняткові ситуації.

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

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

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

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

 

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