Пусть Серёга хочет послать Натали то же число 3, но на это раз не зашифрованное, а подписанное цифровой подписью. Чтобы создать подпись он использует свой личный ключ (21,17):

s=m^dmodn, где s — подпись, m — сообщение.

В нашем случае получается m^d = 3¹⁷ =129140163. Тогда s=129140163 mod 21. Остаток равен 12. Итак, Серёга отправляет само незашифрованное сообщение — 3, и подпись равную 12.

Получив сообщение Натали проверяет подпись. Для этого с помощью открытого ключа Серёги ей необходимо проверить, что

m=s^emodn,где s — подпись, m — сообщение.

В нашем случае, m= 12⁵ mod 21 =248832 mod 21=3.

Все правильно. Сообщение послано действительно Серёгой.