A digital signature is a cryptographic checksum computed as a function of a message and a user's private key. A digital signature is different from a hand-written signature, in that hand-written signatures are constant, regardless of the document being signed. A user's digital signature varies with the data. For example, if a user signs five different messages, five different signatures are generated. Each signature, however, can be authenticated for the signing user.
Due to the efficiency drawbacks of public-key cryptography, a user often signs a condensed version of a message, called a message digest, rather than the message itself. Message digests are generated by hash functions.
A hash function is a keyless transformation function that, given a variable-sized message as input, produces a fixed-sized representation of the message as output (i.e., the message digest). For example, a hash function may condense a one-megabyte message into a 128 or 160-bit digest. For a hash function to be considered secure, it must meet two requirements; the hash function must be 1-way and collisionless. 1-way means that given a digest and the hash function, it is computationally infeasible to find the message that produced the digest. Collisionless means that it is not possible to find two messages that hash to the same digest. If a hash function meets the collisionless and 1-way requirements, signing a message digest provides the same security services as signing the message itself.
The following example describes the digital signature process. It assumes two users have agreed upon a hash function and a signature algorithm for the signature verification process. For clarity, message secrecy is not included in the example.
An originator needs to send a signed message to a recipient. The originator performs the following procedure:
Upon receiving the message, the recipient performs the following procedure:
If the signature is verified, the following services are provided. First, the recipient is assured that the message was not modified. If even one bit of the original message was changed, the digest generated using the received message would cause the signature verification process to fail. Second, the recipient is assured that the originator sent the message. Public key transformation functions are 1-way (i.e., not forgeable); therefore, only a signature generated by the originator's private key can be validated using the originator's public key.
In addition to integrity and authentication, digital signatures provide non-repudiation with proof of origin. Non-repudiation with proof of origin is similar to authentication, but stronger in that the proof can be demonstrated to a third party. To provide authentication and non-repudiation with proof of origin using a digital signature, a message originator signs a message (or digest) using the private key bound to the originator. Since only the originator can access the private key, the signature is unforgeable evidence that the originator generated the message. In contrast, non-repudiation with proof of origin cannot inherently be provided in a conventional cryptosystem. Since both parties involved in a communication share a secret key, both parties can deny sending a message, claiming that the other party is the message originator.
In addition to the non-repudiation with proof of origin service, public-key cryptography has another advantage over conventional cryptography. The keys exchanged in a public-key system need not be kept secret. Thus, key distribution with a public-key system is simplified as compared to a private-key system.