Este formato de paquete es utilizado por muchas distribuciones, entre ellas, RedHat, SuSE, Caldera, Mandrake, Conectiva. En muchas ocasiones no es imprescindible instalar un paquete rpm generado para una distribución en particular en esta distribución (por ejemplo: Un paquete generado para SuSE en un SuSE), pero en la mayoría de las ocasiones esto es lo recomendado. Por lo tanto, dependiendo la distribución que vos utilices te tendrás que dirijir al sitio web de tu distribución (si es que no viene incluida en el CDROM del cual instalaste el Linux) y bajarte el paquete correspondiente. Aunque tengas el paquete en tu CD de instalación, igual te recomiendo que le pegues una visita al sitio web de la distribución ya que puede haber nuevas versiones del gpg.
Para instalar un paquete rpm hay que ejecutar el siguiente comando (como root):
# rpm -Uvh /tmp/gpg-<version+plataforma>.rpm
Si existe alguna dependencia sobre este paquete te recomiendo que instales el
paquete del cual depende el gpg (no utilices --force --nodeps).