Digital Signatures

One of the most useful constructs that can be built using the primitive cryptographic operations previously described is the digital signature.

To create a digital signature of a message, first produce a message digest of the message (e.g. with SHA-1) then encrypt it with an asymmetric cryptographic algorithm (e.g. RSA) and the private key of the person creating the digital signature. The message and the encrypted digest (signature) are sent to the recipient, usually along with the signer's public key (in the form of a digital certificate).

To verify a signature as valid, the recipient decrypts the received encrypted digest (which recovers the original digest produced by the sender), then regenerates the digest from the received message. If the recovered digest matches the regenerated digest, then the signature is valid. A valid signature is proof that the message was signed by the private key corresponding to the public key used to verify it. It is also proof that the message has not been tampered with in any way since it was signed. Note that non-malicious changes (e.g. extra blanks, insertion of a timestamp, etc) will produce an invalid signature. Assuming good key management, this means the message came from the purported sender (sender authentication) and the message is intact (message integrity). A thrid benefit is non-repudiation. This means that since only the owner of the private key could have signed it correctly, that person cannot deny having sent this message. Of course they could always say their private key had been compromised, but then all of their digitally signed messages would be suspect. In general you can trust messages with a valid signature, but you should suspect any message where the signature fails to verify.

The recipient needs the sender's public key to verify the signature. This is usually obtained in the form of a digital certificate, so that you can trust the public key to be that of the sender. This certificate could have been previously cached on the receipient's computer or retrieved from a directory. It doesn't matter how the recipient obtains the sender's digital certificate since it can be independently verified as valid. It can be (and often is) included as part of the message. The standard way to append a signature (and optionally the sender's digital certificate) to a message is covered in RFC 5751, "Secure/Multipurpose Internet Mail Extensions (S/MIME) Version 3.2 Message Specification", January 2010. This also covers digital envlopes (a privacy mechanism).


Digital Signatures in Math Notation

In math notation a digital signature looks like this (note - although this section uses "SHA1" and "RSA", any message digest and asymmetric encryption algorithms can be used. SHA1 and RSA are the most common such algorithms used).

M = Message

SHA1 = Message Digest algorithm

MD = Message Digest

RSA = Asymmetric encryption algorithm, RSA-1 = Asymmetric decryption algorithm

Kpriv = private key of signer, Kpub = public key of signer

EMD = Encrypted Message Digest (Digital Signature)

MD' = Recovered Message Digest (decrypted from EMD)

MD'' = Regenerated Message Digest


Digitally signing a message

MD = SHA1(M)

EMD = RSA(MD, Kpriv)

Send recipient M, EMD and typically Kpub

Verifying a Digital Signature

Receive M, EMD and typically Kpub, from sender

MD' = RSA-1(EMD, Kpub)   (recovered digest)

MD'' = SHA1(M)            (digest of received message)

if MD' == MD'', then the signature is valid


Details About Using Digital Signatures

The signer requires only their own private key to sign a document, and the recipient requires only the signer's public key to validate the signature. So long as the signer's public key is provided in a digital certificate, and the recipient validates that digital certificate, it does not matter how the recipient obtains the signer's digital certificate (it can be retrieved from a directory or even sent along with the message). If the signer's public key digital certificate has been revoked, you should not trust any signatures created using the corrresponding private key.

If the signer's key material expires (or is lost or compromised) and replaced, all existing signatures created with the old private key can still be valdiated using the signer's public key digital certificate (even if that is expired). Any signatures created with the new key will require the new public key digital certificate to validate. This means you should either keep copies of the expired public key digitlal certificate around (to check old signatures), or you should resign all documents with the new private key (if possible). If key renewal is done by embedding the old public key in a new certificate (renewal with rollover), then either the old or the new digital certificate can be used to validate old or new signatures.

Digital Signatures are used in many places. They are used in S/MIME secure email to provide sender authentication (authentication of the sender to the recipient) and message integrity. They are also used on documents (e.g. PDF or MS Office files) to establish the creator of the document and detect tampering. There is a standard for adding a digital signature to any XML message. As elsewhere it can be used to establish the identity of the XML document creator and to detect tampering in specified parts of the XML message.


Example Digitally Signed Messages

If you click on the following link, it should download a digitally signed email message with a valid signature, and load it into your default email client (e.g. Outlook, Windows Live Mail, or Thunderbird). You should be able to see the signature information. It is not necessary to have your own digital certificate for this to work. Anyone can check the validity of a digitally signed message.

Digitally Signed Message.eml

This link contains the same message, but the text has been tampered with ("all good men" has been changed to "all bad men"). This will cause the digtial signature to fail.

Digitally Signed Message - modified.eml