If you are running Red Hat Linux version 5.x, then you should download GPG 1.0.1 for Red Hat 5.x. If you are running Red Hat Linux 6.1, then you should download GPG 1.0.3 for Red Hat 6.1. Both of these files are on an FTP site in Italy. If you have difficulty reaching it, then you might wish to check the GPG home page to see whether other mirror sites are available. And if you wish, you may also build GPG from source code.
Of course, by the time you read this, there may be a newer version of GPG available. If you wish, you can check the FTP site to see whether a newer version of GPG is available.
After downloading the appropriate file for your version of Red Hat Linux, you should install it with this command (substituting the appropriate file name):
rpm -i gnupg-1.0.3-1.i386.rpm
If you are running Red Hat Linux version 4.x or older, then you may not be able to find a pre-compiled version of GPG which will work with your computer. In that case, you may upgrade to a newer version of Red Hat Linux, or build GPG from source code.