Загальні відомості про асиметричні криптоалгоритми

Симетричні криптосистеми володіють одним серйозним недоліком. Пов’язано це із ситуацією, коли спілкування між собою провадять не три-чотири особи, а сотні й тисячі людей. У цьому випадку для кожної пари, що листується між собою, необхідно створювати свій секретний симетричний ключ. Це в підсумку приводить до існування в системі з N користувачів N²/2 ключів. А це вже дуже «пристойне» число. Крім того, при порушенні конфіденційності якої-небудь робочої станції зловмисник одержує доступ до всіх ключів цього користувача й може відправляти, ніби від його імені, повідомлення всім абонентам, з якими «жертва» вела переписку.

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

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

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

В цілому система переписки при використанні асиметричного шифрування виглядає в такий спосіб. Для кожного з N абонентів, що ведуть переписку, обрана своя пара ключів: «відкритий» E_j й «закритий» D_j, де j – номер абонента. Всі відкриті ключі відомі всім користувачам мережі, кожен закритий ключ, навпаки, зберігається тільки в того абонента, якому він належить. Якщо абонент, скажемо під номером 7, збирається передати інформацію абонентові під номером 9, він шифрує дані ключем шифрування E₉ і відправляє її абонентові 9. Незважаючи на те, що всі користувачі мережі знають ключ E₉ й, можливо, мають доступ до каналу, яким йде зашифроване послання, вони не можуть прочитати вихідний текст, тому що процедура шифрування необоротна за відкритим ключем. І тільки абонент 9, одержавши послання, робить над ним перетворення за допомогою відомого тільки йому ключа D₉ і відновлює текст послання. Помітьте, що якщо повідомлення потрібно відправити в протилежному напрямку (від абонента 9 до абонента 7), то потрібно буде використати вже іншу пару ключів (для шифрування ключ E₇, а для дешифрування – ключ D₇).

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

Загальна схема асиметричної криптосистеми зображена на рис. 5.1. За структурою вона практично ідентична симетричній криптосистемі із ключем сеансу.

Рисунок 5.1 - Схема асиметричної криптосистеми

Алгоритм RSA

Алгоритм RSA стоїть у джерел асиметричної криптографії. Він був запропонований трьома дослідниками-математиками Рональдом Ривестом (R.Rivest), Аді Шамиром (A.Shamir) і Леонардом Адльманом (L.Adleman) в 1977-78 роках.

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

1 вибираються два простих (!) числа p й q;

2 обчислюється їхній добуток n=p*q;

3 вибирається довільне число e (e<n), таке, що НСД (e,(p-1)(q-1))=1, тобто e повинне бути взаємно простим із числом (p-1)(q-1);

4 методом Евкліда вирішується в цілих числах (!) рівняння e*d+(p-1)(q-1)*y=1. Тут невідомими є змінні d й y - метод Евкліда саме й знаходить множину пар (d,y), кожна з яких є рішенням рівняння в цілих числах;

5 два числа (e,n) - публікуються як відкритий ключ;

6 число d зберігається в найсуворішому секреті - це і є закритий ключ, що дозволить читати всі послання, зашифровані за допомогою пари чисел (e,n).

Як же провадиться шифрування за допомогою цих чисел:

1 Відправник розбиває своє повідомлення на блоки, рівні k=[log₂(n)] біт, де квадратні дужки позначають узяття цілої частини від дробового числа.

2 Подібний блок, як відомо, може бути інтерпретований як число з діапазону (0;2^k-1). Для кожного такого числа (назвемо його m _i) обчислюється вираз c_i=((m_i)^e)mod n. Блоки c_i й є зашифроване повідомлення Їх можна спокійно передавати по відкритому каналі, оскільки операція піднесення до степеня за модулем простого числа, є необоротною математичною задачею. Зворотна їй задача зветься "логарифмування в кінцевому полі" й є на кілька порядків більш складною задачею. Тобто навіть якщо зловмисник знає числа e й n, то за c_i прочитати вихідні повідомлення m _i він не може ніяк, крім як повним перебором m_i.

А от на прийомній стороні процес дешифрування все-таки можливий, і допомагає збережене в секреті число d. Досить давно була доведена теорема Ейлера, окремий випадок якої стверджує, що якщо число n представити у вигляді двох простих чисел p й q, то для будь-якого x має місце рівність (x^(p-1)(q-1))modn=1. Для дешифрування RSA-повідомлень скористаємося цією формулою. Зведемо обидві її частини в степінь (-y): (x^{(-y)(p-1)(q-1)})modn=1^(-y)=1. Тепер помножимо обидві її частини на x: (x^{(-y)(p-1)(q-1)+1})modn=1*x=x.

А тепер згадаємо як ми створювали відкритий і закритий ключі. Ми підбирали за допомогою алгоритму Евкліда d таке, що e*d+(p-1)(q-1)*y=1, тобто e*d=(-y)(p-1)(q-1)+1. А отже в останньому виразі попереднього абзацу ми можемо замінити показник степеня на число (e*d). Одержуємо (x^e*d)modn=x. Тобто для того щоб прочитати повідомлення c_i=((m_i)^e)modn досить піднести його до степеня d за модулем m: ((c_i)^d)mod n = ((m_i)^e*d)mod n = m_i.

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