ля аналізу широкого класу марківських шифрів. Марківським називається шифр, у якого рівняння шифрування на одному циклі задовольняє умові: вірогідність диференціала не залежить від вибору відкритих текстів. Тоді, якщо підключи циклів незалежні, то послідовність різниць після кожного циклу утворює марковскую ланцюг, де подальший стан визначається тільки попереднім. Прикладами марковських шифрів є DES і FEAL. p align="justify"> Можна показати, що марківський r-циклової шифр з незалежними підключив є вразливим для ДКА тоді і тільки тоді, коли для одного циклу шифрування ключ за відомою трійці (y, y *, D x) може бути легко обчислений, і існує (r-1)-циклової диференціал (a, b) к-1 такий, що його ймовірність задовольняє умові (D y (r-1) = b | D x = a)>> 2-n ,
де n-кількість біт в блоці шіфруемоготексту.
Складність розкриття ключа r-циклічного шифру Q (r) визначається як число використовуваних шифрування з наступним обчисленням ключа:
Q (r) і 2/(Pmax - 1/(2n-1)),
де Pmax = max (a) max (b) (P (D y (r-1) = b | D x = a)).
Зокрема, якщо Pmax В»1/(2n-1), то атака не буде успішною. Оскільки обчислення підключа - більш трудомістка операція, ніж шифрування, то одиницею виміру складності є складність знаходження можливих підключів одного циклу по відомим (D y (r-1), y (r), y * (r)). p align="justify"> Відмінною рисою диференціального аналізу є те, що він практично не використовує алгебраїчні властивості шифру (лінійність, афінність, транзитивність, замкнутість і т.п.), а заснований лише на нерівномірності розподілу ймовірності диференціалів.
.4 Лінійний криптоаналіз
Лінійний криптоаналіз винайшов японський криптолог Міцуру Мацуї (Mitsuru Matsui). Запропонований ним в 1993 р. метод спочатку був направлений на розтин алгоритму DES. Згодом лінійний криптоаналіз був поширений і на інші алгоритми. [12]
Сенс лінійного криптоаналізу полягає в знаходженні співвідношень такого вигляду: [12]
Pi1 Г… Pi2 Г… ... Г… Pia Г… Cj1 Г… Cj2 Г… ... Г… Cjb = Kk1 Г… Kk2 Г… ... Г… Kkc
де Pn, Cn і Kn - n-е біти відкритого тексту, шифртекста і ключа відповідно.
Для довільно обраних біт відкритого тексту, шифртекста і ключа ймовірність P справедливості такого співвідношення становить близько ВЅ. У тому випадку, якщо криптоаналітику вдається знайти такі біти, при яких імовірність P помітно відрізняється від ВЅ, даними співвідношенням можна скористатися для розкриття алгоритму. [12]
Для розкриття ключа шифру DES цим методом необхідно 247 пар відомих відкритих і зашифрованих текстів. [16]
.5 Тимчасової криптоанализ
