¿Estás usando un repositorio oficial? Si es así, primero debes importar la firma digital de los paquetes de fedora, de la siguiente forma:
Código:
rpm --import /usr/share/doc/fedora-release-4/RPM-GPG-KEY*
(Debes hacerlo como root).
Todo esto se explica en más detalle en la
FAQ de Fedora.