Cryptography provides the basis for a number of privacy and authentication mechanisms used in computer-based systems. One such mechanism is a digital signature, which is often used to authenticate the sender of an electronic message. To create a digital signature, the sender first creates a private signature key and a corresponding public verification key. To sign a message or other document, the sender performs a computation that takes as input the message and the private signature key and produces as output a digital signature for that message. To verify a digital signature, a receiver performs a computation that takes as input the message, the digital signature for that message, and the public verification key, and produces as output either “signature verified” or “signature failed to verify.”
In order to facilitate the authentication of a digitally signed document, the receiver must be assured that the public verification key that is used to verify the signature is indeed the public verification key belonging to the sender of the message. Typically, the receiver will obtain a digital certificate, which contains the identity of the sender, the public verification key of the sender, and other information. Typically, this digital certificate is digitally signed by a certification authority. Other mechanisms are also used for establishing the correspondence between an identity and a public verification key such as an entry in a database.