Hola nad,
Antes que nada recomendarte que dejes de lado pgp y en cambio uses gnupg, tambien conocido como gpg (GNU Privacy Guard). Los programas son compatibles y gpg es software libre.
Lo primero que tienes que hacer es instalar el paquete (gnupg) y luego puedes generar con el tu par de claves.
Te dejo unas urls para que leas sobre el tema:
http://www.gnupg.org http://es.tldp.org/COMO-INSFLUG/COMOs/GPG-Mini-Como/ http://linuca.org/body.phtml?nIdNoticia=88 http://bulmalug.net/pdf.phtml?nIdNoticia=1483 (pdf)
Cualquier duda solo pregunta
Saludos ;)