Данный алгоритм основан на нахождении больших простых чисел. Если большое число довольно просто разложить на простые множители, то произведение двух больших простых чисел практически невозможно. Раскрытие шифра RSA эквивалентно такому разложению.
Генерация открытого ключа происходит следующим образом:
1)Выбирают два очень больших простых числа p и q.
2)Вычисляется n=p?q
3)Выбирается большое случайное число d, которое должно быть взаимно простым с числом (p-1)(q-1)
4)Определяется число e, для которого истинно следующее соотношение
e?d mod ((p-1)(q-1))=1
5)числа e и n являются открытым ключем, а d и n – закрытым
Принцип шифрования:
1)Исходный текст разбивается на блоки, каждый из которых может быть представлен в виде числа M(i)=0, 1, 2, … n-1
2)Последовательность чисел M(i) шифруется с помощью открытого ключа (e,n) по формуле C(i)=(M(i))e mod n
Чтобы расшифровать эти данные, используется секретный ключ (d,n) и выполняется следующее вычисление M(i)=(C(i))d mod n. В результате будет получено множество чисел M(i), которое представляет собой исходный текст.
Данный алгоритм реализуется как в виде самостоятельного программного продукта (PGP), так и в качестве вспомогательных средств в приложениях.
Проблема программной реализации данного алгоритма состоит в генерации больших простых чисел. Другая проблема – какой длины выбирать ключ.