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

Криптоаналіз (від грец. Κρυπτός - прихований і аналіз) - наука про методи отримання вихідного значення зашифрованої інформації, не маючи доступу до секретної інформації (ключа), необхідної для цього. У більшості випадків під цим мається на увазі знаходження ключа. У нетехнічних термінах, криптоаналіз є злом шифру (коду). Термін був введений американським криптографом Вільямом Ф. Фрідманом в 1920 році. Під терміном «криптоаналіз» також розуміється спроба знайти вразливість в криптографічному алгоритмі або протоколі. Хоча основна мета залишилася незмінною з часом, методи криптоаналізу зазнали значних змін, еволюціонувавши від використання лише ручки і паперу до широкого застосування обчислювальних потужностей спеціалізованих криптоаналітичних комп'ютерів. Якщо раніше криптоаналітики були здебільшого лінгвісти, то в наш час це «чисті» математики. Результати криптоаналізу конкретного шифру називають криптографічного атакою на цей шифр. Успішну криптографічну атаку, що дискредитує атакований шифр, називають зломом або розкриттям.

Історія криптоаналізу

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

Класичний криптоаналіз

Хоча поняття криптоаналіз було введено порівняно недавно, деякі методи злому були винайдені десятки століть тому. Першою відомою писемною згадкою про криптоаналіз є «Манускрипт про дешифрування криптографічних повідомлень », написаний арабським ученим Ал-Кінді ще в 9 столітті. У цій науковій праці міститься опис методу частотного аналізу. Частотний аналіз - основний інструмент для злому більшості класичних шифрів перестановки або заміни. Даний метод грунтується на припущенні про існування нетривіального статистичного розподілу символів, а також їх послідовностей одночасно і у відкритому тексті, і в шифротексті. Причому даний розподіл буде зберігатися з точністю до заміни символів як в процесі шифрування, так і в процесі дешифрування. Варто відзначити, що за умови досить великої довжини шифрованого повідомлення моноалфавітні шифри легко піддаються частотного аналізу: якщо частота появи букви в мові та частота появи деякого присутнього в шифротексті символу приблизно рівні, то в цьому випадку з великою часткою ймовірності можна припустити, що даний символ і буде цієї самої буквою. Найпростішим прикладом частотного аналізу може служити банальний підрахунок кількості кожного з символів, що зустрічаються, потім слідують процедури розподілу отриманого числа символів на кількість всіх символів у тексті і множення результату на сто, щоб представити остаточну відповідь у відсотках. Далі отримані процентні значення порівнюються з таблицею імовірнісного розподілу букв для передбачуваної мови оригіналу. У період XV-XVI століть у Європі створювалися і розвивалися поліалфавітні шифри заміни. Найбільш відомим є шифр французького дипломата Блеза де Віженера, в основу якого лягло використання послідовності декількох шифрів Цезаря з різними значеннями зсуву. Протягом трьох століть Шифр ​​Віженера вважався повністю криптографічно стійким, поки в 1863 році Фрідріх Касіскі не запропонував свою методику злому цього шифру. Основна ідея методу Касіскі полягає в наступному: якщо у відкритому тексті між двома однаковими наборами символів знаходиться такий блок тексту, що його довжина кратна довжині ключового слова, то ці однакові набори символів відкритого тексту при шифруванні перейдуть в однакові відрізки шифротексту. На практиці це означає те, що за наявності в шифротексті однакових відрізків довжиною у три і більше символи, велика ймовірність того, що ці відрізки відповідають однаковим відрізкам відкритого тексту. Як застосовується метод Касіскі: у шифротекст шукаються пари однакових відрізків довжини три або більше, потім обчислюється відстань між ними, тобто кількість символів, які поділяють стартові позиції парних відрізків. У результаті аналізу всіх пар однакових відрізків ми отримаємо сукупність відстаней d1, d2, d3, ... Очевидно, що довжина ключового слова буде дільником для кожного з відстаней і, отже, для їх найбільшого загального дільника. Наступний етап розвитку криптоаналізу пов'язаний з винаходом роторних шифрувальних машин таких як, наприклад, винайдена Артуром Шербіусом Енігма. Метою таких пристроїв було мінімізувати кількість повторюваних відрізків шифротексту, статистика появи яких використовувалася при зломі шифру Віженера. Польським криптоналітикам вдалося побудувати прототип дешифровальной машини для версії Енігми, використовуваної Нацистською Німеччиною. Машина отримала назву "Бомба" за те, що при роботі видавала звуки схожі на цокання годинника. Пізніше вона була дороблена і взята на озброєння англійським криптоаналітикам.

Сучасний криптоаналіз

У міру розвитку нових методів шифрування математика ставала все більш і більш значущою. Так, наприклад, при частотному аналізі криптоаналітик повинен володіти знаннями і в лінгвістиці, і в статистиці. У той час як теоретичні роботи по криптоаналізу Енігми виконувалися переважно математиками, наприклад, Алан Матісон Тьюрінгом. Проте завдяки все тієї ж математики криптографія досягла такого розвитку, що кількість необхідних для злому елементарних математичних операцій стала досягати астрономічних значень. Сучасна криптографія стала набагато більш стійкою до криптоаналізу, ніж колись використовувані, застарілі методики, для злому яких було достатньо ручки та аркуша паперу. Може здатися, що чистий теоритический криптоаналіз не здатний більш ефективно зламувати сучасні шифри. Тим не менш історик Девід Кан у своїй замітці до 50-ої річниці Агентства національної безпеки пише: "У наші дні сотні фірм пропонують безліч різних криптосистем, які неможливо зламати жодним з відомих методів криптоаналізу. Дійсно, такі системи стійкі навіть до атаки по підібраному відкритому тексту, тобто порівняння відкритого тексту і відповідного йому шифротексту не дозволяє дізнатися ключ шифрування , який би дозволив дешифрувати інші повідомлення. Таким чином, в деякому сенсі криптоаналіз мертвий. Але це ще не кінець. Криптоаналіз може бути і мертвий, але, висловлюючись метафорично, з кішки можна зняти шкірку декількома способами. " Далі у своїх замітці описує збільшене значення перехоплення даних, підкладки жучків, атак по сторонніх каналах і квантових комп'ютерів як методик, що йдуть на зміну традиційним методам криптоаналізу. У 2010 колишній технічний директор Управління національної безпеки Брайан Сноу зазначив, що комерційна криптографія вже майже досягла рівня розвитку технологій, що використовуються розвідувальними службами, і тепер вони разом «дуже повільно просуваються у вже повністю дослідженій області». Тим не менш, криптоаналіз поки ще рано списувати з рахунків. По-перше, невідомо, наскільки ефективні застосовувані спецслужбами методи криптоаналізу, а по-друге за роки становлення та вдосконалення сучасної комп'ютерної криптографії було проведено багато серйозних атак і на теоретичні, і на практичні криптографічні примітиви:

- В 1998 було виявлена ​​уразливість до атак на основі шифротексту у блоковому шифрі MADRYGA, запропонованому ще в 1984, але не отримав широкого розповсюдження.

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

- Також було встановлено, що за допомогою широко доступних обчислювальних засобів потокові шифри A5 / 1, A5 / 2, блочний шифр CMEA, і стандарт шифрування DECT, використовувані для захисту мобільного і бездротового телефонного зв'язку, можуть бути зламано за лічені години або хвилини, а часом і в режимі реального часу.

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

Методи криптоаналізу

Брюс Шнаєр виділяє 4 основних і 3 додаткових методи криптоаналізу, припускаючи знання криптоаналітиків алгоритму шифру: Основні методи криптоаналізу:

- Атака на основі шіфротекста

- Атака на основі відкритих текстів та відповідних шифротекст

- Атака на основі підібраного відкритого тексту (можливість вибрати текст для шифрування)

- Атака на основі адаптивно підібраного відкритого тексту

Додаткові методи криптоаналізу:

- Атака на основі підібраного шіфротекста

- Атака на основі підібраного ключа

- Бандитський криптоаналіз

Література

- David Kahn, Remarks on the 50th Anniversary of the National Security Agency, November 1, 2002.

- Шнайер Б. Криптоанализ // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 19—22. — 816 с. — 3000 экз. — ISBN 5-89392-055-4

- Пилиди В. С. Криптография. Вводные главы. — Ростов-на-Дону: ЮФУ, 2009. — 110 с.

- Alex Biryukov and Eyal Kushilevitz.: From Differential Cryptanalysis to Ciphertext-Only Attacks