Example 2: The Vigenère cipher and one-time pads

This cipher works by replacing each letter by another letter a specified number of positions further in the alphabet. For example J is 5 positions further than E. D is 5 positions after Y. (Y,Z,A,B,C,D) The key is a sequence of shift amounts. If the sequence is of length 10, the 1st, 11th, 21st, ...letters of the plaintext are processed using the first member of the key. The second member of the key processes plaintext letters 2, 12, 22, ...and so forth. If we omit spaces from the plaintext on page  and use the key-sequence:

$$3 1 7 23 10 5 19 14\ 19 24$$

we obtain

WILPOHNFBR BPMQRJKGTC QDVASSZGVF

HNLOOQBSLM QUOBPFVHMF DUULLTWMAY VCLBXFUZXR

REPPMTOSKF RXALDFDSVS EFYLYYLAHB QXPQRTNHDL

RXPKQSLTTA WPYP

(We have divided the ciphertext into groups of ten letters for convenience. The division into lines is arbitrary.)

This type of cipher was considered very secure at one time ($\sim1600$), but is not really difficult. Suppose we guess that the first letter is T. This implies the eleventh letter is Y, the 21st letter is N, etc. Now look at the two-letter combinations that occur from different possiblilities for the second letter:

TI YP ND EN NU AU SC OE OX BF NX OX TP    (no shift of 2nd letter)

TJ YQ NE EO NV AV SD OF OY BG NY OY TQ

TK YR NF EP NW AW SE OG OZ BH NZ OZ TR

TL YS NG EQ NX AX SF OH OA BI NA OA TS

    (skipping over some in the middle)

TF YM NA EK NR AR SZ OB OU BE NU OU TM

TG YN NB EL NS AS SA OC OV BD NV OV TN

TH YO NC EM NT AT SB OD OW BE NW OW TO

The last line is the ``right answer.'' Although it shows several bad combinations (NC NT SB NW), mostly caused by the last letter of one word being adjacent to the first letter of the next word, it looks better than the other possible rows. Once the second letter has been identified, the same approach can be used to get the third letter. This approach is easily automated using a table of digrams.

It is necessary to know the first letter and the length of the key-sequence. If we assume the length is not too large, a program can just try all possibilities, eventually choosing the plaintext which looks best.¹

One-time pads

A long key-sequence makes this approach more difficult, since we have fewer rows. The extreme case is that in which the key-sequence is as long as the plaintext itself. This leads to a theoretically unbreakable cipher. For any possible plaintext, there is a key for which the given ciphertext comes from that plaintext.

This type of cipher has reportedly been used by spies, who were furnished with notebooks containing page after page of randomly generated key-sequence. Notice that it is essential that each key-sequence be used only once (hence the name of the system). Otherwise the approach for Vigenère systems described above could be tried, since we would have at least two rows to work with.

One-time pads seem practical in situations where one agent is communicating with a central command. They become less attractive if several agents may need to communicate with each other. The one-time feature is lost if X and Y inadvertently use the same page to talk as W and Z are using. Also capture of X's equipment makes it possible to overhear a conversation between Y and Z.

Footnotes

... best.¹

Mike Mendelson, a student in this course in 1989, wrote a program to implement this algorithm. Another method would choose the shift amount for each member of the cycle which gives the best letter frequency.