Криптографічні протоколи. Приклади розв’язку задач та задачі для самостійного розв’язання

 

2.13.1 Основні теоретичні відомості

 

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

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

Криптографічні протоколи можна поділити на два великі класи:

1. Протоколи – примітиви або елементарні протоколи.

2. Прикладні або складові протоколи.

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

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

Більшість криптографічних протоколів можна поділити на інтерактивні протоколи та протоколи з нульовими знаннями.

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

Формалізовано криптографічний протокол можна задати у вигляді PVS протоколу. По суті, PVS протокол описує логіку взаємодій двох об’єктів P і V, де P – об’єкт, який формулює логічне твердження S та доводить істинність твердження S. V – перевіряючий об’єкт, S – деяка логіка.

Якщо зловмисником може бути тільки P, то такий протокол називається інтерактивним, і має володіти двома властивостями:

– повнота протоколу;

– коректність протоколу.

Вважається, що протокол володіє властивістю повноти у випадку, якщо S - істинно, то Р завжди доведе перевіряючому V з великою ймовірністю, що S - істинно.

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

У випадку, якщо V може бути зловмисником, для забезпечення слушності протокол має володіти “нульовими знаннями”.

Сутність протоколу з “нульовими знаннями”: перевіряючий V, отримуючи послідовність тверджень S, не має отримати ніяких знань про те, чому твердження S істинні.

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

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

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

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

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

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

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

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

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

,

де - постійні величини, -розмір вхідних даних.

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

,

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

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

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

Сторона В, знаючи функцію від , розраховує

Якщо отримане значення y та розраховане  співпадають – то голосування завершене.

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

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

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

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

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

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

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

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

Для інтерактивного протоколу розглядається стан системи на вхідному
слові х, тобто . Тоді, протокол буде коректним, якщо ймовірність стану

.                                (2.127)

 

Запис (2.127) означає, що якщо S – істинно, то P доведе V істинність S з ймовірністю 1.

Коректність таких протоколів полягає в тому, що, якщо S – хибне, то V з великою ймовірністю доведе P, що S – хибне:

.                           (2.128)

Слушні протоколи в системах паролювання.

Найважливішим етапом автентифікації є побудова слушного протоколу паролювання (автентифікація А та В). На цьому етапі користувачі А та В мають володіти деяким головним секретом та загальносистемними параметрами системи паролювання. Причому ці секрети вони повинні формувати самі собі та обмінюватися ними. Розглянемо це на прикладі, коли головні ключі генерує адміністратор (на прикладі системи RSA). Адміністратор оголошує, що  – власний ключ користувача А,  – власний ключ користувача В, а відкриті параметри користувачів А та В відповідно  та  (рис. 2.28).

A

B

власний

власний

відкриті

відкриті

Рисунок 2.28 – Обмін параметрами

 

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

                               (2.129)

і передає її користувачу В. Користувач В своїм секретним ключем розшифровує це повідомлення і порівнює  відкрите з  після розшифрування.  – випадкове число для контролю цілісності сеансу. В відповідає А: на відкритому ключі  створює криптограму:

,                                (2.130)

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

.                                 (2.131)

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

Протокол виробки загального секрету.

Нехай користувачам А та В необхідно виробити загальний секрет . Використаємо для цього протокол Діффі-Хеллману в полі GF(P). Нехай А та В знають загальносистемні параметри , що породжені випадковим процесом. Тоді за допомогою схеми Діффі-Хеллмана можна забезпечити слушний протокол. Протокол наведено на рис. 2.29.

 

2.13.2 Прилади розв’язку задач

 

Задача 1.

Реалізуйте протокол, що наведений на рис. 2.28, використовуючи RSA криптосистему.

Розв’язок задачі.

Нехай А та В використовують такі параметри та ключі:

            ;

         .

Переконайтесь, що ці параметри та ключі задовольняють вимоги RSA криптосистеми. Для спрощення приймемо, що абонент А передає повідомлення (2.129) , а В у відповідь . Тоді:

.

Криптограма  розшифровується В з використанням особистого ключа

.

Далі абонент В, використовуючи відкритий ключ , зашифровує повідомлення

.

Криптограма розшифровується А з використанням особистого ключа

.

Виділивши із  випадкове число , абонент А установлює цілісність сеансу.        Нехай  є отриманий від В сеансів ключ. Тоді на третьому кроці повідомлення (2.131), що має, наприклад, вид 11101100 10010001 11110000 10100011, зашифровується ключем .

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

 

A

B

Рисунок 2.29 – Протокол Діфі-Хелмана

 

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

                                          (2.132)

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

 

Задача 2.

В системі використовується схема вироблення загального секрету по протоколу Діффі-Хеллмана. Довжина модуля P=37.

Необхідно знайти:

1. Знайти первісний елемент поля GF(P).

2. Визначити величину множини первісних елементів.

3. Сформувати особистий ключ та визначити відкритий ключ.

4. Виробити загальний секрет.

Розв’язок.

Шукаємо первісний елемент поля GF(37). Оскільки , то з теореми Ферма первісний елемент можна знайти, використовуючи співвідношення:

;

.

Знайдемо канонічний розклад  Р=37, , , .

Обчислюємо:

, якщо цей вираз буде рівний 1, то це не поле.

Обчислюємо:

, якщо цей вираз буде рівний 1, то це не поле.

 вибираємо самі, воно може бути не обов’язково простим.

Вибираємо

 

1. Визначення множини первісних елементів.

 – кількість первісних елементів.

. Отже, існує всього 12 первісних елементів.

 

2. Формування відкритого ключа.

, де  k – номер варіанта.

Нехай особистий ключ , тоді відкритий ключ .

 

3. Формування загального секрету. Нехай абонент дає вже розраховане значення

. Тоді загальний секрет із ним є такий:

.

 

 

2.14 Криптографічні протоколи направленого шифрування.
Приклади розв’язку задач та задачі для самостійного розв’язання

 

2.14.1 Приклади розв’язку задач

 

Задача 1.

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

l_n =1024 бітів.

Розв’язок задачі.

Нехай направлене зашифрування здійснюється від A_j користувача до A_i. Нехай E_j –відкритий ключ, а N_j – модуль перетворення A_j користувача. E_i та N_i – відкритий ключ та модуль A_i користувача. Особистими ключами розшифрування є D_j та D_i ключі.

Нехай в зашифрованому вигляді небхідно передати значення часу tA_j,
випадкову компоненту rA_j, ідентифікатор отримувача A_i, цифровий підпис ЦП та конфіденційний ключ K_ij.

Користувач A_j подає послідовність

(tA_j, rA_j, A_i, ЦП, K_ij )                               (2.133)

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

       E_i(tA_j, rA_j, A_i, ЦП_j, K_ij).                               (2.134)

Користувач A_i, використовуючи свій особистий ключ D_i, розшифровує
повідомлення

  D_i (E_i (tA_j, rA_j, A_i, ЦП_j, K_ij))=tA_j, rA_j, A_i, ЦПj, K_ij .      (2.135)

Наведений однораундовий протокол забезпечує:

- перевірку автентичності A_j та, що повідомлення створено A_j (за рахунок цифрового підпису);

- направлену передачу криптограми – її може розшифрувати своїм особистим ключем тільки A_i користувач;

- оригінальність повідомлення, тобто захист від нав’язування раніше переданого повідомлення, що досягається за рахунок аналізу значень tA_j та rA_j;

- цілісність повідомлення, якщо ЕЦП є його цифровий підпис.

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

.                      (2.136)

При N_j= маємо:

.

 

Задача 2.

Використовуючи умови задачі 1, побудуйте слушний протокол виробки ключів, що забезпечує:

- взаємну автентифікацію Ai та Aj користувачів;

- направлену передачу повідомлення від Aj до Ai;

- цілісність та оригінальність обмінів;

- виборку взаємного ключа та його достовірне передавання-приймання.

Протокол реалізується таким чином:

1. Ai®Aj: Ei (tAj, rAj, Ai, ЦПj, Kij)                                                    (2.137)

Aj : Dj (Ei(tAj, rAj, Ai, ЦПj, Kij)) = tAj, rAj, Ai, ЦПj, Kij      (2.138)

Користувач Ai аналізує параметри повідомлення як у задачі 1 та приймає
Kji ключ.

2. Aj®Ai: Ej (tAi, rAi, rAj, ЦПi, Kji)                                                  (2.139)

Ai : Dj (Ej(tAi, rAi, rAj, ЦПi, Kji))= tAi, rAi, rAj, ЦПi, Kji   (2.140)

Користувач Aj, аналізуючи параметри прийнятого повідомлення по Aj, визначає, що повідомлення призначено для нього, по rAj установлює, що обмін цілісний, по ЦП установлює цілісність та справжність Aj та його відповіді.

Ключ Kji користувач Aj приймає для зв’язку від Aj до Ai.

Aj®Ai: EKji ( Ai, rAi)                               (2.141)

Ai: DKji (EKji ( Ai, rAi))= Ai, rAi                     (2.142)

Ai, прийнявши третю криптограму, по Ai визначає, що підтвердження направлено йому, по rAi установлює цілісність з’єднання, а правильне розшифрування на третьому кроці підтверджує, що Aj правильно прийняв від Ai ключ Kij.

 

Задача 3.

Зашифруйте та розшифруйте повідомлення М = (562, 201), використовуючи направлений шифр в групі точок ЕК, якщо Р=751, а= -1, b=188, (крива
y² =(x³-x+188)mod751), G = (0, 376 ).

Розв’язок задачі.

В нашій задачі повідомлення М задано точкою ЕК. Існують спеціальні методи кодування вихідних повідомлень m в M, що задається у вигляді точок ЕК. Ми їх не розглядаємо.

Нехай відправник повідомлення вибирає випадкове число k=386. Тоді
перша компонента обчислюється як

Із наведеного випливає, що обчислення відкритого ключа в основному зводиться до подвоєння. Наведений запис скалярного добутку демонструє алгоритм його обчислення. Зрозуміло, що такі обчислення краще виконувати з використанням комп’ютера.

       Після виконання обчислень отримаємо, що

.

           

Нехай відкритим ключем є точка Q= .

Він визначається як , де d є довгостроковим особистим ключем.

       Тоді зашифрованим текстом є

.

       В цілому ж, джерело має послати отримувачу разовий відкритий ключ С1, та зашифрований текст С2.

(С1,С2)={(676,558),(385,328)}.

 

Задача 4.

Зробіть порівняльний аналіз стійкості направленого RSA шифрування та Ель-Гамаля направленого шифрування в групі точок еліптичних кривих, якщо довжина модуля   N=2²⁰⁴⁸, а порядок базової точки n=2²⁵⁶.

      

Розв’язок задачі.

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

.

       Складність розв’язку дискретного логарифмічного рівняння в групі точок ЕК при використанні методу Полларда можна оцінити як

,

де n – порядок базової точки .

Використовуючи наведені формули , знаходимо

 групових операцій.

I_ρ= = ≈  операцій складання на ЕК.

 

Задача 5.

Зловмисник визначив, що направлене шифрування здійснюєтся на відкритому ключі отримувача Е_к=31, модуль перетворення N=3599. Необхідно знайти особистий ключ отримувача D_k з використанням якого можна здійснити розшифрування повідомлення М, якщо застосовується RSA перетворення.

Розв’язок задачі може здійснюватись в такому порядку:

1) факторизуємо модуль N і визначаємо прості числа P та Q;

2) знаходимо значення функції:

    ;

3) розв’язуємо рівняння:

    .

Факторизацію виконуємо, використовуючи метод двійкового решета.

Спочатку визначаємо базу розкладу – прості невеликі числа р1, р2 , ... рr , добуток яких Р_б є близьким до N=3599.

.

Знаходимо .

Будуємо таблицю аналогічно як у задачі 1, пп. 1.14.

 

Таблиця 2.25 – Розрахунки

x		Z2mod3599	2	3	5	7	17	залишок
1	60	1	─	─	─	─	─	1
2	61	122	1	─	─	─	─	61
3	62	245	─	─	1	2	─	─
4	63	370	1	─	1	─	─	37
14	73	1730	1	─	1	─	─	173
23	82	3125	─	─	5	─	─	─
26	85	27	─	3	─	─	─	─
49	108	867	─	1	─	─	2	─
61	120	4	2	─	─	─	─	─
62	121	245	─	─	1	2	─	─

 

Беремо рядки зі значеннями x=3 та x=62, в результаі маємо:

;

.

Перемноживши рядки, маємо:

або

.

Знайшовши залишок від значення 7502, маємо

.

Отже x=304 , y=245.

Далі

НОД (│304-245│,3599)=59=Р,

= =61.

Отже Р=59, Q=61.

Далі знаходимо

.

Тепер ключовий розв’язок має вигляд

.

Після переходу до рівняння

,

подамо його у вигляді

.

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

 ; r0=112;

; r1=3;

; r2=1;

; r3=7; μ=3;

;

;

;

;

.

Перевіримо правильність розв’язку

.

Таким чином E_k=31; D_k=3031.

 

 

2.15 Криптографічні протоколи виробки та установки ключів.
Приклади розв’язку задач та задачі для самостійного розв’язання

 

2.15.1 Приклади розв’язку задач

 

Задача 1.

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

 

Розв’язок задачі.

Згідно з вимогами міжнародного стандарту ISO-15946-3 та стандарту США X9.63 повний протокол-примітив базується на використанні довгострокових та сеансових ключів. Нехай криптографічні перетворення здійснюються над простим полем Галуа GF(P). Тоді довгостроковими загальносистемними параметрами є:

– A та B – параметри кривої y² = x² + А x + В (mod P);

– порядок кривої u та порядок поля P;

– коефіцієнт ковариації h (u = , де n порядок базової точки G).

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

Загальносистемними параметрами сеансових ключів є:

a_l, b_e, u_e, h_e, P_e, d_e,a, Q_e,a, d_e,b, Q_e,b .

Для довгострокових ключів загальносистемними параметрами є:

a_s, b_s, u_s, h_s, P_s, d_s,a, Q_s,a, d_s,b, Q_s,b.

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

Далі довгострокові відкриті ключі сертифікуються та висилаються кореспондентам A та B згідно з рис. 2.30.

Qs,a A                                                                                                                                                         B ds,a                                                                   Qs,b                                                                  ds,b   Рисунок 2.30 – Висилання сертифікованих ключів

 

 

Виробляємо загальні довгострокові секрети

;                                                               

Сеансові ключі виробляються згідно з рис. 2.31

Qe,a A                                                                                                                                                         B de,a                                                                  Qe,b                                                                  de,b   Рисунок 2.31 – Виробка сеансових ключів

 

 

Короткострокові загальні секрети є

;                                                              .

Загальний секрет на сеанс виробляємо як . Сеансів ключ обчислюємо, як: ,

де kdf – є геш або друга функція.

Тепер обґрунтуємо порядок базової точки n з кута зору стійкості, вважаючи, що секретним є тільки сеансовий ключ d_s. Найбільш простим (швидким) на сьогодні методом роз’язку дискретного логарифмічного рівняння в групі точок ЕК є метод –Полларда. Його складність визначається як

.                                            (2.143)

Якщо потужність криптоаналітичної системи є , тоді безпечний час є

.

Нехай  років, а  =10¹⁰ операцій складання на ЕК/с, тоді

,

де k =  с/рік.

Знаходимо із рівняння n

.

В двійковому поданні довжина e в бітах

бітів.

Якщо секретними є як довгостроковий так і короткостроковий ключі, тоді складність роз’язку двох рівнянь

.

Якщо I_д обмежений I, тобто

і

.

Тому

біт.

Таким чином, вибираючи модулі з довжиною більше 182 бітів, можна забезпечити заданий рівень стійкості.

 

Задача 2.

Розробіть однопрохідний протокол з використанням довгострокових (головних) ключів на основі криптоперетворень в групі точок ЕК. Визначте необхідну величину порядку базової точки, якщо необхідно забезпечити захист від криптоаналітика з потужністю 10¹⁴ операцій складання на ЕК/с. з t _б = 10¹⁰ років (при імовірності успішного криптоаналізу P_k  10^-2).

Розв’язок задачі.

Виробку ключів зображено на рис. 2.32

Qs,b A                                                                                                                                                         B ds,a                                                                   Qs,a                                                                  ds,b   Qe,a de,a

 

 

Рисунок 2.32 – Виробка ключів

 

;                                                              

;                                                                

Загальний секрет Z виробляємо

Z = Z_s || Z_e

і далі аналогічно як і в задачі 1.

Вважаючи, що для розв’язку дискретних логарифмічних рівнянь в групі точок ЕК застосовується метод –Полларда для розв’язку рівнянь

Необхідно застосувати криптоаналітичну систему з потужністю 2I, де I – потужність, необхідна для розв’язку одного рівняння.

Оскільки , то

.

Далі із рівняння (2.143)

.

Порядок базової точки в бітах визначаємо як

 бітів.

 

Задача 3.

Нехай виробка загального секрету здійснюється за схемою Діфі-Хеллмана в полі GF(97) причому твірний елемент =5 для користувачів A та B. Необхідно виробити загальний секрет.

Розв’язок задачі.

Кореспондент A генерує особистий ключ X_a, скажімо X_a = 36.

Кореспондент B генерує особистий ключ X_b, скажімо X_b = 58.

Далі кореспонденти A та B обчислюють свої відкриті ключі

та обмінюються ними між собою.

Загальні секрети виробляються як

оскільки

,

то ключ вироблено правильно.

 

Задача 4.

Ключі криптографічного перетворення виробляються відповідно до протоколу з використанням схем Діфі-Хеллмана. Розробіть протоколи виробки ключів, якщо перетворення здійснюється в полі GF(P), P=37.

Розв’язок задачі.

Загальносистемними параметрами в схемах Діфі-Хеллмана є просте число Р=37 та твірний елемент Q. Оскільки Q не відомо, то виберемо його, перевіривши виконання умов:

де  – співмножники канонічного розкладу Р-1.

Розкладаємо Р-1: . Отже Q буде твірним, якщо

Вибираємо випадкове значення Q=2. Обчислюємо

таким чином  і умова про твірний елемент виконується.

       Обчислюємо

Таким чином, Q=2 – твірний елемент. Зазначимо, що всього для простого Р існує  твірних елементів.

Генеруємо довгострокові ключі для А_і  та А _j користувачів:

 

Ai	Aj
Xi=17	Xj=11

 

Сертифікуємо Y_i  та Y_j і розсилаємо сертифікати Y_i  та Y_j . В результаті у А _i  є Х_і , Y_j  та Y_i ; у А _j  є Х _j , Y_j  та Y_i . На кожному сеансі зв’язку формуються сеансові ключі:

 

Ai	Aj
rri=17	rj=11

 

Загальний секрет формується таким чином:

Користувач А_і розраховує загальний секрет, як

а користувач A_j як  

Підставивши значення, маємо

,

.

Таким чином  і кореспонденти A_i та A_j виробили однаковий загальний секрет. Цей загальний секрет може бути використаний як у явному вигляді, так і за рахунок відповідного перетворення.

 

⇐ Предыдущая123456Следующая ⇒

Поделиться: