Previous | ToC Labs: Cryptography. Part 1. Math Alive

A Variant on the HBO Application

It may be frustrating to check all the binary strings in a stream; the stream could be much bigger; and hardware design could be such that it is unrealistic to check many strings. (It is easy to parity add our key to a lot of strings, but the process of auto-detecting which one of these results in a clear picture may take a long time if we need to check a LOT of strings.) Here we present another version of HBO encryption that incorporates the same idea with a twist, so that it would still apply in these circumstances.

Imagine that HBO sends a large stream of binary strings. One of the strings is a password. Some of the strings are keys parity-added with the password, others are junk strings. (In this scenario, HBO wants to send extra junk to make it more secure---it will take too long to go through all the strings and figure out which one gives a clear picture). All those strings are sent in random order, hence it is unrealistic to find the password by trying them one after another. The strategy for the subscriber is to parity-add his/her key to all the numbers in the string. (Remember, the parity-addition part is fast, the verification of a clear picture is slow.) Let us see what happens in this case.

Usually you will find that most of the new 20-digit strings you obtain are quite different from any of the old strings, except for the two strings that you get when you add your key to the password or to the (password oplus your key).

password oplus key2 password password oplus key7 password oplus your key password oplus key1
pwd oplus key2 oplus your key password oplus your key pwd oplus key7 oplus your key pwd oplus your key oplus your key pwd oplus key1 oplus your key
not one of the originals password oplus your key not one of the originals password not one of the originals

This gives you two matches. One of them is the Password to unlock the channels! In a challenge problem on the homework, you examine the possibility of getting more than two matches.

The following is a chain of randomized strings including the password, the password XOR-added with keys, and junk. When you type in your key, you will get the parity addition of your key to every element of the chain. If you don't type in a mistake, then you will see two overlaps between the original collection of strings and the collection of strings plus your key; one of them is the password. (To decide which one, you would try decrypting with each, That means you need to try only two, not many of them.) Type in one of the three keys you calculated earlier. (Those are keys of the subscribers who still pay). This decoder is a device that allows you not to check each string in a stream one by one, but reduce the number of input strings you need to check. Compare the time you spent for finding a password on this page and on a previous page. This decoder box is used when your stream consists not of 45 strings as on the previous page, but of a very big number of strings.

Decoder Box

Previous | ToC Last Modified: August 2008