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