Лекція №3. Основні види криптографічних атак. Теорія секретних схем Шеннона.

Лекція №3. Основні види криптографічних атак. Теорія секретних схем Шеннона.

Основні види криптографічних атак залежно від відомої інформації поділяються на:

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

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

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

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

5) Атака на основі обраного шифрованого тексту. Криптоаналітик може обрати різні шифровані тексти для дешифрування і має доступ до дешифрованих відкритих текстів (наприклад, криптоаналітик має доступ до апарата-шифратора).

6) Адаптивна атака на основі обраного шифрованого тексту (аналогічно п.4).

7) Атака на основі обраного тексту (адаптивна) - поєднує можливості атак 3,5 (або 4,6).

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

Загальна схема секретного зв'язку

А - відправник, В - одержувач, М - відкритий текст (ОТ); С - криптограма (ШТ) відправника: C’ - отримана криптограма (може бути змінена при передачі). Ключ k попередньо передається по закритому каналу (вважається, що канал надійний).

З математичної точки зору криптосистема являє собою набір просторів ∑ = {М,К, С, Е, D }, де

М - простір всіх повідомлень; К - простір ключів;

С - простір криптограм;

Е - простір алгоритмів шифрування;

D - простір алгоритмів дешифрування.

Розглянемо M,X - деякі кінцеві повідомлення. - криптограми; - деякий ключ; - конкретні перетворення шифрування й дешифрування відповідно на ключі к.

У загальному випадку шифр - це відображення ∑:M ,причому - деяке ін'єктивне відображення.

У теорії Шеннона сформульовані наступні припущення:

1. Криптоаналітику відомий тільки шифрований текст.

2. Ключ і рандомізатор використовуються для шифрування тільки один раз (тобто криптоаналіз робиться тільки по одній криптограмі).

3. На M й K заданий ймовірнісний розподіл.

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

В криптології загальноприйняте наступне правило Керкгоффа:

Стійкість криптосистеми не повинна спиратися на таємність алгоритму шифрування, а має грунтуватися на таємності ключа (при надійному алгоритмі шифрування і достатньому розмірі ключа). Таким чином, всі простори криптосистеми ∑ і розподіл на М і К вважаються відомими криптоаналітику.

Нехай - розподіл ймовірностей на декартовому добутку M * K. Якщо згенеровані відкритий текст і ключ незалежні, то Р(М,к) = Р(М)Р(к). Цей розподіл індукує ймовірнісні розподіли на інших множинах системи. На просторах шифрування E, дешифрування D, криптограм С:

де сумування проводиться по всіх парах (М,к), для яких Е_к(М) = С.

Спільний розподіл ймовірностей криптограм і ключів на СхК:

Р(С,к)=

Спільний розподіл ймовірностей криптограм і відкритих текстів на СхМ:

Р(СМ) = Р{М,С)= .

Умовні розподіли:

;

Цілком секретна криптосистема. Теорема Шеннона.

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

Цілком секретною криптосистемою ∑ називається криптосистема, для якої виконується одна з умов:

1. ( М,С):Р(М|С) = Р(М);

2. Н(М|С)=Н(М),деH(М)іH(М|С) - ентропія й умовна ентропія відповідно.

ТЕОРЕМА 2.1 Необхідною і достатньою умовою цілковитої таємності криптосистеми є виконання будь-якої з умов: 1. ( М,С):Р(С|М) = Р(С);

2. H(С|М)=H(С).

Необхідність. Якщо система цілком секретна, то Р(М) = Р(М | С) =

Аналогічно доводиться достатність.

Приклад. Шифр Вернама (1917 p.).

За ключ береться «чисто» випадкова послідовність:

ОТ: 011011011100101

Å

К: 101101010101011

ШТ: 110110001001110

У даному прикладі ймовірність появи будь-якої ключової послідовності, а

також будь-якої криптограми .

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

Твердження 2.1 Шифр Вернама є зовсім секретною криптосистемою.

Маємо відкритий текст: м = т₁ т₂...т_п, ключ: k = k₁k₂... k_n, криптограму:

С = с₁с_г... с_n, m_i k_i c_i Î Z₂ ={0,1}; c = m₁ Å k_1,.., m_n Å k_n. Розглянемо 2 підходи до доказу

твердження.

1-й підхід. Використовуємо теорему 2.1. Безпосередньо знаходимо, що ймовірність появи будь-якої криптограми P(С) =

2-й підхід. Нехай - імовірність появи 1 на i-ому місці відкритого тексту: За означенням тому що символи ключа «чисто» випадкові. Тоді

ТЕОРЕМА 2.2 (Шеннона) Якщо криптосистема цілком секретна, то H(К)≥ Н(М). Ця нерівність називається границею Шеннона.

Оцінимо H(M). Так як система цілком секретна, то

H(M)= H(M|C)≤H(M,K|C)=H(K|C)+ H(M|K,C)= H(K|C)≤H(K), тобто H(M)≤H(K).

Ненадійність ключа і відкритого тексту по Шеннону. Відстань одиничності

Ненадійністю ключа називається величина

Н(К|С) = -

Ненадійністю відкритого тексту називається величина

Н(M|С) = -

Твердження 2.2 Якщо ключі і відкриті тексти незалежні, то

H(K|C)=H(M)+H(K)-H(C).

H(M,K,C)=H(M,K)+H(C|M,K)=H(K,C)+H(M|K,C). Так як

,

То H(M,K)=H(K,C)⇒H(M)+H(K)-H(C)= H(K|C).

Наслідку з твердження 2.2. Якщо H(M)=H(C), то H(K|C)= H(K).

Нехай – деяка криптограма, - алфавіт криптограм. Функцією ненадійності ключа називається функція

(ентропія за умови, що відомо n символів криптограми).

Очевидно, що f(n) – не зростаюча функція, а саме:

.

Відстанню одиничності називається величина u= min{n|f(n)»0}.

Наслідок з формули Шеннона. Якщо алфавіт шифрованого збігається з алфавітом відкритого тексту то надмірність криптограми збігається з надмірністю відкритого тексту . Для індоєвропейських мов (60-80% залежно від тексту).

Надмірність у бітах на знак алфавіту . Якщо , то коли R®0 та u®∞.

Якщо алфавіт ключа збігається з алфавітом шифрованого і відкритих текстів , то , де |k| -довжина ключа в символах алфавіту.

Дата добавления: 2015-08-29