Безумовно стійкі та обчислювально стійкі криптосистеми

1.2.1 Поняття безумовно стійкої криптосистеми

Для захисту особливо критичної інформації в частині забезпечення високого рівня конфіденційності можуть використовуватися криптографічні перетворення, що забезпечують безумовну стійкість [7-9].

На рис. 1.3 наведена спрощена схема криптографічного захисту пові-
домлень.

Рисунок 1.3 – Спрощена схема криптографічного

захисту повідомлень

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

. (1.8)

З метою забезпечення цілісності і справжності над повідомленням M_i в ПА здійснюється криптоперетворення – автентифікації, в результаті чого на виході формується автентифіковане повідомлення

. (1.9)

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

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

. (1.10)

Криптограма С_j передається користувачу К2 через телекомунікаційну систему по відкритому каналу зв’язку, чи записується на носій інформації.

Якщо криптоаналітик знає апріорні імовірності Р (M_i) та ентропію Н (M_i), він може ставити та розв’язувати задачу визначення: яке повідомлення М_і міститься в С_j і які ключі зашифрування та автентифікації використовується для автентифікації та шифрування.

Вважаючи, що криптоаналітику відомо апріорну статистику:

, ,

а також умовну апостеріорну імовірність криптоаналітик може знайти умовну ентропію ,

. (1.11)

У процесі нагромадження криптограм криптоаналітик зменшує свою невизначеність, у результаті чого він отримує деяку інформацію ΔI, що може бути вимірена як:

. (1.12)

Умовну апостеріорну імовірність можна визначити, використовуючи співвідношення [7]:

. (1.13)

Із (1.13) випливає, що криптоаналітик знаючи апріорні імовірності Р (М_і), P (C_j), може розрахувати імовірність того, що в С_j криптограмі міститься точно М_і повідомлення.

Для практичного використання можна створити криптографічні системи, тобто реалізувати в них криптографічні перетворення, із чотирма рівнями стійкості:

1. Безумовно стійкі криптографічні системи або теоретично не дешифрувальні.

2. Обчислювально стійкі або гарантовано стійкі.

3. Ймовірно стійкі або доказово стійкі.

4. Обчислювально не стійкі або тимчасово стійкі.

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

- N_k – обсяг ключів;

- H (К) – ентропія джерела ключів:

, (1.14)

де – імовірність появи К_і ключа в системі;

- t_б – безпечний час;

- l_o – відстань єдності криптосистеми.

Вище t _б є математичне сподівання часу розкриття криптосистеми із використанням конкретного методу криптоаналізу. Найбільш простим є метод підбору чи грубої сили. При його реалізації потрібно перебрати N_в варіантів, тому безпечний час дорівнює

, (1.15)

де – імовірність, з якою необхідно здійснити криптоаналіз; g – про-дуктивність криптоаналітичної системи; с/рік – є наближене значення кількості секунд в році.

У граничному випадку N_в = N_к, де N_к – розмір множини ключів.

1.2.2 Умови реалізації безумовно стійких криптосистем

Теорема 1.2.1. Необхідною і достатньою умовою теоретичної недешифрованості чи безумовної стійкості є умова [7]:

, (1.16)

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

(1.17)

визначимо імовірність , яку може обчислити криптоаналітик, використовуючи співвідношення

. (1.18)

Якщо = Р (Mi), то це означає, що криптоаналітик не отримав ніякої інформації відносно джерела повідомлення. Тому

. (1.19)

Із (1.19) випливає, що

.

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

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

, (1.20)

де М_i – i -й символ, , а К_і – і -й символ ключа, С_і символ крип-тограми, m – розмір алфавіту, що використовується.

Відмінною рисою системи Вернама є те, що символи ключа К_i мають породжуватися випадково, рівноймовірно та незалежно. У такій системі символів ключа (довжина ключа) має бути не менше довжини повідомлення, тобто

. (1.21)

Розшифрування в системі Вернама здійснюється згідно з правилом

. (1.22)

Аналіз (1.20) і (1.22) показує, що для зашифрування і розшифрування потрібно використовувати однакову випадкову послідовність (ключ).

Можна показати, що для системи, яка розглядається, умовна ентропія [7]:

, (1.23)

де l – довжина криптограми, d – надмірність алфавіту.

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

Задача криптоаналізу може бути розв’язана, коли:

.

Тоді із (1.23) випливає, що

. (1.24)

Розв’язавши рівняння (1.24) отримаємо, що відстань єдності l ₀ визначається як

. (1.25)

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

Очевидно, що успіх криптоаналітика у розв’язанні задачі криптоаналізу залежить від обсягу криптограм, який він отримав. При цьому криптоаналітик знаходиться в невизначеності ,

. (1.26)

Найкращий випадок, якщо .

Використовуючи функції ненадійності Шенона [7]:

, (1.27)

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

Для деякого класу лінійних (групових) шифрів, у яких використовуються природні мови (російська, англійська, С++, графіка) Шенон отримав розв’язок рівняння (1.27). Якщо

,

, (1.28)

(1.29)

і апостеріорна ентропія визначається через умовну апостеріорну імовірність , то

, (1.30)

, (1.31)

.

Далі можна розрахувати за (1.30), знаючи статистики Р (С_j) і .

Надмірність d визначається залежністю символів мови між собою та різними імовірностями появи їх в тексті. Вона може бути визначена, як

, (1.32)

де Н ₀(М) – ентропія мови, де всі символи порівняно ймовірні і незалежні.

Якщо

, (1.33)

то

, (1.34)

тому

. (1.35)

Використовуючи рівняння (1.25), маємо для мови з m алфавітом

. (1.36)

Для двійкового алфавіту (m =2)

. (1.37)

Приклад 1.2.1.

Знайти l ₀ для реального повідомлення (мова українська), за умови, що джерело ключів містить:

, d =0,4.

В результаті маємо

,

біт.

Приклад 1.2.2.

Знайти l ₀ для безумовно стійкого шифру. В результаті маємо

.

Враховуючи, що

та ,

маємо

, (1.38)

коли та

(1.39)

коли .

Таким чином, для безумовно стійкої системи l ₀ не менше довжини пові-домлення, і не менше довжини ключа, оскільки d<1. Тому для успішного криптоаналізу криптоаналітик повинен отримати не менш ніж l_к символів, тобто весь ключ.

Можна показати, що іншою умовою забезпечення безумовної стійкості є:

.

Покладемо, що , тоді

, (1.40)

, (1.41)

де N_k – кількість ключів, N_M – кількість повідомлень.

Імовірності появи К_і ключа і М_і повідомлення є

,

,

тому

,

,

. (1.42)

В результаті отримаємо

. (1.43)

Приклад 1.2.3.

Визначити кількість символів ключа (обсяг ключів), які потрібно розіслати К1 і К2, зв'язаних між собою каналом зі швидкістю V =2Мг біт/с, якщо вони працюють протягом року безупинно, а на носій інформації записується 5*10⁹ бітів.

Довжина повідомлення

.

Число дисків, на які можна записати 5*10⁹ інформації

.

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

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

1.2.3 Обчислювально стійкі криптосистеми

У зв’язку зі складністю реалізації безумовно стійких криптосистем на практиці застосовують обчислювально стійкі криптосистеми. Під обчислю-вально стійкою криптосистемою вважається така для якої безпечний час (t_б) набагато більше часу цінності інформації , що захищається, тобто [7,8,10,11]

. (1.44)

У обчислювально стійких криптосистемах замість ключової послідовності К_i використовують гаму шифрування Г_i. Вона формується як

, (1.45)

де К_і – ключ обчислювально стійкого шифру.

Тоді зашифрування здійснюється, наприклад, як

. (1.46)

Пристрій чи алгоритм, що формує Г_i, тобто реалізує функцію j, називається шифроутворюючим пристроєм. Особливістю обчислювально стійкої системи є те, що ключ зашифрування має невелику довжину. Наприклад, для високостійких систем він повинен мати довжину від 256 до 512 бітів.

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

1) мати заданий період, тобто , де є мінімальне допустиме значення періоду повторення (звичайно задається і більше);

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

, (1.47)

де l_n – мінімальна довжина гами, для якої можна визначити закон формування усіх символів гами на періоді L.

У найкращої гами

.

3) відновленість в просторі і часі, тобто можливість її точного відтворення як у різних користувачів так і у одного і того ж з часом;

4) мінімальна або сприйнятна складність реалізації функції , тобто обчислення гами шифруючої;

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