Знаймо

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

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

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

Диференціальний криптоаналіз



План:


Введення

Диференціальний криптоаналіз - метод криптоаналізу симетричних блокових шифрів (та інших криптографічних примітивів, зокрема, хеш-функцій). Запропоновано в 1990 ізраїльськими фахівцями Елі Біхамом і Аді Шамір.

Диференціальний криптоаналіз заснований на вивченні перетворення різниць між шіфруемого значеннями на різних раундах шифрування. В якості різниці, як правило, застосовується операція побітового підсумовування за модулем 2, хоча існують атаки і з обчисленням різниці по модулю 2 ^ {32} . Є статистичною атакою, в результаті роботи пропонує список найбільш ймовірних ключів шифрування блокового симетричного шифру.

Диференціальний криптоаналіз застосуємо для злому DES, FEAL і деякі інших шифрів, як правило, розроблених раніше початку 90-х. Кількість раундів сучасних шифрів ( AES, Camellia та ін) розраховувалося з урахуванням забезпечення стійкості в тому числі і до диференціального криптоаналізу.


1. Диференціальний криптоаналіз DES

У 1990 році Елі Біхам і Аді Шамір використовуючи метод диференціального криптоаналізу знайшли спосіб розтину DES, більш ефективний, ніж розтин методом грубої сили. Працюючи з парами шіфротекста, відкриті тексти яких мають певні відмінності [1], вчені аналізували еволюцію цих відмінностей при проходженні відкритих текстів через етапи DES.

1.1. Схема злому

Рис.1 Схема злому

На схемі представлено проходження одного з етапів DES. Нехай X і X '- пара входів, що розрізняються на ΔX. Відповідні їм виходи відомі і дорівнюють Y і Y ', різниця між ними - ΔY. Також відомі перестановка з розширенням і P-блок, тому відомі ΔA і ΔC. B і B 'невідомі, але ми знаємо, що їх різниця дорівнює ΔA, тому відмінності XOR K i c A і A 'нейтралізуються. Розтин ключа засноване на тому факті, що для заданого ΔA не всі значення ΔC рівноймовірно, а комбінація ΔA і ΔC дозволяє припустити значення A XOR K i і A 'XOR K i. При відомих A і A 'це дає нам інформацію про K i.

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

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


1.2. Ефективність злому

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

Біхам і Шамір запропонували замість 15-етапної характеристики 16-етапного DES використовувати 13-етапну характеристику і за допомогою ряду прийомів отримувати дані для останніх етапів. Крім того, вони використовували спеціальні оптимізації для отримання вірогідних 56-бітових ключів, що дозволяло перевіряти їх негайно. Це вирішувало проблему з пороговим характером злому і усувало необхідність в зберіганні лічильників.

Найкращий розроблений алгоритм диференційного розтину повного 16-етапного DES вимагає 2 47 обраних відкритих текстів. При цьому временнная складність становить 2 37 операцій DES.

Диференціальний криптоаналіз застосуємо для злому алгоритмів з постійними S-блоками, таких як DES. При цьому його ефективність сильно залежить від структури S-блоків. Виявилося, що S-блоки DES оптимізовані проти диференціального криптоаналізу. Передбачається, що творці DES знали про цей метод. За словами Дона Копперсміта з IBM :

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

1.3. Підвищення стійкості до злому

Стійкість DES до диференціального криптоаналізу може бути підвищена шляхом збільшення кількості етапів. Диференціальний криптоаналіз для DES з 17 або 18 етапами зажадає стільки ж часу, скільки і повний перебір, а при 19 або більше етапах диференціальний криптоаналіз неможливий (тому що для нього буде потрібно більш ніж 2 64 відкритих текстів, що неможливо при довжині блоку 64 біта ).

1.4. Недоліки методу

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

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


1.5. Порівняння з іншими методами

См. Відомі атаки на DES

Примітки

  1. Для алгоритму DES термін "відмінність" визначається як результат застосування операції XOR

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

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

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