Зашифровывается хеш сообщения и посылается вместе с сообщением. Расшифровав хэш и сверив его с вычесленным самостоятельно, можно убедиться в подлинности сообщения.
Сертификат которым подписано сообщение обычно сам имет подпись какого-либо доверенного центра сертификации. Или же вы просто сами уверены, что сертификат точно пренадлежит организации или человеку.