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

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

Доведемо тепер, що протокол, який ми вище розглянули є ідеальним 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 < f(N).

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

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

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

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

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

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

На перший погляд, оскільки розмір числа Challenge великий, стороні А нелегко його вгадати, вона вимушена точно слідувати інструкціям протоколу, що зменшує імовірність несуперечності до величини δ ≈ 1/f(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, 5, 6, 7, 8, 9, 10, 11