Афінна криптосистема
Лабораторна робота №1
Основи шифрування даних
Мета роботи:вивчення основних принципів шифрування інформації, знайомство з широко відомими алгоритмами шифрування, набуття навичок їхньої програмної реалізації.
Проблема приховування інформації була актуальна для людства ще в давні часи, письмові свідчення про використання найпростіших методів шифрування зустрічаються ще у давніх греків у V-VI ст. до н.е. Розвиток цивілізації, поява нових засобів комунікації (спочатку письмових, потім електронних) пред'являли до методів шифрування все більш жорсткі вимоги, що вилилося в появу окремої науки, що займається захистом інформації шляхом її перетворення - криптології. У цієї науки два напрями: криптографія та криптоаналіз.
Криптографія– наука про методи та засоби перетворення інформації у вид, що утрудняє або унеможливлює несанкціоновані операції з нею (читання та/або модифікацію).
Базовим поняттям криптографії є шифр [1].
деXX–кодоване повідомлення з множини відкритих текстів;
SS–шифротекст із безлічі можливих закодованих текстів;
k- ключ шифрування;
F– відображення, яке виконується шифром.
Властивість ін'єктивності шифру означає, що є відображенняF-1 таке, що
Процес перетворення відкритого тексту (переданого повідомлення) в шифротекст називаєтьсяшифруванням.Зворотне перетворення шифротексту у відкритий текст називаєтьсядешифруванням. Класифікацію шифрів за різними ознаками можна переглянути в [2].
Криптоаналіз- наука (і практика її застосування) про методи та способи розкриття шифрів. Під розкриттям розуміється завдання отримання відомого шифротексту відповідного відкритого тексту та/або ключа шифрування.
На цей час винайдено велику кількість різноманітних шифрів. Деякі з них використовуються в даний час для практичних цілей захисту даних у різних інформаційних системах, а деякі представляють лише історичний інтерес, оскільки використовувані в них перетворення не забезпечують належної стійкості від розтину сучасного рівня обчислювальних потужностей ЕОМ. Однак знайомство з такими застарілими криптоалгоритмами має безперечну користь, оскільки дозволяє простежити еволюцію криптоалгоритмів, кристалізацію в них сучасних принципів шифрування, оцінити слабкі та сильні сторони тих чи інших криптоперетворень.
Однією з перших документально зафіксованих шифрів єшифр Цезаря, використовуваний відомим полководцем у своїй листуванні. У шифрі кожна літера заміщається на літеру, що знаходитьсяkсимволами правіше в алфавіті за модулем, що дорівнює кількості літер в алфавіті:
Ck(j)=(j+k)(modn), деj- порядковий номер букви в алфавіті,Ck(j) – порядковий номер літери, що заміщає,n– потужність вхідного алфавіту (кількість літер у алфавіті).
Таким чином, ключем шифрування є число k, що визначає розмір зсуву.
Очевидно, що зворотною підстановкою є
За необхідності алфавіт можна розширити розділовими знаками, великими літерами, цифрами, щоб шифр міг обробляти всесимволи вихідного тексту.
Загальна кількість допустимих ключів дорівнює n, причому один із ключів перетворює текст на самого себе. Така невелика кількість ключів дозволяла здійснювати простий криптоаналіз шифротексту ще за часів Цезаряметодом смужок, коли кілька смужок із записаним на них алфавітом розташовували поруч так, щоб по горизонталі вийшов фрагмент шифротексту. Після цього смужки синхронно зрушувалися вгору або вниз до тих пір, поки по горизонталі на місці шифротексту не виявиться деяка фраза, що читається. Величина усунення смужок однозначно визначає ключk.
Шифр Цезаря із ключовим словом.
У цьому різновиді шифру Цезаря ключ визначається числомk(0-1a,b(j)=(j-b+n)*a-1 (modn)
Пошук мультиплікативно-зворотного (позначеного якa-1) здійснювати за алгоритмом Евкліда. Вочевидь, що за=1 афінна криптосистема вироджується в шифр Цезаря. Взаємна простотаaіnнеобхідна для біективності відображення, інакше можливі відображення різних символів в один і неоднозначність дешифрування. Кількість ключів афінної криптосистеми залежить від потужності алфавіту, що використовується. Для алфавіту української мови коефіцієнтbможе набувати 33 значення, коефіцієнта– лише значення, взаємно прості з числом 33: 1, 2, 4, 5, 7, 8, 10, 13 , 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32. Разом 20 значень. Усі можливі поєднання допустимихbіaдають ключовий простір 33*20=660-1=659 ключів (1 ключ віднімається, оскільки поєднанняa=1 іb=33 перетворює алфавіт на себе).
Шифр Цезаря та афінна криптосистема відносяться до класу одноалфавітних криптосистем, тобто для обраногоключа деяка літера вихідного відкритого тексту завжди замінюватиметься однією і тією ж літерою в шифротексті. Тому дані шифри можуть бути розкриті методомчастотного криптоаналізу.Частотний аналіз використовує ту властивість зашифрованого тексту, що частота народження символів в ньому збігається з частотою народження відповідних символів у відкритому тексті. Якщо ж врахувати, що частоти різних символів у текстах відповідної мови розподілені нерівномірно (так, наприклад, відносна частота народження літери «А» в текстах українською мовою становить 0.069, а літери «Ф» 0.003), то, підрахувавши відносну частоту зустрічності у шифротексті, можна припустити, що символ, що найчастіше зустрічається в шифротексті, відповідає символу, що найчастіше зустрічається в текстах відповідною мовою, і знайти таким чином ключkдля шифру Цезаря. Для розкриття параметрівaіbафінної криптосистеми потрібно знайти відповідність двох літер - найчастіше зустрічається в шифротексті і другий за частотою. Ефективність частотного аналізу шифру Цезаря з ключовим словом великою мірою залежить від довжини використовуваної ключової фрази, загальна кількість допустимих відображень алфавіту дорівнює, як згадувалося,n!.
Квадрат Полібія
Ще однією модифікацією одноалфавітної заміни є квадрат Полібія, у якому символ алфавіту замінюється парою чисел чи символів за певним правилом. Розглянемо прямокутник, який часто називають дошкою Полібія.