Il existe sur Internet des serveurs contenant une très grande quantité de clés publiques accompagnées de certificats les identifiant. Sur ces serveurs, on peut rechercher la clé publique d'un individu avec une grande facilité. Chaque utilisateur envoyant sa propre clé sur ce serveur de clées s'assure que toute personne voulant communiquer avec lui aura accès à sa clé publique, et cela en tout endroit. Toutefois, comment peut-on s'assurer qu'une clé publique appartienne véritablement à qui l'on pense? On peut s'imaginer un scénario, en reprenant nos personnages de départ, où Guy se crée une paire de clés identifiées au nom de Bob et distribue sa clé publique sur les serveurs de clés. Alice pourrait très bien se tromper et utiliser la clé de Guy pour envoyer un message à Bob.
La solution réside dans les certificats d'authencitité qui accompagnent chaque clé. La validité d'un certificat mesure la garantie qu'une clé publique appartienne réellement à son propriétaire. Lorsque quelqu'un s'assure qu'un tel certificat est valide, il peut y apposer sa propre signature digitale et envoyer cette information au serveur de clés publiques. Dans notre situation fictive, Alice devrait s'assurer que la clé de Bob est signée par d'autres personnes pouvant témoigner de la validité de la clé. Ce système de fonctionnement épargne du temps aux autres individus voulant aussi s'assurer de la validité du certificat.
Il est possible de s'assurer manuellement la validité d'un certificat en vérifiant son empreinte digitale. Chaque certificat PGP a une empreinte digitale unique déterminée ici par une fonction de hachage tout comme pour les signatures digitales. S'il lui est possible de contacter le propriétaire de la clé par téléphone, un individu peut lui demander de lui réciter son empreinte digitale (qui est en fait une série de valeurs hexadécimales ou une liste de mots qui sont distincts phonétiquement).
Une autre façon d'établir la validité du certificat d'une clé est de faire confiance à un troisième individu qui a lui-même validé le certificat. Un utilisateur peut faire confiance à des gens qui valident des certificats ou qui font eux-mêmes aussi confiance à d'autres personnes qui valident des certificats. Une véritable toile de confiance peut donc se créer et la validation manuelle des certificats peut être évitée dans plusieurs cas.
À l'aide de PGP, un utilisateur peut choisir de faire confiance à certains contacts. Le niveau de confiance accordé à ces derniers est personnel et est déterminé individuellement. Par exemple, un utilisateur pourrait accorder une totale confiance en son patron mais n'accorder qu'une confiance partielle en son voisin. Il fait alors confiance aux certificats validés par son patron mais doute des certificats validés par son voisin.
Finalement PGP est un moyen simple et efficace de garantir la sûreté des communications de l'utilisateur moyen, en autant qu'il s'en serve. Philip Zimmerman, créateur de PGP, compare son système aux enveloppes postales: si tout le monde écrivait ses messages sur des cartes postales et que quelqu'un décide d'envoyer un message dans une enveloppe, il serait immédiatement soupçonné et l'enveloppe serait probablement ouverte. Il en est de même pour PGP: le plus de gens utilisent PGP, le moins suspects ceux qui s'en servent paraîtront, et plus grande la sécurité de l'information sur l'Internet sera. «PGP donne aux gens le pouvoir de prendre en main leur intimité. Il y a un besoin social croissant pour cela. C'est pourquoi je l'ai créé.»15