Схема RSA.

RSA [Schn 96] используется как для шифрования, так и для подписи. 
Выберем  p и q – большие простые числа. Пусть модуль n = pq, функция
 (n) = (p-1)(q-1) – функция Эйлера. Возьмем произвольное 
1 е(n) такое, что НОД(е, (n)) = 1. Тогда существует единственное 
1 d (n) такое, что ed(mod(n)) = 1. 
Система шифрования RSA – это система с открытым ключом, где 
е –открытый, а d – секретный ключи. Если 0 x<n – это открытое сообщение, то шифрсообщение получается следующим образом:
С = х(mod n).
Возможность расшифрования следует из следующей теоремы.
Теорема 1. Если p и q – большие простые числа, ed(mod(n)) = 1, то  х, 0 x<n:
(х)(modn) = x.
Д о к а з а т е л ь с т в о. Пусть НОД(х, n) =1. Тогда 
(х) = х = x .
Поэтому по теореме Эйлера 
(х)(modn) = (х( x(modn)))(modn)= (x 1)(modn) = x.
Если НОД(х,n)  1, то или х =0(modn), или НОД(х,n) = p, или НОД(х,n) = q. Если х =0(modn), то х =0(modn). Пусть НОД(х,n) = p. Тогда х = хp, где 
(х, n) =1.
х= x= pxpx  y(modpq).
Если mp= y(mod(pq)), то mp = pqk + y, следовательно, y = py. Тогда 
m  y(modq. Следовательно, 
x((pх))  y (modq).
По теореме Ферма z  1 (modq). Поэтому
x= xp(mod(pq)) = y (modn)  х(modn),
что и требовалось доказать.
Открытый и шифрованный тексты эффективно вычисляются, если известны е и d при помощи алгоритма быстрого возведения в степень. Если искать секретный ключ d по известному открытому ключу е, то надо 
знать (n).  
Теорема 2.  Вычисление (n) = (p-1)( q-1) эквивалентно (с точностью до алгоритма полиномиальной сложности) факторизации числа n = pq.
Д о к а з а т е л ь с т в о. Пусть известны n и (n). Тогда p и q находятся быстро. Это следует из следующих равенств.
(n) = (p-1)(q-1) = pq-p-q+1 = n-p-q+1.
Отсюда
p+q= n-(n)+1,
pq = n.
По теореме, обратной к теореме  Виета,  p и q являются корнями квадратного уравнения:
х- (n -(n)+1)x + n = 0.
Вычисление корней – полиномиальный алгоритм. Обратно, если известны p и q, pq = n, то (n) = (p-1)(q-1). Теорема доказана. 

Подпись RSA.
Пусть М – сообщение, которое надо подписать. Подпись получается по следующему алгоритму:
С = М(mod n),
тогда (М, С) - сообщение с подписью. Проверка подписи осуществляется следующим образом
С( mod n) =  М(mod n) = М’.
Если М = М’, то подпись верна.