SUBSTITUTION CIPHER

A substitution cipher is one in which the units of the plaintext (usually letters or numbers) are replaced with other symbols or groups of symbols. The actual order of the units of the plaintext is not changed.

The simplest substitution cipher is one where the alphabet of the cipher is merely a shift of the plaintext alphabet, for example, A might be encrypted as B, C as D and so forth. Of this type of cipher, the most well known is the Caesar cipher, used by Julius Caesar in which A becomes D etc. It is easy to guess that cyclical-shift substitution ciphers of this sort are not at all secure because individual letter frequencies are left completely intact.

There are primarily two approaches that have been used with substitution ciphers to reduce the extent to which the structure of the plaintext, including the letter frequencies, survives into the ciphertext. One of these methods is to treat more than a single letter as one element i.e. two or three successive letters are treated as one unit. The other method is to use several different cipher alphabets.

Historically, for encrypting elements of a plaintext made up of more than a single letter only digraphs (two successive letters) have ever been used. By treating two successive letters as a single unit the extent to which the original letter frequency distribution survives is reduced, thus making the job of the cryptanalysts harder, but not impossible since it can be shown that digraphs themselves have a high degree of correlation. The most well known digraph substitution cipher is the Playfair cipher, invented by Sir Charles Wheatstone.

Charles Wheatstone was a 19th century English physicist, born on February 6th, 1802. As well as devising the Playfair cipher he also invented the Wheatstone bridge, a device for accurately measuring electrical resistance which became widely used in laboratories. He also initiated the usage of electromagnets in electric generators and devised the stereoscope, a device for viewing pictures in three dimensions still used today. The Playfair cipher was named for Lyon Playfair, the first Baron Playfair of St. Andrews, who championed its usage at the British Foreign Office (although he was unsuccessful).

Here is an example of a Playfair cipher. The aid used to carry out the encryption is a 5 x 5 square matrix similar to a Polybius checkerboard in that it contains all the letters of the alphabet (I and J are treated as the same letter); however a keyword is placed first and then the remaining letters are placed in alphabetical order.

If the plaintext contains an odd number of letters then an X is appended to the last word to make it an even number. Also, if any of the digraphs consist of identical letters e.g. SUMMER, then an extra letter is placed between them.

The first step in performing the encryption is to locate the two letters from the plaintext in the matrix. There are then several different substitution rules depending on their positioning:

1. If the pair of letters are in different rows and columns. The rows of the ciphertext letters are kept the same as the rows of the plaintext letters, however the columns swap. Therefore ME, once encrypted, becomes SC because E changes to the letter which is in the same row (2) but in the column of M (1) and M changes to the letter which is in the same row (1) but the column of E (3). It may be easier to remember this as the plaintext letters being at two corners of a rectangle and the ciphertext letters being at the other two corners.
2. If the pair of letters are in the same row. The ciphertext letters are the letters to the right of the plaintext letters. For example, T and A are in the same row so T will encrypt to S and A will encrypt to B, forming SB.
3. If the pair of letters are in the same column. The ciphertext letters are the letters below the plaintext letters. For example, Y and L are in the same column so Y becomes A and L becomes R, forming AR.

Thus, we can now encrypt the phrase "Merchant Taylors’ School":

Plaintext:	ME	RC	HA	NT	TA	YL	OR	SZ	SC	HO	OL
Ciphertext:	SC	OF	LM	BI	AB	AR	PU	BX	ME	OV	RH

(The last S of "TAYLORS" is paired with a Z to separate it from the first S of "SCHOOL").

The other approach to concealing plaintext structure in the ciphertext involves using several different substitution ciphers. The resulting ciphers, which are generically known as polyalphabetics, have a long history of usage. The best-known polyalphabetic ciphers are the simple Vigenère ciphers which are named after the 16^th century French cryptographer Blaise de Vigenère (see History). Blaise de Vigenère actually produced a more sophisticated autokey cipher, but through an accident of history his name has become attached to this weaker cipher.

For many years this cipher was thought to be impregnable and it is rumoured that a well known scientific magazine pronounced it "uncrackable" as late as 1917, despite the fact that it had been broken by then.

In the simplest system of the Vigenère type the key is a word or a phrase which is repeated over and over again. The plaintext is encrypted using the table shown as Figure 4. The ciphertext letter is found at the intersection of the column headed by the plaintext letter and the row indexed by the key letter. To decrypt the plaintext letter is found at the head of the column determined by the intersection of the diagonal containing the cipher letter and the row containing the key letter.

It is the periodicity of the repeating key which leads to the weaknesses in this method and its vulnerabilities to cryptanalysis. This periodicity of a repeating key can be eliminated by the use of a running-key Vigenère cipher, produced when a non-repeating key is used. However, even though running-key ciphers eliminate periodicity it is still possible to cryptanalyse them by means of several methods, however the job of the cryptanalyst is made much harder and a cryptanalyst would require a much larger segment of ciphertext to solve a running-key cipher than one with a repeating key. In fact, the work of Major Joseph Mauborgne of the U.S. Army eventually led to the realisation that the only cryptographic system that is totally secure is that with a one-time completely random key.

Here is how the words "Merchant Taylors School" can be encrypted using this cipher:

Plaintext:

M

E

R

C

H

A

N

T

T

A

Y

L

O

R

S

S

C

H

O

O

L

Key:

D

O

N

T

S

T

A

N

D

A

L

O

N

E

D

O

N

T

S

T

A

Ciphertext:

P

S

E

V

Z

T

N

G

W

A

J

Z

B

V

V

G

P

A

G

H

L