Основи теорії захисту інформації: Конспекти лекцій № 1-32 (Введення в криптологію, основні поняття і визначення. Проблеми теорії і практики криптології), страница 33

3.Приклади протоколів.

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

2)  Протокол голосування по електронному каналі зв'язку. Кожен голосуючий хоче забезпечити таємність голосування, не підробленість і правильність підрахунку результатів голосування.

3)  Протокол “підкидання монети ” по електронному каналі зв'язку. Сутність: сторона А підкидає монету (орел чи решка), а сторона У вгадує по каналі результат підкидання, сторона В хоче мати гарантію, що А не відмовиться від отриманого результату.

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

5)  Римський протокол. Є n об'єктів та суб'єктів, а також k – деяких центрів. Центри можуть управляти об'єктами та суб'єктами. Як центри так і деяка частина об'єктів та суб'єктів можуть бути зловмисниками.

Як необхідно реалізувати протокол їх взаємодій щоб система була у виграші?

Розв'язку практично немає.

Приклад реального протоколу підкидання монети по каналі зв'язку.

Є А та В. Реалізуємо підкидання монети.

А підкидає і у результаті має деякі твердження х. Об’єкт У вгадує це твердження і винний передати по каналі зв'язку результат вгадування. Як реалізується протокол, щоб А не відмовився від х, якщо В його вгадає?

Нехай є однобічна функція: f(x)=y, яка має поліноміальну складність, тобто якщо х має розмір n, те складність обчислюється як:

 

Процедура знаходження х = , повинна бути експоненціальною(чи суб експоненціальною). Складність:

 ,

де n_i-розмір вхідних даних.

Голосування:

Сторона А розраховує  f(x)=y і посилає В, сторона В запам’ятовує в і формує деяке : посилає його стороні А. Сторона А фіксує  і посилає В значення х.

Сторона В, знаючи функцію від f (х), розраховує в: f(x)=y.

Якщо після порівняння розрахованого стороною В результату f (х) і присланого результату від А  f (х), ці результаті співпадають – голосування завершене.

Для арбітражу сторони А і В всі раунди повинні запам'ятовувати і це має здійснюватись автоматично без можливості будь якої корекції.

Лекція № 27

Приклади слушних протоколів.

1.  Модель інтерактивного та з нульовими знаннями протоколу.

2.  Загальний протокол автентифікації (Шнорра).

3.  Протокол типу “Цифровий Підпис”.

4.  Сутність протоколу розподілу секрету.

1. Модель інтерактивного та з нульовими знаннями протоколу.

У протоколі з нульовими знаннями та інтерактивному протоколі, деякий суб'єкт А знає твердження S і він хоче довести В, що S – істина.

Не розголошуючи, наприклад, у протоколі з нульовими знаннями , чому S – істина. Наприклад: А знає доведення деякої теореми, але він не хоче розголошувати зміст доведення теореми, А хоче щоб У погодився на правильність теореми.

Для розгляду введемо наступну модель, нехай є ймовірностні машини Тюрінга Р та V, причому Р – машина якою володіє А, машина Р має нескінченний ресурс потужності. Машина V належить суб’єкту В, і має поліміальну потужність.

Машини Р та V мають загальну послідовну стрічку на яку смороду записують одна іншій повідомлення, крім того машини мають загальну вхідну стрічку на яку записуються вхідні повідомлення х. На цій мові задача доведення полягає в тому, що А хоче довести В, що х належить деякій мові L( ) з алфавітом m, причому задача доведення відноситься до класу NP повних задач, тому В не може сам перевірити, що ( ) фізично NP – повнота еквівалентна перебору усіх можливих варіантів.

Показано, що розв'язок цієї задачі може бути найдений якщо суб’єкт У задає відносно S випадкові питання суб’єкту А. Одержуючи та перевіряючи відповіді А, У може згодитись або не згодитися з тім, що , при цьому машина V зупиняється і записує на загальну стрічку результат сприйняття, або не сприйняття доведення. Тоді для інтерактивного протоколу розглянемо стан системи [A(x),B(x)] на вхідному слові х, тоді протокол буде коректним, якщо ймовірність стану :