GPG2 Encryption – No public key error

It seems you don't have the public key of Set B (PB) in your keyring of Set A. Thus, gnupg won't be able to know if it was really a good signature from that key. Without you having PB, the signature will just "look like" it has been signed by the key with the key id of 0xXXXXXXXX, but it lacks the PB to check it thoroughly.

You might encounter this issue with Kleopatra, and the solution is to set the trust of the public key before verifying. Even if you have the correct public key for the signed file/message, the response from the application will show as not valid unless the public key is trusted.

You're confusing two different digital certificate systems. Certificates are not interchangeable between the two systems.

OpenPGP

OpenPGP provides a non-hierarchical trust system, which does not require central certificate authorities. It is the more powerful, but also more complex system. Most mail clients do not support it out of the box, and require add-ons for using it.

Everybody can create his own key, and get it signed by others.

X.509 and S/MIME

The other option for digital certificates is X.509, used in S/MIME for e-mail, but also SSL/TLS for transport encryption of HTTP and other protocols. Here you have a bunch of certificate authorities (actually usually multiple hundred) that you trust in (by default settings of your computer/mail client), and that can vouch for others (issue certifications) which you automatically trust.

This is a good fit for (hierarchically organized) companies, which probably is the reason that it has much more wide-spread implementation. Outlook, Thunderbird and most other (reasonable) mail clients support it by default.

There are lots of certificate authorities where you could buy such a certificate (valid for a given timespan). I'm only listing two especially interesting ones:

• StartSSL is an Israel-based company issuing free basic certificates for mail and servers, but without validating your real ID (only your mail address). The advantage is that they are trusted by all major browser and operating system vendors. Certificates including your real name are available for a flatrate of around 60$ per year. Be aware revoking a certificate (eg., in case some third got access to it and can now write e-mail in your name) is around 25$ (which is also charged by a lot of other companies).

• CAcert is a "community driven certificate authority". They verify your identity by other community members agreeing to do so, so you will have to meet others and show your ID to get your name into the certificate (for details, read their website). Issuing certificates and revocations are always free, but the downside is their root certificate is not trusted by major operating systems and mail clients.

  Might be feasible for limited groups or private use, but be aware of this problem if using it commercially.