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

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

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

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

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

За свідченням Геродота, вже у 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>

*

*