Атака з відомим відкритим текстом

Основна стаття: Атака на основі шифротексту

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

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

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

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

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

Основна стаття: Лінійний криптоаналіз

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

${\displaystyle x_{i1}+...+x_{ir}+y_{j1}+y_{js}=z_{k1}+...+z_{kt}}$ (1)

яка буде найкращою. Нехай ${\displaystyle p}$ — це ймовірність того, що (1) виконується, зрозуміло що нам треба щоб ${\displaystyle p}$${\displaystyle \thickapprox }$${\displaystyle 0.5}$, а також потрібно щоб величина${\displaystyle |p-0.5|}$ була максимальна. У випадку коли ця величина досить велика і криптоаналітику відомо досить багато пар відкритого і відповідного йому шифрованого тексту, то сума по модулю 2 біт ключа на відповідній позиції в правій частині рівності (1) дорівнює найбільш ймовірного значенням суми по модулю 2 відповідних біт в відкритому і зашифрованому текстах в лівій частині. У разі, коли ${\displaystyle p>0.5}$ сума в правій частині (1) дорівнює нулю, коли сума біт в лівій частині дорівнює нулю більш, ніж в половині пар зашифрованих текстів. Сума біт в правій частині дорівнює одиниці, якщо сума біт в лівій частині дорівнює одиниці більш ніж в половині випадків текстів. Якщо ${\displaystyle p<0.5}$ то навпаки: сума біт в правій частині дорівнює одиниці якщо в лівій частині сума біт дорівнює нулю більш ніж для половини текстів. І сума біт в правій частині дорівнює нулю якщо сума біт в лівій частині дорівнює одиниці більш ніж в половині випадків. Для знаходження кожного біта ключа, тепер треба вирішити систему лінійних рівнянь для відповідних відомих комбінацій цих біт. Це не становить складності так як складність даної системи виражається поліномом не більше ніж третього ступеня від довжини ключа. Кількість необхідних пар відкритий / шифрований текст, для розкриття шифру оцінюється формулою ${\displaystyle N=|p-0.5|2^{-2}}$. Для розкодування шифру DES таким методом виходить, що необхідно приблизно ${\displaystyle 2^{47}}$ пар відкритий / зашифрований блок.

Диференціальний метод криптоаналізу (ДКА) у 1990 році був запропонований Е. Біхамом та А. Шаміром. Диференціальний криптоаналіз — це спроба розкрити секретний ключ блокових шифрів, які засновані на повторному застосуванні криптографічно слабких операцій шифрування r раз. Під час криптоаналізу передбачається, що на кожному циклі шифрування використовується свій підключ шифрування. ДКА може використовувати як вибрані, так і відомі відкриті тексти. Головною умовою успіху розкодування r-циклічного шифру є існування диференціалів (r-1)-го циклу, які мають велику ймовірність. Диференціал i-го циклу визначається як пара чисел ${\displaystyle (\alpha ,\beta )i}$ , таких, що пара різних відкритих текстів x і x* з різницею ${\displaystyle \alpha }$ може після i-го циклу дати на виході пару y і y* з різницею ${\displaystyle \beta }$ . Ймовірність i-циклового диференціала це умовна ймовірність ${\displaystyle P(\Delta y(i)=\beta |\Delta x=\alpha )}$ того, що різниця y і y* після i-го циклу дорівнює ${\displaystyle \beta }$ з умовою, що спочатку були x і x* з різницею ${\displaystyle \alpha }$. Відкритий текст x і підключі {к¹ , к² ,…., кⁱ} вважаємо незалежними і випадковими.

Процедура ДКА r-циклічного шифру з вибраними відкритими текстами може бути наступною:

1. Даний етап є етапом попередніх обчислень. На ньому ми шукаємо множину (r-1)-циклових диференціалів ${\displaystyle (\alpha _{1},\beta _{1})_{(}r-1),(\alpha _{2},\beta _{2})_{(}r-1),....(\alpha _{s},\beta _{s})_{(}r-1)}$. Упорядковуємо цю множину згідно з величиною ймовірностей елементів.
2. Наступний етап вимагає від нас вибору x і x*, так щоб їх різниця дорівнювала ${\displaystyle \alpha _{1}}$, для них маємо пару шифртекстів y(r), y*(r). Вважаємо, що на виході передостаннього циклу різниця дорівнювала найбільш вірогідній ${\displaystyle \Delta y(r-1)=\beta _{1}}$. Для трьох елементів ${\displaystyle (\Delta y(r-1),y(r),y^{*}(r))}$ знаходимо кожне можливе значення підключа k^(r). Збільшуємо лічильник появи кожного такого значення підключа к^(r).
3. На даному етапі повторюємо попередній пункт до тих пір поки один або кілька підключей не почнуть з'являтися частіше за інших. Обираємо даний ключ (або множину ключів) як рішення к^(r).
4. На даному етапі ми повторюємо пункти 1-3 для (r-1) -го циклу при цьому значення y (r-1) обчислюються розшифруванням y(r) з використанням ключа k^(r), знайденого в попередньому пункті. І повторюємо ці дії поки не знайдемо ключі всіх циклів.

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

Покажемо що марковський r-циклічний шифр з незалежними підключами є вразливим для ДКА тоді і тільки тоді коли для одного циклу ключ легко обчислюється за відомих трьох параметрів ${\displaystyle (y,y^{*},\Delta x)}$. Також існує (r-1) диференціал ${\displaystyle (\alpha ,\beta )}$ ^r-1 причому його ймовірність задовольняє виразу ${\displaystyle P(\Delta y(r-1)=\beta |\Delta x=\alpha )>>2^{-n},}$ де n — кількість біт в блоці шифруємого тексу. Складність знаходження ключа r-циклічного шифру Q(r) визначається, як число шифрувань, що використовуються, з подальшим знаходженням ключа: ${\displaystyle Q(r)\geq 2/(P_{max}-1/(2^{n}-1)),}$ де ${\displaystyle P_{max}=max(\alpha )max(\beta )(P(\Delta y(r-1)=\beta |\Delta x=\alpha )).}$ Зокрема у випадку якщо ${\displaystyle P_{max}\approx 1/(2^{n}-1)}$, то така атака не буде успішною. Так як операція знаходження підключа більш трудомістка ніж операція шифрування, то одиницею виміру складності є складність знаходження можливих підключів для одного циклу по відомим трійкам ${\displaystyle (\Delta y(r-1),y(r),y^{*}(r)).}$ Відмінною рисою диференціального криптоаналізу є те, що він майже не використовує алгебраїчних властивостей шифру (таких як лінійність, замкнутість, афінність та інші.) Він заснований тільки на нерівномірності розподілу ймовірностей диференціалів.