Криптографія та криптоаналіз: вікова проблема людства, Криптографія, Security & Hack, статті

Олександр Алексєєв

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

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

Проблема ця далеко не нова, вона хвилює людей вже кілька тисячоліть.

За свідченням Геродота, уже в V столітті до нашої ери використовувалося перетворення інформації методом кодування.

Одним з найперших шифрувальних пристосувань була скитала (за іншими джерелами – сцітала), яка застосовувалася в V столітті до н.е. під час війни Спарти проти Афін. Скитала – це циліндр, на який, виток до витка, намотувалася вузька папірусних стрічка (без пробілів і нахлестов). Потім на цій стрічці уздовж осі циліндра (стовпцями) записувався необхідний для передачі текст. Стрічка змотувалася з циліндра і відправлялася одержувачу. Отримавши таке повідомлення, одержувач намотував стрічку на циліндр такого ж діаметру, як і діаметр скіталу відправника. В результаті можна було прочитати зашифроване повідомлення.

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

Коди з’явилися в далекій давнині у вигляді криптограми (по-грецьки – тайнопис). Часом священні іудейські тексти шифрувалися методом заміни. Замість першої літери алфавіту писалася остання буква, замість другий – передостання і так далі. Цей древній метод шифрування називався атбаш. Відомо, що шифрувалася переписка Юлія Цезаря (100 – 44 рр.. До н. Е..) З Цицероном (106 – 43 рр. до н. Е..).

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

У Стародавній Греції (II ст. До н.е.) був відомий шифр, званий “квадрат Полібія”. Шифрувальна таблиця представляла собою квадрат з п’ятьма стовпцями і п’ятьма рядками, які нумерувалися цифрами від 1 до 5. У кожну клітку такого квадрата записувалася одна буква. У результаті кожній букві відповідала пара чисел, і шифрування зводилося до заміни букви парою чисел.

Ідею квадрата Полібія проілюструємо таблицею з російськими буквами. Число букв в російській алфавіті відрізняється від числа букв у грецькому алфавіті, тому й розмір таблиці обраний іншим (не квадрат 5×5, а прямокутник 8×4).

1 2 3 4 5 6 7 8
1 А Б В Г Д Е Ж З
2 І Й До Л М Н Щ П
3 Р З Т У Ф Х Ц Ч
4 Ш Щ Ред И Ь Е Ю Я

Зашифруємо фразу: Криптографія:

23 31 21 28 33 27 14 31 11 35 21 48

З прикладу видно, що в шифрограмі першим вказують номер рядка, а другим – номер стовпця.

Терміни

Щоб ясніше уявляти собі область знань, що займається шифруванням / дешифруванням, розглянемо докладніше термінологію.

В даний час проблемами захисту інформації займається криптология (Kryрtos – таємний, logos – наука). Криптологія поділяється на два напрямки – криптографію і криптоаналіз. Цілі цих двох напрямків криптології прямо протилежні.

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

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

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

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

Шифрування – Перетворення інформації, в результаті якого вихідний текст, який носить також назву відкритого тексту, замінюється закритим (шифрованим) текстом, тобто шифрограммой.

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

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

Шифри

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

За характером використання ключа відомі алгоритми шифрування можна розділити на два типи: симетричні (З одним ключем, по-іншому – з секретним ключем) і несиметричні (З двома ключами або з відкритим ключем). Несиметричні алгоритми шифрування і дешифрування часом називають асиметричними.

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

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

При оцінці ефективності шифру зазвичай керуються правилом голландця Огюста Керкхоффом (1835 – 1903 р.р.), згідно з яким стійкість шифру визначається тільки секретністю ключа, тобто криптоаналітика відомі всі деталі процесу (алгоритму) шифрування і дешифрування, але невідомо, який ключ використаний для шифрування даного тексту.

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

Алгоритми шифрування з відкритим ключем використовують так звані необоротні або односторонні функції. Ці функції мають наступну властивість: при заданому значенні аргументу x відносно просто обчислити значення функції f (x), проте, якщо відомо значення функції y = f (x), то немає простого шляху для обчислення значення аргументу x.

Всі використовувані в даний час криптосистеми з відкритим ключем спираються на один з наступних типів необоротних перетворень.

  1. Розкладання великих чисел на прості множники (алгоритм RSA, автори – Райвест, Шамір і Адлеман – Rivest, Shamir, Adleman).
  2. Обчислення логарифма або зведення в ступінь (алгоритм DH, автори – Диффи і Хелман)
  3. Обчислення коренів алгебраїчних рівнянь.

Розглянемо простий приклад необоротних функцій. Легко в розумі знайти твір двох простих чисел 11 і 13. Але спробуйте швидко в розумі знайти два простих числа, твір яких дорівнює 437. Такі ж труднощі виникають і при використанні обчислювальної техніки для відшукання двох простих співмножників для дуже великого числа: знайти співмножники можна, але потрібно багато часу.

Таким чином, в системі кодування, заснованої на розкладанні на множники, використовуються два різних ключі: один для шифрування повідомлення, а другий – відмінний від першого, але пов’язаний з ним, – для дешифрування. Ключ шифрування заснований на творі двох величезних простих чисел, а ключ дешифрування – на самих простих числах.

Термін “необоротні” функції невдалий. Правильніше було б їх назвати “швидко (або просто) необоротні” функції. Однак цей термін усталений, і з неточністю доводиться миритися.

У сорокових роках американський інженер і математик Клод Шеннон запропонував розробляти шифр таким чином, щоб його розкриття було еквівалентно рішенню складної математичної задачі, що вимагає виконання таких обчислень, обсяг яких перевершував би можливості сучасних ЕОМ.

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

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

У симетричних алгоритмах використовують більш короткі ключі, тобто шифрування і дешифрування відбуваються швидше. Але в таких системах розподіл (розсилання) ключів є складною процедурою через необхідність тримати в таємниці інформацію про секретний ключі. Використання кур’єрів для розсилки ключів – дорога, складна і повільна процедура.

У США для передачі секретних повідомлень найбільше поширення отримав стандарт DES (Data Encryption Standard). “Потрійний DES” передбачає для підвищення стійкості повідомлення триразове шифрування даних з різними ключами. Стандарт шифрування даних DES був розроблений фірмою IBM на початку 70-х років і спочатку називався Lucifer.

Складний алгоритм DES використовує ключ довжиною 56 біт і вимагає від криптоаналітика перебору 72 квадрильйонів (1015) можливих ключових комбінацій. Недоліком шифру DES є мала довжина ключа – 56 біт і повільна програмна реалізація (великий обсяг обчислень).

Свій розвиток DES отримав в ГОСТ 28147-89, який збільшив довжину ключа до 256 біт.

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

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

У шифрі заміни навпаки, позиції букв в шифровці залишаються тими ж, що й у відкритого тексту, але символи замінюються символами іншого алфавіту. Як приклад тут можна назвати шифр Цезаря. Метод заміни часто реалізується багатьма користувачами випадково при роботі на ЕОМ. Якщо через забудькуватість не перемкнути на клавіатурі регістр з латиниці на кирилицю, то замість букв російського алфавіту при введенні тексту будуть друкуватися букви латинського алфавіту. В результаті вихідне повідомлення буде “зашифровано” латинськими літерами.

В аддитивном методі букви алфавіту заміняються числами, до яких потім додаються числа секретної псевдовипадкової числової послідовності (гамми). Гамма генерується в залежності від наявного ключа. Зазвичай для шифрування використовується логічна операція “Що виключає АБО”. Для розшифрування та ж гамма накладається на зашифровані дані. Метод гамування широко використовується у військових системах.

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

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

Можна стверджувати, що протягом століть дешифруванню криптограм допомагає частотний аналіз появи окремих символів і їх поєднань. Вірогідність появи окремих букв в тексті сильно розрізняються. Для російської мови, наприклад, буква “о” з’являється в 45 разів частіше букви “ф” і в 30 разів частіше букви “е”. Аналізуючи досить довгий текст, зашифрований методом заміни, можна по частотах появи символів провести зворотну заміну і відновити початковий текст.

У таблиці наведені відносні частоти появи російських букв.

Буква Частота Буква Частота Буква Частота Буква Частота
про 0.09 0.038 з 0.016 ж 0.007
е, е 0.072 л 0.035 и 0.016 ш 0.006
а 0.062 до 0.028 б 0.014 ю 0.006
і 0.062 м 0.026 ь, ь 0.014 ц 0.004
н 0.053 д 0.025 г 0.013 щ 0.003
т 0.053 п 0.023 ч 0.012 е. 0.003
з 0.045 у 0.021 ї 0.01 ф 0.002
р 0.04 я 0.018 х 0.009

Відносна частота появи пробілу або знаку пунктуації в російській мові складає 0,174.

Наведені цифри означають наступне: серед 1000 букв тексту в середньому буде 174 пропусків і розділові знаки, 90 букв “о”, 72 літери “е” і т.д.

При проведенні криптоаналізу потрібно по невеликому відрізку тексту вирішити, що собою являє дешифрований текст: осмислене повідомлення або набір випадкових символів. Часто криптоаналитики розкривають шифри на ЕОМ методом перебору ключів. В процесі криптоаналізу доводиться перебирати мільярд ключів зі швидкістю тисяч ключів в секунду, на що йде близько 12 днів. Вручну виконати аналіз безлічі фрагментів дешифрировать текстів неможливо. Тому завдання виділення осмисленого тексту (тобто виявлення правильно дешифрировать тексту) вирішують за допомогою ЕОМ. В цьому випадку використовують теоретичні положення, розроблені в кінці XIX століття петербурзьким математиком Марковим А.А., так звані ланцюги Маркова.

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

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

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

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*