Generating Long Keys

What you would like to have is a very long key to use in a scheme like the Vigenére encoding, but as we stated above, the problem with a long key is that you have to transmit that key to the persons who should be able to decode the messages in some secure manner.

The more ``random'' the key is, the more secure it is. To make a really random key, you could imagine using something like a timer connected to a Geiger counter and placing it close to some radioactive source so you could use the intervals between atomic decays to generate numbers that are truly random.

But if you're willing just to have a sequence that looks very random, there are many techniques for generating such sequences of so-called ``pseudo-random numbers''. Volume 2 of Donald Knuth's classic book, ``The Art of Computer Programming--Seminumerical Algorithms'', contains a treasure-trove of information about how to generate pseudo-random sequences. We will look at just a couple of methods here to give you an idea of the possibilities.

A very easy way to do this (but not a very good one) is based on the fact that if $p$ is a prime number, and $n$ is any number with $0 < n < p$, then the sequence of numbers $kn ({\rm mod}\ p)$ cycle through all the numbers between 1 and $p-1$ without missing any of them, and in an order that appears somewhat random as $k$ goes through $1, 2, 3, \ldots, p-1$.

For example, if $p=13$ and $n=5$:

$5\cdot 1 ({\rm mod}\ 13) = 5$	$5\cdot 2 ({\rm mod}\ 13) = 10$	$5\cdot 3 ({\rm mod}\ 13) = 2$
$5\cdot 4 ({\rm mod}\ 13) = 7$	$5\cdot 5 ({\rm mod}\ 13) = 12$	$5\cdot 6 ({\rm mod}\ 13) = 4$
$5\cdot 7 ({\rm mod}\ 13) = 9$	$5\cdot 8 ({\rm mod}\ 13) = 1$	$5\cdot 9 ({\rm mod}\ 13) = 6$
$5\cdot 10 ({\rm mod}\ 13) = 11$	$5\cdot 11 ({\rm mod}\ 13) = 3$	$5\cdot 12 ({\rm mod}\ 13) = 8$

The numbers cycle through the series: $5, 10, 2, 7, 12, 4, 9, 1, 6, 11, 3, 8$. This sequence has the vague appearance of being random. If you choose a larger prime, the sequence will be longer.

Using such a sequence, let's encrypt a message using the code described in the previous section. The message will be:

PASSWORD: ELEPHANT

Including the space, the numeric codes for these letters are:

26, 11, 29, 29, 33, 25, 28, 14, 65, 10, 15, 22, 15, 26, 18, 11, 24, 30

Now we'll use a combination of the method above to generate a sequence of pseudo-random numbers to use as a sort of Vigenére key. We'll let $p=16139$ and $n=4352$. As $k$ goes from 1 to 18 (there are 18 characters in the message above), $kn ({\rm mod}\ 16139)$ goes through the following 18 numbers:

4352, 8704, 13056, 1269, 5621, 9973, 14325, 2538, 6890, 11242, 15594, 3807, 8159, 12511, 724, 5076, 9428, 13780

We will just encode our numbers by adding these pseudo-random numbers to the numbers in our sequence and taking the result modulo 100. For example, the first letter, 26, is converted to (26+4352) (mod 100) = 78. The encoded sequence becomes:

78, 15, 85, 98, 54, 98, 53, 52, 55, 52, 09, 29, 74, 37, 42, 87, 52, 10

Assuming that the person who wishes to decode the message knows the values of $p$ and $n$, he can generate the exact same sequence of keys, and can undo the encryption above. For example, to decrypt the first character, he generates the first number in the key sequence, 4352, subtracts that from 78 (giving -4274), and taking that result modulo 100 to get 26.

Now notice that the only information that has to be passed to the recipient as the key is the pair of numbers $p$ and $n$--there is no need to transmit a long sequence of keys.