Xreferat.com » Рефераты по информатике и программированию » Розробка імовірнісної моделі криптографічних протоколів

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

М = DA(DB(EA(EB(M)))) = DB(DA(EB(EA(M)))). (2.4)

Іншими словами, вихідне повідомлення можна відновити шляхом подвійного розшифрування незалежно від порядку шифрування.

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

Протокол чесної роздачі карт при грі в уявний покер.

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

А і Б погодили комутативний шифр, що володіє властивістю (2.4), і згенерували свої секретні ключі шифрування. Колода складається з трьох карт: М1, М2 і М3.

Мета:

Чесна роздача по одній карті кожному гравцю за правилами 1 – 4 .

1. А шифрує три карти таким чином: Сі = ЕА( М), де і = 1,2,3. Він посилає Б ці три зашифровані тексти у випадковому порядку. (Передача зашифрованих текстів у випадковому порядку еквівалентна перетасовуванню колоди.)

2. Б випадковим чином витягує один із зашифрованих текстів. Позначимо його через С. Потім він двічі шифрує його як СС = ЕВ( С), випадковим чином витягує інший текст, позначений як Сў , і посилає зашифровані тексти СС і Сў А. ( Символи СС позначають карту, що належить Б , а символ Сў - карту, видану А. Зашифрована карта, що залишилася, ігнорується.)

3. А розшифровує тексти СС і Сў. Результат розшифрування тексту Сў позначає його карту, а розшифрування тексту СС, що позначається як Сўў , - карту Б. Текст Сўў повертається Б.

4. Б розшифровує текст Сўў і узнає свою карту.

Аналіз стійкості.

Після виконання протоколу складається наступна ситуація.

• Оскільки на першому кроці А тасує колоду, обидва гравці з однаковою імовірністю одержують одну з карт, що належать множині {M1, M2, M3}. Потрібно звернути увагу на те, що А прагне добре перетасувати колоду, щоб Б не одержав переваги. Отже, перша умова чесної роздачі виконана.

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

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

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

Хай N - загальний модуль в криптосистемі RSA. А і Б знають розкладання числа N на множники. Позначимо через (еА, dA) показники ступенів, використані при шифруванні і розшифруванні А, а через (еВ, dВ) – показники, що вживаються Б. Знання розкладання числа N на прості множники дозволяє А (Б) знайти число еА по заданому числу dA (число еВ – по заданому числу dВ) за допомогою порівняння

еХ dХ = 1(mod j(N)) (2.5)

де символ X позначає гравця А або В, j(N) – функція Ейлера. Для користувача X одержуємо наступні формули.

ЕХ( М)=Розробка імовірнісної моделі криптографічних протоколів( mod N),

DХ( М)=Розробка імовірнісної моделі криптографічних протоколів ( mod N).

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

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


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


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

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

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

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

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

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

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

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

ДВП породжує тексти у відповідності з правилами граматики деякої мови, що знаходить відображення і в статистичних характеристиках повідомлень. Наприклад у текстах на англійській мові за літерою 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}.

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

Р(а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, В}) виявляється стійким протоколом аутентифікації, що виконується користувачами А і В, якщо імовірність виграшу Зловмисника дуже мала. Тут виграш Зловмисника означає, що обидва користувача приймають позитивне рішення, хоча між ними немає узгоджених діалогів.


Висновки


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

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


3.1. Методика оцінки стійкості


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

1. Формальна поведінка учасників протоколу і атакуючого алгоритму: моделювання, як правило, здійснюється за допомогою атакуючої гри, в якій беруть участь атакуючий алгоритм і об'єкт атаки.

2. Формальне визначення стійкості: перемога атакуючого алгоритму в атакуючій грі звичайно виражається через (значущу) ймовірність і оцінку (розумної) тимчасової складності.

3. Формальна демонстрація існування поліноміальної редукції, що зводить атаку до рішення задачі, що важко вирішується, як правило, має вид математичної теореми.


3.2. Приклади доказу стійкості деяких протоколів на основі їх імовірнісних моделей


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

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

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

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

Розглядаючи ІР-протоколи, необхідно вивчити два питання.

Питання 1. Скільки інформації одержить сторона, що перевіряє в ході інтерактивного доказу?

Питання 2. Скільки раундів повинна виконати сторона, що доводить, щоб переконати сторону, що перевіряє?

Ідеальною відповіддю на перше питання був би "аніскільки", або "нуль". ІР-протокол, що володіє такою властивістю, називається протоколом з нульовим розголошуванням або ZК-протоколом (zero-knowledge). Друге питання важливе не тільки для практичних застосувань, але і для теорії обчислювальної складності, оскільки рішення цієї проблеми пов'язане з отриманням нижчої оцінки складності.

Розглянемо обчислювальну модель інтерактивної системи доказу, яку запропонували Голдвассеср, Мікаплі і Раков. Позначимо основну модель протоколу інтерактивного доказу через (Р, V), де Р – сторона, що доводить (prover), а V – сторона, що перевіряє (verifier). Як правило, протокол (Р, V) призначений для перевірки приналежності певного речення мові, заданій над алфавітом {0, 1}.

Хай L – мова над алфавітом {0,1}. Сторони Р і V одержують зразок хОL, що є загальними вхідними даними. Доказ приналежності зразка позначається як (Р, V)(х). Обидві сторони протоколу пов’язані каналом зв’язку, через який вони обмінюються інформацією.

a1, b1, a2, b2,…, al, bl.

Ця послідовність повідомлень називається стенограмою доказу. У стенограмі доказу дані, що передаються користувачем Р, називаються стенограмою сторони, що доводить. Вони чергуються з даними, що передаються користувачем V, які називаються стенограмою сторони, що перевіряє. Як загальна довжина стенограми доказу l , так і довжина кожної стенограми |аі|, |bi| (i = 1,2...,l) обмежена поліномом, що залежить від параметра |х|. Доказ приналежності зразка (Р, V)(х) мові L також повинен бути обмежений поліномом, який залежить від об'єму вхідних даних |х| .

Результат роботи протоколу записується у вигляді

(Р, V)(х) О { Прийняти, Відхилити}.

Ці два значення означають, що сторона, що перевіряє або підтверджує, або спростовує твердження хОL , висловлене стороною, що доводить Р. Оскільки система (Р, V) є імовірнісною, при кожному х результат (Р, V)(х) є випадковою величиною, залежною від загальних вхідних даних х, закритих вхідних даних (рrivate input) користувача Р і деяких випадкових вхідних даних (random input), загальних для користувачів Р і V. Більш того, елементи стенограми доказу також є випадковими величинами.

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

Дамо визначення протоколу інтерактивного доказу.

Хай L - мова, задана над алфавітом {0,1}. IР-протокол (Р,V) називається системою інтерактивного доказу для мови L, якщо

Ргоb[(Р, V)(х) = Прийняти | х ОL] і , (3.1)

Ргоb[(Р’, V)(х) = Прийняти | х П L] Ј , (3.2)

де числа  і  є константами, що задовольняють умовам

ОРозробка імовірнісної моделі криптографічних протоколів,  ОРозробка імовірнісної моделі криптографічних протоколів.

Імовірнісний простір складається зі всіх вхідних значень протоколу (Р, V) і всіх випадкових вхідних даних користувачів Р і V.

Оцінка (3.1) характеризує повноту протоколу (Р,V). Величина називається імовірністю повноти протоколу (Р, V). Це означає, що якщо хОL, то сторона, що перевіряє, V приймає припущення х з імовірністю, яка не менше величини .

Оцінка (3.2) характеризує несуперечність протоколу (Р,V). Величина називається імовірністю суперечності протоколу (Р,V). Це означає, що якщо хПL, то сторона, що перевіряє, V приймає припущення х з імовірністю, що не перевищує величини .

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

Розглянемо введені поняття на прикладі протоколу інтерактивного доказу приналежності підгрупі (Протокол 3.1) .

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

1. ƒ: однонаправлена функція, визначена в групі Zn і задовольняюча гомоморфній умові:

"х, уО Zn : ƒ (х + у) = ƒ (х) ƒ (у).

2. Х = ƒ (z) для деякого zО Zn .

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

z < n.

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

Х Об ƒ(1)с, тобто елемент Х породжується елементом ƒ (1).

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

1. А генерує число k ОZn, знаходить число Сommit ¬ƒ(k) і посилає його Б.

2. Б генерує число Challenge О {0,1} і посилає його А.

3. А обчислює число Response ¬Розробка імовірнісної моделі криптографічних протоколів і посилає його Б.

4. Б перевіряє значення ƒ (Response)≟Розробка імовірнісної моделі криптографічних протоколів

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

Б приймає доказ.

У цьому протоколі А є стороною, що доводить, а Б стороною, що перевіряє. Загальними вхідними даними А і Б є число X = ƒ (z), де функція ƒ є однонаправленою і гомоморфною функцією, заданою над групою Zn. Твердження про приналежність формулюється А і виглядає таким чином: X О { ƒ (x) | х ОZn}.

Закритими даними А є елемент zО Zn – прообраз елементу X при однонаправленому і гомоморфному відображенні ƒ.

В даному протоколі обидві сторони вступають в контакт т разів і створюють наступну стенограму доказу.

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

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

Повнота.

Оцінка імовірності повноти протоколу виконується, причому  = 1, оскільки відповіді А завжди успішно проходять перевірку у Б, тобто

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

при будь-якому виборі випадкового числа Сhallenge О {0,1}.

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

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

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

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

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

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

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

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

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

• Вибирає випадкове число Response ОZn.

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

• Обчислює число Commit ¬Розробка імовірнісної моделі криптографічних протоколів

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

Якщо функція ƒ є гомоморфізмом, то ƒ(х) = ƒ(1)х для всіх х О Zn. Отже, в протоколі А доводить своє знання дискретного логарифма числа X по підставі ƒ(1). Цей протокол називається «доказуванням приналежності підгрупі», оскільки

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: