Актуальність проблеми захисту інформаційних систем

Розглянемо  другий текст. Значення на виході блоку можна отримати (користуємось таблицею залежностей виходів блоків замін від вхідних даних), якщо на вході у нас або . Таким чином ми отримали два лінійні рівняння: 
 

Розв’язавши їх, одержимо можливе значення другої четвірки бітів ключа:

  та .

     В третій блок заміни для кожного із пари текстів відповідно увійдуть комбінації бітів:

  та , після чого на виході буде отримано та . Очевидно, що

, а .

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

 , , , або

Таким чином ми отримали п’ять лінійних рівнянь: 
 
 
 
 

Розв’язавши їх, одержимо можливе значення останніх чотирьох бітів ключа:

,  , , ,

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

 , , , або

Таким чином ми отримали п’ять лінійних рівнянь: 
 
 
 
 

Розв’язавши їх, одержимо можливе значення останніх чотирьох бітів ключа:

,  , , , .

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

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

       4.3 Узагальнена схема диференціального криптоаналізу 

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

Рисунок 4.2. Узагальнена схема побудови блочного шифру. 

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

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

Визначення  Пара можливих значень вектору називається диференціалом го циклу.

Тоді  диференціальний криптоаналіз описується наступною моделлю:

Рисунок 4.3. Модель диференціального крипто аналізу для раундів. 

Підключ останнього циклу шифрування можна знайти, використовуючи наступний алгоритм:

1. Обираємо диференціал циклу, для якого імовірність велика
2. Випадково обираємо та підбираємо так, щоб . Нехай відомі та
3. Робимо припущення, що і знаючи та знаходимо
4. Повторюємо кроки 2 та 3 доти, доки один із підключів не почне з’являтись частіше

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

     Біхам та Шамір запропонували свій спосіб атаки. Замість використання 15-раундового диференціалу 16-раундового , вони використовують 13-раундовий диференціал та ряд прийомів для проходження останніх декількох раундів. Але більш детальна інформація не дійшла до публікації і залишається лише здогадуватись про те, як саме вони провели атаку диференціальним криптоаналізом. 

     4.4 Висновки 

     Стосовно  блочних шифрів, зокрема , диференціальний криптоаналіз внаслідок своєї вимогливості до ресурсів (як до об’єму використовуваної пам’яті, так і до кількості необхідних обчислень ) має поступатись лінійному та вважатися менш еф активним. В нашому випадку отримані результати є надзвичайно гарними. Знову ж для оцінки ефективності спів ставимо його з методом тотального перебору. Розглянемо найгірший випадок: шуканий ключ буде підібраний останнім. Як вже було сказано раніше зберігання всієї множини ключів у випадку атаки грубою силою вимагає бітів пам’яті. Диференціальний криптоаналіз  для спрощеного варіанту потребує (зв’язані пари відкритих текстів, кожна з яких має відповідний шифротекст) бітів для зберігання 10 пар. Це більше, ніж у випадку лінійного криптоаналізу, але все одно набагато менше, ніж при тотальному перебору. Складність методу лінійного криптоаналізу становить , атаки методом грубої сили – . Диференціальний криптоаналіз зміг відновити всі 12 бітів ключа і оскільки було застосовано 10 пар відкритих текстів (не обмежуючи загальності міркувань, часом аналізу однієї пари ми нехтуємо), то отримали наступну складність . Таким чином, для спрощеного диференціальний криптоаналіз виявився найефективнішим.