Лабораторна робота №5 на тему Симетричні системи шифрування

Лабораторна робота №5
Симетричні системи шифрування

Мета: Ознайомитися із методами кодування та криптографічного захисту інформації та створити алгоритми реалізації деяких таких методів.

Необхідне програмне забезпечення

Компілятор мови програмування (C, Basic, Pascal або ін.)

Теоретичні відомості

1. Основні поняття і терміни

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

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

Шифрування (encryption) - процес зашифровування інформації, тобто застосування криптографічного перетворення до вхідних даних (відкритого тексту).

Дешифрування (deciphering) і розшифровування (decryption) - відповідно методи одержання із зашифрованого тексту інформації без знання криптографічного ключа і зі знанням його.

Шифр і шифросистема (cipher, cypher, ciphercode) - найчастіше вихід криптосистеми і сама симетрична криптосистема відповідно. У залежності від контексту шифр може означати зашифроване повідомлення або саму криптографічну систему перетворення інформації.

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

Криптографічна стійкість, криптостійкість (cryptographic strength) - стійкість шифросистеми проти всіх відомих видів криптоаналізу.

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

Раунд чи цикл шифрування (round) - один комплексний крок алгоритму, в процесі якого перетворюються дані.

Підключ шифрування (round key, subkey) - криптографічний ключ, що обчислюється і використовуваний тільки на етапі шифрування з основного ключа шифрування.

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

Гама-послідовність чи просто гама (gamma sequence, gamma) - послідовність псевдовипадкових елементів, що генеруються за певним законом чи  алгоритмом.

Гамування (gamma xoring) - процес "накладання" гама-послідовності на відкриті дані, найчастіше з допомогою логічної операції XOR (виключне АБО).

Автентичність даних і систем (authenticity of information) - для даних автентичність можна визначити як факт підтвердження дійсності інформації, що міститься в цих даних, а для систем - здатність забезпечувати процедуру відповідної перевірки - аутентифікації даних.

Аутентифікація (authentication) - процедура перевірки дійсності даних, пересвідчення чи доведення факту створення та відправлення легітимними (законними) учасниками процесу обміну інформації.

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

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

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

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

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

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

Основні методи кpиптоаналізу:

Brute force ("грубою силою")- перебірвсіхможливихваріантів (ключів).

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

Known plaintext (з відомим відкритим текстом)- ключ обчислюється за відомим фрагментом відкритого тексту та відповідного йому зашифрованого.

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

Асиметрична криптосистема чи система з відкритим (публічним) ключем - система із двома ключами. Генеруються два ключі - секретний і відкритий. Відкритий ключ передається відкритими каналами зв’язку одному або декільком партнерам, з допомогою нього шифруються повідомлення і передаються володарю секретного ключа. Розшифрувати повідомлення можна тільки секретним ключем. Знайти секретний ключ  за відомим  публічним - обчислювально складна задача, яку неможливо розв’язати (поки що) за допомогою комп’ютерних систем. Для генерації ключів і шифрування  використовуються обчислювально складні  алгоритми, наприклад, розклад астрономічно великих чисел на прості множники, цілочисельне логарифмування, еліптичні функції. Алгоритми, які грунтувались на задачі вкладання ранця, виявились ненадійними і спростовані математично. Недоліком асиметричних криптосистем є їх нестроге теоретичне обгрунтування. Однак є практичні області, де без них обійтись неможливо - це системи електронного підпису, електронного голосування, "електронні" гроші.

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

2. Перестановочні шифри

2.1. Простий стовпчиковий перестановочний шифр

У даному виді шифру текст пишеться на горизонтально розграфленому аркуші паперу фіксованої ширини, а шифротекст прочитується по вертикалі. Дешифрування полягає в записі шифротексту вертикально на аркуші розграфленого паперу фіксованої ширини і потім зчитуванні відкритого тексту горизонтально. Відкритий текст: КИЇВСЬКИЙ СЛАВІСТИЧНИЙ УНІВЕРСИТЕТ

Зашифрований текст: ККАЧНИК ИИВНІТК ЇЙІИВЕА В_СЙЕТЧ  ССТ_Р_Н ЬЛИУС_И.

2.2. Перестановочний шифр із ключовим словом

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

Відкритий текст: Менеджмент організацій  Ключ: Шифр

Криптограма: Ежтгзйееонц_нм_аа_мднріі.

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

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

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

3. Підстановочні шифри

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

3.1. Шифр Цезаря

Юлій Цезар оповідає про відсилання зашифрованого повідомлення Цицерону. Використана при цьому система підстановок була одноалфавітною, але не являлася системою Цезаря: латинські літери замінювалися на грецькі способом, який не був ясний із розповіді Цезаря. Інформація про те, що Цезар дійсно використовував систему Цезаря, прийшла від Светонія.

У шифрі Цезаря кожна літера заміщається на літеру, що знаходиться k символами правіше по модулю рівній кількості літер в алфавіті. (Згідно Светонію в Цезаря k=3 n=50)

C_k(j)=(j+k)(mod n),

де n - кількість літер в алфавіті.

Очевидно, що зворотною підстановкою є

C_k^-1(j)=С_n-k=(j+n-k)(mod n)

3.2. Аффінна криптосистема

Узагальненням системи Цезаря є аффінна криптосистема. Вона визначається двом числами а і b, де 0<=a,b<=n-1. n - як і раніше, є міцністю алфавіту. Числа а і n повинні бути взаємно прості.

Відповідними замінами є:

A_a,b(j)=(a*j+b)(mod n)

A^-1_a,b(j)=(j-b)*a^-1(mod n)

Зворотну заміну також можна отримати, просто помінявши місцями рядки в таблиці замін.

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

3.3. Шифр Полібія

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

Кожна літера може бути представлена парою літер, які вказують на рядок і стовпець, в яких розташована дана літера. Так представлення літер В, Г, П, У будуть АВ, АГ, ГА ГД відповідно, а повідомлення МЕНЕДЖМЕНТ ОРГАНІЗАЦІЙ зашифрується як

ВГАЕВДАЕАДББВГАЕВДГГЕЕВЕГБАГААВДБДБВААДББДВА

4. Багатоалфавітні системи

Багатоалфавітні (поліалфавітні) підстановочні шифри були винайдені Ліном Баттістою (Lean Battista) в 1568 році. Основна ідея багатоалфавітних систем полягає в тому, що впродовж всього тексту одна і та ж літера може бути зашифрована по-різному. Тобто заміни для літери вибираються із багатьох алфавітів залежно від положення в тексті. Це є хорошим захистом від простого підрахунку частот, тому що не існує єдиного маскування для кожної літери в криптотексті. У цих шифрах використовуються множинні однобуквені ключі, кожний з яких використовується для шифрування одного символу відкритого тексту. Першим ключем шифрується перший символ відкритого тексту, другим - другий, і т.д. Після використання всіх ключів вони повторюються циклічно.

4.1. XOR-алгоритм

Найпростішим в реалізації різновидом поліалфавітного шифру є XOR-алгоритм. Операція XOR - eXclusive OR, виключаюче АБО (додавання за модулем 2) - результат логічної операції з двома двійковими розрядами дорівнює 1, якщо розряди різні, і дорівнює 0, якщо розряди збігаються (таблиця 4.1).

Таблиця 4.1. Таблиця істиності функції XOR

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

4.2. Шифр Віженера

Однією із старих і найбільш відомих багатоалфавітних криптосистем є система Віженера, названа на честь французького криптографа Блейза Віженера (Vigenere), відома також як шифр Трітеміуса. Цей метод був вперше опублікований в 1586 році. У даному шифрі ключ задається набором з d літер.

Такі набори підписуються із повторенням під повідомленням, а, потім, отриману послідовність складають із відкритим текстом по модулю n (потужність алфавіту). Тобто виходить наступна формула:

Vig_d(m_i)=(m_i+k_i mod d)(mod n)

Літеру шифротексту можна знаходити також із таблиці (див. додаток А), як перетин стовпця, визначуваного літерою відкритого тексту, і рядка, визначуваною літерою ключа.

В окремому випадку, при d=1, отримуємо шифр Цезаря.

4.3. Шифр Бофорта

Іншим різновидом шифру Віженера є шифр Бофорта (Beaufort, в деякій літературі читається як Бьюфорт), названий на честь адмірала сера Френсіса Бофорта - творця шкали для визначення швидкості вітру.

Його рядками є рядки квадрата Віженера, записані в зворотному порядку, а перший і останній рядки поміняні місцями (див. додаток Б).

Формулою перетворення буде:

Bof_d(m_i)=(k_{i mod d}-m_i)(mod n)

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

Vig_d^-1(m_i)=(m_i-k_{i mod d})(mod n)

Bof_d^-1(m_i)=Bof_d(m_i)=(k_i-m_{i mod d})(mod n)

Повторне застосування двох або більшої кількості шифрів Віженера називатиметься складеним шифром Віженера. Він визначається рівнянням:

Vig^*(m_i)=(m_i + k_{i mod dk} + l_{i mod dl} +...+ s_{i mod ds})´(mod n)

де k_i + l_i + ... + s_i , взагалі кажучи, мають різні періоди dk, dl, ..., ds відповідно. Період їх суми k_i + l_i + ... + s_i буде найменшим спільним кратним окремих періодів.

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

4.4. Шифр Віженера із перемішаним один раз алфавітом

Такий шифр представляє собою просту підстановку із подальшим застосуванням шифру Віженера:

Vig^(m_i)=f(m_i) + k_{i mod d},

Vig^^-1(m_i)=f ^-1(m_i - k_{i mod d}).

4.5. Шифр з автоключем

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

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

5. Блочні шифри

Блочний шифр це послідовність (із можливим повторенням і чергуванням) основних методів перетворення, які застосовуються до блоку (частини) шифрованого тексту. Блочні шифри на практиці зустрічаються частіше, ніж "чисті" перетворення того або іншого класу через їх вищу криптостійкості. Російський (ГОСТ 28147-89) і американський (Rijndael, DES) стандарти шифрування засновані саме на цьому класі шифрів.

5.1. Режим електронної шифрувальної книги

Режим електронної шифрувальної книги (electronic codebook) - це найбільш очевидний спосіб використання блочного шифру: блок відкритого тексту замінюється блоком шифротексту. Оскільки один і той же блок відкритого тексту замінюється одним і тим же блоком шифротексту, то теоретично можливо створити шифрувальну книгу блоків відкритого тексту і відповідних криптотекстів. Однак, якщо розмір блоку 64 біта, то кодова книга складатиметься з 264 записів, що занадто багато для попереднього обчислення і зберігання (для кожного ключа знадобиться окрема шифрувальна книга). Це найлегший режим роботи. Всі блоки відкритого тексту шифруються незалежно і, отже, немає необхідності в послідовному шифруванні, що важливо для баз даних із довільним доступом. Крім того, обробка може бути розпаралелена, на декілька шифрувальних процесорів, незалежно оброблювальних різні блоки. Проблемою даного режиму є те, що якщо у криптоаналітика є відкритий текст і шифротекст для декількох повідомлень, то він може розпочати складати шифрувальну книгу, не знаючи ключа. У більшості реальних ситуацій фрагменти повідомлень можуть повторюватися. Особливо вразливі початок і кінець повідомлення, де знаходиться інформація про відправника, одержувача, дату, формат файлу, і т.п. Позитивними рисами є можливість шифрувати декілька повідомлень одним ключем без зниження безпеці і нерозповсюдженні помилок - при пошкодженні невірно дешифрується лише зіпсований блок.

5.2. Режим зчеплення блоків шифру

У режимі зчеплення блоків шифру перед шифруванням над відкритим текстом і попереднім блоком шифротексту виконується операція побітового складання (XOR). Коли блок відкритого тексту зашифрований, отриманий шифротекст запам'ятовується в регістрі зворотного зв'язку. Перш ніж буде зашифрований наступний блок відкритого тексту, він підлягає операції XOR разом з вмістом регістра зворотного зв'язку, і так далі. Таким чином, шифрування кожного блоку залежить від всіх попередніх.

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

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

Практичне завдання

1. Зашифрувати фразу за допомогою перестановочного шифру із ключовим словом (кількість літер від 4 до 8).

2. Реалізувати алгоритм шифрування даних за допомогою дошки Полібія.

3. Зашифрувати фразу із використанням модернізованого коду Цезаря (змінне число k).

4. Скласти алгоритм шифрування та дешифрування файлів за методом Віженера.

Примітки

У всіх завданнях використовується такий алфавіт (кількість n = 34): А Б В Г Д Е Є Ж З И І Ї Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ю Я – «Символ пробілу»

Варіанти даних для шифрування за варіантами можна отримати із наступної таблиці.

Контрольні запитання

1. Що вивчає криптографія?

2. Які існують основні типи криптографічних систем?

3. Як класифікуються методи кодування, в яких процес дешифрування є дзеркальним відображенням процесу шифрування?

4. Що таке криптоаналіз?

5. Який принцип лежить в основі перестановочних шифрів?

6. Яка математична закономірність покладена у реалізації методу XOR-шифрування?

7. У чому полягає метод шифрування Віженера?

8. Яка відмінність між шифром Віженера та шифром Бофорта?

9. Що собою являють блочні шифри?

10. Назвіть деякі приклади використання блочних шифрів?

Таблиця Віженера для українського алфавіту

З повагою ІЦ "KURSOVIKS"!