Code 18 : Four-square Cipher

The four-square cipher encrypts pairs of letters (digraphs) and is thus less susceptible to frequency analysis attacks. The four-square cipher uses four 5 by 5 matrices arranged in a square. Each of the 5 by 5 matrices contains the letters of the alphabet (usually omitting "Q" or putting both "I" and "J" in the same location to reduce the alphabet to fit). In general, the upper-left and lower-right matrices are the "plaintext squares" and each contain a standard alphabet. The upper-right and lower-left squares are the "ciphertext squares" and contain a mixed alphabetic sequence.

a b c d e   E X A M P
f g h i j   L B C D F
k l m n o   G H I J K
p r s t u   N O R S T
v w x y z   U V W Y Z
 
K E Y W O   a b c d e
R D A B C   f g h i j
F G H I J   k l m n o
L M N P S   p r s t u
T U V X Z   v w x y z

To generate the ciphertext squares, one would first fill in the spaces in the matrix with the letters of a keyword or phrase (dropping any duplicate letters), then fill the remaining spaces with the rest of the letters of the alphabet in order. The four-square algorithm allows for two separate keys, one for each of the two ciphertext matrices. In the example to the right, "EXAMPLE" and "KEYWORD" have been used as keywords.
To encrypt a message you would first split the message into digraphs. "This is a secret message" would become:

TH IS IS AS EC RE TM ES SA GE

a b c d e   E X A M P
f g h i j   L B C D F
k l m n o   G H I J K
p r s t u   N O R S T
v w x y z   U V W Y Z
 
K E Y W O   a b c d e
R D A B C   f g h i j
F G H I J   k l m n o
L M N P S   p r s t u
T U V X Z   v w x y z

Once that was complete, you would take the first pair of letters and find the first letter in the upper left square and the second letter in the lower right square. In this example we are enciphering TH, so we locate T and H in the grid below (see blue characters). Now, we find the intersections of the rows and columns of the plain text letters. In this example, they have been highlighted in red (R and B). These new letters are the enciphered digraph (RB).
You continue enciphering digraphs in this way until you reach the end of the message. To continue our example, "This is a secret message" would be enciphered as:

RB CP CP AL AO TE RI AS NY FE

Introduction

The Four-square cipher encrypts pairs of letters (like playfair), which makes it significantly stronger than substitution ciphers etc. since frequency analysis becomes much more difficult.
Felix Delastelle (1840 - 1902) invented the four-square cipher, first published in a book in 1902. Delastelle was most famous for his invention of several systems of polygraphic substitution ciphers including bifid, trifid, and the four-square cipher.
For a guide on how to break the foursquare cipher using Simulated Annealing, see Cryptanalysis of the Foursquare Cipher.

The Algorithm

The four-square cipher uses four 5 by 5 matrices arranged in a square. Each of the 5 by 5 matrices contains 25 letters, usually the letter 'j' is merged with 'i' (wikipedia says 'q' is omitted, it is not very important since both q and j are rather rare letters). In general, the upper-left and lower-right matrices are the "plaintext squares" and each contain a standard alphabet. The upper-right and lower-left squares are the "ciphertext squares" and contain a mixed alphabetic sequence.
The ciphertext squares can be generated using a keyword (dropping duplicate letters), then fill the remaining spaces with the remaining letters of the alphabet in order. Alternatively the ciphertext squares can be generated completely randomly. The four-square algorithm allows for two separate keys, one for each of the two ciphertext matrices.

Steps

1. Break up the plaintext into bigrams i.e. ATTACK AT DAWN --> AT TA CK AT DA WN
   An 'X' (or some other character) may have to be appended to ensure the plaintext is an even length.
   
2. Using the four 'squares', two plain alphabet squares and two cipher alphabet squares, locate the bigram to encrypt in the plain alphabet squares. The example below enciphers the bigram 'AT'. The first letter is located from the top left square, the second letter is located in the bottom right square.
   

    
   a b c d e   Z G P T F
   f g h i k   O I H M U
   l m n o p   W D R C N
   q r s t u   Y K E Q A
   v w x y z   X V S B L
    
   M F N B D   a b c d e
   C R H S A   f g h i k
   X Y O G V   l m n o p
   I T U E W   q r s t u
   L Q Z K P   v w x y z
   

3. Locate the characters in the ciphertext at the corners of the rectangle that the letters 'AT' make:
   

    
   a b c d e   Z G P T F
   f g h i k   O I H M U
   l m n o p   W D R C N
   q r s t u   Y K E Q A
   v w x y z   X V S B L
    
   M F N B D   a b c d e
   C R H S A   f g h i k
   X Y O G V   l m n o p
   I T U E W   q r s t u
   L Q Z K P   v w x y z
   

4. Using the above keys, the bigram 'AT' is encrypted to 'TI'.
   The text 'attack at dawn', with the keys 'zgptfoihmuwdrcnykeqaxvsbl' and 'mfnbdcrhsaxyogvituewlqzkp', becomes:
   

   ATTACKATDAWN
   TIYBFHTIZBSY
   

JavaScript Example of the Foursquare Cipher

This is an implementation of the Foursquare cipher in javascript. The keysquares are written out as a 25 character string, instead of a 5 by 5 array. Plaintext
attack at dawn keysquare 1 =
keysquare 2 =

Ciphertext

Cryptanalysis

For a guide on how to break the foursquare cipher using Simulated Annealing, see Cryptanalysis of the Foursquare Cipher.
The four-square cipher can be easily cracked with enough ciphertext. It is quite simple to determine the key if both plaintext and ciphertext are known, and for this reason guessing parts of the plaintext is a very effective way of cracking this cipher. If a portion of the plaintext is known or can be guessed this should be exploited first to determine as much of the key as possible, then more guessing can be applied or other techniques described below.
Compared to the Playfair cipher, a four-square cipher will not show reversed ciphertext digraphs for reversed plaintext digraphs (e.g. the digraphs AB BA would encrypt to some pattern XY YX in Playfair, but not in four-square). This, of course, is only true if the two keywords are different. Another difference between four-square and Playfair which makes four-square a stronger encryption is the fact that double letter digraphs will occur in four-square ciphertext. [1]
The four-square cipher is a stronger cipher than Playfair, but it is more cumbersome because of its use of two keys and preparing the encryption/decryption sheet can be time consuming. Given that the increase in encryption strength afforded by four-square over Playfair is marginal and that both schemes are easily defeated if sufficient ciphertext is available, Playfair was much more common.
A good tutorial on reconstructing the key for a four-square cipher can be found in chapter 7, "Solution to Polygraphic Substitution Systems," of Field Manual 34-40-2, produced by the United States Army.

References 

 http://practicalcryptography.com/ciphers/four-square-cipher/

 http://www.braingle.com

• [1] Wikipedia has a good description of the encryption/decryption process, history and cryptanalysis of this algorithm
• Basic Cryptanalysis, FM 34-40-2, FIELD MANUAL, DEPARTMENT OF THE ARMY http://www.umich.edu/~umich/fm-34-40-2/