95

МІНІСТЕРСТВО ВНУТРІШНІХ СПРАВ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ВНУТРІШНІХ СПРАВ

ФАКУЛЬТЕТ управління ТА інформатики

КАФЕДРА ЗАХИСТУ ІНФОРМАЦІЇ І СПЕЦІАЛЬНОЇ ТЕХНІКИ

95

пояснювальна записка

Розробка імовірнісної моделі криптографічних протоколів

^{(тема роботи)}

Курсант гр. 543 ___________ Хомічук Т. О.

^{(шифр групи) (підпис) (прізвище, ініціали)}

Керівник роботи ___________________ нач. кафедри Логвиненко М.Ф.

^{(підпис) (посада, прізвище, ініціали)}

ДО ЗАХИСТУ______________________________________________________

^{(допускається, не допускається)}

Нач. факультету (кафедри) захисту інформації та спеціальної техніки

^{(назва факультету, кафедри)}

________________________Логвиненко М.Ф.

^{(підпис) (прізвище, ініціали)}

Харків - 2006Зміст

• Вступ 3
• Розділ 1. Структура захищених систем і їх характеристики 8
• • 1.1. Структура захищеної системи обміну даними 8
  • 1.2. Сучасні основні шифри 10
  • 1.3. Методика визначення стійкості криптосистем 20
  • 1.4. Криптопротоколи, їх класифікація, особливості використання 27
  • Висновки 35
• Розділ 2. Моделі елементів захищених систем 36
• • 2.1. Поняття стійкості шифрсистеми 36
  • 2.2. Стійкість криптографічних протоколів 40
  • 2.3. Математичні моделі елементів криптографічних систем 46
  • 2.4. Математична модель криптографічного протоколу 51
  • Висновки 53
• Розділ 3. Оцінка стійкості криптографічних протоколів на основі імовірнісних моделей 55
• • 3.1. Методика оцінки стійкості 55
  • 3.2. Приклади доказу стійкості деяких протоколів на основі їх імовірнісних моделей 55
  • Висновки 70
• Розділ 4. Нормативно-правова база розробки, впровадження і експлуатації захищених систем 72
• • 4.1. Структура нормативної бази 72
  • 4.2. Основні поняття та положення 76
  • Висновки 89
• Висновки 91
• Список літератури 93

Вступ

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

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

Історично криптографія використовувалася з однією метою: зберегти секрет. Навіть сама писемність була свого роду шифруванням (у Стародавньому Китаї тільки вищі шари суспільства могли навчатися читанню і листу), а перший досвід застосування криптографії в Єгипті відноситься до 1900 року до н. э.: автор напису користувався незвичайними ієрогліфами. Є і інші приклади: дощечки з Месопотамії, на яких зашифрована формула виготовлення керамічної глазурі (1500 рік до н. э.), єврейський шифр ATBASH (500-600 роки до н. э.), грецький «небесний лист» (486 рік до н. э.) і шифр простої підстановки Юлія Цезаря (50-60 рік до н. э.). Кама Сутра Ватсяяни навіть ставить мистецтво тайнопису на 44-е, а мистецтво секретної розмови на 45-е місце в списку 64 мистецтв (йог), якими повинні володіти чоловіки і жінки.

Основними задачами, які вирішує криптографія є:

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

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

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

Достовірність інформації виражається в суворій приналежності обєкту, який є її джерелом.

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

Юридична значущість означає, що документ володіє юридичною силою.

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

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

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

Необхідно, щоб шифри володіли наступними основними властивостями:

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

- криптоаналітик (зловмисник), що перехопив повідомлення, не зможе відновити по ньому початкове повідомлення без таких витрат часу і засобів, які зроблять цю роботу недоцільною.

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

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

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

Основна відмінність протоколу від алгоритму полягає в тому, що реалізація алгоритму припускає активні дії одного субєкта, тоді як протокол реалізується в ході взаємодії декількох субєктів.

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

Атаки на протоколи з боку супротивника можуть бути направлені як проти криптографічних алгоритмів, використовуваних в протоколах, так і проти самих протоколів. Такі атаки можна розділити на пасивні і активні.

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

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

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

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

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

- аутентифікація сторін, що встановлюють звязок;

- авторизація користувачів при доступі до телекомунікаційних і інформаційних служб.

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

Метою даної роботи є системний аналіз роботи криптографічних протоколів і створення математичних імовірнісних моделей елементів криптографічних систем з метою формалізації оцінок стійкості криптопротоколів.

Для досягнення мети необхідно вирішити наступні завдання:

1. Аналіз структури захищених систем, що використовують криптографічні протоколи.

2. Системний аналіз методик оцінки стійкості шифрів і протоколів.

3. Розробка пропозицій по формалізації завдання оцінки стійкості протоколів, заснованої на імовірнісних моделях.

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

Розділ 1. Структура захищених систем і їх характеристики

1.1. Структура захищеної системи обміну даними

Щоб приступити до математичного аналізу криптосистем необхідно показати структуру захищеної системи обміну даними, яка представлена на мал.1.1.

Шифрувальник

повідомлення

Повідомлення Криптограма Повідомлення

Ключ К Ключ К

Мал. 1.1

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

Очевидно, шифрувальник на передавальному кінці виконує деяку функціональну операцію. Якщо М - повідомлення, К - ключ і Е - зашифроване повідомлення, то маємо

Е= (М, К)

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

Е = Т_i М.

Відображення Т_i, застосоване до повідомлення М, дає криптограму Е. Індекс i відповідає конкретному використовуваному ключу.

Взагалі ми припускатимемо, що є лише кінцеве число можливих ключів, кожному з яких відповідає вірогідність р_i. Таким чином, джерело ключів є статистичним процесом, або пристроєм, який вибирає одне з множини відображень Т₁, …, Т_m з імовірністю р₁, …, р_m відповідно. Також припускатимемо, що число можливих повідомлень скінчене, і ці повідомлення М₁, …, М_n мають апріорну імовірність q₁, …, q_n. Наприклад, можливими повідомленнями могли б бути всілякі послідовності англійських букв, що включають по N букв кожна, а відповідною імовірністю тоді були б відносні частоти появи таких послідовностей в нормативній англійській мові.

Повинна бути можливість відновлювати М на приймальному кінці, коли відомі Е і К. Тому відображення Т_i з нашого сімейства повинна мати єдине зворотне відображення Т_i^-1, так що Т_i Т_i^-1=I, де I - тотожнє відображення. Таким чином, це зворотне відображення Т_i^-1 повинне існувати і бути єдиним для кожного Е, яке може бути одержане з М за допомогою ключа i.

1.2. Сучасні основні шифри

За характером використання ключа відомі кріптосистеми можна розподілити на два типи: симетричні (одноключові, з секретним ключем) і несиметричні (з відкритим ключем).

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

Як приклад симетричного алгоритму шифрування розглянемо достатньо стійкий і надійний алгоритм DES (Data Encryption Standard).

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

Як алгоритм з відкритим ключем далі розглянемо один з найбільш поширених шифр RSA (Rivest - Shamir - Adleman). Його надійність знаходиться в прямій залежності від складності розкладання великих чисел на множники. Якщо множники мають довжину близько 100 десяткових цифр, то в найкращому з відомих способів розкладання на множники необхідно близько 100 млн. років машинного часу, шифрування ж і дешифрування вимагає близько 1-2 с на блок.

Опис алгоритму DES.

У криптосистемі DES використовується блоковий принцип шифрування двійкового тексту. Довжина блоку шифрування складає 64 біта. Розмір ключа - також 64 біта. При цьому кожен восьмий біт є службовим і в шифруванні не бере участь. Кожен такий біт є двійковою сумою семи попередніх і служить лише для виявлення помилок при передачі ключа по каналу звязку. Процес криптоперетворення містить наступні три основні етапи.

1. Біти початкового повідомлення x піддаються початковій підстановці IP відповідно до табл. 1.1.

Таблиця 1.1

Підстановка IP

Це означає, що 58-й біт стає першими, 50-й - другим і т.д. Потім одержаний вектор x₀ = IP(x) представляється у вигляді x₀ =L₀R₀, де L₀ - ліва половина з 32 бітів, а R₀ - права половина з 32 бітів.

2. Повідомлення L₀R₀ перетворюється далі 16 разів по так званій схемі Фейстеля:

L_i =R_i-1, R_i = L_i-1 ( R_i-1, K_i), i = 1, 2, …, 16,

де функція і розклад ключів K₁, K₂, …, K₁₆ будуть описані окремо.

Мал. 1.2 Криптоперетворення Фейстеля

4. Повідомлення L₁₆R₁₆ перемішується підстановкою IP^-1:

y = IP^-1(L₁₆R₁₆),

де у - зашифроване повідомлення.

Таблиця 1.2

Підстановка IP^-1

Шифрування здійснюється по схемі, приведеній на мал. 1.3.

………………………

Мал. 1.3 Схема криптопeретворення DES

Функція . Вона має два аргументи: А і В. Перший складається з 32 бітів, а другий - з 48 бітів. Результат складається з 32 бітів.

1. Аргумент А, що має 32 біта, перетворюється в 48-бітовий вектор Р(А) шляхом перестановки з повтореннями початкового вектора А. Ця процедура однакова для всіх тактів. Вона задана табл. 1.3.

Таблиця 1.3

Підстановка Р1

2. Далі обчислюється сума Р(А) В і записується у вигляді конкатенації восьми 6-бітових слів: Р(А) В = B₁B₂ B₃ B₄ B₅ B₆ B₇ B₈.

3. На цьому етапі кожне слово B_і поступає на відповідний S-блок S_і. Блок S_і перетворює 6-бітовий вхід B_і в 4-бітовий вихід C_i. S-блок є 416 матриця з цілими елементами в діапазоні від 0 до 16.

Два перших біта слова B_і, якщо їх розглядати як двійковий запис числа, визначають номер рядка матриці S-блоку. Чотири останні біти визначають деякий стовпець. Тим самим знайдений деякий елемент матриці. Його двійковий запис і є виходом.

Таблиця 1.4

Блок S₁

Таблиця 1.5

Блок S₂

Продовження табл. 1.5

Таблиця 1.6

Блок S₃

Таблиця 1.7

Блок S₄

Таблиця 1.8

Блок S₅

Таблиця 1.9

Блок S₆

Таблиця 1.10

Блок S₇

Таблиця 1.11

Блок S₈

4. Вихід С = С₁ С₂ … С₈ перемішується фіксованою підстановкою Р2.

Таблиця 1.12

Підстановка Р2.

Розклад ключів.

1. У 64-бітовому ключі К усуваються біти 8, 16..., 64. Біти, що залишилися, перемішуються підстановкою Р3.

Таблиця 1.13

Підстановка Р3

Вихід Р₃(К) представляється у вигляді Р₃(К) = С₀D₀, де С₀ - ліва половина D₀ - права.

2. Чергове значення С_іD_і обчислюється по схемі

С_i = L_i(С_i-1), D_i = L_i(D_i-1),

де L_i - циклічне зрушення вліво на одну позицію, якщо i = 1, 2, 9, 16. У решті випадків L_i - зрушення вліво на дві позиції.

3. На цьому етапі вихід перемішується підстановкою Р4.

Таблиця 1.14

Підстановка Р4

Дешифрування DES.

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

DES дозволяє використовувати для шифрування або дешифрування блоку одну і ту ж функцію. Єдина відмінність полягає в тому, що ключі повинні використовуватися в зворотному порядку. Тобто, якщо на етапах шифрування використовувалися ключі К₁, К₂, К₃, ..., K₁₆, то ключами дешифрування будуть K₁₆, K₁₅, K₁₄, ..., К₁. Алгоритм, який створює ключ для кожного етапу, також циклічний. Ключ зрушується направо, а число позицій зрушення рівне 0, 1,2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1.

Опис алгоритму RSA.

Система RSA використовується як для шифрування, так і для підпису.

Вона базується на односторонній функції з «лазівкою» (trapdoor function).

Ця система базується на наступних двох фактах з теорії чисел:

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

2) задача розкладання чисел виду п = pq (р і q - прості числа) на множники є дуже важкою, якщо ми знаємо тільки п, а р і q - великі числа (це так зване завдання факторизації).

Виберемо p і q - великі прості числа. Хай модуль n = pq, функція (n) = (p-1)(q-1) - функція Ейлера. Візьмемо довільне 1 е(n) таке, що
НОД(е, (n)) = 1. Тоді існує єдине 1 d (n) таке, що

ed(mod(n)) = 1. (1.1)

Система шифрування RSA - це система з відкритим ключем, де
е - відкритий, а d - секретний ключі, п - відоме. Якщо 0 x<n - це відкрите повідомлення, то криптограма отримується таким чином:

С = х(mod n).

Сторона, що отримала зашифроване повідомлення обчислює

х = С^d (mod n), причому х = х.

Доказ:

х = С^d (mod n) = х^ed (mod n)

Рівність (1.2.1) означає, що для деякого k

ed = k(n) + 1.

Звідси і iз теореми Ейлера слідує

x = x^{kц(n) + 1} (mod n) = x.

Те, що і потрібно було довести.

Розглянемо властивості системи RSA

1) Система шифрує і дешифрує інформацію коректно;

2) Зловмисник, що перехоплює всі повідомлення і що знає всю відкриту інформацію, не зможе знайти початкове повідомлення при великих р і q. Це пояснюється тим, що зловмисник знає тільки відкриті параметри n і e. Для того, щоб знайти d, він повинен знати значення (n) = (p - l)(q - 1), а для цього, у свою чергу, йому потрібно знати p і q. Взагалі кажучи, він може знайти p і q, розклавши n на множники, проте це важке завдання.

Одностороння функція у = x^е (mod n), що використовується в системі RSA, володіє так званою «лазівкою», що дозволяє легко обчислити зворотну функцію х = (mod n), якщо відоме розкладання n на прості множники. (Дійсно, легко обчислити (n) = (p - 1)(q - 1), а потім d = e^-1 (mod (n))) Якщо р і q невідомі, то обчислення значення зворотної функції практично неможливе, а знайти p і q по n дуже важко, тобто знання p і q - це «лазівка» або «потайний хід»). Такі односторонні функції з лазівкою знаходять застосування і в інших розділах криптографії.

Відзначимо, що для схеми RSA важливо, щоб кожен абонент вибирав власну пару простих чисел p і q, тобто всі модулі n для кожного учасника повинні бути різні (інакше один абонент міг би читати зашифровані повідомлення, призначені для іншого абонента). Проте цього не вимагається від другого відкритого параметра е. Параметр е може бути однаковим у всіх абонентів. Часто рекомендується вибирати е = 3 . Тоді шифрування виконується максимально швидко, всього за два множення.

Підпис RSA.

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

С = М(mod n),

тоді (М, С) - повідомлення з підписом. Перевірка підпису здійснюється таким чином

С( mod n) = М(mod n) = М.

Якщо М = М, то підпис вірний.

1.3. Методика визначення стійкості криптосистем

Є декілька різних критеріїв, які можна було б використовувати для оцінки якості пропонованої секретної системи. Розглянемо найбільш важливі з цих критеріїв.

1. Кількість секретності.

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

2. Обєм ключа.

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

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

4. Розростання числа помилок.

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

5. Збільшення обєму повідомлення.

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

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

Питання про теоретичну стійкість шифрів вперше було сформульоване Клодом Шенноном: «Наскільки надійна криптосистема, якщо криптоаналітик супротивника має в своєму розпорядженні необмежений час і всі необхідні засоби для аналізу криптограм?». З цим питанням тісно звязане наступне питання: «Чи існують шифри, які не міг би розкрити криптоаналітик, що має в своєму розпорядженні скільки завгодно велику криптограму і необмежені обчислювальні ресурси?».

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

Р_исх(а) = Р_исх/ш(а/у) (1.2)

за умови, що Р_у(у)>0, де

Р_исх(а) - розподіл імовірності на множині відкритих текстів;

Р_исх/ш(а/у) - сумісний розподіл імовірності на множині пар відкритих і шифрованих текстів;

Р_у(у) - розподіл імовірності на множині шифрованих текстів.

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

Розглянемо основні підходи до оцінки практичної стійкості шифрів.

Системний підхід.

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

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

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

Припустимо, що перед криптоаналітиком поставлене завдання дешифрування шифру Е по деякому набору криптограм. Хай А_Е - клас застосовних до шифру Е алгоритмів дешифрування, які має в своєму розпорядженні криптоаналітик. При цьому криптоаналітик розглядає як імовірнісний простір W елементарних подій множину пар ключів і відкритих текстів, якщо відкриті тести невідомі, або множуну ключів, якщо відкриті тексти відомі. Для алгоритму A_E позначимо через Т() середню трудомісткість його реалізації, вимірювану в деяких умовних обчислювальних операціях. При цьому величина трудомісткості звичайно усереднюється по множині W.

Однією з основних характеристик практичної стійкості шифру Е є середня трудомісткість Т_Е дешифрування, яка визначається виразом

Т_Е =Т(). (1.3)

При цьому важливо відзначити наступне:

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

Якщо надійність алгоритму дешифрування мала, то з погляду криптографа він є безпечним, а з погляду криптоаналітика неефективним. Таким чином, при отриманні оцінки (1.3.2) величини Т_Е доцільно розглядати лише ті алгоритми дешифрування, надійність яких достатньо велика. При цьому для визначення «найкращого» алгоритму дешифрування системи Е можна використовувати різні критерії залежно від конкретних умов завдання. Наприклад, можна вважати «найкращим» алгоритм дешифрування , для якого найменше значення приймає величина T()/(). Цю величину можна інтерпретувати як середні трудовитрати, необхідні для успішного дешифрування шифрсистеми.

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

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

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

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

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

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

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

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

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

Асимптотичний аналіз стійкості.

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

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

Оцінка кількості необхідного шифрматериалу.

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

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

Як приклад такого шифру розглянемо шифр Діффі. У цьому шифрі рандомізатором є масив з 2ⁿ випадкових двійкових послідовностей, занумерованих елементами множини V_n. Ключем є п-мірний двійковий вектор. При шифруванні з використанням ключа k двійкова послідовність відкритого тексту складається побітово з послідовністю рандомізатора, що має номер k. Таким чином, для дешифрування повідомлення супротивнику необхідно досліджувати порядка 2^п біт.

Вартісний підхід.

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

1.4. Криптопротоколи, їх класифікація, особливості використання

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

Властивості криптопротоколів:

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

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

- протокол повинен бути несуперечливим, кожна дія повинна бути визначена так, щоб не було можливості нерозуміння;

- ?протокол повинен бути повним, кожній можливі ситуації повинна відповідати певна дія.

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

В крипптопротоколах використовується загальне правило: «Неможливо зробити або дізнатися більше, ніж це визначене в протоколі».

Умови криптографічного завдання визначають особливості відповідного протоколу.

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

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

Але при реалізації цих протоколів існують деякі труднощі:

- Легко знайти нейтрального посередника, якому можна довіряти, якщо ви знаєте його і можете особисто його побачити. Дві сторони, що відносяться одна до одної з підозрою, з тією ж підозрою віднесуться і к посереднику, що загубився десь в мережі.

- Компютерна мережа повинна забезпечити підтримку посередника.

- Існує затримка, що властива всім протоколам із посередником.

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

- Через те, що в мережі всі повинні довіряти посереднику, він є слабким місцем мережі при спроби злому.

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

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

В ідеальному випадку будь-який протокол повинен бути самодостатнім, але, на великий жаль, не існує самодостатніх протоколів для кожної ситуації.

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

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

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

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

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

Як приклад роботи протоколу приведемо організацію секретного звязку з використанням симетричної криптосистеми. Діючими особами є відправник, адресат, пасивний супротивник та ін. Задача протоколу - передати таємне повідомлення Х від відправника до адресату. Послідовність виглядає наступним чином:

1. Відправник і адресат домовляються про використовувану симетричну криптосистему, тобто про сімейство відображень Е = , k К, де К - простір ключів.

2. Відправник і адресат домовляються про секретний ключ звязку k, тобто про використовуване відображення ЕЕ_к.

3. Відправник шифрує відкритий текст X за допомогою відображення Е_к, тобто створює криптограму Y = Е_к (Х).

4. Криптограма Y передається по лінії звязку адресату.

5. Адресат розшифровує криптограму Y, використовуючи той же
ключ k і відображення Е_к^-1, зворотне до відображення Е_к, і читає повідомлення X:

Х = Е_к^-1(Y).

Пояснимо важливі особливості даного протоколу за допомогою схеми, приведеної на рис. 1.4.

Крок 2 протоколу реалізується або за допомогою посередника, третьої сторони, яку можна умовно назвати центром генерації і розподілу ключів (ЦГРК), або функції ЦГРК покладаються на абонентів. У першому випадку криптографічний протокол звязку шифру називають трибічним, а в другому випадку - двостороннім.

Захищений

канал звязку

Х k k Х

Лінія звязку

Х

k

Рис. 1.4

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

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

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

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

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

1) криптоаналітик контролює лінію звязку;

2) криптоаналітику відомий пристрій сімейства Е відображень шифру;

3) криптоаналітику невідомий ключ k, тобто невідомо відображення Е_к, яке використане для отримання криптограми Y.

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

1. Визначити відкритий текст X і використаний ключ k по перехопленій криптограмі Y, тобто побудувати алгоритм дешифрування такий, що

( Y) = (Х, k).

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

(Х, Y) = к.

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

3. Визначити використовуваний ключ k по спеціально підібраному відкритому тексту X і по відповідному шифрованому тексту Y, тобто побудувати алгоритм дешифрування _Х такий, що

_Х(Y) = к.

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

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

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

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

Таким чином, по організації секретного звязку з використанням симетричної криптосистеми можна зробити наступні висновки:

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

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

3. Якщо допустити, що кожна пара користувачів мережі звязку
застосовує окремий ключ, то число необхідних ключів дорівнює
п(п-1)/2 для п користувачів. Це означає, що при великому п генерація, зберігання і розподіл ключів стає трудомісткою проблемою.

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

1. Відправник і адресат домовляються про використовувану асиметричну криптосистему.

2. Адресат посилає відправнику відкритий ключ k.

3. Відправник шифрує відкритий текст X за допомогою відкритого
ключа k, тобто створює криптограму Y = Е_k(X).

4. Криптограма Y передається по лінії звязку адресату.

5. Адресат розшифровує криптограму Y, використовуючи закритий ключ z, і читає повідомлення X:

X = Е_z(X).

Поза сумнівом, даний протокол захищає повідомлення X: пасивний супротивник може перехопити відкритий ключ і криптограму Y, але не може розшифрувати повідомлення, оскільки немає закритого ключа.

Гідністю протоколу є те, що він не вимагає розподілу секретних ключів. У мережі звязку нерідко відкриті ключі всіх користувачів поміщаються в загальнодоступну базу даних, а закриті ключі зберігаються у користувачів. Це спрощує протокол, оскільки відправник сам виконує крок 2 протоколи, не чекаючи дії адресата. Адресат не бере участь в протоколі до тих пір, поки не збереться прочитати відкрите повідомлення.

Висновки

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

На практиці алгоритми з відкритим ключем не замінюють симетричних алгоритмів. Як правило, вони використовуються для шифрування не самих повідомлень, а ключів або деяких інших «допоміжних» інформаційних блоків відносно невеликої довжини. Це викликано наступними обставинами:

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

2. Криптосистеми з відкритим ключем уразливі до атак на основі
підібраного відкритого тексту, особливо коли число варіантів блоку
відкритого тексту обмежене і допустимо перебір цих варіантів.

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

Розділ 2. Моделі елементів захищених систем

2.1. Поняття стійкості шифрсистеми

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

Щоб конкретизувати наші міркування, розглянемо «ігрову атаку», яка розігрується між Зловмисником і законним Учасником сеансу звязку. Ця гра дозволить продемонструвати обчислювальні аспекти, повязані з поняттям стійкості.

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

Ігрова атака описується наступним протоколом .

Попередні умови:

а) Зловмисник і законний Учасник діють в заданій криптосистемі, що складається з алгоритму шифрування , простору початкових повідомлень М і простору зашифрованих текстів С;

б) законний Учасник володіє фіксованим ключем шифрування k.

1. Зловмисник підбирає різні повідомлення m₀, m₁ М і посилає їх учаснику. Повідомлення m₀, m₁ називаються підібраним початковим текстом (chosen plaintext messages). Зловмисник поки знаходиться на етапі пошуку ("find-stage") повідомлень m₀, m₁. Зрозуміло, він готує їх так, щоб легко розпізнати результат їх шифрування.

2. Якщо ці повідомлення мають різну довжину, Учасник доповнює коротше з них, щоб їх довжини стали однаковими. Наприклад, для доповнення повідомлень він може використовувати фіктивний рядок 0^d, де d - різниця між довжинами повідомлень. Учасник підкидає ідеальну монету b{0,1} і виконує наступну операцію шифрування

с* =

Учасник посилає Зловмиснику повідомлення с* С. Зашифроване повідомлення с* називається зашифрованим текстом оклику (challenge ciphertext). Слід памятати, що зашифрований текст с* є випадковою величиною, залежною від двох випадкових вхідних величин: ідеальної монети b і внутрішньої випадкової операції алгоритму .

3. Одержавши зашифрований текст с*, Зловмисник повинен вгадати результат підкидання монети, надіславши учаснику 0 або 1. Тепер Зловмисник знаходиться на етапі осмисленого вгадування ("guess-stage" for an educated guess), намагаючись вгадати результат жеребкування, проведеного учасником. Відповіді, що відрізняються від 0 і 1, не допускаються.

У цій грі учасник пропонує зловмиснику відповісти на наступне питання. Результатом якого з експериментів _k(m₀) чи _k(m₁) є оклик с*?

Вважатимемо, що Зловмисник застосовує імовірнісний поліноміальний алгоритм розпізнавання. Позначимо через Adv перевагу Зловмисника, з яким він може розпізнавати відмінність між зашифрованими текстами. Вона дорівнює різниці між ймовірностями, з якими Зловмисник може розпізнати експерименти _k(m₀) чи _k(m₁).

Adv = | Prob[0 Зловмисник(с* = _k(m₀))] - Prob[0 Зловмисник(с* = =_k(m₁))]|. (2.1)

Імовірнісний простір повинен містити випадковий вибір, зроблений Учасником і Зловмисником, а також внутрішню випадкову операцію алгоритму шифрування. Відзначимо, що відповідь Зловмисника залежить не тільки від зашифрованого тексту оклику с*, але і від двох підібраних початкових повідомлень (m₀, m₁). Тільки тому його відповідь можна вважати результатом «осмисленого вгадування» («educated guess»).

Слід відмітити, що Зловмисник має додаткову можливість для того, щоб поліпшити результати свого вгадування: Учасник підкидає ідеальну монету. Формула обчислення переваги (2.1.1) не указує явно на те, як Зловмисник може скористатися цим фактом, хоча неявно відомо, що кожна з імовірності, що входить у формулу (2.1.1), ніколи не перевищить , наприклад, імовірность події с* = _k(m₀) складає рівно . Необхідно явно вказати, як саме Зловмисник використовує додатковий ключ у формулі обчислення переваги. Застосовуючи умовну імовірность і помічаючи, що імовірность обох результатів при підкиданні ідеальної монети рівна , можна переписати формулу (2.1.1) в наступному вигляді

Adv = |Prob[0 Зловмисник(с* = _k(m₀))] -

- Prob[0 Зловмисник(с*=_k(m₁))]|. (2.2)

Згідно з правилами гри Зловмиснику не дозволяється давати відповіді, які відрізняються від 0 та 1, тому неправильна відповідь є подією, додатковою по відношенню до правильної відповіді. З цього випливає наступна формула

Adv = |Prob[0 Зловмисник(с* = _k(m₀))] -

- (1 - Prob[0 Зловмисник(с*=_k(m₀))] )|.

Тобто

Prob[0 Зловмисник(с* = _k(m₀))] = Adv. (2.3)

Формула (2.3) часто застосовується для виразу переваги алгоритму при вгадуванні результатів підкидання ідеальної монети. Отже, якщо Adv = 0, то випадкова відповідь Зловмисника має такий самий розподіл, як і результати підкидання ідеальної монети. Проте слід враховувати, що перевага завжди більше нуля. Очевидно, що формула (2.1.3) також справедлива, якщо в результатах жеребкування всі нулі замінити одиницями.

З формули (2.3) виходить, що перевага Зловмисника ніколи не перевищує , оскільки імовірність завжди лежить в інтервалі [0,1]. Дійсно, якщо Учасник шифрує обидва початкові тексти з імовірністю , перевагу Adv, що задана формулою (2.1), є різниця імовірності сумісних подій і ніколи не перевищує . Можна відмітити, що формула (2.1.3) виглядає так, ніби Учасник підкидає несиметричну монету, наприклад, Учасник з імовірністю шифрує повідомлення m