Лабораторна работа №1
Тема: Використання теорії множин до аналізу текстів та підбору здвигу в шифрі Цезарі (одноалфавітної заміни).
Цель: опрацювати методи аналізу множин на прикладі статистичного аналізу текстів при одноалфавітній заміні.
Теоретические сведения
У теорії множин є два основних первісних не означуваних понять: Множина і елемент, а основні не означувані відношення між ними описуються словами: належить, відповідає, передує, отже, поняття множина приймаємо без означення, тому пояснимо його прикладами.
Можна говорити про множину букв в алфавіті, про множину розв’язків, множину студентів І курсу і т.д. У повсякденному житті замість терміну множина вживають сукупність, череда, табун, зграя, екіпаж, колекція, клас, трупа і т.д.
У математиці під множиною розуміють сукупність, зібрання деяких предметів, об’єктів, які об’єднуються між собою характеристичною ознакою.
Математичний зміст терміну „множина” відрізняють від повсякденного, де його зв’язують з великою кількістю об’єктів. В математиці розглядаються множини, які складаються з декількох елементів або їх не має.
Об’єкти будь-якої природи (літери, числа, книги), з яких складається множина називається елементами.
Завдання.Які літери використовуються в записі слова „м а т е м а т и к а”? Яка їх потужність(кількість елементів)?
М={ м, а, т, е, и, к}
Зауваження:
1) в множині кожен елемент зустрічається лише один раз.
2) порядок запису елементів множин не має значення.
| літери
| м
| а
| т
| е
| и
| к
|
| потужн
|
|
|
|
|
|
|
Такий спосіб можна використовувати для аналізу шифрів. Наприклад.
Шифри одноалфавітної заміни є найпростішими серед інших шифрів заміни. Принцип їхньої дії побудований на тому, що кожній букві відкритого тексту ставиться у відповідність інша, але детермінована (незмінна) буква деякого алфавіту (алфавіту заміни). Через те, що кожній букві відкритого тексту відповідає єдина буква алфавіту заміни, всьому відкритому алфавіту відповідає єдиний незмінний алфавіт заміни, тому шифри цього класу називають шифрами одноалфавітної заміни.
Розглянемо шифр одноалфавітної заміни на прикладі так званого шифру Цезаря. Щоб розібрати і прочитати його тексти, потрібно всякий раз читати четверту букву замість першої відповідно до алфавіту, наприклад Д замість А, при цьому алфавіт представлявся як кільце – наступним за символом Я вважався символ А. Ми розглянемо узагальнений шифр Цезаря, в якому будемо зсовувати символи початкового алфавіту на довільну кількість позицій. Знак пробілу між словами не враховується.
Алфавіт для шифрування: АБВГДЕЄЖЗИІЇЙКЛМНОПРСТУФХЦЧШЩЬЮЯ
| Алф
| А
| Б
| В
| Г
| Д
| Е
| Є
| Ж
| З
| И
|
| Зам
| Е
| Є
| Ж
| З
| И
| І
| Ї
| Й
| К
| Л
|
|
|
|
|
|
|
|
|
|
|
|
|
| І
| Ї
| Й
| К
| Л
| М
| Н
| О
| П
| Р
| С
|
| М
| Н
| О
| П
| Р
| С
| Т
| У
| Ф
| Х
| Ц
|
|
|
|
|
|
|
|
|
|
|
|
|
| Т
| У
| Ф
| Х
| Ц
| Ч
| Ш
| Щ
| Ь
| Ю
| Я
|
| Ч
| Ш
| Щ
| Ь
| Ю
| Я
| А
| Б
| В
| Г
| Д
|
Зашифруємо текст шифром Цезаря при ключі К=5:
Відкритий текст:
МНОЖИНА — ОДНЕ З ОСНОВНИХ ПОНЯТЬ СУЧАСНОЇ МАТЕМАТИКИ. СТРОГО ВОНО НЕ ВИЗНАЧАЄТЬСЯ, АЛЕ МОЖЕ БУТИ ДАНО ІНТУЇТИВНЕ ВИЗНАЧЕННЯ МНОЖИНИ ЯК СУКУПНОСТІ ПЕВНИХ І РІЗНИХ ОБ'ЄКТІВ ДОВІЛЬНОЇ ПРИРОДИ, ЯКА РОЗГЛЯДАЄТЬСЯ ЯК ОДНЕ ЦІЛЕ. ОБ'ЄКТИ, ЯКІ СКЛАДАЮТЬ МНОЖИНУ, НАЗИВАЮТЬСЯ ЇЇ ЕЛЕМЕНТАМИ. НАПРИКЛАД, МОЖНА ГОВОРИТИ ПРО МНОЖИНУ УСІХ КНИГ В ПЕВНІЙ БІБЛІОТЕЦІ, МНОЖИНУ ЛІТЕР УКРАЇНСЬКОГО АЛФАВІТУ АБО ПРО МНОЖИНУ ВСІХ КОРЕНІВ ПЕВНОГО РІВНЯННЯ.
Всього літер у тексті – 360.
Шифртекст:
СТУЙЛТЕУИТІКУЦТУЖТЛЬФУТДЧВЦШЯЕЦТУНСЕЧІСЕЧЛПЛЦЧХУЗУЖУТУТІЖЛКТЕЯЕЇЧВЦДЕРІСУЙІЄШЧЛИЕТУМТЧШНЧЛЖТІЖЛКТЕЯІТТДСТУЙЛТЛДПЦШПШФТУЦЧМФІЖТЛЬМХМКТЛЬУЄЇПЧМЖИУЖМРВТУНФХЛХУИЛДПЕХУКЗРДИЕЇЧВЦДДПУИТІЮМРІУЄЇПЧЛДПМЦПРЕИЕГЧВСТУЙЛТШТЕКЛЖЕГЧВЦДННІРІСІТЧЕСЛТЕФХЛПРЕИСУЙТЕЗУЖУХЛЧЛФХУСТУЙЛТШШЦМЬПТЛЗЖФІЖТМОЄМЄРМУЧІЮМСТУЙЛТШРМЧІХШПХЕНТЦВПУЗУЕРЩЕЖМЧШЕЄУФХУСТУЙЛТШЖЦМЬПУХІТМЖФІЖТУЗУХМЖТДТТД
Побудуємо діаграму розподілу частот символів відкритого і шифртексту:
Відкритий текст:
| А
| Б
| В
| Г
| Д
| Е
| Є
| Ж
| З
| И
| І
| Ї
| Й
| К
| Л
| М
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Н
| О
| П
| Р
| С
| Т
| У
| Ф
| Х
| Ц
| Ч
| Ш
| Щ
| Ь
| Ю
| Я
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Шифртекст:
| А
| Б
| В
| Г
| Д
| Е
| Є
| Ж
| З
| И
| І
| Ї
| Й
| К
| Л
| М
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Н
| О
| П
| Р
| С
| Т
| У
| Ф
| Х
| Ц
| Ч
| Ш
| Щ
| Ь
| Ю
| Я
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
З двох приведених діаграм розподілу частот, ми бачимо, що рядок чисел для відкритого тексту складається з чисел:
23, 6, 17, 6, 8, 18, 4, 8, 6, 25, 18, 6, 1, 14, 10, 12 , 43, 37, 9, 13, 13, 19, 12, 1, 5, 2, 3, 0, 0, 7, 2, 12
а рядок чисел для шифртексту складається з чисел:
0, 0, 7, 2, 12, 23, 6, 17, 6, 8, 18, 4, 8, 6, 25, 18, 6, 1, 14, 10, 12 , 43, 37, 9, 13, 13, 19, 12, 1, 5, 2, 3
Іншими словами, починаючи з шостого символу, числовий рядок для шифртексту ідентичний початку рядка для відкритого тексту, перші п’ять членів рядка повторюють останні п’ять членів рядка. Побудувавши діаграму, побачимо це в більш наглядній формі:
Рис. 1. Діаграма розподілу частот відкритого і шифрованого текстів. де  – відкритий текст;  – шифртекст.
|
Причому порівнювати можна як окремі елементи (О – У (37)), так і групи символів (И, І – Л, М).
Перейдемо до аналізу шифру Цезаря тільки на основі шифртексту. Для цього ми повинні:
− побудувати діаграми розподілу частот для відкритого і шифрованого текстів у процентному відношенні, оскільки довжина відкритого і шифрованого текстів може відрізнятися;
− розташувати частоти у порядку зростання;
− знайти можливі значення ключа як різницю між відповідними значеннями частот.
Приведемо приклад:
Таблиця 3 – Ранжовані частоти використання букв української мови
| О
| 0,0942
| р
| 0,0448
| я
| 0,0248
| ж
| 0,0093
|
| А
| 0,0807
| с
| 0,0424
| з
| 0,0232
| ю
| 0,0093
|
| Н
| 0,0681
| л
| 0,0369
| б
| 0,0177
| ц
| 0,0083
|
| И
| 0,0626
| к
| 0,0354
| ь
| 0,0177
| ш
| 0,0076
|
| І
| 0,0575
| д
| 0,0338
| г
| 0,0155
| ї
| 0,0065
|
| В
| 0,0535
| у
| 0,0336
| ч
| 0,0141
| є
| 0,0061
|
| Т
| 0,0535
| м
| 0,0303
| й
| 0,0138
| щ
| 0,0056
|
| Е
| 0,0495
| п
| 0,0290
| х
| 0,0119
| ф
| 0,0028
|
Рисунок 2. Гістограма частот використання букв алфавіту української мови
Завдання лабораторної роботи.
1. Проаналізувати текст згідно варіанту за наступним алгоритмом.
Шифртекст:
СТУЙЛТЕУИТІКУЦТУЖТЛЬФУТДЧВЦШЯЕЦТУНСЕЧІСЕЧЛПЛЦЧХУЗУЖУТУТІЖЛКТЕЯЕЇЧВЦДЕРІСУЙІЄШЧЛИЕТУМТЧШНЧЛЖТІЖЛКТЕЯІТТДСТУЙЛТЛДПЦШПШФТУЦЧМФІЖТЛЬМХМКТЛЬУЄЇПЧМЖИУЖМРВТУНФХЛХУИЛДПЕХУКЗРДИЕЇЧВЦДДПУИТІЮМРІУЄЇПЧЛДПМЦПРЕИЕГЧВСТУЙЛТШТЕКЛЖЕГЧВЦДННІРІСІТЧЕСЛТЕФХЛПРЕИСУЙТЕЗУЖУХЛЧЛФХУСТУЙЛТШШЦМЬПТЛЗЖФІЖТМОЄМЄРМУЧІЮМСТУЙЛТШРМЧІХШПХЕНТЦВПУЗУЕРЩЕЖМЧШЕЄУФХУСТУЙЛТШЖЦМЬПУХІТМЖФІЖТУЗУХМЖТДТТД
Визначаємо потужність множин:
Шифртекст:
| А
| Б
| В
| Г
| Д
| Е
| Є
| Ж
| З
| И
| І
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Ї
| Й
| К
| Л
| М
| Н
| О
| П
| Р
| С
| Т
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| У
| Ф
| Х
| Ц
| Ч
| Ш
| Щ
| Ь
| Ю
| Я
| Разом
|
|
|
|
|
|
|
|
|
|
|
|
|
2. Сортуємо за потужністю входження літер в шифротекст, будуємо діаграму (необов’язково, але наглядно).
| Рис. 3. Діаграма розподілу літер шифротексту.
|
Визначаємо ключ (дана діаграма для всіх варіантів!!!):
Рис. 4. Діаграма розподілу літер тексту лабораторної роботи 1.
3. Повинна існувати взаємно однозначна відповідність між літерами із найчастішим входженням. Для цього потрібно врахувати номер відповідної літери в алфавіті.
| А
| Б
| В
| Г
| Д
| Е
| Є
| Ж
| З
| И
| І
| Ї
| Й
| К
| Л
| М
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Н
| О
| П
| Р
| С
| Т
| У
| Ф
| Х
| Ц
| Ч
| Ш
| Щ
| Ь
| Ю
| Я
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Між елементами діаграм немає постійної різниці. Це відбувається через те, що шифртекст має досить малу довжину (360 символів) і обчислення потужності входження символів було не таким точним. Тому вибираємо п’ять перших елементів і розраховуємо їх різницю у будь-яких сполученнях:
| текст
| Н
| О
|   А
| И
| Т
| або->
| А
| И
|
|
| №
|
|
|
|
|
|
|
|
|
|
| шифр
| т
| у
| л
| е
| ч
|
| е
| л
|
|
| №
|
|
|
|
|
|
|
|
|
|
| різниця
|
|
|
|
|
|
|
|
|
|
Враховуючи невелику кількість літер в тексті можливі різні комбінації.
4. Найчастіше значення, як ми бачимо, дорівнює 5, тому можна з досить великою імовірністю казати, що ключ дорівнює 5. До того ж різниця між найчастішими символами дорівнює також 5 але це може бути 32-5=27.
5. Порядок виконання лабораторної роботи
5.1. Вивчити відомості з криптоаналізу.
5.2. Усі тексти зашифровані шифром Цезаря ключем, не перевищуючим 32. Алфавіт для шифрування:
5.3. АБВГДЕЄЖЗИІЇЙКЛМНОПРСТУФХЦЧШЩЬЮЯ
5.4. Номер завдання добирається відповідно номеру студента у журналі.
5.5. Дешифрувати поданий текст (додаток 1), вказати відповідний йому відкритий текст, знайдений ключ. Студент повинен навести таблицю потужності входження літер відкритого і шифрованого текстів.
5.6. Скласти звіт, у якому вказати всі результати виконання лабораторної роботи і відповідний дешифрований текст.
6. Приклад виконання завдання
