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

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

2.3. Математичні моделі елементів криптографічних систем

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

Модел джерел відкритих текстів.

Детерміновані моделі.

Кожне джерело відкритого тексту (ДВП) характеризується:

1.  одним або декількома мовами спілкування;

2.  набором алфавітів, що використовуються;

3.  визначеною тематикою  повідомлень, що генеруються;

4.  частотними характеристиками повідомлень.

ДВП породжу тексти у відповідності з правилами граматики деякої мови, що знаходить відображення і в статистичних характеристиках повідомлень. Наприклад у текстах на англійській мові за літерою q завжди йде літера r, в російських текстах літери ь і ъ ніколи не слідують за голосними буквами. Взагалі кожну мову і кожне ДВП можна характеризувати розбиттям множини усіх k-грам, k = 2, 3,…, на допустимі (що зустрічаються в яких-небудь текстах) недозволені (що не зустрічаються в жодних текстах).

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

Імовірнісн моделі.

В імовірнісних моделях ДВП розглядається як джерело випадкових послідовностей.

Хай джерело генерує в алфавіті Zm текст кінцевої або нескінченно довжини. При цьому можна вважати, що джерело генерує кінцеву або нескінченну послідовність випадкових змінних х0, х1, …, хn-1, що приймають значення в Zm. Імовірність випадкового повідомлення (а0, а1,…, аn-1) визначається як імовірність тако послідовності подій:

Р(а0, а1,…, аn-1)= Р{ х0 = а0, х1 = а1,…, х n-1 = аn-1}.

Множина випадкових повідомлень утворює імовірнісний простір, якщо виконані умови:

1) Р(а0, а1,…, аn-1)³0 для будь-якого випадкового повідомлення

(а0, а1,…,аn-1);

2) = 1;

3) Для будь-якого повідомлення (ао, а1, ,аn-1) і будь-якого s > n  

Р(ао, а1, ,аn-1) = ,

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

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

Розглянемо таку імовірнісну модель ДВП, як стаціонарне джерело незалежних символів алфавіту.

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

Р(а0, а1,…, аn-1) =

де для всіх iÎ{0,1,…, n-1} і будь-якого aÎZm

P{xi = a}>0;  = 1.

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

Приведемо списки букв високої частоти використання для деяких європейських мов (табл. 2.3.1).

Таблица 2.1 Частота букв в різних мовах

Мова	Буква алфавіту/частота букви у текстах, %
Англійська	Е/ 12,86	Т/9,72	А/7,96	S/7,77	N / 7,51	К / 7,03
Іспанська	Е/ 14,15	А/ 12,90	О / 8,84	S / 7,64	S/7,01	К / 6,95

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

Італійська	І/12,04	Е/11,63	А/11,12	О/8,92	N/7,68	Т / 7,07
Німецька	Е/ 19,18	N1/ 10,20	S/8,21	S/7,07	К/7,01	Т/5,86
Французьська	Е/ 17,76	S / 8,23	А/7,68	N/7,61	Т / 7,30	I/7,23
Російська	О / 11,0	И/8,9	Е/8,3	А/7,9	Н / 6,9	Т/6,0

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

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

Імовірнісна модель ключової множини.

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

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

1)  для чергового періоду експлуатації (сеансу, доби, і т. п.) кожен ключ вибирається випадково рівноймовірно з ключової множини K, тобто pk = 1/|K| для будь-якого kÎК;

2)  при зміні ключів новий ключ вибирається незалежно від попередніх.

Імовірнісна модель шифру.

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

Рвідкр – р. й. на множині відкритих текстів;

 Ркл  - р. й. на множині ключів;

Рш  - р. й. на множині шифрованих текстів;

 Рвідкр,к  - сумісний р. й. на множині пар відкритих текстів і ключів;

 Рвідкр,ш – сумісний  р. й. на множині пар відкритих і шифрованих текстів;

 Рвідкр/ш  - умовний р. й. на множині відкритих текстів (при умові, що шифрований текст фіксований).

Хай а – відкритий текст, z – ключ, y шифрований текст, Е(а, z) - криптограма, одержана в результаті шифрування відкритого тексту а на ключі z.

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

Рвідкр,к(a, z) = Рвідкр(a) Ркл(z).

Сумісн умовні р. й. визначаються із формул:

Рш(y) = ,

Рвідкр,ш = ,

Рвідкр/ш = Рвідкр,ш(a,y)/ Рш(y),

де остання рівність витікає з визначення умовної імовірності і справедливо за умови Рш(y)>0.

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

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

2.4. Математична модель криптографічного протоколу

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

1k – Параметр безпеки k Î N.

i – Ідентифікатор  користувача i Î I , що викону дану частину протоколу. Називатимемо цього користувача "власником". Множина I складається з користувачів, що володіють одним і тим же довготривалим ключем.

j – Ідентифікатор партнера, з яким спілкується власник; j Î I.

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

сonv – Попередн повідомлення – conv (від англ.: conversation ), що рядком бітів. Цей рядок збільшується у міру виконання протоколу, причому новий рядок приписується до старого.

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

Оскільки P(1k,i,j,K,conv,r) ма поліноміальну складність, залежну від розміру аргументів (відзначимо, що розмір параметра k рівний 1k), можна вважати, що аргументи K і r мають розмір k, а розмір аргументів i, j і conv поліноміальнo залежить від параметра k.

Значеннями функції P(1k,i,j,K,conv,r) є три числа.

m – Наступне повідомлення, що підлягає відправці, - m Î {0,1}*  {"повідомлень немає"}. Це – відкрите повідомлення, що підлягає відправці адресату через відкриту мережу.

δ – Рішення користувача – δ Î { Прийняти, Відмовити, Не приймати рішення}. Користувач вирішує, прийняти або відкинути ідентифікатор партнера по переговорах, або не ухвалювати рішення взагалі. Прийняття ідентифікатора, як правило, відкладається до завершення протоколу, а відхилити його можна у будь-який момент. Якщо користувач ухвалює яке-небудь певне рішення, значення δ більше не змінюється.

α – Закритий результат, обчислений власником, - α Î {0,1}*  {"результату немає"}. Можна вважати, що закритим результатом, обчисленим власником при сприятливому результаті протоколу, є узгоджений сеансовий ключ.

Діалог між цими користувачами є послідовністю впорядкованих в часі повідомлень, що посилаються ними в мережу, і одержуваних на них відповідей. Хай t1 < t2 < …<tR ,(де R – деяке позитивне ціле число) – моменти часу, в які  користувач і посилає повідомлення. Діалог можна позначити таким чином.

conv =( t1, m1, m’1), (t2, m2, m’2),…, (tR, mR, m’R).

Цей запис означає, що у момент t1 користувач і одержу запит m1 і посилає у відповідь повідомлення m’1. Потім у момент t1> t2 користувач і одержує запит m2 і посилає у відповідь повідомлення m’2 і так далі, поки у момент tR він не одержить запит mR і пошле у відповідь повідомлення m’R.

Нагадаю, що в даній моделі користувач будь-який запит повинен вважати повідомленням від Зловмисника, поки в якийсь момент tR він не прийме позитивне рішення. Зручно припустити, що діалог починає Зловмисник. Отже, якщо m1 = “”, називатимемо користувача і ініціатором діалогу, інакше відповідачем.

Хай

conv = (t0, , m1), (t2, m’1, m2), (t4, m’2, m3),…, (t2t-2, m’t-1, mt)

 позначає діалог користувача і . Користувач j веде діалог conv', узгоджений з діалогом conv, якщо існує послідовність моментів часу t0 < t1 < t2 <tR, така що

conv’ = (t1, m1, m’1), (t3, m2, m’2), (t5, m3, m’3),…, (t2t-2, mt, m’t),

де рядок m’t  означає "немає повідомлень".

Якщо користувачі i і  j ведуть узгоджені діалоги, то Зловмисник не в змозі організувати небезпечну атаку і вимушений грати роль нешкідливого супротивника.

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

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11