Public-Key Cryptography

The art and science of cryptography consists of two worlds. There is the world of legal communications: parties such as legal users of a data bank exchanging messages. This world can be viewed as open and sunlit. There is also the dark world of the enemy who illegally tries to intercept the messages and do all kinds of vicious things. For people in the legal world, it is desirable that the enemy understands very little of the messages. The enemy, on the other hand, would like to have easily understandable messages.

Think about any of the cryptosystems presented in Chapter 1, or any other similar systems. There will be no difficulties in the decryption process for a cryptanalyst who has learned the encryption method. The encryption and decryption keys coincide even in such a sophisticated system as DES. So you give away your secrets if you work with one of the systems mentioned and publicize your encryption method.

Public-key cryptosystems based on the knapsack problem were already briefly discussed in Example 2.1 in Chapter 2. It was also pointed out that knapsack systems are very suitable for illustrating all basic ideas behind public-key cryptography. The setup is also versatile enough to produce new variants to avoid cryptographic weaknesses.

The most widely used and tested public-key cryptosystem was originally introduced by Rivest, Shamir and Adleman, and is now referred to as the RSA system. It is based on an amazingly simple number-theoretical (one could even say arithmetical) idea, and yet it has been able to resist all cryptanalytic attacks. The idea is a clever use of the fact that, while it is easy to multiply two large primes, it is extremely difficult to factorize their product. Thus, the product can be publicized and used as the encryption key. The primes themselves cannot be recovered from the product. On the other hand, the primes are needed for decryption. Thus, we have an excellent framework for a public-key cryptosystem. Moreover, the details can be explained very fast — that’s why we called the system “amazingly simple”.

The framework presented in Section 2.2 for the construction of public-key cryptosystems is very general. Indeed, the area or subject matter of the underlying problem is not specified in any way. Any one-way street could be worth a try, and many streets have actually been tried. By now there exist numerous public-key cryptosystems, based on quite diverse concepts.

A protocol usually refers to customs and regulations dealing with diplomatic formality, precedence and etiquette. Typically, a protocol determines a map for seating the participants, or the order of speeches. It has happened that an international conference has spent most of the time while arguing about the seating protocol.