Слайд 1ЗМІСТОВНИЙ МОДУЛЬ № 1
КЛАСИЧНІ КРИПТОГРАФІЧНІ СИСТЕМИ
Сіденко Володимир Павлович,
Старший викладач кафедри
“Безпека інформаційних та комунікаційних систем”
1
Слайд 2Лекція № 2
КЛАСИЧНІ КРИПТОГРАФІЧНІ СИСТЕМИ З ОДНОАЛФАВІТНИМИ
ШИФРАМИ ЗАМІНИ (ПІДСТАНОВКИ)
2
Слайд 3Питання лекції № 2
1. Одноалфавітні шифри заміни (підстанов-ки)
2. Криптоаналіз
одноалфавітних шифрів за-міни (підстановки)
3. Одноалфавітні афінні шифри заміни (під-становки)
4.
Одноалфавітні шифри заміни (підста-новки) з ключовим словом
Література: Л2, с. 101 - 120; Л3, с. 48 – 60.
3
Слайд 4
1. ОДНОАЛФАВІТНІ ШИФРИ ЗАМІНИ (ПІДСТАНОВКИ)
4
Слайд 5 До шифрів заміни відносяться крипто-графічні перетворення, при яких фрагмен- ти
відкритого тексту (окремі символи або групи символів - блоки) заміняються
деякими символами або групами символів у шифротексті.
Найбільше розповсюдження одержали шифри простої заміни, безлічі шифровели- чин і шифропозначень яких збігаються з алфавітом відкритого тексту М. Ключем такого шифру є підстановка k на множині M, верхній рядок якої являє собою природ- ну послідовність букв алфавіту, а нижня -
5
Слайд 6систематично перемішану або випадкову послідовність букв із M.
При використанні цих
шифрів букви ал- фавіту M зручно ототожнювати з їхніми по-
рядковими номерами.
Ключ для шифру Цезаря (k=3) з викорис- танням англійського алфавіту (n=26) може бу- ти заданий у вигляді рис. 2.1.
Ключ для шифру Цезаря (k=3) з викорис- танням російського алфавіту (n=32) може бути заданий у вигляді рис. 2.2.
6
Слайд 77
Рис. 2.1. Ключ для шифру Цезаря з використанням англійського алфавіту
Слайд 99
Як видно з рис. 2.1 і 2.2 цей шифр реа-
лізує наступне перетворення тексту.
Кожна буква відкритого тексту заміня-ється буквою, яка
стоїть на три позиції пізніше її в алфавіті. При цьому алфавіт вважається записаним по колу, тобто після останньої букви алфавіту йде перша буква.
Крім явного завдання (у вигляді двох- рядкового запису) ключ може бути заданий деякими формулами.
Для шифру Цезаря довжина алфавіту шифровеличин (nМ) і довжина алфавіту шифропозначень (nС) однакова, тобто
Слайд 1010
У такому випадку можна записати
де М и С – множина
символів алфавіту шиф- ровеличин і шифропозначень у числовому вигляді.
Множина ключів
узагальненого шифру Цезаря
Для
алгоритм шифрування можна представити у вигляді
Слайд 1111
а алгоритм розшифрування у вигляді
Наприклад, слово ПЕРЕМЕНА на ро- сійській
мові, при використанні рис. 2.2 і k=3 перетвориться в щифропозначення
ТИУИПИРГ.
Слайд 1212
Слову ПЕРЕМЕНА відповідає числова послідовність
а слову ТИУИПИРГ
Якщо тепер розшифруємо числову
по- слідовність (2.8) з використанням алгорит- му розшифрування (2.5), те
одержимо
Слайд 1313
Як видно з (2.9) шифротекст ТИУИПИРГ у результаті розшифрування перетворився
у відкритий текст ПЕРЕМЕНА.
Слайд 1414
2. КРИПТОАНАЛІЗ ОДНОАЛФАВІТНИХ ШИФРІВ ЗАМІНИ (ПІДСТАНОВКИ)
Слайд 1515
Звернемося тепер до аналізу дій злов- мисника, що намагається розшифрувати
повідомлення й довідатися секретний ключ, іншими словами розкрити, або зла-
мати шифр.
Кожна спроба розкриття шифру нази- вається атакою на шифр (або на криптосис- тему). У криптографії прийнято вважати, що зловмисник може знати використаний алго- ритм шифрування, характер повідомлень, які передаються і перехоплений шифро- текст, але не знає секретний ключ.
Слайд 1616
У нашому прикладі думаємо, що злов- мисник знає, що шифр
був побудований відповідно до (2.5) і (2.6), що вихідне пові-
домлення було російською мовою (n=32) і що був переданий шифротекст ТИУИПИРГ, але ключ k йому не відомий.
Найбільш очевидна спроба дешифрувати - послідовний перебір всіх можливих ключів (це так званий метод "грубої сили"). Отже, зловмисник переби- рає послідовно всі можливі ключі k = 0, 1, 2,...,31, підставляючи їх в алгоритм розши- фрування й оцінюючи результати, що ви-
Слайд 1717
ходять.
Спробуємо й ми використати цей ме- тод. Результати дешифрування по
(2.6) при різних ключах і шифротексте ТИУИПИРГ зведені на рис.
2.3.
Слайд 1818
Рис. 2.3. Дешифрування шифротекста ТИУИПИРГ шляхом перебору ключів
Слайд 1919
З рис. 2.3 ми бачимо, що був викорис-таний ключ k=3
і зашифроване повідом- лення ПЕРЕМЕНА. Причому для того, щоб перевірити
інші можливі значення ключа, нам не було потрібно дешифрувати всі ві- сім букв, а в більшості випадків після ана- лізу двох-трьох букв ключ відкидався (тільки при k=8 треба було дешифрувати п'ять букв, зате при k=22, 23 і 24 вистачало й однієї, тому що в російській мові немає слів, що починаються з букв Ь, Ъ, Ы).
Із цього приклада ми бачимо, що роз- глянутий шифр зовсім нестійкий, для його
Слайд 2021
розкриття досить проаналізувати декілька перших букв повідомлення й після цього
ключ k однозначно визначається (і, отже, однозначно дешифрується все повідом-
лення).
У чому ж причини нестійкості розгля- нутого шифру і як можна було б збільшити його стійкість?
Розглянемо ще один приклад. Нехай хтось сховав документи в чарунці камери схову, постаченої п’ятидекадним кодовим замком.
Тепер він хоче повідомити другові комбінацію цифр, що відкриває чарунку.
Слайд 2121
Він вирішив використати аналог шиф- ру Цезаря (k=3), адаптований до
алфавіту, що складає з десяткових цифр відповідно до рис. 2.4.
Рис.
2.4. Ключ для шифру Цезаря з використанням десяткових цифр
Слайд 2222
При цьому алгоритм шифрування й розшифрування може бути представлений у
такому вигляді.
Нехай відкрите повідомлення (текст) має вигляд: 35148. У такому
випадку шиф- роване повідомлення, відповідно до вира- зу (2.5) або рис. 2.4 буде відповідати – 68471.
Зловмисник намагається дешифрува- ти його, послідовно перебираючи всі мож- ливі ключі. Результати його спроб предс- тавлені на рис. 2.5.
Слайд 2323
Рис. 2.5. Дешифрування повідомлення 35148 шляхом перебору ключів
Ми бачимо, що
всі отримані варіанти рівнозначні й зловмисник не може зрозу- міти,
яка саме комбінація справжня.
Слайд 2424
Аналізуючи шифротекст, він не може знайти значення секретного ключа. Звичай-
но, до перехоплення повідомлення у злов- мисника було 105 можливих
значень кодо- вої комбінації, а після - тільки 10. Однак важливо відзначити те, що в цьому випад- ку всього 10 значень ключа.
Тому при такому ключі (одна десятко- ва цифра) немає можливості розраховува- ти на більшу таємність.
У першому прикладі повідомлення - текст російською мовою, тому воно підко-ряється численним правилам, різні букви і
Слайд 2525
їхні сполучення мають різні ймовірності й, зокрема, багато наборів букв
взагалі забо- ронена (Ця властивість називається над- мірністю тексту). Тому-те
й удалося легко підібрати ключ і дешифрувати повідомлен- ня, тобто надмірність дозволила “зламати” шифр. На противагу цьому, у другому прик- ладі всі комбінації цифр припустимі. “Мова” кодового замка не містить надмір- ності. Тому навіть простий шифр, застосо- ваний до повідомлень цієї мови, стає та- ким що не розкривається.
Слайд 2626
Описана в наведених прикладах атака називається атакою на шифротекст.
З аналізу
вищесказаного треба, що для збільшення стійкості шифру Цезаря необ- хідно
збільшувати довжину алфавіту або довжину ключа. Але зробити це при вико- ристанні одноалфавітної заміни практично неможливо, тому що довжина ключа зале- жить від довжини алфавіту.
Ясно, що при використанні шифру простої заміни частота повторень зашиф- рованих символів у шифротексті збігається із частотою повторень відповідних вихід-
Слайд 2727
них символів у відкритому тексті.
Це дозволяє досить легко розкрити
такий шифр. Більше тонкі характеристики (облік сполучуваності різних букв) дозволяють
на- віть автоматизувати процес злому.
Слайд 2828
3. ОДНОАЛФАВІТНІ АФІННІ ШИФРИ ЗАМІНИ (ПІДСТАНОВКИ)
Слайд 2930
У системі шифрування Цезаря вико- ристалися тільки адитивні властивості множини
цілих M і C. Однак символи цих множин можна й
множити за модулем n. Застосовуючи одночасно операції дода- вання й множення за модулем n над еле- ментами множин M і C можна одержати систему шифрування, що називають афін- ної системою шифрування.
Для афінних шифрів довжина алфаві- ту шифровеличин (nМ) і довжина алфавіту шифропозначень (nС) однакова як і для шифру Цезаря, множини символів алфаві-
Слайд 3030
ту шифровеличин і шифропозначень ви- значаються (2.2).
Множина ключів афінних шифрів
визначається так
Ключ для афінних шифрів представ-ляється у вигляді
Як видно з
(2.10) довжина ключа афінних шифрів набагато більше чим довжина ключа шифру Цезаря.
Для (2.4) алгоритм шифрування можна представити у вигляді
Слайд 3131
а алгоритм розшифрування у вигляді
Слайд 3232
де - елемент із мультиплікативної групи
Z зворотний до a.
Варто помітити, що перетворення (2.12) і (2.13) є взаємно однозначними тіль- ки в тому випадку, якщо найбільший спіль- ний дільник чисел a і n, позначуваний як НСД(a,n), дорівнює одиниці, тобто a і n по- винні бути взаємно простими числами.
Наприклад, нехай n=32, а=3, b=5. Тоді, очевидно НСД(3,32) =1.
Зашифруємо слово ПЕРЕМЕНА за до- помогою афінного шифру, при k=(3,5).
Слайд 3333
Рис. 2.6. Ключ для афінних шифрів числового
російського алфавіту
Даний ключ формує
наступну заміну (під- ста новку) на Z (рис. 2.6).
Слайд 3434
Якщо декодувати числа в букви, то одер-жимо наступну відповідність букв
(рис. 2.7).
Рис. 2.7. Ключ k=(3,5) для афінних шифрів російського алфавіту
Слайд 3535
Відповідно до рис. 2.6 і 2.7, слово ПЕРЕМЕНА в російській
мові, при викорис- танні k=(3,5) перетвориться в шифропозна- чення C:
ТФХФЙФМЕ.
Слову ПЕРЕМЕНА відповідає числова послідовність
а слову
Якщо тепер розшифруємо числову по- слідовність (2.15) з використанням алгорит- му розшифрування (2.13), за умови = 11 то одержимо
Слайд 3636
Як видно з (2.16) шифротекст ТФХФЙФМЕ у результаті розшифрування перетворився
у відкритий текст ПЕРЕМЕНА.
Слайд 3737
Перевагами афінної системи є:
- зручне керування ключами;
- криптостійкість вище чим
у системи простої заміни Цезаря, тому що довжина ключа в
неї дорівнює (n-1)(n-1), тобто більше в n-1 раз.
Недоліки афінної системи аналогічні недолікам системи шифрування Цезаря.
Слайд 3838
4. ОДНОАЛФАВІТНІ ШИФРИ ЗАМІНИ (ПІДСТАНОВКИ)
З КЛЮЧОВИМ СЛОВОМ
Система шифрування Цезаря
із ключо-вим словом є одноалфавітною системою заміни (підстановки). Особливістю цієї
сис-теми є використання ключового слова для зсуву й зміни порядку символів в алфавіті.
Слайд 3939
Виберемо деяке число k з діапазону 0≤k
коротку фразу як клю- чове слово. Бажано, щоб всі букви
ключо- вого слова були різними. Довжина слова або фрази не повинна бути більше довжи- ни алфавіту. Нехай обране слово DIPLOMAT і число k=5.
Ключове слово записується під буква- ми алфавіту, починаючи з букви, числовий код якої збігається з обраним числом k.
Букви алфавіту, що залишилися, запи-суються після ключового слова за абеткою (рис. 2.8).
Слайд 4040
Рис. 2.8. Система шифрування Цезаря із ключовим словом для англійського
алфавіту
Тепер ми маємо підстановку для кож- ної букви довільного відкритого
тексту.
Слайд 4141
Наприклад відкритий текст SEND MORE MONEY (відправляю багато грошей) представляється
у вигляді шифротексту HZBY TCGZ TCBZS.
Слід зазначити, що вимога про
розход- ження всіх букв ключового слова або фра- зи не обов'язково. Можна просто записати ключове слово або фразу без повторення однакових букв. Наприклад, ключова фраза КАК ДЫМ ОТЕЧЕСТВА НАМ СЛАДОК И ПРИЯТЕН і число k=3 породжує наступну таблицю підстановок (рис. 2.9).
Слайд 4242
Рис. 2.9. Система шифрування Цезаря із ключовим словом для російського
алфавіту
Слайд 4343
Безсумнівною перевагою системи ши- фрування Цезаря із ключовим словом є,
те, що кількість можливих ключових слів прак- тично невичерпне.
Недоліком цієї
системи є можливість злому шифротекстів на основі аналізу час- тот появи букв.