Public-key algorithms are asymmetric algorithms and, therefore, are based on the use of two different keys, instead of just one. In public-key cryptography, the two keys are called the private key and the public key
Private key: This key must be know only by its owner.
Public key: This key is known to everyone (it is public)
Relation between both keys: What one key encrypts, the other one decrypts, and vice versa. That means that if you encrypt something with my public key (which you would know, because it's public :-), I would need my private key to decrypt the message.
In a basic secure conversation using public-key cryptography, the sender encrypts the message using the receiver's public key. Remember that this key is known to everyone. The encrypted message is sent to the receiving end, who will decrypt the message with his private key. Only the receiver can decrypt the message because no one else has the private key. Also, notice how the encryption algorithm is the same at both ends: what is encrypted with one key is decrypted with the other key using the same algorithm.
Public-key systems have a clear advantage over symmetric algorithms: there is no need to agree on a common key for both the sender and the receiver. As seen in the previous example, if someone wants to receive an encrypted message, the sender only needs to know the receiver's public key (which the receiver will provide; publishing the public key in no way compromises the secure transmission). As long as the receiver keeps the private key secret, no one but the receiver will be able to decrypt the messages encrypted with the corresponding public key. This is due to the fact that, in public-key systems, it is relatively easy to compute the public key from the private key, but very hard to compute the private key from the public key (which is the one everyone knows). In fact, some algorithms need several months (and even years) of constant computation to obtain the private key from the public key.
Another important advantage is that, unlike symmetric algorithms, public-key systems can guarantee integrity and authentication, not only privacy. The basic communication seen above only guarantees privacy. We will shortly see how integrity and authentication fit into public-key systems.
The main disadvantage of using public-key systems is that they are not as fast as symmetric algorithms.
Integrity is guaranteed in public-key systems by using digital signatures. A digital signature is a piece of data which is attached to a message and which can be used to find out if the message was tampered with during the conversation (e.g. through the intervention of a malicious user)
The digital signature for a message is generated in two steps:
A message digest is generated. A message digest is a 'summary' of the message we are going to transmit, and has two important properties: (1) It is always smaller than the message itself and (2) Even the slightest change in the message produces a different digest. The message digest is generated using a set of hashing algorithms.
The message digest is encrypted using the sender's private key. The resulting encrypted message digest is the digital signature.
The digital signature is attached to the message, and sent to the receiver. The receiver then does the following:
Using the sender's public key, decrypts the digital signature to obtain the message digest generated by the sender.
Uses the same message digest algorithm used by the sender to generate a message digest of the received message.
Compares both message digests (the one sent by the sender as a digital signature, and the one generated by the receiver). If they are not exactly the same, the message has been tampered with by a third party. We can be sure that the digital signature was sent by the sender (and not by a malicious user) because only the sender's public key can decrypt the digital signature (which was encrypted by the sender's private key; remember that what one key encrypts, the other one decrypts, and vice versa). If decrypting using the public key renders a faulty message digest, this means that either the message or the message digest are not exactly what the sender sent.
Using public-key cryptography in this manner ensures integrity, because we have a way of knowing if the message we received is exactly what was sent by the sender. However, notice how the above example guarantees only integrity. The message itself is sent unencrypted. This is not necessarily a bad thing: in some cases we might not be interested in keeping the data private, we simply want to make sure it isn't tampered with. To add privacy to this conversation, we would simply need to encrypt the message as explained in the first diagram.
The above example does guarantee, to a certain extent, the authenticity of the sender. Since only the sender's public key can decrypt the digital signature (encrypted with the sender's private key). However, the only thing this guarantees is that whoever sent the message has the private key corresponding to the public key we used to decrypt the digital signature. Although this public key might have been advertised as belonging to the sender, how can we be absolutely certain? Maybe the sender isn't really who he claims to be, but just someone impersonating the sender.
Some security scenarios might consider that the 'weak authentication' shown in the previous example is sufficient. However, other scenarios might require that there is absolutely no doubt about a user's identity. This is achieved with digital certificates, which are explained in the next page.