Криптоаналіз блочних та потокових шифрів.

Найбільш поширеними видами криптоаналізу блокових шифрів є диференціальний і лінійний криптоаналіз.

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

Поняття диференціального криптоаналізу було введено Елі Біхамом (Biham) і Аді Шамір (Shamir) у 1990 році. Кінцева завдання диференціального криптоаналізу - використовуючи властивості алгоритму, в основному властивості S-box, визначити з'єднання раунду. Конкретний спосіб диференціального криптоаналізу залежить від розглянутого алгоритму шифрування.

Якщо в основі алгоритму лежить мережа Фейштеля, то можна вважати, що блок m складається з двох половин - m0 і m1. Диференціальний криптоаналіз розглядає відмінності, які відбуваються в кожній половині при шифруванні. (Для алгоритму DES "відмінності" визначаються за допомогою операції XOR, для інших алгоритмів можливий інший спосіб). Вибирається пара незашифрованих текстів з фіксованим відзнакою. Потім аналізуються відмінності, що вийшли після шифрування одним раундом алгоритму, і визначаються ймовірності різних ключів. Якщо для багатьох пар вхідних значень, що мають одне і те ж відмінність Х, при використанні одного і того ж підключа однаковими (Y) виявляються і відмінності відповідних вихідних значень, то можна говорити, що Х тягне Y з певною ймовірністю. Якщо ця ймовірність близька до одиниці, то можна вважати, що з'єднання раунду знайдений з даною ймовірністю. Так як раунди алгоритму незалежні, ймовірності визначення підключа кожного раунду слід множити. Вважається, що результат шифрування даної пари відомий. Результати диференціального криптоаналізу використовуються як при розробці конкретних S-box, так і при визначенні оптимального числа раундів.

Лінійний криптоаналіз

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

Позначимо

P [1], ...,P [n] - незашифрований блок повідомлення.

C [1], ...,C [n] - зашифрований блок повідомлення.

K [1], ..., K [m] - ключ.

A[i, j, …, k] = A[i]⊕A[j]⊕ …⊕A[k].

Метою лінійного криптоаналізу є пошук лінійного рівняння виду

P[α1, α2, …, αa] ⊕C[β1, β2, …, βb ] = K[γ1, …, γc]

Запускається з ймовірністю р ≠ 0.5.αi, βi і γi - фіксовані позиції в блоках повідомлення та ключі. Чим більше р. відхиляється від 0.5, тим більш відповідним вважається рівняння.

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

Рівняння складаються наступним чином. Обчислюються значення лівої частини для великого числа пар відповідних фрагментів незашифрованого і зашифрованого блоків. Якщо результат виявляється дорівнює нулю більш ніж у половині випадків, то вважають, що K [γ1, ..., γс] = 0. Якщо в більшості випадків виходить 1, вважають, що K [γ1, ..., γс] = 1. Таким чином отримують систему рівнянь, рішенням якої є ключ.

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

При розгляді методів криптоаналізу потокових шифрів всі методи можна умовно розділити на три класи:

силові;

статистичні;

аналітичні атаки.

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

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

Силові атаки

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

Статистичні атаки

Статистичні атаки діляться на два підкласи:

метод криптоаналізу статистичних властивостей шифрувальної гами : спрямований на вивчення вихідний послідовності криптосистеми; криптоаналітик намагається встановити значення наступного біта послідовності з імовірністю вище ймовірності випадкового вибору за допомогою різних статистичних тестів.

метод криптоаналізу складності послідовності: криптоаналітик намагається знайти спосіб генерувати послідовність, аналогічну гамі, але більш просто реалізованим способом.

 Обидва методи використовують принцип лінійної складності.

Аналітичні атаки

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

кореляційні

компроміс "час-пам'ять"

інверсійна

"Припускай і визначай"

на ключову завантаження і реініціалізацію

XSL-атака

Кореляційні атаки

Є найбільш поширеними атаками для злому потокових шифрів.

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

Існують наступні підкласи кореляційних атак:

 Базові кореляційні атаки

 Атаки, засновані на низько-вагових перевірках парності

 Атаки, засновані на використанні сверточних кодів

 Атаки, що використовують техніку турбо кодів

 Атаки, засновані на відновленні лінійних поліномів

 Швидкі кореляційні атаки.

Компроміс «час-пам'ять»

Мета даної атаки - відновлення початкового стану регістра зсуву (знаходження ключа), використовуючи відому схему пристрою та фрагмент шифрувальної послідовності. Складність атаки залежить від розміру шифру і довжини перехопленої гами.

Складається з двох етапів:

 побудова великого словника, в якому записані всілякі пари «стан-вихід»;

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

Прикладами цього класу атак є атака Стіва Беббідж і атака Бірюкова-Шаміра.

 «Припускай і визначай»

Атака грунтується на припущенні, що криптоаналітик відомі гамма, поліном зворотного зв'язку, кількість зрушень регістра між виходами схеми і фільтруюча функція. Складається з трьох етапів:

 припущення про заповнення деяких осередків регістру;

 визначення повного заповнення регістра на підставі припущення про знання криптоаналітик;

 генерація вихідний послідовності; якщо вона збігається з гамою, то припущення на першому етапі було вірно, якщо не збігається, то повертаємося до етапу 1.

Складність алгоритму залежить від пристрою генератора і від кількості припущень.

Асиметрична криптографія.

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

Крім того, процедура шифрування обрана так, що вона необоротна навіть за відомим ключу шифрування - це друга необхідна умова асиметричної криптографії. Тобто, знаючи ключ шифрування і зашифрований текст, неможливо відновити вихідне повідомлення - прочитати його можна тільки за допомогою другого ключа - ключа дешифрування. А раз так, то ключ шифрування для відправки листів будь-якій особі можна взагалі не приховувати - знаючи його все одно неможливо прочитати зашифроване повідомлення. Тому, ключ шифрування називають в асиметричних системах "відкритим ключем", а ось ключ дешифрування одержувачу повідомлень необхідно тримати в секреті - він називається "закритим ключем". Напрошується питання: "Чому, знаючи відкритий ключ, не можна обчислити закритий ключ?" - Це третя необхідна умова асиметричної криптографії - алгоритми шифрування і дешифрування створюються так, щоб знаючи відкритий ключ, неможливо обчислити закритий ключ.

У цілому система листування при використанні асиметричного шифрування виглядає наступним чином. Для кожного з N абонентів, що ведуть листування, обрана своя пара ключів: "відкритий" Ej і "закритий" Dj, де j - номер абонента. Всі відкриті ключі відомі всім користувачам мережі, кожен закритий ключ, навпаки, зберігається тільки у того абонента, якому він належить. Якщо абонент, скажімо під номером 7, збирається передати інформацію абоненту під номером 9, він шифрує дані ключем шифрування E9 і відправляє її абоненту 9. Незважаючи на те, що всі користувачі мережі знають ключ E9 і, можливо, мають доступ до каналу, по якому йде зашифроване послання, вони не можуть прочитати вихідний текст, так як процедура шифрування незворотна по відкритому ключу. І тільки абонент № 9, отримавши послання, здійснює над ним перетворення за допомогою відомого тільки йому ключа D9 і відновлює текст послання. Зауважте, що якщо повідомлення потрібно відправити у протилежному напрямку (від абонента 9 до абоненту 7), то потрібно буде використовувати вже іншу пару ключів (для шифрування ключ E7, а для дешифрування - ключ D7).

Як ми бачимо, по-перше, в асиметричних системах кількість існуючих ключів пов'язано з кількістю абонентів лінійно (у системі з N користувачів використовуються 2 * N ключів), а не квадратично, як у симетричних системах. По-друге, при порушенні конфіденційності k-ої робочої станції зловмисник дізнається лише ключ Dk: це дозволяє йому читати всі листи, що надходять абоненту k, але не дозволяє видавати себе за нього при відправці листів.

Алгоритм RSA стоїть біля витоків асиметричної криптографії. Він був запропонований трьома дослідниками-математиками Рональдом Рівестом (R. Rivest), Аді Шамір (A. Shamir) і Леонардом Адльманом (L. Adleman) в 1977-78 роках.

Першим етапом будь-якого асиметричного алгоритму є створення пари ключів: відкритого та закритого і поширення відкритого ключа "по всьому світу". Для алгоритму RSA етап створення ключів складається з наступних операцій:

1. Вибираються два прості (!) Числа p і q

2. Обчислюється їх добуток n (= p * q)

3. Вибирається довільне число e (e <n), таке, що НОД (e, (p-1) (q-1)) = 1, тобто e повинно бути взаємно простим з числом (p-1) (q-1) .

4. Методом Евкліда вирішується в цілих числах (!) Рівняння e * d + (p-1) (q-1) * y = 1. Тут невідомими є змінні d і y - метод Евкліда як раз і знаходить безліч пар (d, y), кожна з яких є рішенням рівняння в цілих числах.

5. Два числа (e, n) - публікуються як відкритий ключ.

6. Число d зберігається в найсуворішому секреті - це і є закритий ключ, який дозволить читати всі послання, зашифровані за допомогою пари чисел (e, n).