5.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=[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.

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