After moving to a new PC and importing my existing keys, even after verifying fingerprints, trusting, and signing the public key I needed to verify a signature with, GPG just would not verify signatures. Below I'm trying to verify the signature of the latest PuTTY release as of this post:
C:\test>gpg --verify putty.zip.gpg putty.zip
gpg: Signature made 11/07/15 05:28:00 Eastern Standard Time using RSA key ID B43434E4
gpg: Good signature from "PuTTY Releases" [unknown]
gpg: WARNING: This key is not certified with a trusted signature!
gpg: There is no indication that the signature belongs to the owner.
Primary key fingerprint: 0054 DDAA 8ADA 15D2 768A 6DE7 9DFE 2648 B434 34E4
But I trust it! I signed it! I tediously verified the fingerprint from multiple sources! Why do you still not know it belongs to them?!
A look at gpg --list-keys has the answer:
C:\test>gpg --list-keys
C:/Users/******/AppData/Roaming/gnupg/pubring.gpg
----------------------------------------------------
pub 2048R/D34D1337 2011-09-21 [expires: 2018-06-13]
uid [ unknown] Joshua McKinnon
pub 4096R/29C17558 2013-12-29
uid [ unknown] Steffen Land (Apache Lounge)
sub 4096R/BC11F6FE 2013-12-29
pub 2048R/B43434E4 2015-08-31 [expires: 2018-08-30]
uid [ unknown] PuTTY Releases
...That's not right! My own key is unknown, even though it's the first key I imported, has a matching private key and everything. I was so focused on the other certs I wanted to trust, I didn't see that GPG didn't even trust my _OWN_ cert. The chain of unknown -> something else stays unknown. Now, I don't know why this happened (aside from a possible BUG), but the circumstances have occurred on 2 or more computers. I manage and import my certificates with Kleopatra on Windows, so it's possible that when you re-import your existing private key on a new computer, it does not set trust even though it should - it certainly appears this way, but I have not tried to reproduce this again yet. Creating a new key does set trust of that key to ultimate, as expected. (If you don't trust yourself, you've got bigger problems ;)
Let's fix it:
C:\test>gpg --edit-key
gpg (GnuPG) 2.0.26; Copyright (C) 2013 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Secret key is available.
pub 2048R/D34D1337 created: 2011-09-21 expires: 2018-06-13 usage: SCE
trust: unknown validity: unknown
[ unknown] (1). Joshua McKinnon
gpg> trust
pub 2048R/D34D1337 created: 2011-09-21 expires: 2018-06-13 usage: SCE
trust: unknown validity: unknown
[ unknown] (1). Joshua McKinnon
Please decide how far you trust this user to correctly verify other users' keys
(by looking at passports, checking fingerprints from different sources, etc.)
1 = I don't know or won't say
2 = I do NOT trust
3 = I trust marginally
4 = I trust fully
5 = I trust ultimately
m = back to the main menu
Your decision? 5
Do you really want to set this key to ultimate trust? (y/N) y
Now let's look at it again:
C:\test>gpg --verify putty.zip.gpg putty.zip
gpg: Signature made 11/07/15 05:28:00 Eastern Standard Time using RSA key ID B43434E4
gpg: Good signature from "PuTTY Releases" [full]
That's more like it. Now that my own key is trusted, the chain of trust from me verifying and signing other certificates is properly passed down. Now I can extract and begin using this version of PuTTY.
This could also be fixed in the Kleopatra GUI, and in fact, if you right click your own Certificate and choose "Change Owner Trust", in the situation I found myself in, _nothing_ was select, despite the only valid option being "This is my certificate". That's what I noticed before I saw the "unknown" in my own cert at the command line, which I had glazed over initially. This probably re-affirms that this is a bug.
Hopefully this post helps at least 1 person figure out how to properly verify a GPG signature...even if that person is a just a future version of me.