Some public-key algorithms can be used to generate digital signatures. A digital signature is a small amount of data that was created using some private key, and there is a public key that can be used to verify that the signature was really generated using the corresponding private key. The algorithm used to generate the signature must be such that without knowing the private key it is not possible to create a signature that would verify as valid.

Digital signatures are used to verify that a message really comes from the claimed sender (assuming only the sender knows the private key corresponding to the public key). This is called (data origin) authentication. They can also be used to timestamp documents: a trusted party signs the document and its timestamp with his/her private key, thus testifying that the document existed at the stated time.

Digital signatures can also be used to certify that a public key belongs to a particular entity. This is done by signing the combination of the public key and the information about its owner by a trusted key. The resulting data structure is often called a public-key certificate (or simply, a certificate). Certificates can be thought of as analogous to passports that guarantee the identity of their bearers.

The trusted party who issues certificates to the identified entities is called a certification authority (CA). Certification authorities can be thought of as being analogous to governments issuing passports for their citizens.

A certification authority can be operated by an external certification service provider, or even by a government, or the CA can belong to the same organization as the entities. CAs can also issue certificates to other (sub-)CAs. This leads to a tree-like certification hierarchy. The highest trusted CA in the tree is called a root CA. The hierarchy of trust formed by end entities, sub-CAs, and root CA is called a public-key infrastructure (PKI).

A public-key infrastructure does not necessarily require an universally accepted hierarchy or roots, and each party may have different trust points. This is the web of trust concept used, for example, in PGP.

A digital signature of an arbitrary document is typically created by computing a message digest from the document, and concatenating it with information about the signer, a timestamp, etc. This can be done by applying a cryptographic hash function on the data. The resulting string is then encrypted using the private key of the signer using a suitable algorithm. The resulting encrypted block of bits is the signature. It is often distributed together with information about the public key that was used to sign it.

To verify a signature, the recipient first determines whether it trusts that the key belongs to the person it is supposed to belong to (using a certificate or a priori knowledge), and then decrypts the signature using the public key of the person. If the signature decrypts properly and the information matches that of the message (proper message digest etc.), the signature is accepted as valid. In addition to authentication, this technique also provides data integrity, which means that unauthorized alteration of the data during transmission is detected.

Several methods for making and verifying digital signatures are freely available. The most widely known algorithm is RSA.