A public key certificate issuing system is disclosed which comprises a certificate authority for issuing a public key certificate used by an entity, and a registration authority which, on receiving a public key certificate issuance request from any one of entities under jurisdiction thereof, transmits the received request to the certificate authority. The certificate authority, having a plurality of signature modules each executing a different signature algorithm, selects at least one of the plurality of signature modules in accordance with the public key certificate issuance request from the registration authority, and causes the selected signature module to attach a digital signature to message data constituting a public key certificate.
展开▼