Section 2.3: Substitution Ciphers
A substitution cipher is a cipher in which correspondents agree on a rearrangement (permutation) of the alphabet in which messages are written.
Examples
1. Ciphers given in newspapers
2. Atbash cipher – p. 3 of textbook.
3. Poe Gold Bug Short Story
4. Beale Cipher – Bedford, Virginia
Shift ciphers and affine ciphers are special examples of substitution ciphers where mathematical formulas are used to rearrange the alphabet. There are other ways to create a more random arrangement of the letters which we describe next.
Techinques For Creating Simple Substitution Ciphers
1. Mixed Alphabets with Simple Keyword Substitution Cipher.
2. Mixed Alphabets with Keyword Columnar Substitution Cipher.
We describe these techniques next
1. Mixed Alphabets with Keyword Substitution Cipher
We write the letters of a keyword without repetitions in order of appearance below the plaintext alphabet. We then list the remaining letters of the alphabet below the plaintext in the usual order.
Example 1: Suppose we want the use the keyword “NEILSIGMON” to create a simple keyword substitution cipher.
a. Use the keyword to create the cipher alphabet.
b. Encipher “BURIED TREASURE”
c. Decipher “TQAXAS AR N HAIS LJM”.
Solution: For part a, we first must remove the repetitions from the keyword. This means that that the repetitive keyword letters I and N in the keyword “NEILSIGMON” are only listed once. Hence, the following operation is performed on the keyword.
NEILSIGMON NEILSGMO
We now use “NEILSGMO” to form the cipher alphabet in the following fashion:
Plain: A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
Cipher: N  E  I  L  S  G M O  A  B C  D  F  H  J  K  P  Q  R T  U  V  W  X  Y  Z
Keyword (no repetitions) Rest of Alphabet Letters
To do part b, we simply list the corresponding ciphertext letters under the letters for the plaintext using the above ciphertext alphabet. That is,
B  U  R  I  E  D  T  R  E  A  S  U  R  E
E  U  Q  A  S  L  T  Q  S  N  R  U  Q  S
Hence, the ciphertext is “EUQASL TQSNRUQS”
To do part c, we simply list the corresponding plaintext over the ciphertext letters using the alphabet assignment given above
T  R  I  X  I  E  I  S  A  N  I  C  E  D  O  G
T  Q  A  X  A  S  A  R  N  H  A  I  S  L  J  M
Hence, the plaintext is “TRIXIE IS A NICE DOG”. █
Example 1 illustrates a flaw that can occur in a simple substitution keyword cipher. Normally, the last several letters of the plain and ciphertext in a simple substitution cipher are the same. These “collisions” can make this type of cipher more vulnerable to cryptanalysis. The next method for creating a substitution cipher attempts to alleviate this problem.
1. Mixed Alphabets with Keyword Columnar Substitution Cipher
We write the letters of a keyword without repetitions in order of appearance. The remaining letters of the alphabet are written in successive rows below the keyword. The mixed ciphertext alphabet is obtained by writing the letters of the resulting array column by column (starting with column 1) below the plaintext alphabet.
Example 2: Suppose we want to use the keyword “RADFORDVA” to create a keyword columnar substitution cipher.
a. Create the cipher alphabet.
b. Encipher “THOMAS BARR”
c. Decipher “VFUDO RH UKFQYO JFEEYCY”
Solution: For part a, we first must remove the repetitions from the keyword. Hence, the following operation is performed on the keyword.
RADFORDVA RADFOV
Next, we list the remainder of the alphabet in an array below the keyword.
R A D F O V keyword
B C E G H I
J K L M N P rest of alphabet
Q S T U W X
Y Z
Using this array, we now form the cipher alphabet by writing the array column by column going from left to right under the plaintext alphabet .
Plain: A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
Cipher: R  B  J  Q Y  A C K  S  Z  D  E  L  T  F  G  M  U  O H  N  W V  I  P  X
Column 1 Column 2 Column 3 etc.
To do part b, we simply list the corresponding ciphertext letters under the letters for the plaintext using the above ciphertext alphabet. That is,
T  H  O  M  A  S  B  A  R  R 
H  K  F  L  R  O  B  R  U  U 
Hence, the ciphertext is “”HKFLRO BRUU”
To do part c, we simply list the corresponding plaintext over the ciphertext letters using the alphabet assignment given above
W  O  R  K  S  A  T  R  H  O  D  E  S  C  O  L  L  E  G  E
V  F  U  D  O  R  H  U  K  F  Q  Y  O  J  F  E  E  Y  C  Y
Hence, the plaintext is “WORKS AT RHODES COLLEGE”. █
Cryptanalysis of Substitution Ciphers
To break a ciphertext that is encrypted using a substitution cipher, we use frequency analysis on single letters, digraphs (highly occurring two letter sequences), and trigraphs (highly occurring three letter sequences.
Example 3: Suppose the following messg
Example 4:
