Цифровая подпись на базе RSA

Число d, мультипликативно обратное к числу e по модулю M
Число d называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
проще говоря, DE = 1 (mod М) означает, что остаток от деления DE на М должен быть равен 1

Следующий пример наглядно демонстрирует алгоритм шифрования RSA:
Зашифруем и расшифруем сообщение "САВ" по алгоритму RSA. Для простоты возьмем небольшие числа - это сократит наши расчеты.
Выберем p=3 and q=11.
Определим n= 3*11=33.
Hайдем (p-1)*(q-1)=20. Следовательно, d будет равно, например, 3: (d=3).
Выберем число е по следующей формуле: (e*3) mod 20=1. Значит е будет равно, например, 7: (e=7).
Представим шифруемое сообщение как последовательность чисел в диапозоне от 0 до 32 (незабывайте, что кончается на n-1). Буква А =1, В=2, С=3.
Теперь зашифруем сообщение, используя открытый ключ {7,33}
C1 = (3^7) mod 33 = 2187 mod 33 = 9;
C2 = (1^7) mod 33 = 1 mod 33 = 1;
C3 = (2^7) mod 33 = 128 mod 33 = 29;
Теперь расшифруем данные, используя закрытый ключ {3,33}.
M1=(9^3) mod 33 =729 mod 33 = 3(С);
M2=(1^3) mod 33 =1 mod 33 = 1(А);
M3=(29^3) mod 33 = 24389 mod 33 = 2(В);

Данные расшифрованы!

Все просто.

Если два числа a и b (a, b ∈ Z) при делении на число m (m ∈ N) дают один и тот же остаток r, где 0

— криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.