Системы цифровой подписи на основе сложности факторизации чисел специального вида
Теорема Эйлера: для любых взаимно простых целых чисел M и n, где M < n, выполняется соотношение В криптосистеме RSA в качестве числа M используется сообщение, которое необходимо подписать или зашифровать. Будем полагать, что условие взаимной простоты чисел М и n выполняется. Например, это обеспечивается тем, что в данной криптосистеме выбирается число n, равное произведению двух больших простых множителей. Поэтому вероятность того, что случайное сообщение не будет взаимно простым с модулем, является пренебрежимо малым. Алгоритм формирование ключей:
Секретным ключом является тройка чисел р, q и d. Открытым ключом является пара n и е, которая сообщается пользователям. Процедура подписывания сообщения: Процедура проверки подписи:
|
.
и вычисляет значение функции Эйлера 
. Числа р и q являются частью закрытого ключа и должны иметь специальную структуру. Для этого разложение на простые сомножители, по крайней мере, одно из чисел (р ‑ 1) или (q ‑ 1) должно иметь один большой простой множитель.Модуль n является частью открытого ключа и его размер должен быть не менее 1024 бит.
и 
, и вычисляется число е, удовлетворяющее условию 
. 
.
. Если 
, то сообщение М признается подписанным.
