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

3. А обчислює число Response ¬ і посилає його Б.

4. Б перевіряє значення ƒ (Response)≟

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

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

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

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

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

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

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

Повнота.

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

ƒ (Response)=

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

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

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

Оцінимо імовірність суперечності 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 | х Î Zn}

є циклічною групою (оскільки вона породжується елементом ƒ(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.


Информация о работе «Розробка імовірнісної моделі криптографічних протоколів»
Раздел: Информатика, программирование
Количество знаков с пробелами: 142838
Количество таблиц: 20
Количество изображений: 5

Похожие работы

Скачать
58706
1
7

... захисту необхідно виявити можливі погрози безпеці інформації, оцінити їх наслідки, визначити необхідні заходи і засоби захисту і оцінити їх ефективність. [25] 1.3 Криптографічні методи захисту інформації   Криптографічний захист інформації — вид захисту інформації, що реалізується за допомогою перетворень інформації з використанням спеціальних даних (ключових даних) з метою приховування (або ...

Скачать
367716
10
48

... В АБС АКБ «ПРОМІНВЕСТБАНК» ТА ОЦІНКА РІВНЯ ВРАЗЛИВОСТІ БАНКІВСЬКОЇ ІНФОРМАЦІЇ 3.1 Постановка алгоритму задачі формування та опис елементів матриці контролю комплексної системи захисту інформації (КСЗІ) інформаційних об’єктів комерційного банку В дипломному дослідженні матриця контролю стану побудови та експлуатації комплексної системи захисту інформації в комерційному банку представлена у вигляді ...

Скачать
114386
2
2

... передбаченою. 3. Генерація гамми не повинна бути дуже трудомісткою. Слід зазначити, що алгоритми криптосистем з відкритим ключем (СВК) можна використовувати за трьома напрямками: 1. Як самостійні засоби захисту даних, що передаються чи зберігаються. 2. Як засіб для розподілу ключів. Алгоритми СВК більш трудомісткі, ніж традиційні криптосистеми. Обмін великими інформаційними потоками здійснюють ...

Скачать
294342
0
0

... ональних інтересів та безпеку інформаційного простору. Підсумки: В цьому розділі ми з’ясували, які саме зміни всередині урядових організацій, в їх структурі, функціях і методах роботи ініціює запровадження електронного уряду. А саме: відбувається перенесення акцентів з вертикальних на горизонтальні зв’язки всередині уряду, між різними його підрозділами і гілками влади. За рахунок створення внутрі ...

0 комментариев


Наверх