1. Шифрування з секретним ключем

Алгоритм 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.

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