Modern computing has generated a tremendous need for convenient, manageable encryption technologies. Symmetric algorithms, such as Triple DES and Rijndael, provide efficient and powerful cryptographic solutions, especially for encrypting bulk data. However, under certain circumstances, symmetric algorithms can come up short in two important respects: key exchange and trust. In this chapter we consider these two shortcomings and learn how asymmetric algorithms solve them. We then look at how asymmetric algorithms work at a conceptual level in the general case, with emphasis on the concept of trapdoor one-way functions. This is followed by a more detailed analysis of RSA, which is currently the most popular asymmetric algorithm. Finally, we see how to use RSA in a typical program using the appropriate .NET Security Framework classes.
We focus on the basic idea of asymmetric algorithms, and we look at RSA in particular from the encryption/decryption point of view. In Chapter 5 we explore using the RSA and DSA asymmetric algorithms as they relate to authentication and integrity checking, involving a technology known as digital signatures. For a more thorough discussion of RSA from a mathematical point of view, please see Appendix B.
Problems with Symmetric Algorithms
One big issue with using symmetric algorithms is the key exchange problem, which can present a classic catch-22. The other main issue is the problem of trust between two parties that share a secret symmetric key. Problems of trust may be encountered when encryption is used for authentication and integrity checking. As we saw in Chapter 3, a symmetric key can be used to verify the identity of the other communicating party, but as we will now see, this requires that one party trust the other.
The Key Exchange Problem
The key exchange problem arises from the fact that communicating parties must somehow share a secret key before any secure communication can be initiated, and both parties must then ensure that the key remains secret. Of course, direct key exchange is not always feasible due to risk, inconvenience, and cost factors. The catch-22 analogy refers to the question of how to securely communicate a shared key before any secure communication can be initiated.
In some situations, direct key exchange is possible; however, much commercial data exchange now takes place between parties that have never previously communicated with one another, and there is no opportunity to exchange keys in advance. These parties generally do not know one another sufficiently to establish the required trust (a problem described in the next section) to use symmetric algorithms for authentication purposes either. With the explosive growth of the Internet, it is now very often a requirement that parties who have never previously communicated be able to spontaneously communicate with each other in a secure and authenticated manner. Fortunately, this issue can be dealt with effectively by using asymmetric algorithms.1
The Trust Problem
Ensuring the integrity of received data and verifying the identity of the source of that data can be very important. For example, if the data happens to be a contract or a financial transaction, much may be at stake. To varying degrees, these issues can even be legally important for ordinary email correspondence, since criminal investigations often center around who knew what and when they knew it. A symmetric key can be used to check the identity of the individual who originated a particular set of data, but this authentication scheme can encounter some thorny problems involving trust.
As you may recall from Chapter 3, in this technique the data is hashed, and the resulting hash is encrypted using a shared secret key with a symmetric algorithm. The recipient, who also knows the secret key, is sent the data along with the encrypted hash value. The recipient then decrypts the hash using the shared key, and the result is verified against a fresh recalculation of the hash value on the data received. This works because only someone who knows the secret key is capable of correctly encrypting the hash of the original data such that it will match the recalculated hash value computed by the recipient. This verifies the identity of the data source. As an added bonus, this technique verifies data integrity in that any individual who is ignorant of the secret key could not have tampered with the data.
This is great if you have the luxury of establishing the shared secret beforehand, but there is an additional problem here. What if you cannot trust the other party with whom you have shared the secret key? The problem is that this scheme cannot discriminate between the two individuals who know the shared key. For example, your pen pal may fraudulently send messages using your shared key, pretending to be you. This would allow your friend to write IOUs to himself in your name, making this scheme useless in any trust-lacking relationship. Other problems could arise if your partner shared the secret key with others without telling you about it. Suddenly, you would have no leg to stand on if certain disputes were to arise. For example, your partner could renege on a contract by claiming that someone else must have obtained the key from you and signed off on a deal in his name. This problem is known as repudiation,2 and we often need a way to enforce nonrepudiation between untrusting parties. The basic problem with all this is that any symmetric algorithm scheme requires that one party can safely trust the other party, which often is not realistic.
Fortunately, asymmetric algorithms can be used to solve these problems by performing the same basic operations but encrypting the hash using a private key (belonging to an asymmetric key pair) that one individual and only one individual knows. Then anyone can use the associated public key to verify the hash. This effectively eliminates the problems of trust and repudiation.3This technique is called a digital signature, which is the main topic of the next chapter.