Криптографічні протоколи

___________________________________________________________________________

Московський Державний Інститут електроніки та Математики
___________________________________________________________________________

Курсова робота

на тему «Криптографічні протоколи»

Студенти групи М8-08

Расін Вадим

Клочков Павло

м.Москва

2000

Криптографічні протоколи

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

• кожен учасник протоколу повинен бути заздалегідь повідомлена про кроки,які йому належить зробити;

• всі учасники протоколу повинні слідувати його правилами добровільно,без примусу;

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

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

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

У повсякденному житті нам доводиться стикатися з протоколамибуквально на кожному кроці - граючи в будь-які ігри, або роблячи покупки вмагазинах, або голосуючи на виборах. Багатьма протоколами нас навчиликористуватися батьки, шкільні вчителі і друзі. Решта ми зумілидізнатися самостійно.

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

Більшість протоколів, які люди використовують при спілкуванні один здругом віч-на-віч, добре себе зарекомендували тільки тому, що їхучасники мають можливість вступити в безпосередній контакт.
Взаємодія з іншими людьми через комп'ютерну мережу, навпаки,має на увазі анонімність. Чи будете ви грати з незнайомцем в преферанс,не бачачи, як він тасує колоду і роздає карти? Довіра ви свої грошізовсім сторонній людині, щоб він купив вам що-небудь в магазині?
Надішлете ви свій бюлетень голосування поштою, знаючи, що з ним зможеознайомитися хтось з поштових працівників і потім розповісти всім про вашінетрадиційних політичні пристрасті? Думаю, що ні.

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

Розподіл ролей

Щоб опис протоколів було більш наочним, їх учасники будутьносити імена, які однозначно визначають ролі, їм уготовані (див.таблицю). Антон і Борис беруть участь в усіх двосторонніх протоколах.
Як правило, починає виконання кроків, передбачених протоколом, Антон,а у відповідь дії вживає Борис. Якщо протокол є три-абочотиристоронніх, виконання відповідних ролей беруть на себе Володимир і
Георгій.

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

Протоколи з арбітражем

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

У протоколах, яких ми дотримуємося у повсякденному житті, роль арбітранайчастіше грає адвокат. Однак спроби перенести протоколи з адвокатом вяк арбітр з повсякденного життя в комп'ютерні мережі наштовхуються насуттєві перешкоди:

• Легко довіритися адвокатові, про якого відомо, що у ньогонезаплямована репутація і з яким можна встановити особистий контакт. Однакякщо два учасники протоколу не довіряють один одному, арбітр, не одягненийв тілесну оболонку і існуючий де-то в надрах комп'ютерної мережі, наврядЧи буде користуватися в них великою довірою.

• Розцінки на послуги, що надаються адвокатом, відомі. Хто і якимчином буде оплачувати аналогічні послуги арбітра в комп'ютерній мережі?

• Вступ арбітра в будь-який протокол збільшує час, що витрачаєтьсяна реалізацію цього протоколу.

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

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

Незважаючи на зазначені перешкоди, протоколи з арбітражем знаходятьшироке застосування на практиці.

Протокол із суддівством

Щоб знизити накладні витрати на арбітраж, протокол, в якомубере участь арбітр, часто ділиться на дві частини. Перша повністю співпадає ззвичайним протоколом без арбітражу, а до другої вдаються лише у разівиникнення розбіжностей між учасниками. Для вирішення конфліктівміж ними використовується особливий тип арбітра - суддя.

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

У комп'ютерних протоколах із суддівством передбачається наявністьданих, перевіривши які довірена третя особа може вирішити, несмошеннічал чи хто-небудь з учасників цього протоколу. Хороший протокол зсуддівством також дозволяє з'ясувати, хто саме веде себе нечесно. Цеслужить прекрасним превентивним засобом проти шахрайства з бокуучасників такого протоколу.

самостверджуються протокол

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

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

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

Атакуючий може спробувати внести зміни до протоколу радивласної вигоди. Він може видати себе за учасника протоколу, внестизміни до повідомлення, якими обмінюються учасники протоколу, підмінитиінформацію, яка зберігається в комп'ютері і використовується учасникамипротоколу для прийняття рішень. Це активна атака на протокол, оскількиатакуючий (назвемо його Зіновієм) може втручатися в процес виконаннякроків протоколу його учасниками.

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

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

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

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

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

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

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

Борис: "Чим доведеш?"

Антон: "Добре, я тобі все розповім".

Антон довго шепоче щось на вухо Борису.

Борис: "Дійсно цікаво! Треба повідомити про це газетярам! "

Антон:" Е-майо ..."

На жаль, у звичайних умовах Антон може довести Борису, що знаєбудь-яку таємницю, єдиним способом - розповівши, у чому полягає її суть.
Але тоді Борис автоматично дізнається цю таємницю і зможе розповісти про неїпершому зустрічному. Чи є у Антона можливість перешкодити Борису цезробити?

Звичайно, є. У першу чергу, Антону не слід довіряти свою таємницю
Борису. Але як тоді Антон зможе переконати Бориса у тому, що дійсновходить до числа присвячених?

Антону треба скористатися протоколом докази з нульовимрозголошення конфіденційної інформації. За допомогою цього протоколу Антонопиниться в стані довести Борисові, що він володіє якоюсь секретноюінформацією, однак розголошувати цю інформацію перед Борисом буде зовсімне обов'язково.

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

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

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

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

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 протоколи, самому. Адже він ітак в курсі розміру оплати праці Антона.

Як знайти собі подібного

Антон любить грати з гумовими ляльками, виробники якихпотрудилися на славу, ретельно скопіювавши в натуральну в