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

Математическая схема электронной цифровой подписи по алгоритму RSA была предложена в 1977 году сотрудниками Массачусетского технологического института США. Данная система цифровой подписи стала первым практическим решением задачи подписи электронных документов при помощи криптосистем с открытым ключом. Процедура вычисления цифровой подписи в данной системе использует криптографическое преобразование по алгоритму RSA.

В соответствии с данной системой цифровой подписи, субъект, желающий пересылать подписанные им документы, должен сформировать два ключа алгоритма RSA: открытый и закрытый.

Пару значений (KO, r), которая является открытым ключом подписи, отправитель передаёт всем возможным получателям его сообщений. Именно эти значения будут использоваться для проверки подлинности и принадлежности отправителю полученных от него сообщений.
Значение KC сохраняется отправителем в секрете. Данное значение вместе с модулем r является секретным ключом, который будет использоваться отправителем для постановки подписей под своими сообщениями.

Схема использования алгоритма цифровой подписи на базе RSA для обмена двух абонентов подписанными сообщениями показана на рис. 14.

Рис. 14 . Схема использования цифровой подписи на базе RSA
Допустим, что получатель уже располагает открытым ключом подписи отправителя. Процедура подписи отправителем сообщения M будет состоять из следующих шагов.

1. Отправитель сжимает сообщение M при помощи криптографической хеш-функции h в целое число m = h(M).
2. Отправитель вычисляет значение цифровой подписи S для сообщения M на основе ранее полученного значения хеш-образа m и значения своего закрытого (секретного) ключа подписи KC. Для этого используется преобразование, аналогичное преобразованию, выполняемому при шифровании по алгоритму RSA:
                                           (24)
Пара (М, S), представляющая собой подписанное отправителем сообщение, передаётся получателю. Сформировать подпись S мог только обладатель закрытого ключа KC.
Процедура проверки получателем подлинности сообщения и принадлежности его отправителю состоит из следующих шагов.

• Получатель сжимает полученное сообщение M’ при помощи криптографической хеш-функции h, идентичной той, которая была использована отправителем, в целое число m’.
• Получатель выполняет расшифрование открытым ключом KO отправителя дайджеста m оригинального сообщения, преобразуя значение подписи S по алгоритму RSA:

.                                           (25)
3. Получатель сравнивает полученные значения m’ и m. Если данные значения совпадают, т. е.
,                                        (26)
то получатель признает полученное сообщение подлинным и принадлежащим отправителю.

Фальсификация сообщения при его передаче по каналу связи возможна только при получении злоумышленником секретного ключа KC  либо за счет проведения успешной атаки против использованной для вычисления дайджеста сообщения хеш-функции. При использовании достаточно больших значений p и q определение секретного значения KC по открытому ключу (KО, r) является чрезвычайно трудной задачей, соответствующей по сложности разложению модуля r на множители. Используемые в реальных приложениях хеш-функции обладают характеристиками, делающими атаку против цифровой подписи практически неосуществимой.

Автор: Ярмолик, В. Н.