You have to search the public keyservers for the given key id: in your case ID C3C45C06
Import the found key in your local keystore and after this the verification should be OK.
I use Ubuntu 12.04 and it comes with Seahorse key management software. Before the key import I was seeing this:
~/Downloads$ gpg --verify --keyring ./gnu-keyring.gpg icecat-31.5.0.en-US.linux-x86_64.tar.bz2.sig icecat-31.5.0.en-US.linux-x86_64.tar.bz2
gpg: Signature made 9.03.2015 (пн) 22,35,52 EET using RSA key ID D7E04784
gpg: Can't check signature: public key not found
After the key import I was seeing this:
~/Downloads$ gpg --verify --keyring ./gnu-keyring.gpg icecat-31.5.0.en-US.linux-x86_64.tar.bz2.sig icecat-31.5.0.en-US.linux-x86_64.tar.bz2
gpg: Signature made 9.03.2015 (пн) 22,35,52 EET using RSA key ID D7E04784
gpg: Good signature from "Ruben Rodriguez (GNU IceCat releases key) <[email protected]>"
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: A573 69A8 BABC 2542 B5A0 368C 3C76 EED7 D7E0 4784