Digital Signatures: Integrity in Public-Key Systems

Integrity is guaranteed in public-key systems by using digital signatures. A digital signature is a piece of data which is attached to a message and which can be used to find out if the message was tampered with during the conversation (e.g. through the intervention of a malicious user).

The digital signature for a message is generated in two steps:

1. A message digest is generated. A message digest is a 'summary' of the message we are going to transmit, and has two important properties:
   

1. It is always smaller than the message itself and

2. Even the slightest change in the message produces a different digest.

The message digest is generated using a set of hashing algorithms.

2. The message digest is encrypted using the sender's private key. The resulting encrypted message digest is the digital signature.

Figure 6. Digital signatures

The digital signature is attached to the message, and sent to the receiver. The receiver then does the following:

1. Using the sender's public key, decrypts the digital signature to obtain the message digest generated by the sender.


2. Uses the same message digest algorithm used by the sender to generate a message digest of the received message.


3. Compares both message digests (the one sent by the sender as a digital signature, and the one generated by the receiver). If they are not exactly the same, the message has been tampered with by a third party. We can be sure that the digital signature was sent by the sender (and not by a malicious user) because only the sender's public key can decrypt the digital signature (which was encrypted by the sender's private key; remember that what one key encrypts, the other one decrypts, and vice versa). If decrypting using the public key renders a faulty message digest, this means that either the message or the message digest are not exactly what the sender sent.

Using public-key cryptography in this manner ensures integrity, because we have a way of knowing if the message we received is exactly what was sent by the sender.