Криптография. Лекція Захист інформації, його складові і рівні формування режиму інформаційної безпеки
 Скачать 1.04 Mb.
|
Поворотна решітка представляла собою лист з твердого матеріалу з прорізями. Накладаючи таку решітку на лист паперу, можна записувати у вирізи таємне повідомлення. Після цього, знявши решітку, треба було заповнити вільні місця, що залишились, маскуючим текстом. Подібним стеганографічним методом маскування повідомлень користувались багато історичних осіб, зокрема, кардинал Рішіл’є у Франції. Він використовував в якості решітки прямокутник розміру 7х10 (Рис.2.2) з 13 прорізами в позиціях (1,8), (2,9), (3,6), (4,5), (4,6), (5,1), (5,6), (5,7), (5,9), (6,2), (6,10), (7,9), (7,10). Для довгих повідомлень прямокутник застосовувався кілька разів. 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 Рис.2.2. Решітка Рішіл’є В історії криптографії XVII-XVIII ст. називають ерою «чорних кабінетів». В цей період в багатьох державах Європи з’явились дешифрувальні підрозділи, які і називались «чорними кабінетами». Перший з них був створений у Франції за ініціативою кардинала Рішіл’є. Характерним для цього періоду є широке розповсюдження шифрів, які називались номенклаторами. Номерклатори поєднували в собі просту заміну і код. В якості прикладу номенклатура наведемо «малий шифр», що використовувався в наполеонівській армії (Таблиця 2.2). Таблиця 2.2. «Малий шифр», що використовувався в наполеонівській армії A-15 AR-25 AL-39 J-87 JAI-123 R-169 RA-146 RE-126 RI-148 B-37 BU-3 BO-35 BI-29 K-? S-167 SA-171 SE-177 SI-134 C-6 CA-32 CE-20 L-96 LU-103 LE-117 SO-168 SU-174 D-23 DE-52 LA-106 T-176 TI-145 TO-157 E-53 ES-82 ET-50 EN-68 M-114 MA-107 U-138 F-55 FA-69 FE-58 FO-71 N-115 NE-94 NI-116 V-164 VE-132 VI-161 VO-175 G-81 GA-51 O-90 OT-153 W, X, Y-? H-85 HI-77 P-137 PO-152 Z-166 I-119 IS-122 Q-173 QUE-136 Приклад застосування цього шифру наведений в Таблиці 2.3. 14 Таблиця 2.3. Приклад шифрування «малим шифром» слова NAPOLEON N A P O L E O N 115 15 137 90 96 53 90 115 або N A PO LE O N 115 15 152 117 90 115 В простих нуменклаторах код складався з кількох десятків слів або фраз з двобуквеними кодовими позначеннями. З часом списки слів в номерклаторах збільшились до двох-трьох тисяч. В цілому XVII-XVIII ст. не дали для криптографії нових ідей. Ера «чорних кабінетів» закінчилась в 40их роках XIX ст. Нові ідеї з’явились в середині XIX ст. Цей період пов’язаний з виникненням стійкого способу ускладнення числових кодів – гаміювання. Він полягав у перешифровуванні закодованого повідомлення за допомогою деякого ключового числа, яке називалось гамою. Шифрування за допомогою гами полягало у сумуванні всіх кодованих груп повідомлення з одним і тим самим ключовим числом. Приклад 1. Результат накладення гами 6413 на кодований текст (одиниці перенесення, що з’являються при додаванні між кодовими групами, опускаються): 3425 7102 8139 + 6413 6413 6413 9838 3515 4552 Приклад 2. Результат оберненої операції «зняття гами» 6413: 9838 3515 4552 - 6413 6413 6413 3425 7102 8139 15 Перша світова війна стала поворотним пунктом в розвитку криптографії в зв’язку зі зростанням обсягів шифропереписки. Криптографія стала широким полем діяльності. Проте нових наукових ідей в цей час не з’явилося. Майже половина XX ст. була пов’язана з використанням колісних шифраторів. Їх різні конструкції були запатентовані майже одночасно в різних країнах (Голандії, Німеччині, Швеції). Найбільш відомою шифромашиною цих часів була «Енігма», яка у довоєнний період і під час другої світової війни використовувалась в германській армії. Принцип її роботи такий. На екрані оператору показувалася буква, якою шифрувалася відповідна літера на клавіатурі. Те, якою буде зашифрована літера, залежало від початкової конфігурації коліс. Суть в тому, що існувало понад сто трильйонів можливих комбінацій коліс, і з часом набору тексту колеса зсувалися самі, так що шифр змінювався протягом усього повідомлення. Все Енігми були ідентичними, так що при однаковому початковому положенні коліс на двох різних машинах і текст виходив однаковий. У німецького командування були Енігми і список положень коліс на кожен день, так що вони могли з легкістю розшифровувати повідомлення один одного, але вороги не повідомляючи положень послання прочитати не могли. У другій половині XX ст. в зв’язку з розвитком елементної бази обчислювальної техніки з’явились електронні шифратори. Сьогодні для шифрування даних найбільш широко застосовують три види шифраторів: апаратні, програмно-апаратні та програмні. Їх основна відмінність полягає не тільки в способі реалізації шифрування і ступеня надійності захисту даних, але і в ціні. Найдешевші пристрої шифрування - програмні, потім йдуть програмно-апаратні засоби і, нарешті, найдорожчі - апаратні. В 70-их роках народилась «нова криптографія» - криптографія з відкритим ключем. Криптографія почала широко використовуватись не тільки у військовій, дипломатичній, державній сферах, а також в комерційній, банківській та інших сферах. 16 2.5.Види історичних шифрів Історичними (докомпютерними) називають шифри, що використовувались до 1960 року, тобто в доком’ютерну епоху. Ці шифри є типовими прикладами симетричних алгоритмів шифрування і залишаються основою багатьох сучасних криптосистем. В класичній криптографії доведено, що в основі криптографічних алгоритмів знаходяться тільки два основних типи перетворень – заміни і перестановки; всі інші є лише їх комбінацією. В перестановочних шрифтах символи відкритого тексту змінюють свої розташування. Наприклад, відкритий текст виписується у вигляді матриці з пронумерованими стовпцями, після чого порядок стовпців змінюється: Простий шифр маршрутної перестановки Саме цей шифр реалізовувала Сцитала. У даному вигляді шифру текст пишеться на горизонтально разграфленому аркуші паперу фіксованої ширини, а шифротекст зчитується по вертикалі. Розшифрування полягає в записі шіфротекста вертикально на аркуші розграфлений паперу фіксованої ширини і потім зчитуванні відкритого тексту горизонтально. Для приклада (Рис.2.3) в якості відкритого тексту взято КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ. Рис.2.3. Приклад використання маршрутної перестановки Тоді зашифрований текст буде таким: к пчнтуийоіиит тйнлиївкіх с ніетьс. Стовпчикова транспозиція Стовпчикова транспозиція – перестановочний шифр, в якому використовується блоковий алгоритм шифрування: 17 1. Відкрите повідомлення вписується в прямокутник [nхm] заздалегідь обумовленим способом. 2. Стовпчики прямокутника нумеруються в звичайному порядку. 3. Стовпчики переміщуються в порядок, що задається вказаною ключовою послідовністю (або в порядку букв ключа - літерного ключового слова). Рис.2.4. Приклад використання стовпчикової перестановки Простий перестановочний шифр Фіксується матриця перестановки n-елементів. Для n=5 вона може бути такою: Вхідне повідомлення розбивається на блоки по n символів, в кожному з яких символи переставляються у відповідності з матрицею перестановки.Саме перестановка є секретним ключем. Зашифруємо в якості прикладу відкритий текст ПЕРЕСТАНОВКА. Розіб'ємо текст на частини по 5 букв: ПЕРЕС ТАНОВ КА. Потім переставимо букви в них відповідно до нашої матриці: еспре автно ка. Прибравши проміжки між групами, отримаємо шіфротекст: еспреавтнока. Шифр зсуву Шифр зсуву – один з перших відомих шифрів, що використовувався ще в давнину. Використовується поточний алгоритм шифрування, який полягає у такому: 18 1. Перенумеровуються всі літери вихідного алфавіту, починаючи з 0, наприклад, букві «а» присвоюється номер 0, «b» - 1, і т.д. до літери «z» під номером 25. 2. Переписується вихідний текст з заміною кожної букви відповідним номером. 3. До кожного числа в утвореній послідовності додається значення3 ключа К по модулю 26; К- ціле число між 0 і 26. Криптостійкість шифру зсуву вкрай низька. Наївний шлях атаки на шифр зсуву полягає в простому переборі можливих значень ключа до тих пір, поки не вийде осмислений текст. Оскільки існує рівно 25 варіантів (ключ О не змінює тексту), то для їх перебору потрібно не дуже багато часу, особливо у випадку короткої шифрограми. Приклад 1. Шифр зсуву з кроком 1 використовував ще імператор Август (1 в. н. е.). У своєму листуванні він замінював першу букву латинського алфавіту на другу, другу - на третю і т. д., нарешті, останню – на першу: Улюблений вислів імператора Августа виглядало так: GFTUJOB MFOUF ("Festina lente" - лат. "Поспішай повільно"). Приклад 2. Шифр зсуву з ключем 3 використовував ще Юлій Цезар; тому його також називають шифром Цезаря. У 1 в. н.е. Юлій Цезар під час війни з галлами, листуючись зі своїми друзями в Римі, заміняв у повідомленні першу літеру латинського алфавіту (А) на четверту (D), другу (В) - на п'яту (Е), нарешті, останньому - на третю: 19 Донесення Ю. Цезаря Сенату про здобутуї їм перемогу над Понтійським царем виглядало так: YHQL YLGL YLFL ("Veni, vidi, vici" - лат. "Прийшов, побачив, переміг"). Приклад 3. Прикладом шифру простої заміни може служити програма ROT13, яку зазвичай можна знайти в операційній системі UNIX. З її допомогою буква "А" відкритого тексту англійською мовою замінюється на літеру "N", "В" - на "О" і так далі. Таким чином, ROT13 циклічно зсуває кожну букву англійського алфавіту на 13 позицій вправо. Щоб отримати вихідний відкритий текст треба застосувати функцію шифрування ROT 13 двічі: Р = ROT13 (ROT13 (P)). В шифрах заміни один символ відкритого тексту замінюється символом зашифрованого тексту. Шифр заміни Основний недолік шифру зсуву полягає в тому, що існує надто мало можливих ключів – всього 25. З метою усунення цього недоліку був винайдений шифр заміни. Шифр заміни використовує блочний алгоритм шифрування, який полягає у такому: 1. Описуєтьяс ключ такого шифру, для чого спочатку виписується алфавіт, а беспосередньо під ним - той же алфавіт, але з переставленими літерами тогож або іншого алфавіту. 2. Шифрування полягає в заміні кожної букви у відкритому тексті на відповідну їй нижню літеру. 3. Щоб розшифрувати шифротекст, потрібно кожну його букву знайти в нижньому рядку таблиці і замінити її відповідною верхньою. Кількість всіх можливих ключів шифру заміни збігається з числом всіх перестановок 26 елементів, тобто рівним 26! 10 9 . Тому, перебираючи всі можливі ключі за допомогою комп'ютера, ми витратимо стільки часу, що задача про дешифрування конкретного повідомлення перестане бути 20 актуальною. Тим не менш, шифр заміни можна зламати, спираючись на частотному аналізі символів мови. Шифр заміни є блоковим, блок в якому складається з однієї букви. Блок шифротексту отримується з блоку відкритого тексту в результаті застосування ключа (таблиці відповідності). Приклад 4. Криптограма слова «hello» буде виглядати як ESVVJ, якщо користуватися наведеною відповідністю: Поліалфавітний шифри заміни Шифр заміни відноситься до так званих моноалфавітних шифрів заміни, в яких використовується тільки один впорядкований набір символів, підміняючий собою стандартний алфавіт. Основний недолік шифру заміни (і зсуву) полягає в тому, що кожна буква відкритого тексту при шифруванні замінюється раз і назавжди фіксованим символом. Тому при дешифруванні ефективно працює частотний аналіз символів мови. З початку XIX століття розробники шифрів намагалися подолати такий зв'язок між відкритим текстом і його шифрованим варіантом. Один із шляхів вирішення вказаної проблеми полягає в тому, щоб брати кілька наборів символів замість стандартного алфавіту і шифрувати букви відкритого тексту, вибираючи відповідні знаки з різних наборів у визначеній послідовності. Шифри такого типу носять назву поліалфавітних шифрів заміни. Алгоритм поліалфавітного шифру заміни може полягати у такому: 21 1. Описується відповідність між алфавітом відкритого тексту і кількома рівнями алфавітів шифротексту 1 : 2. При шифруванні букви відкритого тексту, що знаходяться на непарних позиціях, замінюються відповідними буквами другого рядка, а ті, що знаходяться на парних позиціях – буквами третього рядка. 3. При розшифруванні букви криптотексту, що знаходяться на непарних позиціях, шукаються в другому рядку, а ті, що знаходяться на парних позиціях – в третьому рядку. Приклад 5. Вхідне слово hello в шифротексті буде виглядати як SHLJV, що суттєво ускладнює застосування для атаки частотного аналізу мови. На практиці можна використовувативати не два, а аж до п'яти різних алфавітів шифротексту, багаторазово збільшуючи простір ключів. Дійсно, легдо підрахувати, що якщо ми беремо символи з п'яти заміщуючих наборів, то число можливих ключів (26!) 5 2 441 . Проте в цьому випадку ключ - послідовність з 26*5 = 130 літер. Для середнього користувача початку XIX століття такий ключ був занадто великим, щоб запам'ятати його. Незважаючи на зазначений недолік, найвідоміші шифри XIX століття грунтувалися саме на описаному принципі. До них відносяться модифікований шифр Цезаря та шифр Віженера. Модифікований шифр Цезаря Модифікований шифр Цезаря - один з варіантів поліалфавітного шифру зсуву. Використовується потоковий алгоритм шифрування, який полягає у такому: 1 Тут перший рядок - англійський алфавіт, а другиі і третій - перший і другий алфавіти шифротекста. 22 1. Як і у випадку шифру зсуву, перенумеруємо 26 літери вхідного алфавіту, починаючи з 0: 2. Створюємо секретний ключ – будь-яке слово, яке наивають гаслом. 3. Гасло підписується ють під повідомленням з повторенням. 4. Щоб отримати шифрований текст, складають номер чергової букви з номером відповідної букви ключа. Якщо отримана сума більше 26, то з неї віднімають 26. В результаті отримують послідовновательность чисел від 1 до 31. Знову замінюючи числа цієї последовательности відповідними буквами, отримують шифрований текст. Приклад 6. Якщо гаслом є слово sesame, то шифрування виглядає так: Шифр Віженера Шифр Віженера є поліалфавітним блоковим шифром. Шифрування і розщифрування грунтується на використанні таблиці Віженера. В загальному випадку першим її рядком є алфавіт відкритого текту, а першим стовпчиком – алфавіт ключа. Тіло таблиці складається з циклічно зсунутих алфавітів, причому його перший рядок може бути довільним змішаним алфавітом. 23 В найпростішому випадку використання незмішаного алфавіту для самоключа таблиця Віженера матиме такий вигляд (складена з 31 літери російського алфавіту – без літер ё і ъ) : Щоб зашифрувати повідомлення: 1. Вибирається слово - гасло і підписується з повторенням над буквами відкритого повідомлення. 2. Щоб отримати шифрований текст, знаходять черговий знак лозунгу, починаючи з першого у вертикальному алфавіті, а відповідний йому знак повідомлення – в горизонтальному. Приклад 7. Вибираємо гасло - математика. Знаходимо стовпець, що відповідає букві "м" гасла, а потім рядок, відповідну букві "к". На перетені виділених стовпця і рядка знаходимо букву "ц". Продовжуючи далі, знаходимо весь зашифрований текст: Ц Р Ь Ф Я О Х Ш К Ф Ф Я Д К Э Ь Ч П Ч А Л Н Т Ш Ц А. У 1888 р. француцз маркіз де Віарі довів, що щифрування по Віженеру відтворює алгебраїчна формула 24 С=(p+G) mod 26 , де С – будь-яка буква шифротексту, p– будь-яка буква відкритого тексту, G – будь-яка буква гами, а заміна букв числами здійснюється за таблицею: Процес розшифрування відтворює формула p = ( С – G +26) mod 26 , Викоритсання рівняння шифрування дозволило відмовитись від громіздкої таблиці Віженера. Згодом лозунгова гама стала довільною числовою послідовністю, а щифр з вказаним рівнянням шифрування став називатись шрифтом гаміювання. Як бачимо, у простому варіанті з коротким ключовим словом і з таблицею, що складається зі звичайних алфавітів, шифр Віженера є еквівалентним модифікованому шифру Цезаря. В літературі часто саме цей найпростіший варіант і називають шифром Віженера. 25 Лекція 4-5. Криптографічна стійкість шифрів 3.1. Поняття криптографічної стійкості Криптографічна стійкість (або крипостійкість) - здатність криптографічного алгоритму протистояти можливим атакам на нього. Стійким вважається алгоритм, який для успішної атаки вимагає від противника: • недосяжних обчислювальних ресурсів, • недосяжного обсягу перехоплених відкритих і зашифрованих повідомлень чи • такого часу розкриття, що по його закінченню захищена інформація буде вже не актуальна, і т. д. Стійкість не можна підтвердити, її можна тільки спростувати зломом. Для оцінки стійкості шифру використовують оцінку обчислювальної складності алгоритму успішної атаки на криптосистему. Рівень криптостійкості (англ. security level) - показник криптостійкості алгоритму, пов'язаний з обчислювальною складністю виконання успішної атаки на криптосистему. Зазвичай рівень криптостійкості вимірюється в бітах. N-бітний рівень криптостійкості криптосистеми означає, що для її злому потрібно виконати n обчислювальних операцій. Наприклад, якщо симетрична криптосистема зламуються не швидше, ніж за повний перебір значень n-бітного ключа, то кажуть, що рівень криптостійкості дорівнює n. Складність алгоритмів зазвичай оцінюють за часом виконання, але не менш важливі й інші показники - вимоги до обсягу пам'яті, вільного місця на диску. В теорії алгоритмів обчислювальна складність алгоритму - це функція, яка визначає залежність обсягу роботи, виконуваної деяким алгоритмом, від розміру вхідних даних. У загальному випадку складність алгоритму можна оцінити по порядку величини. Алгоритм має складність O (f (n)), якщо при збільшенні розмірності 26 вхідних даних n, час виконання алгоритму зростає з тією ж швидкістю, що і функція f (n). Використання великої літери О (або так звана О-нотація) прийшло з математики, де її застосовують для порівняння асимптотичної поведінки функцій. Формально O (f (n)) означає, що час роботи алгоритму (або обсяг займаної пам'яті) росте в залежності від обсягу вхідних даних не швидше, ніж деяка константа, помножена на f (n). Типові приклади використання О-нотації: |