20-CS-653-001 Network Security Spring 2010
Some Odd Ciphers

Public Key Encryption: Merkle-Hellman

The secure transmission of data is currently extremely important for two reasons: more than ever, huge quantities of information need to be passed long distance; and a very competitive global environment can severly hurt a company if sensitive information falls in the wrong hands.

The well known private-key encryption methods may not work well in a fast-paced, heavy message-passing environment. Such methods rely on the distribution of codekey books, by the sender, to the receivers. Since the route taken by such books must be secure, distribution is slow. Therefore, codes can not be changed rapidly. Such private-key systems are vulnerable to attack by determined adversaries armed with extremely fast computational power.

In public-key methods the receiver sends the codekeys to all senders. These codekeys are publicly broadcasted. A sender takes such a key, encrypts a message with it and sends the encrypted message to the receiver. The receiver can decode the message because, associated with the public key is a private key, known only to the receiver. The private key is applied to the encrypted message and it is decoded.

Certain public-key systems are considered hard to crack for two reasons: a receiver can change keys daily, even hourly; and consistent successful attacks on encrypted messages would imply that some well known, very hard problems in mathematics are actually easy - an unlikely event. Two of the "hard" problems used by public-key systems are the knapsack problem and factoring.

One of the most useful public-key systems is known as the RSA system. We present below, in an interactive applet, a much less useful but more easily explained public-key system based on the knapsack problem. Suppose you have a knapsack of a particular size capacity S and suppose you have a collection of objects that can be put into the knapsack. Each object has a different size. The question is whether some subset of the objects has a total size which is exactly S (that is, whether there is a subset of objects that can precisely fill up the knapsack). The knapsack problem is very hard to solve. In other words, the amount of computer time needed to solve it can be so enormous that it is fruitless to try for an exact solution.

Knapsack can be used to encode messages as follows. A message is naturally broken down into a series of bits. Each bit has a value of 1 or 0. Associate with each bit a "size". Construct a number which is the sum of the sizes of all 1 bits. Send the number. A typical adversary will have a tough time trying to decode this message if the number of bits is large enough because doing so consistently implies the knapsack problem can be solved easily.

However, the receiver must be able to decode the message. The trick used is based on the fact that certain knapsack instances are easy to solve. In particular, if the sizes from one bit to another are increasing so that, for all i, the size of bit i is at least as great as the sum of the sizes of bits 1 to i-1, then the problem is trivially solved. Such a sequence is called superincreasing. The receiver produces a superincreasing sequence of n sizes, then disguises these by multiplying each by a private multiplier and dividing by a private modulus. The remainder of each is the size that is transmitted as a public key. The multiplication and division "scrambles" the superincreasing sequence so each message seems to be hard to crack. On the other hand, the receiver uses the private multiplier and modulus to convert the incoming message to another number that can be solved on the original superincreasing sequence - thus, because the receiver has the private key, the message can be decoded easily.

Try encrypting and decrypting your own messages using the applet to the right. In this simple example n=8, the number of bits in one character. Usually, the key would involve many more bits. Select the private key sizes. To insure a superincreasing sequence, press the return key after each change. Don't press the return key if you want to experiment with non-superincreasing sequences. Select a multiplier and modulus and click on the "Record" button. Enter a plain text message that you want to encrypt. Encrypt the message to numbers by clicking on the "Encrypt" button. See the message decoded by clicking on the "Decrypt" button. Notice that not all choices of multiplier, modulus, and sizes will work! Try to figure out why some do and some don't.

The knapsack-based system presented here was "cracked" some time ago. It has been shown that it is possible to discover the private keys from the public ones in a reasonable amount of time. However, it can be used to effectively explain the nature of public-key systems.