Главная | Обратная связь | Поможем написать вашу работу!

Системи шифрування з відкритим ключем

Поряд з традиційним шифруванням на основі секретного ключа в останні роки все більше визнання отримують системи шифрування з відкритим ключем. У таких системах використовуються два ключі. Інформація шифрується за допомогою відкритого ключа, а розшифровується з використанням секретного ключа. В основі застосування систем з відкритим ключем лежить використання необоротних або односторонніх функцій [8]. Ці функції мають наступну властивість. За відомим x легко визначається функція у = f (x). Але за відомим значенням у практично неможливо отримати х. У криптографії використовуються односторонні функції, мають так званий таємний хід. Ці функції з параметром z мають такі властивості. Для певного z можуть бути знайдені алгоритми Ez і Dz. За допомогою Ez легко отримати функцію fz (x) для всіх х з області визначення. Так само просто за допомогою алгоритму Dz виходить і зворотна функція х = f^'1(y) для всіх у з області допустимих значень. У той же час практично для всіх z і майже для всіх у з області допустимих значень знаходження f^'1(y) за допомогою обчислень неможливо навіть при відомому Е^. Як відкритий ключ використовується у, а в якості закритого - х. При шифруванні з використанням відкритого ключа немає необхідності в передачі секретного ключа між взаємодіючими суб'єктами, що істотно спрочує криптозахист переданої інформації. Криптосистеми з відкритими ключами розрізняються видом односторонніх функцій. Серед них найвідомішими є системи RSA, Ель-Гамаля і Мак-Еліса. В даний час найбільш ефективним і поширеним алгоритмом шифрування з відкритим ключем є алгоритм RSA, який отримав свою назву від перших букв прізвищ його творців: Rivest, Shamir і Adleman. Алгоритм заснований на використанні операції піднесення до степеня модульної арифметики. Його можна представити у вигляді такої послідовності кроків [39].

Крок 1. Вибираються два великих простих числа р і q. Простими називаються числа, які діляться тільки на самих себе і на 1. Величина цих чисел повинна бути більше 200.

Крок 2. Виходить відкрита компонента ключа n:

n=pq.

Крок 3. Обчислюється функція Ейлера за формулою:

f(p,q) = (p-1)(q-1).

Функція Ейлера показує кількість цілих додатних чисел від 1 до n, які взаємно прості з n. Взаємно простими є такі числа, які не мають жодного спільного дільника, крім 1. Крок 4. Вибирається велике просте число d, що є

взаємно простим зі значенням f (p, q).

Крок 5. Визначається число е, що задовольняє умову:

e*d =l(modf(p,q)).

Дана умова означає, що залишок від ділення (лишок) добутку ed на функцію f(p, q) дорівнює 1. Число е приймається в якості другої компоненти відкритого ключа. Як секретний ключ використовуються числа d і n.

Крок 6. Вихідна інформація, незалежно від її фізичної природи, представляється в числовому двійковому вигляді. Послідовність біт поділяється на блоки довжиною L біт, де L - найменше ціле число, що задовольняє умову: L>log2(w+7). Кожен блок розглядається як ціле додатне число X (i), що належить інтервалу [0, n -1].

Крок 7. Зашифрована інформація отримується у вигляді послідовності чисел Y (i), що обчислюються за формулою:

Y(i) = (X(i)) (mod n).

Крок 8. Для розшифровування інформації використовується така залежність:

X(i) = (Y(i)) (mod n).

Приклад застосування методу RSA для криптографічного закриття інформації. Примітка: для простоти обчислень використані мінімально можливі числа. Нехай потрібно зашифрувати повідомлення російською мовою «ГАЗ». Для зашифрування і розшифрування повідомлення необхідно виконати наступні кроки.

Крок 1. Вибирається p = 3 та q = 11.

Крок 2. Вибирається n = 3*11 = 33.

Крок 3. Визначається значення функції Ейлера

f(p,q) = (3-1)*(11-1) = 20/

Крок 4. Як взаємно просте вибирається число d = 3.

Крок 5. Вибирається таке число е, що задовольняло б співвідношенню: (е * 3) (mod 20) = 1. Нехай е = 7. Крок 6. Початкове повідомлення подається як послідовність цілих чисел. Нехай букві А відповідає число 1, букві Г - число 4, букві 3 - число 9. Для представлення чисел в двійковому коді потрібно 6 двійкових розрядів, тому що в російській алфавіті використовуються 33 літери (випадковий збіг з кількістю п). Вихідна інформація в двійковому коді має вигляд:

000100 +000001001001.

Довжина блоку L визначається як мінімальне число з цілих чисел, що задовольняють умові: L>log₂(33+1), так як п = 33. Звідси L = 6. Тоді вихідний текст представляється у вигляді кортежу X (i) = <4, 1,9>;.

Крок 7. Кортеж X (i) зашифровується за допомогою відкритого ключа {7, 33}:

Y(l) = (47) (mod 33) = 16384 (mod 33) = 16;

Y(2) = (1^7) (mod 33) = 1 (mod 33) = 1;

Y(3) = (97) (mod 33) = 4782969 (mod 33) = 15.

Крок 8. Розшифрування повідомлення Y(i) = <16, 1, 15> здійснюється з використанням секретного ключа [3, 33]:

Х(1) = (163) (mod 33) = 4096 (mod 33) = 4;

Х(2) = (I3) (mod 33) = 1 (mod 33) = 1;

X(3) = (153) (mod 33) = 3375 (mod 33) = 9.

Вихідна числова послідовність в розшифрованому вигляді X (i) = <4, 1, 9> замінюється вихідним текстом ≪ГАЗ≫.

Система Ель-Гамаля заснована на складності обчислення дискретних логарифмів в кінцевих полях [22]. Основним недоліком систем RSA і Ель-Гамаля є необхідність виконання трудомістких операцій у модульній арифметиці, що вимагає залучення значних обчислювальних ресурсів. Криптосистема Мак-Еліса використовує коди, що виправляють помилки. Вона реалізується в кілька разів швидше, ніж криптосистема RSA, але має й істотний недолік. У криптосистема Мак-Еліса використовується ключ великої довжини і одержуваний шифротекст в два рази перевищує довжину вихідного тексту. Для всіх методів шифрування з відкритим ключем математично строго не доведено відсутність інших методів криптоаналізу крім рішення NP-повної задачі (задачі повного перебору). Якщо з'являться методи ефективного вирішення таких завдань, то криптосистеми такого типу будуть дискредитовані. Наприклад, раніше вважалося, що завдання укладання рюкзака є NP-повною. В даний час відомий метод вирішення такого завдання, що дозволяє уникнути повного перебору.

⇐ Предыдущая 12 13 14 15 161718 19 20 21 Следующая ⇒