5.3. Digital Signatures

PK encryption can be used for digitally signing an electronic document in a way that allows for later validation for authenticity [5]. We explain here, with the help of Fig. 5.3, how digital signatures work.

Suppose that A wants to send a message Msg to B. The following steps are followed by A before sending the message.

1.	A generates a fixed size string, called the message digest (MD), by applying a one-way hash function h to the message Msg. So MD = h (Msg). For a hash function to be useful for digital signatures, it must have the following properties: it should be easy to compute h (Msg), it should be very hard to obtain Msg given h (Msg), and it should be very hard to find another message Msg' such that Examples of hash functions used to compute message digests are MD4, MD5, SHA, and SHA-1 [13]. The size of the strings generated by these functions are 128, 128, 160, and 160 bits, respectively.
2.	The message digest MD is encrypted with A's private key resulting in an encrypted message digest Encrypt (MD, ).
3.	At this point, A assembles a message to be sent to B, composed of the original message and the encrypted message digest. Thus, A sends to B the pair (Msg, Encrypt (MD, )).
4.	B receives the pair (Msg, Encrypt (MD, )) from A and does the following: it computes the message digest MD from the message Msg using the same hash function h used by A. it decrypts the encrypted message digest Encrypt (MD, ) received from A using A's public key. In other words, B performs the computation Decrypt (Encrypt (MD, ), ). The result should be the original message digest MD if a) the message was not tampered with during transmission and b) the message was indeed sent by A. If the message was not sent by A, then using A's public key would not produce the same message digest. If the message was corrupted during transmission, a different message digest would have been computed by B.

Steps 1-3 above are the steps needed to sign a message and step 4 is the verification step. A message is signed with the private key of the signer and verified with the public key of the signing party. Thus, for the reasons explained in Section 5.2.2, message verification is much faster than message signing.

So, as we can see, digital signatures can be used to verify the authenticity of the sender of the message and to verify data integrity. If we wanted to ensure confidentiality as well, the message contents should also be encrypted.

We are now ready to explain in the next section how authentication protocols work.