Алгоритм RSA (вывозящий) RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом.
RSA стал первым алгоритмом такого типа, пригодным и для шифрования, и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений.
Алгоритм создания открытого и секретного ключей
RSA-ключи генерируются следующим образом:
1. Выбираются два случайных простых числа p и q заданного размера (например, 1024 бита каждое).
2. Вычисляется их произведение n = pq, которое называется модулем.
3. Вычисляется значение функции Эйлера от числа n:
4. Выбирается целое число e взаимно простое со значением функции . Обычно в качестве e берут простые числа, содержащие небольшое количество единичных битов в двоичной записи, например, простые числа Ферма 17, 257 или 65537.
5. Вычисляется число d, мультипликативно обратное к числу e по модулю , то есть число, удовлетворяющее условию:
или: где k — некоторое целое число.
6. Пара P = (e,n) публикуется в качестве открытого ключа RSA (англ. RSA public key).
7. Пара S = (d,n) играет роль секретного ключа RSA (англ. RSA private key) и держится в секрете.
Число n называется модулем, а числа e и d — открытой и секретной экспонентами, соответственно.
Пример: