Алгоритм цифровой подписи RSA

Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSA.

Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель электронных документов вычисляет два больших простых числа P и Q, затем находит их произведение

N = P∙Q

и значение функции

j (N) = (P –1)(Q –1).

Далее отправитель вычисляет число E из условий:

E £ j (N), НОД (E, j(N)) =1

и число D из условий:

D < N, E∙D º1 (mod j(N)).

Пара чисел (E,N) является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число D сохраняется отправителем как секретный ключ для подписывания.

Обобщенная схема формирования и проверки цифровой подписи RSA показана на приводимом ниже рисунке.

Допустим, что отправитель хочет подписать сообщение M перед его отправкой. Сначала сообщение M (блок информации, файл, таблица) сжимают с помощью хэш-функции H(·) в целое число m:

m = H(M).

Затем вычисляют цифровую подпись S под электронным документом M, используя хэш-значение m и секретный ключ D:

S = m^D (mod N).

Пара (M,S) передается партнеру-получателю как электронный документ M, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа D.

После приема пары (M,S) получатель вычисляет хэш-значение сообщения M двумя разными способами. Прежде всего он восстанавливает хэш-значение m´, применяя криптографическое преобразование подписи S с использованием открытого ключа E:

m´ = S^E (mod N).

Кроме того, он находит результат хэширования принятого сообщения M с помощью такой же хэш-функции H(·):

m = H(M).