ABCDEFGHIJKLMNOPQRSTUVWXYZ 7 страница

4 асиметричні криптографічні системи

4.1 Концепція криптосистеми з відкритим ключем

Ефективними системами криптографічного захисту даних є асиметрічні криптосистеми. Такі системи також називають криптосистемами з відкритим ключем. Таку назву вони отримали внаслідок того, що для зашифрування даних використовується один ключ, К₁ (відкритий, несекретний), проте для розшифровування – другий ключ, К₂ (секретний). Розшифровування даних за допомогою відкритого ключа не є можливим. Ключ розшифрування не можна отримати з ключа зашифрування.

 

Узагальнена схема криптосистеми з відкритим ключем має такий вигляд: (Рис. 4.1)

 

 

Ключ К₁ – відкритий ключ відправника;

Ключ К₂ – закритий ключ отримувача;

Е_К1(М) – перетворення шифрування над відкритим текстом М за допомогою ключа К₁;

D _К2(С) - перетворення розшифровування над шифртекстом С за допомогою ключа К₂;

 

Рис. 4.1 Узагальнена схема асиметрічної криптосистеми

 

Генератор ключів розташовується на стороні отримувача, щоб не пересилати секретний ключ К₂ по незахищеному каналу. Значення ключів К₁, К₂ не пов’зані від початкового стану генаратора ключів.

 

Характерні особливості асиметричних криптосистем:

1 Відкритий ключ К₁ та криптограма С можуть пересилатись по незахищеному каналу зв’язку.

2 Алгоритми шифрування

Е _К1 : М С

та розшифровування

D _К2 : С М

є відкритими.

 

Захист інформації в асиметрічної криптосистемі базується на секретності ключа К₂.

 

У. Диффі та М. Хеллман сформулювали вимоги, які необхідно виконувати для того, щоб шифрування за допомогою асиметричної криптосистеми було небезпечним:

1 Розрахування ключів К₁ та К₂ повинно бути легким, щоб отримувач міг згідно початкових умов швидко їх знайти.

2 Відправник, що знає відкритий ключ К₁ та повідомлення М, може легко розрахувати криптограму

С = Е _К1 (М)

3 Отримувач, за допомого секретного ключа К₂ та криптограми С, може легко відновити вихідне повідомлення

М = D _К2 (С) = D _К2 (Е _К1 (М))

4 Злочинник, що знає відкритий ключ К₁ при попиту розрахувати секретний ключ К₂ наштовхується на задачу, яку не можна розв’язати.

5 Злочинник, що знає відкритий ключ К₁ і криптограму С при попиту розрахувати вихідне повідомлення М наштовхується на задачу, яку не можна розв’язати.

 

4.2 Однонаправленні функції

 

Концепція асиметричних криптосистем базується на використанні однонаправлених функцій. Неформально однонаправлену функцію можливо визначити таким чином. Нехай Х та Y – деякі довільні множини. Функція

 

f : Х Y

є однонаправленою, коли для усіх х є Х можливо легко обчислити функцію

 

y = f (х), де y є Y.

 

В той же час для більшості y є Y достатньо важко отримати значення х є Х, таке, що f (х) = y (при цьому вважається, що існує як найменш одне таке значення х).

Основним критерієм віднесення функції f до класу однонаправлених функцій є відсутність ефективних алгоритмів зворотних перетворень Y Х.

В якості першого приклада однонаправленої функції розглянемо цілочислове множення. Задача обчислення добутку двох дуже великих цілих чисел P і Q,

N = P * Q

 

є відносно легкою задачею для ЕОМ.

Навпаки зворотна задача – розкладення на складові великого цілого

цисла N = P * Q (обчислення дільників P і Q) є задачею, яку не можна розв’язати при великих значеннях N.

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

Обчислимо множину Z_N:

Z_N = {0, 1, 2, …, N - 1}.

Тоді модульна експонента з основою А за модулем N уявляє функцію

f _{А, N} : Z_N Z_N,

f_{А, N} (х) = А^х (mod N),

де Х – ціле число, 1 х N – 1.

Існують ефективні алгоритми, які спроможні досить швидко обчислити значення функції f_{А, N} (х).

Якщо y = А^х, то можна записати х = log_A (y). Тому задачу обернення функції f_{А, N} (х) звуть задачею знаходження дискретного логарифму, яку можна сформулювати наступним чином.

Для відомих цілих А, N та y треба знайти ціле число х, таке, що

 

А^х (mod N) = y.

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

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

 

4.3 Криптосистема шифрування данних RSA

 

Першою і найбільш відомою криптографічною системою з відкритим ключем є так звана система RSA, яка була запропонована в 1978 році. Її назва походить від перших букв прізвищ авторів Rivest, Shamir і Aldeman, які розробили її під час сумісних досліджень в Массачусетському технологічному інституті в 1977 році. Алгоритм RSA став першим алгоритмом, який спроможний працювати як в режимі шифрування даних, так і в режимі електронного цифрового підпису.

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

В криптоситстемі RSA відкритий ключ К₁, секретний ключ К₂, повідомлення М та криптограма С належать множині цілих чисел

 

Z_N = {0, 1, 2, …, N - 1},

де N – модуль:

N = P * Q.

Тут P і Q – випадкові великі прості числа. Для забезпечення максимальної безпеки обирають P і Q однакової довжини та зберігають у таємниці.

Множина Z_N з операціями складання та множення за модулем N утворює арифметику за модулем N.

Відкритий ключ К₁ обирають випадково таким чином, щоб виконувалися умови:

 

1 < К₁ (N); НОД (К₁, (N) ) = 1; (N) = (P - 1) (Q - 1),

 

де (N) – функція Ейлера, що вказує кількість додатних цілих чисел в інтервалі від 1 до N, які є взеємно простими з N.

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

Далі, використовуючи розширений алгоритм Евкліда, обчислюють секретний ключ К₂ , такий, що

К_1* К₂ 1(mod (N))

чи

К₁ = К₂ ^-1 ( mod (P-1) (Q -1)).

Це можливо обчислити, тому що отримувач знає числа P і Q та може легко знайти (N).

Відкритий ключ К₁ використовують для шифрування даних, а секретний ключ К₂ – для розшифровування.

Перетворення шифрування визначає криптограму С згідно наступної формули:

С = Е _К1 (М) = М ^К1 (mod N).

Проте зворотню задачу (розшифровування криптограми С) можна вирішити згідно наступної формули:

М = D _К2 (С) = С ^К2 (mod N).

Припустімо, що користувач А хоче передати користувачеві В повідомлення, яке зашифровоне за допомогою криптосистеми RSA. Тоді користувач А є відправником повідомлення, проте користувач В- отримувач повідомлення. Криптосистему утворює отримувач повідомлення, тобто користувач В. Розглянемо послідовністьдій користувачів А та Вна прикладі.

 

 

Приклад Треба зашифрувати повідомлення “САВ” за допомогою криптосистеми RSA.

Для простоти будемо використовувати маленькі числа (на практиці застосовуються набагато більші).

1 Користувач В обирає два випадкових простих числа Р = 3 і Q = 11.

2 Користувач В визначає модуль N = 3 * 11 = 33.

3 Користувач В визначає функцію Ейлера

(N) = (33) = (Р - 1)( Q - 1) = 2 * 10 = 20.

Відкритий ключ К₁ обирають випадково таким чином, щоб виконувалися умови:

 

1 < К₁ 20; НОД (К₁, 20 ) = 1.

Отже, нехай буде К₁= 7.

4 Користувач В розраховує значення секретного ключа К₂ за допомогою розширенного алгоритму Евкліда, для якого задовольняється співвідношення

К_1* К₂ 1(mod (N))

Тобто К₂ 7^-1(mod 20) = 3.

5 Користувач В передає користувачеві Апару чисел (N = 33, К₁= 7).

6 Користувач Ауявляєшифроване повідомлення як послідовність цілих чисел за допомогою відображення: А® 1, В® 2, С® 3.Тоді повідомлення приймає вигляд 312( в двійковому вигляді 011.001.010),

тобто М₁ = 3, М₂ = 1, М₃ = 2.

7 Користувач Азашифровуває за допомогою ключа К₁= 7 тамодуля N =33 текст, який розбитий на блоки наступним чином:

С_i = М_i ^К1 (mod N) = М_i ⁷ (mod 33)

С₁ = (3⁷) (mod 33) = 2187 (mod 33) = 9,

С₂ = (1⁷) (mod 33) = 1 (mod 33) = 1,

С₃ = (2⁷) (mod 33) = 128 (mod 33) = 29.

Користувач А передає користувачеві Вкриптограму С_1, С_2, С₃ = 9, 1, 29.

 

8 Користувач В розшифровуває одержане повідомлення (9, 1, 29) за допомогою секретного ключа К₂= 3:

 

М_i = С_i ^К2 (mod N) = С_i ³ (mod 33)

 

М₁ = (9³) (mod 33) = 729 (mod 33) = 3,

М₂ = (1³) (mod 33) = 1 (mod 33) = 1,

М₃ = (29³) (mod 33) = 24389 (mod 33) = 2.

 

Таким чином, відновлено вихідне повідомлення САВ.

 

Недоліком системи RSAє менша, в порівнянні з симетричними криптосистемами стійкість, унаслідок чого довжина ключів у таких криптосистем повинна бути в 4-5 разів більше.

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

 

 

4.4 Схема шифрування Ель Гамаля

 

Схема Ель Гамаля спроможна працювати як в режимі шифрування даних, так і в режимі електронного цифрового підпису.

Криптостійкість алгоритму заснована на трудності обчислення дискретних логарифмів в кінцевому полі.

Для того щоб генерувати пару ключів (відкритий ключ, секретний ключ), спочатку вибирають деяке велике просте ціле число P і велике ціле число G, причому G < Р. Числа P та G не є секретними.

Потім обирають випадкове ціле число X, причому Х < Р. Число Х є секретним ключем.

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

 

Y = G^X mod P.

 

Для того, щоб зашифрувати повідомлення М, обирають випадкове ціле число К, 1< K< (P -1), таке, що K і (P -1) є взаємно простими.

Потім обчислються цілі числа :

a = G^K mod P,

b = Y^KM mod P.

Пара чисел (a,b) є шифртекстом. Довжина шифртексту удвічі більша довжини вихідного повідомлення М.

Для того, щоб розшифрувати шифртекст (a,b), обчислюють

 

М = b/ a^X (mod P),

тому що

a^X G^KX mod P,

можна записати

 

b / a^X (mod P) Y^KM / a^X (mod P) G^KX M / G^KX (mod P) M(mod P).

 

Приклад. Треба зашифрувати повідомлення М = 5 за допомогою криптосистеми Ель Гамаля.

Оберемо Р =11, G = 2, секретний ключ Х = 8.

Обчислимо значення відкритого ключа Y

Y = G^Х mod P = 2⁸ mod 11 = 256 mod 11 = 3

Тобто, Y = 3.

Оберемо деяке випадкове число К = 9.

Переконаємося, що НСД (К, Р-1) =1. Дійсно, НСД (9, 10) =1.

Обчислимо пару чисел a та b:

a = G^K mod P = 2⁹ mod 11 = 512 mod 11 = 6,

b = Y^KM mod P = 3⁹*5 mod 11 = 19683*5 mod 11 = 98415mod 11 = 9

 

Пара чисел (6, 9) є шифртекстом.

 

Розшифруємо цей шифртекст. Обчислимо повідомлення М, використовуючи секретний ключ Х = 8:

М = b/ a^X (mod P) = 9/6⁸ mod 11 = 9/1679616 mod 11 = 5,

 

тобто

1679616* М 9 mod 11.

Розв’язання цього порівняння : М = 5.

 

 

4.5 Комбінований метод шифрування.

 

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

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

· генерація нових секретних та відкритих ключів базується на генерації нових великих простих чисел, а перевірка чисел на простоту потребує багато часу для обчислення на ЕОМ;

· процедури шифрування та розшифровування, які пов’язані з піднеснем до степеня багатозначного числа є достатньо громіздкі.

 

Тому швидкодія криптосистем з відкритим ключем набагато менша швидкодії криптосистем з секретним ключем.

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

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

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

 

Якщо користувач А хоче передати користувачеві В повідомлення, яке зашифроване комбінованим методом, тоді алгоритм буде наступним:

1. Створити (наприклад, згенерувати випадковим чином) симетричний сеансовий ключ K_s .

2. Зашифрувати повідомлення М за допомогою сеансового ключа K_s.

3. Зашифрувати сеансовий ключ K_s за допомогою відкритого ключа K_в користувача В та свого секретного ключа K_А.

4. Передати по незахищенному каналу зв’язку на адресу користувача В повідомлення М разом з сеансовим ключем K_s, які є зашифровувані.

 

Дії користувача В будуть зворотними.

 

5. Розшифрувати сеансовий ключ K_s за допомогою свого секретного ключа K_в та відкритого ключа K_А користувача А.

6. За допомогою отриманного сеансового ключа K_s розшифрувати та прочитати повідомлення М.

 

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

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

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

 

Таблиця 4.1 - Довжини ключів для симетричних та асиметричних криптосистем, які дають однакову криптостійкість.