logo search
Конспект лекцій з дисципліни

6.3.2. Алгоритм 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 = [log2(n)] біт, де квадратні дужки позначають узяття цілої частини від дробового числа.

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

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

Піднімемо обидві її частини до степені (-y): (x(-y)(p-1)(q-1))mod n = 1(-y) = 1. Тепер помножимо обидві частини на x: (x(-y)(p-1)(q-1)+1)mod n = 1*x = x.

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

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

Питання для самоконтролю

  1. В чому полягає захист інформації від несанкціонованого доступу?

  2. Що вивчає наука криптографія?

  3. Дайте характеристику симетричних криптографічних систем.

  4. Охарактеризуйте асиметричні криптографічні системи.

  5. Що таке електронний цифровий підпис?

  6. Чим регулюється правове забезпечення електронного цифрового підпису в Україні?

  7. Для чого призначена сертифікація ключів?

  8. У чому полягає процедура аутентифікації та авторизації користувачів?

  9. Які вимоги ставляться до паролів?

  10. Комп’ютерні віруси та антивірусні програми.

  11. Програмні засоби захисту та резервування інформації