Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

Криптоаналіз (від др.-греч. κρυπτός - Прихований і аналіз) - наука про методи розшифровки зашифрованою інформацією без призначеного для такої розшифровки ключа.

Термін був введений американським криптографом Уїльямом Ф. Фрідманом в 1920. Неформально криптоаналіз називають також зломом шифру.

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

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

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


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

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

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

Хоча поняття криптоаналіз було введено порівняно недавно, деякі методи злому були винайдені десятки століть тому. Першим відомим писемною згадкою про криптоаналіз є " Манускрипт про дешифрування криптографічних повідомлень ", написаний арабським вченим Ал-Кінді ще в 9 столітті. У цій науковій праці міститься опис методу частотного аналізу.

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

В період XV-XVI століть у Європі створювалися й розвивалися поліалфавітние шифри заміни. Найбільш відомим є шифр французького дипломата Блеза де Віженер, в основу якого лягло використання послідовності декількох шифрів Цезаря з різними значеннями зсуву. Протягом трьох століть Шифр Віженер вважався повністю криптографічно стійким, поки в 1863 році Фрідріх Касіскі не запропонував свою методику злому цього шифру. Основна ідея методу Касіскі полягає в наступному: якщо у відкритому тексті між двома однаковими наборами символів знаходиться такий блок тексту, що його довжина кратна довжині ключового слова, то ці однакові набори символів відкритого тексту при шифруванні перейдуть в однакові відрізки шіфротекста. На практиці це означає те, що за наявності в шіфротекста однакових відрізків довжиною в три і більше символів, велика ймовірність того, що ці відрізки відповідають однаковим відрізкам відкритого тексту. Як застосовується метод Касіскі: в шіфротекста шукаються пари однакових відрізків довжини три або більше, потім обчислюється відстань між ними, тобто кількість символів, які поділяють стартові позиції парних відрізків. У результаті аналізу всіх пар однакових відрізків ми отримаємо сукупність відстаней d 1, d 2, d 3,... Очевидно, що довжина ключового слова буде дільником для кожного з відстаней і, отже, для їх найбільшого загального дільника.

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


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

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

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

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

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

  • У 1998 було виявлена ​​уразливість до атак на основі шіфротекста у блоковий шифр MADRYGA, запропонований ще в 1984, але не отримав широкого розповсюдження.
  • Ціла серія атак з боку наукового співтовариства, багато з яких були цілком практичними, буквально знищила блоковий шифр FEAL, запропонований як заміна DES в якості стандартного алгоритму шифрування, але також не отримав широкого розповсюдження
  • Також було встановлено, що за допомогою широко доступних обчислювальних засобів потокові шифри A5 / 1, A5 / 2, блоковий шифр CMEA, і стандарт шифрування DECT, використовувані для захисту мобільного і бездротового телефонного зв'язку, можуть бути зламані за лічені години чи хвилини, а часом і в режимі реального часу.
  • Атака методом грубої сили допомогла зламати деякі з прикладних систем захисту, наприклад, CSS - систему захисту цифрового медіаконтенту на DVD-носіях.

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


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

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

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

  1. Атака на основі шіфротекста
  2. Атака на основі відкритих текстів і відповідних шіфротекста
  3. Атака на основі підібраного відкритого тексту (можливість вибрати текст для шифрування)
  4. Атака на основі адаптивно підібраного відкритого тексту

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

  1. Атака на основі підібраного шіфротекста
  2. Атака на основі підібраного ключа
  3. Бандитський криптоаналіз

2.1. Основні методи криптоаналізу

2.1.1. Атаки на основі шіфротекста

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

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


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

Нехай у розпорядженні криптоаналітика є не тільки шіфротекста, але і відповідні їм відкриті тексти.

Тоді існують два варіанти постановки задачі:

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

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

У разі злому листування можна зробити припущення, що лист має структуру типу:

  • "Привітання"
  • "Основний текст"
  • "Заключна форма ввічливості"
  • "Підпис"

Отже, атака може бути організована шляхом підбору різних видів "Привітання" (наприклад, "Привіт!", "Добрий день" і т. д.) і / або "Заключною форми ввічливості" (таких як "З повагою", "Щиро Ваш "і т. п.). Легко помітити, що дана атака сильніша атаки на основі одного лише шіфротекста.


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

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

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

Отримати вхідні дані для такого виду атаки можна, наприклад, таким чином:

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

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


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

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


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

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

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

Стисло сформулювати цю задачу можна таким чином:

Дано: З 1, P 1 = D k1), С 2, P 2 = D k2), З 3, P 3 = D k3),..., С n, P n = D kn),

де С n - n-ий наявний шіфротекст, P n - відповідний З n відкритий текст, а D k - функція дешифрування за допомогою ключа k.

Знайти: використовуваний ключ шифрування k.

Цікавим може бути той факт, що атака на основі підібраного шіфротекста також може носити назву "Атаки в обідній час" (lunchtime attack) або "Нічний атаки" (midnight attack). Скажімо, в назві "Атаки в обідній час" відображається той факт, що легітимний користувач може залишить свій комп'ютер з функцією дешифрування без нагляду на час обіду, а криптоаналітик може цим скористатися.


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

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


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

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

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


3. Різні види атак

Література


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Лінійний криптоаналіз
Диференціальний криптоаналіз
© Усі права захищені
написати до нас