Системы цифровой подписи на основе сложности факторизации чисел специального вида

Теорема Эйлера: для любых взаимно простых целых чисел M и n, где M < n, выполняется соотношение .

В криптосистеме RSA в качестве числа M используется сообщение, которое необходимо подписать или зашифровать.

Будем полагать, что условие взаимной простоты чисел М и n выполняется. Например, это обеспечивается тем, что в данной криптосистеме выбирается число n, равное произведению двух больших простых множителей. Поэтому вероятность того, что случайное сообщение не будет взаимно простым с модулем, является пренебрежимо малым.

Алгоритм формирование ключей:

1. Каждый пользователь выбирает два больших не равных между собой простых числа р и q, находит их произведение и вычисляет значение функции Эйлера . Числа р и q являются частью закрытого ключа и должны иметь специальную структуру. Для этого разложение на простые сомножители, по крайней мере, одно из чисел (р ‑ 1) или (q ‑ 1) должно иметь один большой простой множитель.Модуль n является частью открытого ключа и его размер должен быть не менее 1024 бит.
2. Затем выбирается целое число d, что и , и вычисляется число е, удовлетворяющее условию .

Секретным ключом является тройка чисел р, q и d. Открытым ключом является пара n и е, которая сообщается пользователям.

Процедура подписывания сообщения: .

Процедура проверки подписи: . Если , то сообщение М признается подписанным.