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

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

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

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

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

Імовірнісна модель ключової множини використовується крип-тоаналітіком для аналізу статистичних властивостей криптосистеми. Імовірнісна модель визначається, зокрема, завданням імовірнісного розподілу на ключовій множині, яка розглядається як простір елементарних подій. Кожному ключу kK ставиться у відповідність імовірність 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. Математична модель криптографічного протоколу

Несуперечливість.

Протокол є несуперечливим.

Оцінимо імовірність суперечності d.

Результат перевірки, що виконується Б на етапі 4, залежить від випадкового числа Сhallenge після отримання числа Соmmit від А. Перевірка завершується успішно в двох випадках.

Варіант 1: Challenge = 0: Б бачить, що А відомий прообраз числа Commit.

Варіант 2: Challenge = 1: Б бачить число

прообраз(Х)= Response - прообраз(Commit)(mod n).

Оскільки сторона А не може передбачити випадковий вибір Б після отримання передачі, якщо число, що передається не дорівнює одиниці, вона повинна знати прообраз(Commit), а значить, і прообраз(Х).

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

* Вибирає випадкове число Response --Zn.

* Вгадує число Challenge.

* Обчислює число Commit

Очевидно, що на кожному кроці Б може відкинути помилковий доказ з імовірністю 1/2. Отже, імовірність суперечності (тобто імовірність успішного обману) рівна d = 1/2. Якщо протягом m ітерацій Б жодного разу не відкинув доказ, імовірність успішного обману не перевершує 2-m. Успішний обман стане практично неможливим, якщо число m достатньо велике, тобто число 2-m є дуже малим.

Якщо функція ѓ є гомоморфізмом, то ѓ(х) = ѓ(1)х для всіх х ?Zn. Отже, в протоколі А доводить своє знання дискретного логарифма числа X по підставі ѓ(1). Цей протокол називається «доказуванням приналежності підгрупі», оскільки ця назва має більш загальний характер. Слід підкреслити, що огd[ѓ(1)] є секретним дільником числа n, тобто в загальному випадку елемент ѓ(1) не породжує групу що складається з п елементів. Як правило, Б не може безпосередньо перевірити приналежність елемента підгрупі, не вдаючись до допомоги А.

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

Ln = ѓ(x) = ѓ(1)x

є циклічною групою (оскільки вона породжується елементом ѓ(1)), Б нелегко перевірити умову # Ln ? n. Для цього він повинен розкласти число п на прості множники. Б може відповісти ТАК, не вступаючи в контакт з А, тільки якщо #Ln = п (оскільки число ѓ(1) повинно породжувати всі п елементів множини Ln). Таким чином, завдання про приналежність елементу підгрупі зводиться до факторизації великого цілого числа. Отже, щоб затруднити рішення цієї задачі, ціле число п в протоколі повинне бути достатньо великим. Саме з цієї причини параметр безпеки в протоколі повинен мати довжину log n.

Нульове розголошування.

Припустимо, що на Питання 1 існує ідеальна відповідь (Р, V) - протокол з нульовим розголошуванням, тобто користувач V переконується у коректності твердження користувача Р, не дізнавшись нічого нового про закриті вхідні дані.

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

Для будь-якого речення х L виконання протоколу (Р, V)(х) приводить не тільки до виведення результату Прийняти, але і породжує стенограму доказу, в якому чергуються елементи стенограм сторони, що доводить і сторони, що перевіряє. Елементи стенограми доказу є випадковими величинами, що залежать від всіх вхідних даних, включаючи випадкові вхідні дані протоколу (Р, V).

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

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

Доведемо тепер, що протокол, який ми вище розглянули є ідеальним ZК-протоколом.

Стенограма доказу, створена при виконанні протоколу (А, Б)(Х), виглядає таким чином.

Commit1, Challenge1, Response1,..., Commitm, Challengem, Responsem,

де для і = 1,2..., m виконуються наступні умови.

* Commitі = ѓ(ki), де ki Zn.

Очевидно, оскільки сторона А витягує числа ki з рівномірно розподіленої генеральної сукупності, величини Commitі також рівномірно розподілені по простору значень функції ѓ і не залежать від загальних вхідних даних Х.

* Challengei {0,1}.

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

* Responsei = ki + z Challenge(mod n).

Очевидно, що завдяки рівномірному розподілу чисел ki, величина Responsei рівномірно розподілена по групі Zn при всіх значеннях Challengei {0,1} (навіть якщо Challenge не є рівномірно розподіленою випадковою величиною) і не залежить від загальних вхідних даних Х.

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

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

Протокол ідентифікації Шнорра.

В протоколі, який ми вище розглянули сторона Б використовує біти оклику. Це призводить до великої імовірності суперечності протоколу: д = 1/2. Отже для того, щоб зменшити помилку до 2-m необхідно повторити протокол m разів. Для запобігання шахрайства з боку А достатньо прийняти m = 100. Але необхідність великої кількості раундів знижує ефективність протоколу.

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

Загальні вхідні дані.

p, q: два простих числа, що задовольняють умові q | p - 1.

(Типовий розмір: | p | = 1024, |q| = 160.)

g : огdp(g)= q;

y : y = g-a (mod р).

( Кортеж (р,q,g,у) складається з параметрів відкритого ключа сторони А,

сертифікованого органом авторизації.)

Закриті вхідні дані сторони А:

а < q.

Висновок сторони Б :

А відомий деякий елемент а Zq, що задовольняє умові

у ? g-a(mod р).

Наступні кроки виконуються 1оg2 1оg2 р разів.

1. А генерує число k Zn, знаходить число Соmmit gk(mod р) і посилає його Б.

2. Б генерує число Сhallenge і посилає його A.

3. A обчислює значення Responsе k + a Сhallenge(mod p) і надсилає його Б.

4. Б перевіряє число Соmmit = gResponse yChallemge(mod p).

Якщо перевірка завершується невдало, сторона Б посилає відмову і припиняє роботу протоколу. Сторона Б ідентифікує сторону А.

Цей протокол є різновидом попереднього протоколу, в якому функція ѓ(х) реалізується за допомогою операції g-x(mod p) над кінцевим полем Fр, де підгрупа g має простий порядок q | р - 1. Легко, бачити, що функція g-x(mod p) є гомоморфною. Більш того, для достатньо великих простих чисел q і р, наприклад |р| = 1024, | q | = 160, функція g-x(mod p) є однонаправленою.

При такому виборі параметрів Б може використовувати злегка збільшені оклики, що складаються з log2 log2 p біт.

Оскільки умова q | р - 1 накладається явно, протокол ідентифікації Шнорра більше не повинен вирішувати задачу про приналежність елементу певній підгрупі. Тепер Б може самостійно визначити, чи належить елемент у підгрупі g, не вдаючись до допомоги сторони А: уq ? gq ? 1(mod р). Отже, протокол ідентифікації Шнорра призначений для вирішення конкретнішого завдання: чи знає сторона А дискретний логарифм числа у по підставі g, що є її криптографічним мандатом.

Проаналізуємо стійкість даного протоколу.

Повнота.

Ця властивість виконується тривіальним чином, причому е = 1.

Несуперечність.

Припустимо, що сторона А' шахраює, тобто не знає правильне значення дискретного логарифма. Одержавши число Commit від А, сторона Б генерує число Challenge і чекає відгуку.

Response = logg [Commit*yChallenge(mod p)] (mod q).

Це рівняння демонструє, що при заданих числах Commit і у існують log2 р різних значень Response, що відповідають log2 р різним значенням Challenge. При невеликій величині log2 р найкращою стратегією обчислення правильної відповіді по величині Commit*yChallenge(mod p) є вгадування числа Challenge перед фіксацією числа Commit.

1. Генеруємо число Response Zq.

2. Вгадуємо значення Сhallenge .

3. Обчислюємо величину Соmmit = gResponse yChallemge(mod p).

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

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

При р 21024 i m = 100 одержуємо l = 100/10 = 10. Інакше кажучи, збільшення довжини оклику скорочує кількість ітерацій в порівнянні з попереднім протоколом в 10 разів при тій же імовірності суперечності.

Ефективність раунду.

Розглянемо друге питання, сформульоване в розділі 3.1: скільки раундів необхідне для того, щоб сторона, що доводить, переконала в своїй правоті сторону, що перевіряє? Це питання про так звану ефективність раунду. Раундом називається повний цикл дій, пов'язаних з відправкою і отриманням повідомлень. Оскільки багато ZК - (і IР) протоколів складаються із обчислень величин Commit(перший крок учасника Р), Challenge (другий крок учасника V), Response (другий крок учасника Р), ми часто називатимемо раундом саме ці три дії.

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

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

Сформулюємо питання таким чином.

Чи можна поліпшити ефективність протоколу 3.1, збільшивши розмір оклику, що генерується стороною Б, як це зроблено в протоколі ідентифікації Шнорра, якщо ѓ(х) = gх(mod N) і стороні A відоме розкладання складеного цілого числа N на прості множники?

Нагадаємо, що, наприклад, в протоколі ідентифікації Шнорра ми трохи збільшили довжину оклику: Challenge. В результаті ефективність протоколу підвищилася: замість m раундів, передбачених в протоколі 3.1, для доказу виявилось достатньо виконати раунди, причому імовірність суперечності не змінилася.

На жаль, якщо А знає розкладання числа N на прості множники, такий прийом стає неможливим. Проблема полягає не в нульовому розголошенні. Вона пов'язана з імовірністю суперечності. Імовірність суперечності даного протоколу рівна д = 1/2 незалежно від довжини оклику.

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

Отже, опишемо протокол з нульовим розголошуванням під назвою «Непридатний протокол», призначений для доказу приналежності елемента однієі з підгруп Zn. Цей протокол непридатний для використання на практиці. Він описується його лише для демонстрації ідеї.

Загальні вхідні дані:

велике складене ціле число;

g, у: два елементи групи Zn, де g має великий порядок по модулю N, а у = gz (mod N).

Закрита інформація сторони А:

ціле число z < (N).

Висновок сторони Б:

у g, тобто у ? gz (mod N) при деякому х.

1. A генерує число k Z(N), обчислює значення Commit gk (mod N )і посилає його Б.

2. Б генерує рівномірно розподілену випадкову величину Challenge < N і посилає її А.

3. А обчислює значення Response k + z Challenge(mod (N)) і посилає його Б.

4. Якщо gResponse = Commit*yChallenge(mod N), сторона Б приймає доказ, інакше вона його відкидає.

На перший погляд, оскільки розмір числа Challenge великий, стороні А нелегко його вгадати, і вона вимушена точно слідувати інструкціям протоколу, що зменшує імовірність несуперечності до величини д ? 1/(N). Якби це було правдою, то протокол складався б тільки з одного раунду. Але, на жаль, ця оцінка імовірності суперечності некоректна.

Знаючи факторизацію числа N, А може легко обчислити нетривіальний квадратний корінь одиниці, тобто елемент Я ZN, що задовольняє умовам Я ? ±1 Я2 ? 1(mod N).

Далі А обчислює загальні вхідні дані:

Y Яgz(mod N).

Замість обчислення значення Commit по інструкціях протоколу, сторона А підкидає монету b{0,1}, намагаючись вгадати парність оклику сторони Б. Потім вона обчислює величину Commit по наступній формулі.

Commit

В частині протоколу, що залишилася, сторона А повинна слідувати інструкціям.

Очевидно, що шанси правильно вгадати число Challenge рівні 1/2. Якщо сторона А правильно вгадала парний оклик Challenge = 2и, Б виконує наступну верифікацию.

gResponse ? gk gz2u ? Commit(Яg)z2u ? Commit YChallenge(mod N).

Значить, Б приймає доказ. Якщо сторона А правильно вгадала непарний оклик Challenge = 2и + 1, Б виконує верифікацію наступним чином.

gResponse ? gk gz(2u+1) ? Яgk (Я g)z(2u+1) ? Commit YChallenge(mod N).

Значить сторона Б знову повинна прийняти доказ.

Таким чином, незалежно від довжини оклику, імовірність суперечності рівна всього лише д = 1/2.

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

Використовуючи нетривіальний квадратний корінь одиниці по модулю N, A досягає максимальної імовірності угадування, що дорівнює д = 1/2. В тривіальному випадку Я = - 1 (інший тривіальний випадок Я = 1, в атаці не використовується) сторона Б може досягти більшої переконливості: або Y, або - Y належить підгрупі g. Проте, оскільки сторона А знає факторизацію числа N, а Б - ні, використовуючи китайську теорему про залишки, вона також може приховати число gk використовуючи інший множник малого порядку, наприклад, третього. Таким чином, імовірність суперечності не може бути дуже малою величиною.

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

Висновки

В цьому розділі були розглянуті імовірнісні моделі протоколів з нульовим розголошенням і на їх основі визначені стійкість цих крипторотоколів. Можна сказати, що задача І L (приналежності елемента підгрупі) є такою, що легко вирішується (відповідно такою, що важко вирішується), якщо існує (відповідно не існує) додаткова інформація, що полегшує роботу алгоритму. В процесі аналізу даних протоколів ми зробили висновок, що якщо стороні, що доводить відомий розклад складеного числа (N) на прості множники, то незалежно від довжини оклику (Challenge), імовірність суперечності рівна всього лише д = 1/2. Тобто для зменшення цієї імовірності в будь-якому випадку потрібно збільшити кількість раундів протоколу.

Розділ 4. Нормативно-правова база розробки, впровадження і експлуатації захищених систем

4.1. Структура нормативної бази

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

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

До загальних нормативно-правових актів належать:

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

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

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

Страницы: 1, 2, 3, 4