Розробка імовірнісної моделі криптографічних протоколів (стр. 11 из 19)
Р(а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),