RSA (назван по имени авторов - Rivest, Shamir и Alderman) - это алгоритм с открытым ключом (public key), предназначенный как для шифрования, так и для аутентификации (цифровой подписи). Алгоритм шифрования с открытым ключом RSA был предложен одним из первых в конце 70-х годов ХХ века. Его название составлено из первых букв фамилий авторов: Р.Райвеста (R.Rivest), А.Шамира (A.Shamir) и Л.Адлемана (L.Adleman). Алгоритм RSA является, наверно, наиболее популярным и широко применяемым асимметричным алгоритмом в криптографических системах. Он основан на трудности разложения очень больших целых чисел на простые сомножители (факторизации).
RSA - очень медленный алгоритм. Для сравнения, на программном уровне DES по меньше мере в 100 раз быстрее RSA; на аппаратном - в 1 000-10 000 раз, в зависимости от выполнения.
Алгоритм основан на использовании того факта, что задача разложения большого числа на простые сомножители является трудной. Криптографическая система RSA базируется на следующих двух фактах из теории чисел:
- задача проверки числа на простоту является сравнительно легкой;
- задача разложения чисел вида n = pq ( р и q — простые числа); на множители является очень трудной, если мы знаем только n, а р и q — большие числа (это так называемая задача факторизации).
Алгоритм RSA представляет собой блочный алгоритм шифрования, где зашифрованные и незашифрованные данные должны быть представлены в виде целых чисел между 0 и n -1 для некоторого n.