Розробка імовірнісної моделі криптографічних протоколів (стр. 6 из 19)
Рисх(а) = Рисх/ш(а/у) (1.2)
за умови, що Ру(у)>0, де
Рисх(а) – розподіл імовірності на множині відкритих текстів;
Рисх/ш(а/у) – сумісний розподіл імовірності на множині пар відкритих і шифрованих текстів;
Ру(у) – розподіл імовірності на множині шифрованих текстів.
Інакше кажучи, при використанні шифру розподіл імовірності на множині відкритих текстів після перехоплення криптограми у (апостеріорний розподіл імовірності) не відрізняється від розподілу імовірності на множині відкритих текстів до отримання перехопленої криптограми у (від апріорного розподілу імовірності). Перехоплення повідомлення, зашифрованого за допомогою ідеального шифру, не містить для криптоаналітика ніякої інформації, якщо ключ йому невідомий.
Розглянемо основні підходи до оцінки практичної стійкості шифрів.
Системний підхід.
З одного боку, криптографічна система повинна забезпечувати надійний захист інформації і, з іншого боку, повинна бути зручна з погляду технічної реалізації і експлуатації. Оскільки шифрсистеми, що забезпечують ідеальну секретність, в більшості випадків практично непридатні, то питання відноситься перш за все до шифрсистемам, що використовують ключі обмеженого розміру і здатним обробляти великі об'єми інформації.
Системний підхід до оцінки стійкості шифрсистеми має на увазі певну деталізацію поняття «стійкий шифр». В результаті цієї деталізації формується ряд критеріїв математичного і технічного характеру, яким повинна задовольняти стійка шифрсистема. Під час розробки нового підходу до аналізу шифрсистеми формується відповідний критерій якості шифрсистеми, який доповнює систему критеріїв, що раніше склалася.
Основною кількісною мірою криптографічної стійкості шифру є обчислювальна складність рішення задач дешифрування. Обчислювальна складність визначається декількома характеристиками. Розглянемо найважливіші з них.
Припустимо, що перед криптоаналітиком поставлене завдання дешифрування шифру Е по деякому набору криптограм. Хай АЕ – клас застосовних до шифру Е алгоритмів дешифрування, які має в своєму розпорядженні криптоаналітик. При цьому криптоаналітик розглядає як імовірнісний простір W елементарних подій множину пар ключів і відкритих текстів, якщо відкриті тести невідомі, або множуну ключів, якщо відкриті тексти відомі. Для алгоритму yÎAE позначимо через Т(y) середню трудомісткість його реалізації, вимірювану в деяких умовних обчислювальних операціях. При цьому величина трудомісткості звичайно усереднюється по множині W.
Однією з основних характеристик практичної стійкості шифру Е є середня трудомісткість ТЕ дешифрування, яка визначається виразом
ТЕ =
Т(y). (1.3)При цьому важливо відзначити наступне:
1. Існують алгоритми дешифрування, визначені не на всьому імовірнісному просторі W, а лише на деякій його частині. Крім того, деякі алгоритми дешифрування влаштовані так, що їх реалізація приводить до успіху (рішенню дешифрувальної задачі) не на всій області визначення, а лише не деякій її підмножині. Тому до найважливіших характеристик алгоритму дешифрування y необхідно віднести не тільки його трудомісткість Т(y), але і надійність n(y), під якою розуміється середня частка інформації, що дешифрується з використанням алгоритму y.
Якщо надійність алгоритму дешифрування мала, то з погляду криптографа він є безпечним, а з погляду криптоаналітика неефективним. Таким чином, при отриманні оцінки (1.3.2) величини ТЕ доцільно розглядати лише ті алгоритми дешифрування, надійність яких достатньо велика. При цьому для визначення «найкращого» алгоритму дешифрування системи Е можна використовувати різні критерії залежно від конкретних умов завдання. Наприклад, можна вважати «найкращим» алгоритм дешифрування y, для якого найменше значення приймає величина T(y)/n(y). Цю величину можна інтерпретувати як середні трудовитрати, необхідні для успішного дешифрування шифрсистеми.
2. Складність дешифрування залежить від кількісних і якісних характеристик криптограм, які має в своєму розпорядженні криптоаналітик. Кількісні характеристики визначаються числом перехоплених криптограм і їх довжинами. Якісні характеристики пов'язані з достовірністю перехоплених криптограм (наявність спотворень, пропусків і т. д.).
За Шенноном, кожен шифр має об'єктивну характеристику Те(п) – середню (по всіх криптограмах довжини п і ключам) обчислювальну складність дешифрування. Величина
Те(п) характеризує граничні можливості дешифрування системи Е при необмеженій кількості шифрматеріала і абсолютної кваліфікації криптоаналітика.Оцінюючи стійкість шифру, криптоаналітик одержує верхні оцінки граничної стійкості, оскільки практичне дешифрування використовує обмежену кількість шифрматеріала і обмежений клас так званих відомих методів дешифрування.
Важливою характеристикою криптографічної стійкості системи є тимчасова складність її дешифрування. Оцінка тимчасової складності дешифрування системи має на увазі детальніше опрацьовування реалізації алгоритмів дешифрування з урахуванням характеристик обчислювального пристрою, використовуваного для дешифрування. До таких характеристик обчислювального пристрою, що реалізовує алгоритми дешифрування, відносяться архітектура, швидкодія, об'єм і структура пам’яті, швидкість доступу до пам’яті і ін. Отже, час дешифрування системи Е визначається наявним класом алгоритмів дешифрування АЕ і обчислювальними можливостями криптоаналітика.
Вибір найкращого алгоритму дешифрування ускладнюється і тим, що різним обчислювальним пристроям можуть відповідати різні «найкращі» алгоритми дешифрування.
Питання про криптографічну стійкість шифрсистеми має деякі особливості з погляду криптоаналітика і криптографа.
Криптоаналітик атакує шифрсистему, маючи в своєму розпорядженні конкретні інтелектуальні, обчислювальні і економічні ресурси. Його мета – успішне дешифрування системи.
Криптограф оцінює стійкість шифрсистеми, імітуючи атаку на шифр з боку криптоаналітика супротивника. Для цього криптограф моделює дії криптоаналітика, оцінюючи по максимуму інтелектуальні, обчислювальні, технічні та інші можливості супротивника. Мета криптографа – переконатися у високій криптографічній стійкості розробленої шифрсистеми.
Таким чином, системний підхід до оцінки практичної стійкості шифру пов'язаний з оцінкою обчислювальних трудовитрат при дешифруванні системи з позиції різних критеріїв якості шифру.
Асимптотичний аналіз стійкості.
Цей підхід розвивається теорією складності обчислень. При дослідженні шифру оцінка його стійкості ув'язується з деяким параметром шифру, звичайно це довжина ключа, і проводиться асимптотичний аналіз оцінок стійкості.
Вважається, як правило, що шифрсистема має високу криптографічну стійкість, якщо остання виражається через довжину ключа експоненціально, і шифрсистема має низьку криптографічну стійкість, якщо стійкість виражається у вигляді многочлена від довжини ключа.
Оцінка кількості необхідного шифрматериалу.
Даний підхід заснований не на складності обчислень при реалізації дешифрування, а на оцінці середньої кількості матеріалу, який необхідно проаналізувати криптоаналітику для розкриття шифру. Оцінка кількості необхідного криптоаналітику шифрматеріалу представляє інтерес з тієї точки зору, що є нижньою оцінкою стійкості шифру в сенсі обчислювальної складності дешифрування.
Цей підхід застосовується в основному для оцінки стійкості потокових рандомізованих шифрів. Особливістю пристрою таких шифрів є те, що вони використовують для шифрування і расшифрування секретний ключ невеликого розміру, а також велику і загальнодоступну випадкову послідовність чисел (рандомізатор). Ключ визначає, які частини рандомізатора використовуються для шифрування, тоді як криптоаналітику, що не знає секретного ключа, доводиться аналізувати весь рандомізатор.
Як приклад такого шифру розглянемо шифр Діффі. У цьому шифрі рандомізатором є масив з 2n випадкових двійкових послідовностей, занумерованих елементами множини Vn. Ключем є п-мірний двійковий вектор. При шифруванні з використанням ключа k двійкова послідовність відкритого тексту складається побітово з послідовністю рандомізатора, що має номер k. Таким чином, для дешифрування повідомлення супротивнику необхідно досліджувати порядка 2п біт.
Вартісний підхід.
Цей підхід передбачає оцінку вартості дешифрування системи. Особливо він актуальний тоді, коли для дешифрування криптосистеми необхідно розробити і побудувати новий обчислювальний комплекс. Вартісний підхід корисний з погляду зіставлення матеріальних витрат на дешифрування системи і цінності інформації, що захищається криптосистемою.
1.4. Криптопротоколи, їх класифікація, особливості використання
Нагадаємо поняття криптопротокола. Криптографічним протоколом називається встановлена послідовність дій, що виконуються двома або більше сторонами для виконання певного криптографічного завдання. Послідовність дій означає, що протокол виконується в певному порядку, з початку до кінця. Кожна дія повинна виконуватися в свою чергу і лише після закінчення попередньої. Такі, що виконуються двома і більше сторонами означає, що для реалізації протоколу потрібно принаймні дві люди, одна людина не зможе реалізувати протокол.