 |
|
Цифровая подпись RSA.
Реализует так называемую схему с восстановлением сообщения и является фактически той же самой системой асимметричного шифрования с инвертированным порядком применения шифрующих экспонент. Для обеспечения стойкости, как и при шифровании необходимо, чтобы каждый абонент имел свой модуль для вычислений. Кроме того, если RSA используется и для шифрования и для подписывания сообщений, для решения каждой из этих задач обязательно использования разных наборов ключей.
Абонент, желающий подписывать сообщения на секретном ключе ключе, выбирает два простых числа p и q и вычисляет:
Открытая экспонента, как и при шиффровании выбирается из условия 
. Соблюдение данного требования обязательно по условию возможности проверки подписи.
Закрытая экспонента находится при помощи обобщенного алгоритма Евклида: 
Открытым ключом является пара: 
Закрытым ключом является набор: 
Подписание сообщения M производится как: 
Так как для удобства абонентов, выполняющих проверку подписи на открытом ключе, предлагается выбирать малые экспоненты E, значение d может иметь значительно больший размер, поэтому удобнее выполнять возведение в степень по методу «разделяй и властвуй» по модулям простых чисел p и q:
Значение S затем восстанавливается при помощи китайской теоремы об остатках из системы сравнений:
Проверка подписи осуществляется как: 
Подпись считается правильной, при корректном восстановлении исходного сообщения M = M’
Задача 4.1. Для заданной пары простых чисел p и q и открытого текста M, определить самостоятельно остальные параметры схемы электронно-цифровой подписи RSA и осуществить подписание сообщения. Проверить правильность цифровой подписи. (При возможном переполнении регистра калькулятора – воспользоваться КТО аналогично задаче 3.3.)
Пример решения
| Дано: p = 113 q = 131 M = 765 | Решение:
|
| Найти: N, φ(N), E, d, S, M’ Проверить: M’ = M | |
|