Алгоритм RSA предложен в 1978 г. тремя авторами: Райвестом (Rivest), Шамиром (Shamir) и Адлеманом (Adleman). Это первый полноценный алгоритм с открытым ключом, который может работать в режиме шифрования и ЭЦП. Алгоритм использует две однонаправленные функции: произведение больших простых чисел и модульную экспоненту.
Безопасность RSA базируется на трудности разложения большого числа на произведение двух простых чисел (факторизация).
Задача факторизации является трудно разрешимой задачей для больших значений модуля N.
Сначала авторы алгоритма RSA предлагали для вычисления модуля N выбирать простые числа Р и Q случайным образом, по 50 десятичных разрядов каждое. Считалось, что такие большие числа N очень трудно разложить на простые множители. Один из авторов алгоритма RSA, Р. Райвест, полагал, что разложение на простые множители числа из почти 130 десятичных цифр, приведенного в их публикации, потребует более 40 квадриллионов лет машинного времени. Однако этот прогноз не оправдался из-за сравнительно быстрого прогресса компьютеров и их вычислительной мощности, а также улучшения алгоритмов факторизации.
Криптосистемы RSA реализуются как аппаратным, так и программным путем.
Для аппаратной реализации операций шифрования и расшифрования RSA разработаны специальные процессоры. Эти процессоры, реализованные на сверхбольших интегральных схемах, позволяют выполнять операции RSA, связанные с возведением больших чисел в колоссально большую степень по модулю N, за относительно короткое время. И все же аппаратная реализация RSA примерно в 1000 раз медленнее аппаратной реализации симметричного криптоалгоритма DES.
Программная реализация RSA примерно в 100 раз медленнее программной реализации DES. С развитием технологии эти оценки могут несколько изменяться, но асимметричная криптосистема RSA никогда не достигнет быстродействия симметричных криптосистем.
Следует отметить, что малое быстродействие криптосистем RSA ограничивает область их применения, но не перечеркивает их ценность.