公开钥匙算法的一个弱点在于如何传播公开钥匙。有可能有用户传递一把有虚假身份的公开钥匙。如果别人不知就里，用这把公钥加密信息，持有该虚假钥匙的侵入者就可以解密而读到信息。如果侵入者再将解密的信息以真正的公开钥匙加密，然后传送出去，这种进攻无法被发现。

对此问题，PGP的解决方法（因此也自动是GnuPG的解决方法）是对公开钥匙签名。每把公开钥匙都有一个相应的用户身份。一个人的公开钥匙可以由别人来签名。这些签名承认这把钥匙确实属于它所宣称的用户。至于有多信任这些签名，完全取决于GnuPG用户。当你信任给这把钥匙签名的人时，你认为这把钥匙是可信的，并确信这把钥匙确实属于拥有相应用户身份的人。只有当你信任签名者的公开钥匙时，你才能信任这个签名。要想绝对确信一把钥匙是正确和真实的，你就得在给予绝对信任之前，通过可靠渠道比较钥匙的“指纹”。