5.2.4. Ідентифікація та перевірка справжності

З кожним об’єктом комп’ютерної системи зв’язана деяка інформація, яка однозначно його ідентифікує. Це може бути число, набір символів, алгоритм, який визначає даний об’єкт. Таку інформацію називають ідентифікатором об’єкта. Якщо об’єкт має деякий ідентифікатор, зареєстрований в мережі, він називається законним (легальним) об’єктом; інші об’єкти відносяться до незаконних (нелегальних) [Error: Reference source not found].

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

Наступний крок – автентифікація об’єкту (перевірка справжності об’єкту). Ця процедура встановлює чи є даний об’єкт саме таким, яким він себе оголошує.

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

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

Після встановлення з’єднання необхідно забезпечити виконання вимог захисту при обміні повідомленнями [Error: Reference source not found]:

1. отримувач повинен бути впевненим у автентичності джерела даних;

2. отримувач повинен бути впевненим у автентичності отриманих даних;

3. відправник повинен бути впевненим в отриманні даних отримувачем;

4. відправник повинен бути впевненим в справжності доставлених даних.

Для виконання першої і другої вимог використовується цифровий підпис. Для виконання другої і третьої вимог відправник повинен отримати повідомлення про отримання за допомогою підтверджуючого листа (certified mail). Засобом захисту в такій процедурі є цифровий підпис підтверджуючого повідомлення, яке, в свою чергу, є доказом пересилки вихідного повідомлення. Якщо ці чотири вимоги реалізовано в інформаційній системі, то гарантується захист даних при їх передачі по каналу зв’язку та забезпечується функція захисту, яка називається функцією підтвердження (незаперечності) передачі. В цьому випадку відправник не може заперечувати ні факту пересилання повідомлення, ні його змісту, а отримувач не може заперечувати ні факту отримання повідомлення, ні справжності його змісту.

Ідентифікація та автентифікація користувачів. Перш ніж отримати доступ до ресурсів комп’ютерної системи, користувач повинен пройти процес представлення комп’ютерній системі, який включає дві стадії:

• ідентифікацію – користувач повідомляє системі за її запитом своє ім’я (ідентифікатор);

• автентифікацію – користувач підтверджує ідентифікацію, вводячи в систему унікальну, не відому іншим користувачам інформацію про себе (наприклад, пароль).

Для проведення процедур ідентифікації та автентифікації користувача необхідно:

• наявність відповідного суб’єкта (модуля) автентифікації;

• наявність автентифікуючого об’єкту, що зберігає унікальну інформацію для автентифікації користувача.

Розрізняють дві форми представлення об’єктів, що автентифікують користувача [Error: Reference source not found]:

• зовнішній автентифікуючий об’єкт, що не належить системі;

• внутрішній об’єкт, що належить системі, в який переноситься інформація з зовнішнього об’єкту.

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

Типові схеми ідентифікації та автентифікації користувача. Розглянемо структури даних та протоколи ідентифікації та автентифікації користувача. Допустимо, що в комп’ютерній системі зареєстровано n користувачів. Нехай і-й автентифікуючий об’єкт і-го користувача містить два інформаційні поля:

ID_i – незмінний ідентифікатор і-го користувача, який є аналогом імені та використовується для ідентифікації користувача;

K_i – автентифікуюча інформація користувача, яка може змінюватися та служить для автентифікації (наприклад, пароль P_i=K_i).

Описана структура відповідає практично будь-якому ключовому носію інформації, що використовується для ідентифікації користувача. Наприклад, для носіїв типу пластикових карт виділяється незмінна інформація ID_i первинної персоналізації користувача та об’єкт у файловій структурі карти, що містить K_i. Сукупну інформацію в ключовому носії можна назвати первинною автентифікуючою інформацією і-го користувача. Очевидно, що внутрішній автентифікуючий об’кт не повинен існувати в системі тривалий час (більше часу роботи окремого користувача). Для тривалого зберігання слід використовувати дані в захищеній формі. Розглянемо дві типові схеми ідентифікації та автентифікації.

Схема 1. В комп’ютерній системі виділяють об’єкт-еталон для ідентифікації та автентифікації користувачів. Структура об’єкта-еталону для цієї схеми показана в табл. 5.6. Тут E_i=F(ID_i,K_i), де F – функція, яка має властивість „невідновлюваності“ значення K_i за E_i та ID_i. „Невідновлюваність“ K_i оцінюється деякою пороговою трудомісткістю T_o розв’язання задачі відновлення автентифікуючої інформації K_i за E_i та ID_i. Крім того, для пари K_i та K_j можливе співпадання відповідних значень E. У зв’язку з цим ймовірність хибної автентифікації користувача не повинна бути більшою деякого порогового значення P_o. На практиці задають T_o=10²⁰...10³⁰, P_o=10^-7‑...10^-9.

Таблиця 5.6

Структура об’єкту-еталону для схеми 1

Номер користувача	Інформація для ідентифікації	Інформація для автентифікації
1	ID1	E1
2	ID2	E2
...	...	...
N	IDn	En

При використанні описаної схеми використовується наступний протокол ідентифікації та автентифікації:

1. Користувач надає свій ідентифікатор ID.

2. Якщо ID не співпадає ні з одним ID_і, зареєстрованим у комп’ютерній системі, то ідентифікація відхиляється – користувач не допускається до роботи, в іншому випадку (існує ID_і= ID) встановлюється, що користувач, який назвався користувачем і, пройшов ідентифікацію.

3. Суб’єкт автентифікації запитує у користувача його автентифікатор K.

4. Суб’єкт автентифікації обчислює значення Y=F(ID_i,K_i).

5. Суб’єкт автентифікації порівнює значення Y та E_i. При співпаданні цих значень встановлюється, що даний користувач успішно автентифікований у системі. Інформація про цього користувача передається в програмні модулі, які використовують ключі користувачів (системи шифрування, розмежування доступу тощо). В іншому випадку автентифікація відхиляється – користувач не допускається до роботи.

Дана схема ідентифікації та автентифікації користувача може бути модифікованою. Модифікована схема 2 має кращі характеристики, порівняно зі схемою 1.

Схема 2. У комп’ютерній системі виділяється модифікований об’єкт-еталон, структура якого представлена у табл. 5.7.

Таблиця 5.7

Структура модифікованого об’єкту-еталону

Номер користувача	Інформація для ідентифікації	Інформація для автентифікації
1	ID1, S1	E1
2	ID2, S2	E2
...	...	...
N	IDn, Sn	En

На відміну від схеми 1, у схемі 2 значення Е_і рівне F(S_i,K_i), де S_i – випадковий вектор, що задається при створенні ідентифікатора користувача (при створенні запису), необхідного для ідентифікації та автентифікації користувача; F – функція, яка володіє властивістю „невідновлюваності“ значення K_i по E_i та S_i.

Протокол ідентифікації та автентифікації для схеми 2 складається з наступних кроків:

1. Користувач надає свій ідентифікатор ID.

2. Якщо ID не співпадає ні з одним ID_і, зареєстрованим у комп’ютерній системі, то ідентифікація відхиляється – користувач не допускається до роботи, в іншому випадку (існує ID_і= ID) встановлюється, що користувач, який назвався користувачем і, пройшов ідентифікацію.

3. За ідентифікатором ID_і виділяється вектор S_i.

4. Суб’єкт автентифікації запитує у користувача його автентифікатор K.

5. Суб’єкт автентифікації обчислює значення Y=F(S_i,K).

6. Суб’єкт автентифікації порівнює значення Y та E_i. При співпаданні цих значень встановлюється, що даний користувач успішно автентифікований у системі. В іншому випадку автентифікація відхиляється – користувач не допускається до роботи.

Друга схема автентифікації застосовується, зокрема, в ОС UNIX [¹⁵⁶]. В якості ідентифікатора ID використовується ім’я користувача (login), в якості автентифікатора К – пароль (password), а функція F представляє собою алгоритм шифрування DES.

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

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

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

Іноді отримувач не повинен розкривати вихідну відкриту форму пароля. В цьому випадку відправник повинен пересилати замість відкритої форми паролю його відображення, отримане з використанням односторонньої функції () паролю. Це перетворення повинно гарантувати неможливість розкриття противником паролю за його відображенням. Наприклад, функція () може бути визначена наступним чином:

(P)=E_P(ID),

де P – пароль відправника; ID – ідентифікатор відправника; E_P – процедура шифрування, яка виконується з використанням паролю P в якості ключа. Такі функції є дуже зручними, якщо довжина паролю і ключа однакові. В цьому випадку підтвердження справжності за допомогою паролю складається із пересилки отримувачу відображення (P) та порівняння його з попередньо розрахованим еквівалентом '(P).

На практиці паролі складаються всього з кількох символів для полегшення запам’ятовування їх користувачами. Короткі паролі вразливі до атаки повного перебору усіх варіантів. Для уникнення такої атаки функцію (P) визначають іншим способом:

(P)=E_PK(ID),

де K та ID – відповідно ключ та ідентифікатор відправника. При цьому значення (P) обчислюється заздалегідь і зберігається у вигляді '(P) в ідентифікаційній таблиці у отримувача. Підтвердження справжності складається з порівняння двох відображень паролю (P_А) та '(P_А) і визнання паролю P_А, якщо ці відображення рівні. Зрозуміло, що при такому методі потрібно забезпечити неможливість несанкціонованого доступу до ідентифікаційної таблиці.

Також в сучасних інформаційних системах для ідентифікації та автентифікації використовують персональні ідентифікаційні номери (PIN), загальні принципи використання яких подібні до парольної автентифікації.

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

Відмітимо основні переваги біометричних методів ідентифікації та автентифікації користувачів у порівнянні з традиційними:

• високий рівень достовірності ідентифікації за біометричними ознаками у зв’язку з їх унікальністю;

• невіддільність біометричних ознак від дієздатної особи;

• складність фальсифікації біометричних ознак.

В якості біометричних ознак, які можуть бути використані при ідентифікації потенційного користувача, можна виділити наступні [Error: Reference source not found]:

• узор райдужної оболонки та сітківки ока;

• відбитки пальців;

• геометрична форма руки;

• форма та розміри обличчя;

• особливості голосу;

• біомеханічні характеристики рукописного підпису;

• біомеханічні характеристики „клавіатурного почерку“.

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

Системи ідентифікації за узором райдужної оболонки та сітківки ока можуть бути розділені на два класи:

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

• системи, які використовують рисунок кров’яних судин сітківки ока.

Оскільки ймовірність повторення даних параметрів рівна 10^-78, ці системи є найбільш надійними серед усіх біометричних систем. Такі засоби ідентифікації застосовуються там, де потрібен високий рівень безпеки.

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

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

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

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

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

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

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

• механізм запиту-відповіді;

• механізм відмітки часу („часовий штемпель“).

Механізм запиту-відповіді полягає в наступному. Якщо користувач А хоче бути впевненим, що повідомлення, отримувані ним від користувача В є справжніми, він включає у відправлене для В повідомлення непередбачуваний елемент – запит Х (наприклад, деяке випадкове число). При відповіді користувач В повинен виконати над цим елементом деяку операцію (наприклад, розрахувати деяку функцію f(X)). Це неможливо зробити заздалегідь, оскільки користувачу В невідомо яке випадкове число Х прийде в запиті. Отримавши відповідь з результатом дій В, користувач може бути впевненим, що В – справжній. Недоліком цього методу є можливість встановлення закономірності між запитом та відповіддю.

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

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

Розглянемо в якості прикладу процедуру „рукостискання“ для двох користувачів А та В. (Таке допущення не впливає на суть розгляду. Така ж процедура використовується, коли вступаючі у зв’язок сторони не є користувачами). Нехай застосовується симетрична криптоситема. Користувачі А та В розділяють один і той же секретний ключ К_АВ. Схема цієї процедури наведена на рис 5.13.

Рис. 5.13. Схема процедури „рукостискання“

• Нехай користувач А ініціює процедуру „рукостискання“, відправляючи користувачу В свій ідентифікатор ID_A у відкритій формі.

• Користувач В, отримавши ідентифікатор ID_A, знаходить в базі даних секретний ключ K_AB і вводить його в свою криптосистему.

• Тим часом користувач А генерує випадкову послідовність S за допомогою псевдовипадкового генератора та відправляє її користувачу В у вигляді криптограми

.

• Користувач В розшифровує цю криптограму і розкриває вихідний вигляд послідовності S.

• Потім обидва користувачі А та В перетворюють послідовність S, використовуючи відкриту односторонню функцію ().

• Користувач В шифрує повідомлення (S) і відправляє цю криптограму користувачу А.

• Нарешті, користувач А розшифровує цю криптограму і порівнює отримане повідомлення '(S) з вихідним (S). Якщо ці повідомлення однакові, користувач А визнає автентичність користувача В.

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

Іноді користувачам потрібно забезпечувати неперервну перевірку автентичності відправників на протязі всього сеансу зв’язку. Схема одного з найпростіших способів неперервної автентифікації зображена на рис. 5.14.

Рис. 5.14. Схема неперервної перевірки автентичності відправника

Передана криптограма має вигляд

E_K(ID_A,M),

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

Інший варіант неперервної перевірки автентичності використовує замість ідентифікатора відправника його секретний пароль. Заздалегідь підготовлені паролі відомі двом сторонам. Нехай Р_А та Р_В – паролі користувачів А та В відповідно. Тоді користувач А створює криптограму

С=Е_К(Р_А,М).

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

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

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

Спрощена схема ідентифікації з нульовою передачею знань. Схему ідентифікації з нульовою передачею знань запропонували в 1986 році У. Фейге, А. Фіат та А. Шамір [¹⁵⁷]. Вона є найвідомішим доказом ідентичності з нульовою передачею конфіденційної інформації. Розглянемо спочатку спрощений варіант схеми ідентифікації з нульовою передачею знань для кращого розуміння її концепції. Спочатку вибирають випадкове значення модуля n, який є добутком двох великих простих чисел. Модуль n повинен мати довжину в межах 512-1024 біт. Це значення n може бути надане групі користувачів, яким прийдеться доводити свою автентичність. В процесі ідентифікації приймають участь дві сторони:

• сторона А, яка доводить свою автентичність;

• сторона В, яка перевіряє надані стороною А докази.

Для генерації відкритого та закритого ключів для сторони А, довірений арбітр (Центр) вибирає деяке число V, яке є квадратним лишком (російською – вычетом) по модулю n. Інакше кажучи, вибирається таке число V, що вираз

x²V(modn)

має розв’язок і існує ціле число

V^-1modn.

Вибране значення V є відкритим ключем для А. Потім розраховують найменше значення S, для якого

Ssqrt(V^-1)(modn)

Це значення S є секретним ключем для А.

Тепер можна приступити до виконання протоколу ідентифікації:

1. Сторона А вибирає деяке випадкове число r, r<n. Потім вона обчислює

x=r²modn

і відправляє х стороні В.

2. Сторона В посилає А випадковий біт b.

3. Якщо b=0, тоді А відправляє r стороні В. Якщо b=1, то А відправляє стороні В

y=r*Smodn.

4. Якщо b=0, сторона В перевіряє, що

x=r²modn,

щоб впевнитися, що А знає sqrt(x). Якщо b=1, сторона В перевіряє, що

x=y²*Vmodn,

щоб бути впевненою, що А знає sqrt(V^-1).

Ці кроки утворюють один цикл протоколу, який називається акредитацією. Сторони А та В повторюють цей цикл t разів при різних випадкових значеннях r і b доти, поки В не впевниться, що А знає значення S.

Якщо сторона А не знає значення S, вона може вибрати таке значення r, яке дозволить їй обманути сторону В, якщо В відправить їй b=0 чи b=1. Однак це неможливо зробити в обидвох випадках. Ймовірність того, що А обмане В в одному циклі складає 1/2. Ймовірність обману В в t циклах рівна (1/2)^t. Для того, щоб цей протокол працював, сторона А ніколи не повинна повторно використовувати значення r. Якщо б А поступила таким чином, а сторона В відправила б стороні А на кроці 2 інший випадковий біт b, то В мала б обидві відповіді А. Після цього В може обчислити значення S, і для А все було б закінчено.

Паралельна схема ідентифікації з нульовою передачею знань. Паралельна схема ідентифікації дозволяє збільшити число акредитацій, що виконуються за один цикл, зменшуючи, тим самим, тривалість процесу ідентифікації. Як і в попередньому випадку, спочатку генерується число n як добуток двох великих чисел. Для генерації відкритого і секретного ключа для сторони А, спочатку вибирають К різних чисел V₁, V₂,..., V_k, де кожне V_і є квадратним лишком по модулю n. Інакше кажучи, вибирають значення V_і таким, що вираз

x²V_і modn

має розв’язок і існує V_і^-1modn. Отриманий рядок V₁, V₂,..., V_k є відкритим ключем. Потім обчислюють такі найменші значення S_i, що

S_іsqrt(V_і^-1) modn.

Цей рядок є секретним ключем сторони А.

Протокол процесу ідентифікації має наступний вигляд:

1. Сторона А вибирає деяке випадкове число r, r<n. потім вона обчислює x=r²modn і посилає х стороні В.

2. Сторона В відправляє стороні А деякий випадковий двійковий рядок із К біт: b₁,b₂,...,b_k.

3. Сторона А обчислює

.

Перемножаються тільки ті значення S_i, для яких b_i=1. Обчислене значення y відправляється стороні В.

4. Сторона В перевіряє, що

.

Фактично сторона В перемножає тільки ті значення V_i, для яких b_i=1. Сторони А і В повторюють цей протокол t раз, поки В не впевниться, що А знає S₁, S₂,..., S_k.

Ймовірність того, що А може обманути В, рівна (1/2)^Kt. Автори рекомендують в якості контрольного значення брати ймовірність обману В рівною (1/2)²⁰ при K=5 і t=4.

В цей протокол також можна включити ідентифікаційну інформацію. Нехай І – деякий двійковий рядок, який представляє ідентифікуючу інформацію про власника карти. Цю інформацію І формують в Центрі видачі інтелектуальних карт за заявкою користувача А. Далі використовують односторонню функцію f() для обчислення f(I,j), де j – деяке двійкове число, яке зчіпляється з рядком І. Обчислюють значення

V_j=f(I,j)

для невеликих значень j, відбирають К різних значень j, для яких V_j є квадратичними лишками по модулю n. Потім для відібраних квадратичних лишків V_j обчислюють найменші квадратні корені із . Сукупність ізК значень V_j утворює відкритий ключ, а сукупність із К значень S_j – секретний ключ користувача А.

Схема ідентифікації Гіллоу-Кіускуотера. Алгоритм ідентифікації, розроблений Л. Гіллоу та Ж. Кіускуотером, має дещо кращі характеристики, порівняно з попередньою схемою ідентифікації. В цьому алгоритмі обміни між сторонами А і В та акредитації в кожному обміні зведені до абсолютного мінімуму – для кожного доказу потрібен тільки один обмін з однією акредитацією [Error: Reference source not found]. Однак об’єм необхідних обчислень для цього алгоритму більший, ніж для схеми Фейге-Фіата-Шаміра.

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

Рядок І є аналогом відкритого ключа. Іншою відкритою інформацією, яку використовують усі картки, є модуль n та показник степеня V. Модуль n є добутком двох секретних простих чисел. Секретним ключем сторони А є величина G, яка вибирається таким чином, щоб виконувалося співвідношення

I*G^V1(modn).

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

Протокол доведення автентичності А без передачі стороні В значення G складається з наступних кроків:

1. Сторона А вибирає випадкове ціле r таке, що 1<r≤n-1. Вона обчислює

T=r^Vmodn

і відправляє це значення стороні В.

2. Сторона В вибирає випадкове ціле d, таке, що 1<d≤n-1, і відправляє це значення d стороні А.

3. Сторона А обчислює

D=r*G^dmodn

і відправляє це значення стороні В.

4. Сторона В обчислює значення

T'=D^VI^dmodn.

Якщо

TT'(modn),

то перевірка автентичності успішно завершена.

Математичні викладки, використані в цьому протоколі не є складними:

T'=D^VI^d=(rG^d)^VI^d=r^VG^dVI^d=r^V(IG^V)^d=r^VT(modn),

оскільки G обчислювалося таким чином, щоб виконувалося співвідношення

IG^V1(modn)