Bei jedem Public Key Verfahren ist die Authentizität (Echtheit) der Public Keys ein Problem. Ein kleines Beispiel: Bob erhalte von Carol eine elektronisch unterschriebene Mail. Um die Unterschrift zu prüfen, braucht Bob Carols public key.
Eine Mail an pgp-public-keys@keys.ch.pgp.net mit dem Subject GET carol@error-42.de liefert ihm ihre public key. Aber ist das wirklich ihr public key? Mallory könnte einen Key mit dem Namen Carol erzeugt und auf dem Keyserver deponiert haben.
Bob muss nun die Echtheit dieses public keys überprüfen. Dazu hat Bob verschiedene Möglichkeiten, z.B:
Jeder Schlüssel ist in genau einer Vertrauenstufe. Hat ein Schlüssel einen anderen Schlüssel signiert, wird anhand der Vertrauensstufe bestimmt, ob der signierte Schlüssel als gültig anerkannt wird. Es gibt drei Stufen des Vertrauens, die man Schlüsseln von anderen Leuten entgegenbringen kann:
Um das ganze etwas verwirrender zu machen, gibt es auch noch 3 Stufen der Gültigkeit:
Als Beispiel: Bobs Schlüsselring enthält Alices Schlüssel. Bob hat Alices Schlüssel für gültig befunden und dies dadurch bestätigt, daß er Alices Schlüssel unterschreibt.Bob weiß, daß Alice sehr gründlich vorgeht, wenn sie die Schlüssel anderer Leute unterschreibt. Deswegen stattet Bob Alices Schlüssel mit vollständigem Vertrauen aus. Wenn Alice jetzt einen anderen Schlüssel signiert, ist dieser in Bobs Schlüsselring gültig.
PGP verlangt einen komplett oder zwei teilweise vertrauenswürdige Schlüssel, um einen Schlüssel als gültig zu akzeptieren.
Aus diesen verschiedenen Schlüsseln baut sich nun ein Netzwerk auf das sogenannte Web-of-Trust. Da es in diesem Netz nicht zwingend Instanzen geben muß, die eine große Menge von Schlüssel unterschreiben, kann der Weg von einem Schlüssel zum nächsten so weit sein, das man keine Möglichkeit findet, einen Schlüssel zu validieren.