Как проверить файл AAA.tar.bz2 имея AAA.tar.bz2.sig?

так надо на связку ключей добавить нужный ключ.

как?

см. man gpg

gpg --verify gcc-3.4.3.tar.bz2.sig gcc-3.4.3.tar.bz2

root@localhost# gpg --verify gcc-3.4.3.tar.bz2.sig
gpg: Signature made Птн 05 Лис 2004 10:37:33 EET using DSA key ID B75C61B8
gpg: Can't check signature: public key not found
...
Тогда я иду на http://www.keyserver.net/en/, http://math-www.uni-paderborn.de/pgp/, http://pgp.zdv.uni-mainz.de/keyserver/pks-commands.html#extract
и другие подобные сайты и ищу этот ID B75C61B8...
Результат везьде одинаковый - ключ не находят либо из-за ошибки в БД, либо его просто нет...
?