Where do I get the package signing key for CentOS 4?

You need to install the CentOS RPM signing key. It is not installed as part of the base system install for security reasons. This provides you the opportunity to validate the key before installing it on your system.

RPM has the capacity to retrieve the key from a Centos Mirror:

rpm –import http://mirror.centos.org/centos/RPM-GPG-KEY-CentOS-4

(as root) will install (‘import’) the CentOS 4 package signing key for RPM to use to confirm a validly signed package.

Please note that it is safer to import the copy of the key from the install ISO media. It is in the root directory of each ISO, as RPM-GPG-KEY, and the same key is present on disc 1 as RPM-GPG-KEY-CentOS-4.