Розробка імовірнісної моделі криптографічних протоколів (стр. 14 из 19)
При деяких параметрах безпеки імовірність суперечності протоколу можна понизити, що приведе до зменшення кількості необхідних раундів. Для цього сторона Б повинна знати розкладання числа п на прості множники. Особлива ситуація виникає, коли число п є простим. Розглянемо протокол ідентифікації Шнора.
Загальні вхідні дані.
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 log2p біт.
Оскільки умова 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).