Швидкість роботи алгоритму RSA

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

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

Таким чином час виконання операцій зростає зі збільшенням кількості ненульових бітів у двійковому поданні відкритої експоненти e. Щоб збільшити швидкість шифрування, значення e часто вибирають рівним 17, 257 або 65 537 - простим числам, двійкове подання яких містить лише дві одиниці: 17 = 0x11, 257 = 0x101, 65537 = 0x10001 (прості числа Ферма).

За евристичним оцінками довжина секретної експоненти d, нетривіальним чином залежною від відкритої експоненти e і модуля n, з великою ймовірністю близькою до довжини n. Тому розшифрування даних йде повільніше ніж шифрування, а перевірка підпису швидше ніж підписання.

Алгоритм RSA набагато повільніше ніж DES і інші алгоритми блокового шифрування. Програмна реалізація DES працює швидше, принаймні, в 100 разів і від 1000 до 10 000 - в апаратній реалізації (в залежності від конкретного пристрою). [Джерело не вказано 300 днів]