Digital Signature means some digital data that are attached to a digital document, which cannot be falsified, and which guaranty the integrity and the authenticity of the document.

The "integrity" means that the document has not been changed/corrupted since the time that it was digitally signed, either intentionally or by mistake. The "authenticity" means that we can verify and be sure about the person that signed the document (the author of the document).

So, the Digital Signature on digital documents has the same purpose as the hand-written signature on the hard-copy (printed) documents.

The digital signature is not related to a scanned version of a hard-copy document which is hand-signed, or to a faxed paper document which is hand-signed, or to a scanned image of the hand-signature which is included to a document or attached to an email. All these methods seem to be intuitive for a digital signature, however they do not fully guaranty the integrity and the authenticity of a document, therefore cannot be used as valid digital signatures.

Without being able to sign digital documents, they can never be considered official, because we cannot be sure that they are original and we cannot be sure who is the real author (they can be corrupted and manipulated). So, despite using computers, digital systems and digital documents, we always have to rely on the hard copies of the documents and keep them around for official purposes, since we can't fully trust the digital documents. This means that we will never be able to build totally digital systems for institutions and organizations, free from papers and hard-copy documents.

For example if a citizen has to interact with a governmental institution and sends some documents online, nevertheless he still has to submit the hard copies of the documents in person, since we can't rely on the authorship and correctness of the digital documents.

Or if a person sends a document by email to a bank, the bank cannot rely on it, since it cannot be fully sure about the authenticity (real authorship) of the document, that it is not manipulated or corrupted somehow, or that it is not just a trick or deception.

Only the Digital Signature can guaranty the identity of the author of a document and establish a secure relationship between the people and the digital documents. So, it is an essential tool for enabling/supporting the digital identity, for establishing trust and security on the digital world, and for building a digital society (digital governance, digital business, etc.).

The job of a hash function is to digest (process) an electronic document and to generate from it an extract. No matter how big is the document, the extract has always the same fixed size. Two different documents cannot produce the same extract. A document that is changed even by a single character will produce a different extract after being digested by the hash function.

Different from the symmetric cryptography, which uses the same key for both encryption and decryption, asymmetric cryptography uses one key for encryption and a different one for decryption. Each person has a pair of encryption keys; one of them is private (secret) and is known only by the person himself, and the other key is public and is known by everybody. A message that is encrypted by one of the keys, can be decrypted only by the other key of the pair. It is almost impossible to find the private key from the public key that is known by everybody.

The algorithms that are used for generating a pair of private/public keys and for encrypting and decrypting a message are based on the arithmetic of large prime numbers and calculations with residue classes. It is not difficult to understand them, however this is not the proper place to explain such details. It is enough to know that the asymmetric key cryptography is thought to be quite secure and unbreakable.

To sign a digital document, these steps are followed:

1. The digital document is digested by the hash function and a digital extract is produced.
2. The digital extract of the document is encrypted with the private key of the author.
3. This encrypted extract of the document is the digital signature and it can either be appended to the original document, or can be saved as a separate file.

The verification of the digital signature of a document is done like this:

1. The digital document is digested by the hash function and its digital extract is produced.
2. The digital signature of the document is decrypted with the public key of the author. This gives us the digital extract of the original document.
3. The digital extract of the current document (from the first step) and the digital extract of the original document (from the second step) are compared. If they are the same, then the signature is good and the document is original. Otherwise the signature is bad and the authenticity of the document cannot be guarantied (most probably it has been corrupted, intentionally or by error).

If the two digital extracts compared on the third step are equal, this means that the original document is unmodified (since the digital extract has not changed) and it verifies the authenticity of the author (since his public key is able to decrypt the digital signature correctly).

If these digital extracts are not equal, either the content of the document has been corrupted (by error or intentionally), or the author of the document is not the one who claims to be, or both. Any of these reasons is enough to discard the document as invalid.

Email is a kind of digital document, and it can be signed digitally. Actually it is the document that is most widely used with a digital signature nowadays. This is probably due to the fact that the Internet of today is not secure, and emails can be faked easily, and one cannot be completely sure about its authenticity, unless it is digitally signed.

Suppose that Alice sends an email to Bob. She signs this email using her private key. Then Bob verifies the signature using the public key of Alice. If the verification is successful, then Bob can be sure that this email cannot have been signed except with the private key of Alice. Since only Alice has her private key, then only she can be the signer (and hence the author) of the message.

Consider again the example of the last section, where Alice sends an email to Bob. Where can Bob find the public key of Alice, so that he can verify the authenticity of her message?

There are several ways that Bob can get her public key. Maybe Alice gave it to him directly, using a removable media or sending it as an attachment. Maybe Alice published it on her website and Bob got it from there. Maybe Alice published it on some public key server and Bob retrieved it from there (and this is the most common case in practice).

A Public Key Server (PKS) is like a directory server (a dictionary), where you can look up and retrieve the public key of a given person. Alice can upload her public key on a PKS, and Bob (or anyone else that needs to verify her signature) can look up and retrieve this key from there.

Actually the public key of a person is stored in a digital document that contains also the identity of a person (name, email, address, organization, etc.). This document is called Digital Certificate (or Identity Certificate, or Public Key Certificate). It is the Digital Certificate that is uploaded to a PKS and retrieved from it, and it is the Digital Certificate that makes the relation (connection) between the digital identity of a person and his public key.

Here we are faced with a problem. If Bob retrieved the digital certificate of Alice from a PKS, how can he be sure that it is authentic? How can he be sure that this certificate was uploaded there by Alice and the public key in it really belongs to Alice? Probably somebody else uploaded that digital certificate there instead of Alice, with the identity of Alice but with a different public key.

This is actually a social problem, not a technical one, and it can be solved by social means. Bob can actually call Alice and make sure that the ID of her key is the same as the one that he got from the PKS. Or probably Alice gave Bob a business card where she has also written the ID of her public key, so Bob can check this ID with the ID of the key that he retrieved from the PKS and make sure that it is correct.

However most of the time we communicate with people that we have never met before and we have no idea who they are. It can be that "Alice" is just a fake identity (a nickname or a fake name, not the name of a real person). Or maybe somebody else uploaded the certificate instead of Alice, pretending to be Alice, and the key in the certificate does not really belong to Alice (is a fake public key).

If Bob has never met Alice, then how can he be sure about her real identity? How can he be sure that Alice is a real person and that the messages that he gets are really coming from her and not from somebody pretending to be her? In other words, how can Bob be sure that the digital certificate of Alice, that he gets from the PKS, is authentic?

Just verifying that the signature of the message is correct is not enough. We need to verify also that the digital certificate that was used for the signature is authentic.

Again, this is a social problem and cannot be solved only by technical means. It can be solved only by a combination of social and technical procedures.

Suppose that Chloe has checked the digital certificate of Alice and is sure that:

1. Alice is a real person and the digital identity on her digital certificate corresponds to her real-life identity and is correct.
2. The public key in the digital certificate is the correct one (the one that belongs to Alice).

How can Chloe check and verify the digital identity of Alice (first point above)? If Chloe does not know Alice personally, she can ask to meet her in person, check her identity documents (passport, identity card, driver license, etc.) and make sure that the digital identity of Alice (name, birthday, etc.) corresponds to the real-life identity. For checking and verifying the public key (second point above), Chloe has to get from Alice the fingerprint or ID of her public key, compare it with the one on the digital certificate, and make sure that it is the same.

Now that Chloe has verified that the digital certificate of Alice is authentic, she can sign it. A digital certificate is just a digital document, so it can be signed with a digital signature.

By signing the digital certificate of Alice, Chloe testifies that it is correct and valid, which means that the digital identity is authentic and the public key really belongs to Alice. The digital signature of Chloe also guaranties that the information on the digital certificate has not been changed since the time that she verified and signed it.

If Bob has full trust on Chloe about checking and verifying the information of digital certificates, then he can be sure that the digital certificate of Alice is authentic and valid, without having to check and verify it himself.

So, Bob asserts (derives) the validity/authenticity of the digital certificate of Alice by trusting a third party, which is Chloe. Bob can trust as well any other digital certificates that Chloe has signed. In such a case Chloe is called an "introducer" for Bob.

If Chloe verifies and signs a lot of digital certificates and a lot of people trust the certificates signed by Chloe, then Chloe is called a Certification Authority (CA).

In the OpenPGP model each person acts as a root CA and first of all self-signs his own digital certificate (to protect it from any modification and forgery). For example Alice signs her own certificate and Bob signs his own.

Second, each of them can sign the certificates of the people, which they have personally checked and verified. Verification includes both making sure that the digital identity matches the real-life identity of the person, and making sure that the public key in the certificate is the correct one that belongs to this person. This certificate verification and signing can be mutual as well, for example Alice signs the certificate of Bob, and Bob signs the certificate of Alice.

When Alice signs the certificate of Bob, usually she makes public this signature by uploading the signed certificate on a PKS. This lets everybody know that she has checked and verified the digital certificate of Bob and that she guaranties that this certificate is authentic and valid.

Next, each person decides who are the people that he can trust about making correct verification of others' certificates, and how much he can trust them. The trust levels that are defined by the OpenPGP standard are: unknown (default), none, marginal, full, ultimate. These trust values are not about how trustable is this person in the real life, but rather about the ability of the person to make correct verification of digital certificates, before signing them.

For example the trust value 'marginal' means that you believe that this person sometimes may not check and verify carefully the details of a certificate, before signing it. The trust value 'full' means that you believe that this person is very careful when signing certificates. The trust value 'ultimate' means that you believe that this person is so careful when checking and signing certificates, that he almost never makes mistakes.

The trust level that one assigns to a person is subjective and can be different from one person to another. For example Alice may have full trust on Bob, however Chloe may think that Bob can be trusted only marginally. The trust level is also private, which means that it is relevant only to the person who assigns it, and it is not published on any servers.

The figure shows a web of trust rooted at Alice. The graph illustrates who has signed who's certificate.

Alice is sure that the certificates of Blake and Dharma are valid, since she has verified and signed them herself.

If Alice has full trust on Dharma, then she would consider valid the certificates of Chloe and Fransis as well. She has not verified them herself, but Dharma has verified and signed them and Alice has full trust on the ability of Dharma to correctly verify and sign digital certificates.

In case that Alice has only marginal trust on Blake and Dharma, then she cannot be really sure about the validity of the Francis' certificate, although Dharma has signed it. However, she can be almost sure about the validity of the Chloe's certificate. Both Blake and Dharma have verified and signed it, so the possibility of both of them being deceived (or corrupted, mistaken) is small.

The decision on which certificate can be considered fully valid, or partially valid, or non-valid, is actually done automatically by the software that is used for verifying the signature. The software makes this decision based on who has signed who's certificate, on the trust value assigned to each of the people on the web of trust, and applying certain rules that are used to calculate the validity (authenticity) of a certificate. Such a rule can be for example: a certificate that is signed by at least three marginally trusted people can be considered fully valid.

The validation rules are customizable and can be different for each person, in order to fit the security requirements of everybody. For example, if Alice does not have any high security needs, and she lives in a friendly (not hostile) environment, then she may decide that even two marginally trusted signatures are enough to consider a certificate fully valid. However, if she has high security requirements and she lives in a rather hostile environment, then she can decide that at least five marginally trusted signatures should be required, so that a certificate that she has not verified herself can be considered valid. In this case, since she has decided to depend less on the verifications done by the others, she has to do more verifications on her own.

Sometimes there are people who do a great many of verification and signing of the others' digital certificates, even on a full time bases, and they are trusted by everybody (or at least a lot of people). These people play the role of a CA (Certification Authority) in the OpenPGP model.

Such people can be for example the head of the IT department in a company or institution. Or they can be people approved, verified and authorized by the government to offer this kind of service to the citizens. In this case they can also be called Digital Notaries and they may offer other Digital Services as well, besides verifying and signing digital certificates.

The Digital Notaries can also be held responsible in front of law for the correctness and truthfulness of the verifications and signatures that they make (as well as for other digital or non-digital services that they may offer). This accountability can be very useful for increasing their responsibility, as well as for increasing the trust of people on them and the health and reliability of the web-of-trust system as a whole.

If we compare the structure of the authentication models of the X.509 and the OpenPGP standards, we will notice that the first one closely resembles a tree (is hierarchical, like the structure of the private/governmental organizations), while the second one resembles a web or mesh (like the structure of the Internet).

A mesh is a much more flexible structure than a tree, because a tree structure is just a special case of a mesh structure.

In the web-of-trust authentication model of OpenPGP there can be CAs as well (like in the case of Digital Notaries that we have discussed previously). If many people choose to fully trust the same CA for checking the validity/authenticity of the others certificates (and they all configure their own copies of the OpenPGP client software to trust that CA), then the OpenPGP model acts just like the X.509 model. In fact, the web model of OpenPGP is a proper superset of the hierarchical model of X.509. There is no situation in the X.509 model that cannot be handled exactly the same way in the OpenPGP model. But OpenPGP can do much more.

In the X.509 model the set of trusted root CAs is fixed and predetermined. The users have no choice and can make no decision whether to trust them or not. This is so true that these CAs are "baked into" the major software that uses digital certificates (e.g. browsers). On the OpenPGP model, on the other hand, the users can decide themselves whom to trust and how much to trust them.

We can notice as well that the hierarchical model is centralized, while the web-of-trust model is distributed and decentralized. This is related to who is responsible for ensuring the correctness, authenticity and validity of the certificates, the security, trustability and reliability of the whole system, etc.

On the hierarchical model this responsibility falls on some central authority (the root CA), and on the sub-authorities (CAs) that it approves. On the web-of-trust model this responsibility falls on everybody participating on the system, since each of them helps to verify and validate the certificates of the others. So, on the web-of-trust model, each person that holds a digital certificate is verified by the others and helps to verify the others at the same time. This is a more democratic model, that encourages the responsibility and the participation of the citizens.

The decentralized/distributed model is also more robust and reliable than the hierarchical model.

The hierarchical model has just a single point-of-failure that has to be watched, protected and guarded very carefully, since it is a clear target of attack. This is the root CA. In case that its security is compromised or corrupted some day, then the security of the whole system is compromised and all of the digital certificates of the system are rendered invalid.

This doesn't have to be a technical failure (for example some hackers breaking into the system), it can be a social corruption as well (and this can be even more likely than a technical failure). This risk is amplified by the fact that most of the CAs are commercial. Matt Blaze once made the cogent observation that commercial CAs will protect you against anyone who that CA refuses to accept money from!

The distributed model, on the other hand, is much more difficult to corrupt because each participant is a little CA on its own. Maybe some of them can be corrupted for some time, but it is quite difficult to corrupt many or most of them at the same time. In any case, there can be inflicted only local damages, the whole system will survive the attack, and with time it can auto-correct and heal itself gradually.