Криптографічні протоколи
Протокол - це послідовність кроків, які роблять дві або більше сторін для спільного вирішення деякої задачі. Слід звернути увагу на те, що всі кроки робляться в порядку суворої черговості і жоден з них не може бути зроблений раніше, ніж закінчиться попередній.
Крім того, будь-який протокол передбачає участь двох сторін. Самотужки можна змішати та випити коктейль, але до протоколу ці дії не будуть мати ніякого відношення. Тому доведеться почастувати кого-небудь зробленим коктейлем, щоб його приготування і дегустація стали справжнім протоколом. І нарешті, протокол обов'язково призначений для досягнення якоїсь мети, інакше це не протокол, а пусте проведення часу.
У протоколів є також і інші відмітні риси:
• кожен учасник протоколу повинен бути заздалегідь повідомлена про кроки, які йому належить зробити;
• всі учасники протоколу повинні слідувати його правилами добровільно, без примусу;
• необхідно, щоб протокол допускав тільки однозначне тлумачення, а його кроки були абсолютно чітко визначені і не допускали можливості їх неправильного розуміння;
• протокол повинен описувати реакцію учасників на будь-які ситуації, які можуть виникнути в ході його реалізації. Іншими словами, неприпустимим є положення, при якому для ситуації, що виникла протоколом не визначено відповідна дія.

Криптографічних протоколів називається протокол, в основі якого лежить криптографічний алгоритм. Однак метою криптографічного протоколу найчастіше є не тільки збереження інформації в таємниці від сторонніх. Учасники криптографічного протоколу можуть бути близькими друзями, у яких немає один від одного секретів, а можуть бути і непримиренними ворогами, кожен з яких відмовляється повідомити іншому, яке сьогодні число. Проте їм може знадобитися поставити свої підписи під спільним договором або засвідчити свою особу. У цьому випадку криптографія потрібна, щоб запобігти або виявити підслуховування сторонніми особами, а також не допустити шахрайства. Тому часто криптографічний протокол потрібно там, де його учасники не повинні зробити або дізнатися більше того, що визначено цим протоколом.
Навіщо потрібні криптографічні протоколи
У повсякденному житті нам доводиться стикатися з протоколами буквально на кожному кроці - граючи в будь-які ігри, або роблячи покупки в магазинах, або голосуючи на виборах. Багатьма протоколами нас навчили користуватися батьки, шкільні вчителі і друзі. Решта ми зуміли дізнатися самостійно.
В даний час люди все частіше контактують один з одним за допомогою комп'ютерів. Комп'ютери ж, на відміну від більшості людей, до школи не ходили, у них не було батьків, та й вчитися без допомоги людини вони не в змозі. Тому комп'ютери доводиться забезпечувати формалізованими протоколами, щоб вони змогли робити те, що люди виконують не замислюючись. Наприклад, якщо в магазині не виявиться касового апарату, ви все одно опинитеся в змозі купити в ньому необхідну для себе річ. Комп'ютер же таке кардинальна зміна протоколу може поставити в повний глухий кут.
Більшість протоколів, які люди використовують при спілкуванні один з одним віч-на-віч, добре себе зарекомендували тільки тому, що їх учасники мають можливість вступити в безпосередній контакт. Взаємодія з іншими людьми через комп'ютерну мережу, навпаки, має на увазі анонімність. Чи будете ви грати з незнайомцем в преферанс, не бачачи, як він тасує колоду і роздає карти? Довіра ви свої гроші зовсім сторонній людині, щоб він купив вам що-небудь в магазині? Надішлете ви свій бюлетень голосування поштою, знаючи, що з ним зможе ознайомитися хтось з поштових працівників і потім розповісти всім про ваші нетрадиційних політичні пристрасті? Думаю, що ні.
Нерозумно вважати, що комп'ютерні користувачі ведуть себе більш чесно, ніж абсолютно випадкові люди. Те ж саме стосується і мережевих адміністраторів, і проектувальників комп'ютерних мереж. Більшість з них і справді досить поважні, однак інші можуть завдати вам дуже великі неприємності. Тому так потрібні криптографічні протоколи, використання яких дозволяє захиститися від непорядних людей.
Розподіл ролей
Щоб опис протоколів було більш наочним, їх учасники будуть носити імена, які однозначно визначають ролі, їм уготовані (див. таблицю). Антон і Борис беруть участь в усіх двосторонніх протоколах. Як правило, починає виконання кроків, передбачених протоколом, Антон, а у відповідь дії вживає Борис. Якщо протокол є трьох-або чотиристоронніх, виконання відповідних ролей беруть на себе Володимир та Георгій.
Про решту персонажів докладніше буде розказано трохи пізніше.

Протоколи з арбітражем
Арбітр є незацікавленим учасником протоколу, якому інші учасники повністю довіряють, роблячи відповідні дії для завершення чергового кроку протоколу. Це означає, що у арбітра немає особистої зацікавленості в досягненні тих або інших цілей, переслідуваних учасниками протоколу, і він не може виступити на боці одного з них. Учасники протоколу також беруть на віру все, що скаже арбітр, і беззаперечно виконують всім його рекомендаціям.
У протоколах, яких ми дотримуємося у повсякденному житті, роль арбітра найчастіше грає адвокат. Однак спроби перенести протоколи з адвокатом як арбітр з повсякденного життя в комп'ютерні мережі наштовхуються на істотні перешкоди:
• Легко довіритися адвокатові, про якого відомо, що в нього незаплямована репутація і з яким можна встановити особистий контакт. Однак якщо два учасники протоколу не довіряють один одному, арбітр, не одягнений в тілесну оболонку і існуючий де-то в надрах комп'ютерної мережі, навряд чи буде користуватися в них великою довірою.
• Розцінки на послуги, що надаються адвокатом, відомі. Хто і яким чином буде оплачувати аналогічні послуги арбітра в комп'ютерній мережі?
• Введення арбітра в будь-який протокол збільшує час, що витрачається на реалізацію цього протоколу.
• Оскільки арбітр контролює кожен крок протоколу, його участь у дуже складних протоколах може стати вузьким місцем при реалізації таких протоколів. Відповідне збільшення числа арбітрів дозволяє позбутися від цього вузького місця, проте одночасно збільшуються і витрати на реалізацію протоколу.
• У силу того, що всі учасники протоколу повинні користуватися послугами одного і того ж арбітра, дії зловмисника, який вирішить завдати їм шкоди, будуть спрямовані, в першу чергу, проти цього арбітра. Отже, арбітр є слабка ланка в ланцюзі учасників будь-якого протоколу з арбітражем.
Незважаючи на зазначені перешкоди, протоколи з арбітражем знаходять широке застосування на практиці.
Протокол із суддівством
Щоб знизити накладні витрати на арбітраж, протокол, в якому бере участь арбітр, часто ділиться на дві частини. Перша повністю збігається зі звичайним протоколом без арбітражу, а до другої вдаються лише у разі виникнення розбіжностей між учасниками. Для вирішення конфліктів між ними використовується особливий тип арбітра - суддя.
Подібно до арбітру, суддя є незацікавленим учасником протоколу, якому інші його учасники довіряють при прийнятті рішень. Однак на відміну від арбітра, суддя бере участь аж ніяк не в кожному кроці протоколу. Послугами судді користуються, тільки якщо потрібно дозволити сумніви щодо правильності дій учасників протоколу. Якщо таких сумнівів ні в кого не виникає, суддівство не знадобиться.
У комп'ютерних протоколах із суддівством передбачається наявність даних, перевіривши які довірена третя особа може вирішити, не смошеннічал чи хто-небудь з учасників цього протоколу. Хороший протокол із суддівством також дозволяє з'ясувати, хто саме веде себе нечесно. Це служить прекрасним превентивним засобом проти шахрайства з боку учасників такого протоколу.
Самостверджуються протокол
Самостверджуються протокол не потребує присутності арбітра для завершення кожного кроку протоколу. Він також не передбачає наявність судді для вирішення конфліктних ситуацій. Самостверджуються протокол влаштований так, що якщо один з його учасників шахраювати, інші зможуть вмить розпізнати нечесність, виявлену цим учасником, і припинити виконання наступних кроків протоколу.
Звичайно ж, хочеться, щоб існував універсальний самостверджуються протокол на всі випадки життя. Однак на практиці в кожному конкретному випадку доводиться конструювати свій спеціальний самостверджуються протокол.
Різновиди атак на протоколи
Атаки на протоколи бувають спрямовані проти криптографічних алгоритмів, які в них задіяні, проти криптографічних методів, що застосовуються для їх реалізації, а також проти самих протоколів. Для початку припустимо, що використовуються криптографічні алгоритми і методи є досить стійкими, і розглянемо атаки власне на протоколи.
Особа, яка не є учасником протоколу, може спробувати підслухати інформацію, якою обмінюються його учасники. Це пасивна атака на протокол, яка названа так тому, що атакуючий (будемо називати його Петром) може тільки накопичувати дані і спостерігати за ходом подій, але не в змозі впливати на нього. Пасивна атака подібна криптоаналітичних атаці зі знанням тільки шифртексту. Оскільки учасники протоколу не володіють надійними засобами, що дозволяють їм визначити, що вони стали об'єктом пасивної атаки, для захисту від неї використовуються протоколи, що дають можливість запобігати можливі несприятливі наслідки пасивної атаки, а не розпізнавати її.
Атакуючий може спробувати внести зміни до протоколу заради власної вигоди. Він може видати себе за учасника протоколу, внести зміни до повідомлення, якими обмінюються учасники протоколу, підмінити інформацію, яка зберігається в комп'ютері і використовується учасниками протоколу для прийняття рішень. Це активна атака на протокол, оскільки атакуючий (назвемо його Зіновієм) може втручатися в процес виконання кроків протоколу його учасниками.
Отже, Петро намагається зібрати максимум інформації про учасників протоколу і про їхні дії. У Зиновія ж зовсім інші інтереси - погіршення продуктивності комп'ютерної мережі, отримання несанкціонованого доступу до ресурсів, внесення спотворень в бази даних. При цьому і Петро, і Зіновій не обов'язково є абсолютно сторонніми особами. Серед них можуть бути легальні користувачі, системні й мережні адміністратори, розробники програмного забезпечення і навіть учасники протоколу, які ведуть себе непорядно чи навіть зовсім не дотримують цей протокол.
В останньому випадку атакуючий називається шахраєм. Пасивний шахрай слід всіма правилами, які визначені протоколом, але при цьому ще й намагається дізнатися про інших учасників більше, ніж передбачено цим протоколом. Активний шахрай вносить довільні зміни в протокол, щоб нечесним шляхом добитися для себе найбільшої вигоди.
Захист протоколу від дій декількох активних шахраїв є вельми нетривіальну проблему. Проте за деяких умов цю проблему вдається вирішити, надавши учасникам протоколу можливість вчасно розпізнати ознаки активного шахрайства. А захист від пасивного шахрайства повинен надавати будь-який протокол незалежно від умов, в які поставлені його учасники.


Доказ з нульовим розголошенням конфіденційної інформації

Антон: "Я знаю пароль для входу в комп'ютерну мережу Центробанку і рецепт приготування" Байкалу "".

Борис: "Ні, не знаєш!"

Антон: "Ні, знаю!"

Борис: "Чим доведеш?"
Антон: "Добре, я тобі все розповім".
Антон довго шепоче щось на вухо Борису.
Борис: "Дійсно цікаво! Треба повідомити про це газетярам!"
Антон: "Е-майо ..."< br /> На жаль, у звичайних умовах Антон може довести Борису, що знає будь-яку таємницю, єдиним способом - розповівши, у чому полягає її суть. Але тоді Борис автоматично дізнається цю таємницю і зможе розповісти про неї першому зустрічному. Чи є у Антона можливість перешкодити Борису це зробити?
Звичайно, є. У першу чергу, Антону не слід довіряти свою таємницю Борису. Але як тоді Антон зможе переконати Бориса у тому, що дійсно входить до числа присвячених?
Антону треба скористатися протоколом докази з нульовим розголошенням конфіденційної інформації. За допомогою цього протоколу Антон опиниться в стані довести Борисові, що він володіє якоюсь секретною інформацією, однак розголошувати цю інформацію перед Борисом буде зовсім не обов'язково.
Доказ носить інтерактивний характер. Борис задає Антону серію питань. Якщо Антон знає секрет, то правильно відповість на всі поставлені йому запитання. Якщо не знає, ймовірність правильної відповіді на кожне з питань буде невелика. Після приблизно 10 питань Борис буде точно знати, чи обманює його Антон. При цьому шанси Бориса витягти для себе будь-яку корисну інформацію про суть самого секрету практично дорівнюють нулю.
Протокол докази з нульовим розголошенням конфіденційної інформації
Використання докази з нульовим розголошенням конфіденційної інформації можна пояснити на конкретному прикладі.
Припустимо, що є печера, точка входу в печеру позначена буквою A, в точці B печера розгалужується на дві половини - C і D (див. малюнок). У печери є секрет: тільки той, хто знає чарівні слова, може відкрити двері, розташовану між C і D.
Антону чарівні слова відомі, Борису - ні. Антон хоче довести Борису, що знає чарівні слова, але так, щоб Борис як і раніше залишався в невіданні щодо цих слів. Тоді Антон може скористатися наступним протоколом:
1. Борис стоїть у точці A.
2. За своїм вибором Антон підходить до дверей або з боку точки C, або з боку точки D.
3. Борис переміщується в точку B.
4. Борис наказує Антону з'явитися або (а) - через лівий прохід до дверей, або (б) - через правий прохід до дверей.
5. Антон підпорядковується наказом Бориса, у разі необхідності використовуючи чарівні слова, щоб пройти через двері.
6. Кроки 1-5 повторюються n раз, де n - параметр протоколу.
Припустимо, що у Бориса є відеокамера, за допомогою якої він фіксує всі зникнення Антона в надрах печери і всі його наступні появи з тієї чи іншої сторони. Якщо Борис покаже запису всіх n експериментів, зроблених ним спільно з Антоном, чи зможуть ці записи послужити доказом знання Антоном чарівних слів для іншої людини (наприклад, для Володимира)?
Навряд чи. Володимир ніколи не зможе повністю упевнитися в тому, що Антон кожного разу заздалегідь не повідомляв Борису, з якого боку він попрямує до дверей, щоб потім Борис наказував йому виходити саме з того боку, з якою Антон зайшов. Або що з зробленої відеозаписи не вирізані всі невдалі експерименти, в ході яких Антон з'являвся зовсім не з того боку, з якою йому наказував Борис.
Це означає, що Борис не в змозі переконати Володимира, особисто не був присутній при проведенні експериментів в печері, в тому, що Антон дійсно підтвердив там своє знання секрету. А значить, використаний Антоном протокол докази характеризується саме нульовим розголошенням конфіденційної інформації. Якщо Антон не знає чарівні слова, що відкривають двері в печері, то, спостерігаючи за Антоном, не зможе нічого довідатися і Борис. Якщо Антону відомі чарівні слова, то Борису не допоможе навіть детальна відеозапис проведених експериментів. По-перше, оскільки при її перегляді Борис побачить тільки те, що вже бачив живцем. А по-друге, тому що практично неможливо відрізнити сфальсифіковану Борисом відеозапис від справжньої.
Протокол докази з нульовим розголошенням спрацьовує в силу того, що, не знаючи чарівних слів, Антон може виходити тільки з того боку, з якою зайшов. Отже, тільки в 50% всіх випадків Антон зуміє обдурити Бориса, зумівши вийти саме з того боку, з к?? торою той попросить. Якщо кількість експериментів одно n, то Антон успішно пройде всі випробування тільки в одному випадку з 2n. На практиці можна обмежитися n = 16. Якщо Антон правильно виконає наказ Бориса у всіх 16 випадках, значить, він і справді знає чарівні слова.
Приклад з печерою є дуже наочним, але має істотний недолік. Борису буде значно простіше простежити, як в точці B Антон повертає в один бік, а потім з'являється з протилежного боку. Протокол докази з нульовим розголошенням тут просто не потрібен.
Тому припустимо, що Антону відомі не якісь там чарівні слова типу "Сезам, відчинись". Ні, Антон володіє більш цікавою інформацією - він першим зумів впоратися з труднорешаемой завданням. Щоб довести цей факт Борису, Антону зовсім не обов'язково публічно демонструвати своє рішення. Йому достатньо застосувати наступний протокол докази з нульовим розголошенням конфіденційної інформації:
1. Антон використовує наявну у нього інформацію та згенероване випадкове число, щоб звести труднорешаемую завдання до іншої труднорешаемой завдання, ізоморфної вихідної задачі. Потім Антон вирішує цю нове завдання.
2. Антон задіє протокол предсказания біта для знайденого на кроці 1 рішення, щоб згодом, якщо у Бориса виникне необхідність ознайомитися з цим рішенням, Борис міг би достовірно переконатися, що пред'явлене Антоном рішення дійсно було отримано їм на кроці 1.
3. Антон показує нову труднорешаемую завдання Борису.
4. Борис просить Антона
або (а) - довести, що дві труднорешаемие завдання (стара і нова) ізоморфні,
або (б) - надати рішення, яке Антон повинен був знайти на кроці 1, і довести, що це дійсно рішення задач, на якій Антон звів вихідну задачу на тому ж кроці.
5. Антон виконує прохання Бориса.
6. Антон і Борис повторюють дії 1-6 n раз, де n - параметр протоколу.
Труднорешаемие завдання, спосіб відомості однієї задачі до іншої, а також випадкові числа повинні по можливості вибиратися так, щоб у Бориса не з'явилося жодної інформації щодо рішення вихідної задачі навіть після багаторазового виконання кроків протоколу.
Не всі труднорешаемие завдання можуть бути використані при доведенні з нульовим розголошенням конфіденційної інформації, проте більшість з них цілком придатні для таких цілей. Прикладами можуть служити відшукання в зв'язкового графі циклу Гамільтона (замкнутого шляху, що проходить через усі вершини графа тільки один раз) і визначення ізоморфізму графів (два графа ізоморфні, якщо вони відрізняються тільки назвами своїх вершин).

Паралельні докази з нульовим розголошенням конфіденційної інформації

Звичайний протокол докази з нульовим розголошенням конфіденційної інформації вимагає, щоб Антон і Борис послідовно повторили його кроки n разів. Можна спробувати виконувати дії, передбачені цим протоколом, одночасно:
1. Антон використовує наявну в нього інформацію і n згенерованих випадкових чисел, щоб звести труднорешаемую завдання до n іншим труднорешаемим завданням, ізоморфні вихідної задачі. Потім Антон вирішує ці n нових завдань.
2. Антон задіє протокол предсказания біта для знайдених на кроці 1 n рішень, щоб згодом, якщо у Бориса виникне необхідність ознайомитися з цими рішеннями, Борис міг би достовірно переконатися, що пред'явлені Антоном рішення дійсно були отримані ним на кроці 1.
3. Антон показує n нових труднорешаемих завдань Борису.
4. Для кожної з n нових труднорешаемих завдань Борис просить Антона
або (а) - довести, що вона ізоморфна вихідної труднорешаемой завдання,
або (б) - надати рішення цього завдання, яке Антон повинен був знайти на кроці 1, і довести, що вона дійсно є її рішенням.
5. Антон виконує всі прохання Бориса.
На перший погляд паралельний протокол володіє тим же властивістю нульового розголошення конфіденційної інформації, що і звичайний. Однак суворого докази цього факту ще не знайдено. А поки з повною впевненістю можна сказати лише одне: деякі інтерактивні протоколи докази з нульовим розголошенням в деяких ситуаціях можна виконувати паралельно, і від цього вони не втрачають властивість нульового розголошення конфіденційної інформації.

Неінтерактивні протоколи докази з нульовим розголошенням конфіденційної інформації

Сторонній особа, яка не бере участь у виконанні кроків інтерактивного протоколу докази з нульовим розголошенням конфіденційної інформації, неможливо переконати в тому, в чому в ході реалізації протоколу переконується Борис, а саме - що Антон дійсно володіє конфіденційною інформацією. Щоб подолати цей недолік, потрібно застосувати неінтерактивних протокол, в якому замість Бориса використовується односпрямований функція:
1. Антон використовує наявну в нього інформацію і n згенерованих випадкових чисел, щоб звести труднорешаемую завдання до n іншим труднорешаемим завданням, ізоморфні вихідної задачі. Потім Антон вирішує ці n нових завдань.
2. Антон задіє протокол предсказания біта для знайдених на кроці 1 n рішень.
3. Антон подає n зобов'язань, отриманих ним на кроці 2, на вхід односпрямованої функції.
4. Для кожної i-й труднорешаемой завдання, до якої Антон звів вихідну задачу на кроці 1, він бере i-й біт значення, обчисленого за допомогою односпрямованої функції, і
(а) якщо цей біт дорівнює 1, то Антон доводить, що вихідна і i-а завдання ізоморфні, або
(б) якщо цей біт дорівнює 0, то Антон поміщає в загальнодоступну базу даних рішення i-й завдання, обчислена на кроці 1.
5. Антон передає в загальнодоступну базу даних всі зобов'язання, які були отримані ним на кроці 2.
6. Борис, Володимир або будь-яка інша зацікавлена особа можуть перевірити правильність виконання кроків 1-5 Антоном.

Дивно, але факт: Антон надає в загальне користування дані, які дозволяють будь-якому переконатися в тому, що він володіє деякими секретом, і в той же час не містять ніякої інформації про суть самого секрету.
Роль Бориса в цьому протоколі виконує односпрямований функція. Якщо Антон не знає рішення труднорешаемой завдання, він все одно може виконати дії, передбачені або пунктом (а), або пунктом (б) кроку 4 протоколи, але аж ніяк не обома пунктами відразу. Тому, щоб смошеннічать, Антону доведеться навчитися передбачати значення односпрямованої функції. Однак, якщо функція дійсно є односпрямованої, Антон не зможе ні здогадатися, якими будуть її значення, ні вплинути на неї з тим, щоб на її виході вийшла потрібна Антону бітова послідовність.
На відміну від інтерактивного протоколу, тут потрібна більша кількість ітерацій. Оскільки генерація випадкових чисел покладена на Антона, підбором цих чисел він може спробувати домогтися, щоб на виході односпрямованої функції вийшла бітова послідовність потрібного йому вигляду. Адже навіть якщо Антон не знає рішення вихідної труднорешаемой завдання, він завжди в змозі виконати вимоги або пункту (а), або пункту (б) кроку 4 протоколи.
Тоді Антон може спробувати здогадатися, на який з цих пунктів впаде вибір, і виконати кроки 1-3 протоколу. А якщо його думка невірна, він повторить все спочатку. Саме тому в неінтерактивних протоколах необхідний більший запас міцності, ніж в інтерактивних. Рекомендується вибирати n = 64 або навіть n = 128.
Доведено, що в загальному випадку будь-яке математичне доказ може бути відповідним чином перетворено на доказ з нульовим розголошенням конфіденційної інформації. А це означає, що тепер математику зовсім не обов'язково публікувати результати своїх наукових досліджень. Він може довести своїм колегам, що знайшов рішення якоїсь математичної проблеми, не розкриваючи перед ними суті знайденого рішення.

Посвідчення особи з нульовим розголошенням конфіденційної інформації

У повсякденному житті людям регулярно доводиться засвідчувати свою особу. Зазвичай вони роблять це шляхом пред'явлення паспортів, водійських прав, студентських квитків та інших подібних документів. Такий документ зазвичай має деяку індивідуальну відмінну рису, яка дозволяє однозначно пов'язати його з певною особою. Найчастіше це малюнок, іноді - підпис, рідше - відбитки пальців або рентгенівський знімок зубів. Чи можна робити те ж саме за допомогою криптографії?
Звичайно. У цьому разі для посвідчення особи Антона використовується його таємний криптографічний ключ. Застосовуючи доказ з нульовим розголошенням конфіденційної інформації, Антон може продемонструвати будь-кому, що знає свій таємний ключ, і тим самим однозначно ідентифікувати себе. Ідея цифрової ідентифікації досить приваблива і таїть у собі масу різноманітних можливостей, однак у неї є ряд істотних недоліків.
По-перше, зловмисник Зіновій під фальшивим приводом може попросити Антона пред'явити своє цифрове посвідчення особи. Одночасно за допомогою сучасних засобів зв'язку Зіновій ініціалізує процес ідентифікації Антона зовсім в іншому місці і буде переадресовувати всі запити з цього місця Антону, а дані їм відповіді - пересилати назад. Наприклад, Зіновій може зв'язатися з ювелірним магазином і, видавши себе за Антона, сплатити з його кишені досить дорогу покупку.
По-друге, Зіновій може запросто обзавестися декількома таємними ключами, а отже, і отримати відповідне число цифрових посвідчень особи. Одне з них він використовує єдиний раз для фінансової афери і більше їм користуватися не буде. Свідком злочину стане особа, якій Зіновій пред'явить своє "одноразове" посвідчення особи, проте довести, що це був саме Зиновій, не вдасться. Адже завбачливий Зіновій ніколи не засвідчував таким чином свою особистість раніше. Чи не стане він робити цього й надалі. А свідок зможе тільки показати, яке посвідчення особи було пред'явлено злочинцем. Однозначно пов'язати це посвідчення з особистістю Зиновія буде не можна.
По-третє, Антон може попросити Зиновія позичити на час його цифрове посвідчення особи. Мовляв, Антону треба з'їздити до Сполучених Штатів, а оскільки він - колишній співробітник радянської розвідки, який працював проти США, американський уряд навідріз відмовляє йому в'їзної візи. Зиновій з радістю погоджується: після від'їзду Антона він може піти практично на будь-який злочин, оскільки обзавівся "залізним" алібі. З іншого боку, ніщо не заважає вчинити злочин Антону. Хто повірить лепет Зиновія про те, що він позичив своє цифрове посвідчення особи якійсь іншій людині?
Позбутися від перерахованих недоліків допомагають додаткові заходи безпеки. У першому випадку шахрайство стало можливим, оскільки Зіновій, перевіряючи цифрове посвідчення особи Антона, міг одночасно спілкуватися із зовнішнім світом по телефону або радіо. Якщо Зиновія помістити в екранована кімната без будь-яких засобів зв'язку, ніякого шахрайства не було б.
Щоб виключити друге форму шахрайства, необхідно ввести обмеження на кількість ключів, які людині дозволяється використовувати, щоб засвідчити свою особу (як правило, такий ключ повинен існувати в одному екземплярі).
І нарешті, щоб не допустити третій вид шахрайства, потрібно або змусити всіх громадян засвідчувати свою особу якомога частіше (наприклад, у кожного ліхтарного стовпа, як це робиться в тоталітарних державах), або доповнити засоби цифрової ідентифікації іншими ідентифікаційними методами (наприклад, перевіркою відбитків пальців).
Неусвідомлена передача інформації
Припустимо, що Борис безуспішно намагається розкласти на прості множники 700-бітове число. При цьому йому відомо, що дане число є твором семи 100-бітових множників. На допомогу Борису приходить Антон, який випадково знає один з множників. Антон пропонує Борису продати цей множник за 1000 рублів - по 10 рублів за біт. Проте у Бориса є в наявності лише 500 рублів. Тоді Антон висловлює бажання віддати Борису 50 біт за половину ціни. Борис сумнівається, оскільки навіть купивши ці 50 біт, він все одно не зможе переконатися, що вони дійсно є частиною шуканого множника, поки не дізнається всі його біти цілком.
Щоб вийти з глухого кута, Антон і Борис повинні скористатися протоколом неусвідомленої передачі інформації. Відповідно до нього Антон передає Борису декілька зашифрованих повідомлень. Борис вибирає один з них і відсилає всі повідомлення назад. Антон розшифровує вбрання Борисом повідомлення і знову відсилає Борису. При цьому Антон залишається в невіданні стосовно того, яке саме повідомлення вибрав для себе Борис.
Протокол неусвідомленої передачі інформації не вирішує всіх проблем, які стоять перед Антоном і Борисом, що бажають укласти угоду про купівлю-продаж одного з множників 700-бітового числа. Щоб угода стала чесною, Антон повинен буде довести Борису, що продані 50 біт дійсно є частиною одного з простих множників, на які розкладається це число. Тому Антону швидше за все доведеться додатково скористатися ще й протоколом докази з нульовим розголошенням інформації.
Наступний протокол дозволяє Антону послати два повідомлення, одне з яких буде прийнято Борисом, але яке саме, Антон так і не дізнається.
1. Антон генерує дві пари ключів, що складаються з відкритого і таємного ключа, і відсилає обидва відкритих ключа Борису.
2. Борис генерує ключ для симетричного алгоритму (наприклад, для DES-алгоритму), шифрує цей ключ за допомогою одного з відкритих ключів, надісланих Антоном, і відсилає назад Антону.
3. Антон розшифровує ключ Бориса за допомогою кожного з двох своїх таємних ключів, згенерованих їм на кроці 1, і отримує два бітових послідовності. Одна з них є справжнім ключем для DES-алгоритму, а інша містить довільний набір бітів.
4. Антон шифрує два повідомлення по DES-алгоритмом, використовуючи як ключів обидві бітові послідовності, які були отримані ним на кроці 3, і відсилає результати шифрування Борису.
5. Борис розшифровує обидва надісланих Антоном повідомлення на ключі, згенероване на кроці 2, і знаходить два відкритих тексту повідомлення, один з яких є справжньою тарабарщину, а другий - змістовне послання.
Тепер у Бориса є одне з двох повідомлень Антона, проте останній не може з певністю сказати, яке саме. На жаль, якщо в протоколі не передбачити додатковий перевірочний крок, у Антона буде можливість смошеннічать (наприклад, зашифрувати на кроці 4 два ідентичних повідомлення). Тому необхідний ще один, заключний крок протоколу:
6. Після того як відпала потреба зберігати в секреті друге повідомлення (наприклад, у Бориса знайшлися ще 500 рублів, щоб викупити у Антона решту множника), Антон надає Борису свої таємні ключі, щоб той міг переконатися в чесності Антона.

Протокол приховується від атаки з боку Антона, оскільки на кроці 3 Антон не в змозі відрізнити довільну бітову послідовність від справжнього ключа DES-алгоритму, згенерованого Борисом. Протокол також забезпечує захист від атаки з боку Бориса, так як у того немає таємних ключів Антона, щоб визначити бітову послідовність, використану Антоном як ключ DES-алгоритму для шифрування друге повідомлення.
Звичайно, протокол неусвідомленої передачі інформації аж ніяк не гарантує, що Антон не пошле Борису якісь безглузді послання (типу "Борис - лох" або "Мяу-мяу") замість бітів одного з семи простих множників, на які розкладається оригінал 700-бітове число . Або що Борис взагалі захоче з ними ознайомитися і візьме участь у виконанні кроків цього протоколу.
На практиці протокол неусвідомленої передачі інформації використовується досить рідко. Зазвичай він служить у якості одного з будівельних блоків для побудови інших протоколів.
Анонімні спільні обчислення
Іноді буває так, що групі людей потрібно спільно обчислити деяку функцію від багатьох змінних. Кожен учасник обчислювального процесу є джерелом значень однієї або декількох змінних цієї функції. Результат обчислень стає відомий усім членам групи, однак жоден з них не в змозі з'ясувати що-небудь про значення, поданих на вхід функції іншим членом групи.
Обчислення середньої зарплати
Припустимо, що начальник відділу наказав своїм підлеглим підрахувати середню зарплату у відділі. Начальник обізнаний про зарплату будь-якого співробітника, але надто зайнятий більш важливими справами, щоб відволікатися на подібні дрібниці. Кожен співробітник прекрасно знає власну зарплату, але категорично не бажає повідомляти про неї товаришам по службі. Щоб співробітники відділу могли підсумувати свої оклади, зберігаючи їх у таємниці від інших, їм слід скористатися наступним протоколом:
1. Антон генерує випадкове число, додає його до своєї зарплати, шифрує отриману суму за допомогою відкритого ключа Бориса і потім передає те, що у нього вийшло, Борису.
2. На своєму таємному ключі Борис розшифровує результат, обчислений Антоном, додає до нього свою зарплату, шифрує отриману суму за допомогою відкритого ключа Володимира і потім передає те, що у нього вийшло, Володимиру.
3. На своєму таємному ключі Володимир розшифровує результат, обчислений Борисом, додає до нього свою зарплату, шифрує отриману суму за допомогою відкритого ключа Георгія і потім передає те, що у нього вийшло, Георгію.
4. На своєму таємному ключі Георгій розшифровує результат, обчислений Володимиром, додає до нього свою зарплату, шифрує отриману суму за допомогою відкритого ключа Антона і потім передає те, що у нього вийшло, Антону.
5. На своєму таємному ключі Антон розшифровує результат, обчислений Георгієм, віднімає з нього випадкове число, згенероване на кроці 1, ділить на кількість співробітників відділу і отримує шукану середню зарплату у відділі.

Точність обчислення середньої зарплати залежить від чесності кожного співробітника. Якщо хоча б один з учасників протоколу збреше щодо своєї платні, підсумкове значення буде невірним. Особливо потенційними великими можливостями для зловживань має Антон. На кроці 5 він може відняти будь-яке число, яке тільки прийде йому в голову, і ніхто не помітить підробки. Тому необхідно зобов'язати Антона скористатися будь-якою зі схем предсказания бита. Однак якщо від Антона буде потрібно розкрити перед усіма випадкове число, згенероване їм на кроці 1, зарплату Антона дізнається Борис. Це означає, що начальнику відділу все ж таки доведеться відволіктися і виконати обчислення, передбачені кроком 2 протоколи, самому. Адже він і так в курсі розміру оплати праці Антона.
Як знайти собі подібного
Антон любить грати з гумовими ляльками, виробники яких потрудилися на славу, ретельно скопіювавши в натуральну величину певні особливості анатомічної будови жінки. А Борису подобається у всіх яскравих подробицях спостерігати за життям сусідів з багатоквартирного будинку навпроти за допомогою сучасних оптичних пристроїв. Обидва ретельно приховують свої уподобання від родичів, друзів