What are the principal elements of a public-key cryptosystem?

Answer 1

A "public key cryptosystem" would be one using an asymmetric encryption algorithm. It is related to Public Key Infrastructure (PKI) and sometimes confused with it. The principal elements could be categorized as:

1) the algorithm for generating the asymmetric key pairs (private key and public key)

2) the algorithm to encrypt a message using the private key or to "sign" the message

3) the algorithm to decrypt a message using the public key or to authenticate it from the digital signature

4) a means to publish the public key

5) a means to authenticate that the public key actually belongs to the entity it purports to belong to - sometimes omitted in "public-key cryptography". PKI provides a means to achieve this.

There are many different public key encryption algorithms. Some of the more popular ones are: SSL (Secure Socket Layer), TLS (Transport Layer Security), PGP (Pretty Good Privacy), and GPG (Gnu Privacy Guard). A mathematical algorithm is used to generate a private key which is held by the owner while the public key is provided to everyone that the owner wants to communicate with. The owner of the private key uses it to encrypt the message. Someone receiving it can only decrypt it by using the author's public key. This provides some authentication of the source of the message - if the recipient is confident that the public key they are using really belongs to the purported author. A user's public key can also be used to encrypt a message so that only the holder of the corresponding private key will be able to decrypt it. This provides confidentiality for the sent message. Two people can achieve secure communications by using each others public keys to encrypt messages so that only the recipient can read each message.

Asymmetric encryption algorithms can also be used to digitally sign messages. In this case a message digest is created and then encrypted using the private key. The recipient can duplicate the message digest, then decrypt the digital signature using the originators public key and compare the two digests. If the message has been tampered with, then the digests will not match.

Authentication of the public keys, i.e. being certain who a public key really belongs to, can be achieved in different ways:

1. a web of trust - you get public keys from people or entities you personally know and trust and build up a "key ring" of those keys. If someone whom you have a public key from sends you a public key for another entity, you can decide whether or not you trust them enough to add the new key to your key ring. You have to install each certificate manually in order to be able to use it with the other person.
2. PKI - in this scenario, you have a Certificate Authority (CA) that vouches for the ownership of a public key. PKI permits each certificate to be signed only by a single party: a certificate authority (CA). The CA's certificate may itself be signed by a different CA, all the way up to a 'self-signed' root certificate. These root certificates are maintained by a "Registration Authority" (RA). Root certificates must be available to those who use a lower level CA certificate and so are typically distributed widely. They are for instance, distributed with such applications as browsers and email clients. In this way SSL/TLS-protected Web pages, email messages, etc. can be authenticated without requiring users to manually install root certificates. Applications commonly include over one hundred root certificates from dozens of PKIs, thus by default bestowing trust throughout the hierarchy of certificates which lead back to them. An important additional feature is needed for this approach. You must also have a mechanism for revoking expired or compromised certificates and getting that information out to users.
3. A third alternative is Simple Public Key Infrastructure (SPKI). SPKI does not associate users with persons, since the key is what is trusted, rather than the person. SPKI does not use any notion of trust, as the verifier is also the issuer. This is called an "authorization loop" in SPKI terminology, where authorization is integral to its design. In this case, the entity originating a connection with a subsidiary node sends a message including the key it plans to use for communication with the subsidiary node. Each entity is identified by its public key.