PGP significa Pretty Good Privacy, y su funcionamiento es mas o menos como lo describes.
Existe sin embargo la versión GNU que se llama GPG (por GNU Privacy Guard) y que es la que se suele usar en *nix.
Para información detallada prueba el COMO de gpg en español:
http://www.dewinter.com/gnupg_howto/spanish/
Saludos ;)