Система RSA

Коректний вибір ключів та шифрування

Вибираємо два досить великі прості числа р і q , і для їх добутку п = рq обчислюють значення функції Ейлера   φ(n)=(p-1)(q-1). Далі випадковим чином вибирають елемент e, що не перевищує значення φ(n) і взаємно простий з ним. Для е за алгоритмом Евкліда знаходимо елемент d, обернений до е в Z^*_Фі(n)  ,
тобто такий, що
d < φ(n) і
ed Ξ φ(n)
Як результат покладають:
Відкритий ключ: е, п.
Таємний ключ: d.
Шифрування відбувається блоками. Для цього повідомлення записують у цифровій формі і розбивають на блоки так, щоб кожен блок позначає число, яке не перевищу п
Алгоритм шифрування Е  у системі RSA полягає у піднесенні М до степеня е. Записуємо це гак:
E(M) = M ⁿ mod n
В результаті отримаємо блок криптотексту:
 D(C) = C ^d mod n

Криптоаналіз

Алгоритм дешифрування блоку криптотексту С полягає у піднесенні С до степеня d, тобто:
D(C) = C ^d mod n.