RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших полупростых чисел.
Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений, включая PGP, S/MIME, TLS/SSL, IPSEC/IKE и других.
Алгоритм шифрования с открытым и закрытым ключом приписывается Уитфилду Диффи и Мартину Хеллману, которые опубликовали эту концепцию в 1976 году. Они также ввели цифровые подписи и попытались применить теорию чисел. В их формулировке использовался секретный ключ с общим доступом, созданный путем экспоненциализации некоторого числа, простого по модулю. Однако они оставили открытой проблему реализации односторонней функции, возможно, потому что сложность факторизации в то время не была хорошо изучена.
Рон Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института в течение года предприняли несколько попыток создать одностороннюю функцию, которую было бы трудно инвертировать. Ривест и Шамир, будучи компьютерными учеными, предложили множество потенциальных функций, а Адлеман, будучи математиком, отвечал за поиск их слабых мест. Они опробовали множество подходов, включая “ранцевый” и “перестановочные полиномы”. Какое-то время они думали, что-то, чего они хотели достичь, невозможно из-за противоречивых требований. В апреле 1977 года они провели Песах в доме одного из студентов и выпили много манишевицкого вина, а затем вернулись к себе домой около полуночи. Ривест, не в силах заснуть, лег на диван с учебником математики и начал думать о своей односторонней функции. Остаток ночи он провел, формализуя свою идею, и к рассвету большая часть статьи была готова. Алгоритм теперь известен как RSA – инициалы их фамилий в том же порядке, что и в их статье.
Клиффорд Кокс, английский математик, работавший в британской разведывательной службе Government Communications Headquarters (GCHQ), описал эквивалентную систему во внутреннем документе в 1973 г. Однако, учитывая относительно дорогие компьютеры, необходимые для ее реализации в то время, она считалась в основном курьезом и, насколько известно, так и не была применена. Однако его открытие было раскрыто только в 1997 году из-за его сверхсильного засекречивания.
Алгоритм шифрования RSA основан на следующих шагах:
1. Генерация ключей:
– Выбор двух простых чисел p и q.
– Вычисление произведения n = p * q.
– Вычисление функции Эйлера от числа n, φ(n) = (p-1) * (q-1).
– Выбор числа e, которое является взаимно простым с числом φ(n) и меньше его.
– Вычисление числа d, которое является обратным по модулю φ(n) для числа e. То есть, e * d ≡ 1 (mod φ(n)).
– Пара чисел (e, n) является открытым ключом, а (d, n) – закрытым ключом.
2. Зашифрование сообщения:
– Преобразование сообщения в числовое представление m.
– Вычисление зашифрованного сообщения c = m^e (mod n).
3. Дешифрование сообщения:
– Вычисление расшифрованного сообщения m’ = c^d (mod n).
– Преобразование числового представления m’ обратно в исходное сообщение.
Этот алгоритм основан на том факте, что взятие больших степеней чисел по модулю числа n является вычислительно сложной задачей, в то время как нахождение обратного элемента по модулю n выполняется довольно быстро. RSA шифрование считается криптографически стойким и широко используется для защиты данных.
Система RSA используется для защиты программного обеспечения и в схемах цифровой подписи.
Также она используется в открытой системе шифрования PGP и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании с симметричными алгоритмами.
Из-за низкой скорости шифрования сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным сеансовым ключом (например, AES, IDEA, Serpent, Twofish), а с помощью RSA шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема. Такой механизм имеет потенциальные уязвимости ввиду необходимости использовать криптографически стойкий генератор псевдослучайных чисел для формирования случайного сеансового ключа симметричного шифрования.