Four-square cipher

Last updated

The four-square cipher is a manual symmetric encryption technique. [1] It was invented by the French cryptographer Felix Delastelle.

Contents

The technique encrypts pairs of letters (digraphs), and thus falls into a category of ciphers known as polygraphic substitution ciphers. This adds significant strength to the encryption when compared with monographic substitution ciphers which operate on single characters. The use of digraphs makes the four-square technique less susceptible to frequency analysis attacks, as the analysis must be done on 676 possible digraphs rather than just 26 for monographic substitution. The frequency analysis of digraphs is possible, but considerably more difficult - and it generally requires a much larger ciphertext in order to be useful.

Using four-square

The four-square cipher uses four 5 by 5 (5x5) 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.

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 (again omitting "Q" to reduce the alphabet to fit). The key can be written in the top rows of the table, from left to right, or in some other pattern, such as a spiral beginning in the upper-left-hand corner and ending in the center. The keyword together with the conventions for filling in the 5 by 5 table constitute the cipher key. The four-square algorithm allows for two separate keys, one for each of the two ciphertext matrices.

As an example, here are the four-square matrices for the keywords "example" and "keyword." The plaintext matrices are in lowercase and the ciphertext matrices are in caps to make this example visually more simple:

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

Algorithm

To encrypt a message, one would follow these steps:

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
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
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
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

Using the four-square example given above, we can encrypt the following plaintext:

Plaintext:  he lp me ob iw an ke no bi Ciphertext: FY GM KY HO BX MF KK KI MD

Here is the four-square written out again but blanking all of the values that aren't used for encrypting the first digraph "he" into "FY"

- - - - -   - - - - - - - h - -   - - - - F - - - - -   - - - - - - - - - -   - - - - - - - - - -   - - - - -   - - Y - -   - - - - e - - - - -   - - - - - - - - - -   - - - - - - - - - -   - - - - - - - - - -   - - - - -

As can be seen clearly, the method of encryption simply involves finding the other two corners of a rectangle defined by the two letters in the plaintext digraph. The encrypted digraph is simply the letters at the other two corners, with the upper-right letter coming first.

Decryption works the same way, but in reverse. The ciphertext digraph is split with the first character going into the upper-right matrix and the second character going into the lower-left matrix. The other corners of the rectangle are then located. These represent the plaintext digraph with the upper-left matrix component coming first.

Four-square cryptanalysis

Like most pre-modern era ciphers, the four-square cipher can be easily cracked if there is enough text. Obtaining the key is relatively straightforward if both plaintext and ciphertext are known. When only the ciphertext is known, brute force cryptanalysis of the cipher involves searching through the key space for matches between the frequency of occurrence of digrams (pairs of letters) and the known frequency of occurrence of digrams in the assumed language of the original message.

Cryptanalysis of four-square generally involves pattern matching on repeated monographs. This is only the case when the two plaintext matrices are known. A four-square encipherment usually uses standard alphabets in these matrices but it is not a requirement. If this is the case, then certain words will always produce single-letter ciphertext repeats. For instance, the word MI LI TA RY will always produce the same ciphertext letter in the first and third positions regardless of the keywords used. Patterns like these can be cataloged and matched against single-letter repeats in the ciphertext. Candidate plaintext can then be inserted in an attempt to uncover the ciphertext matrices.

Unlike 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.

By all measures, four-square is a stronger system for encrypting information than Playfair. However, 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 has become 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.

Related Research Articles

In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called blocks. They are specified elementary components in the design of many cryptographic protocols and are widely used to encrypt large amounts of data, including in data exchange protocols. It uses blocks as an unvarying transformation.

In cryptography, a substitution cipher is a method of encrypting in which units of plaintext are replaced with the ciphertext, in a defined manner, with the help of a key; the "units" may be single letters, pairs of letters, triplets of letters, mixtures of the above, and so forth. The receiver deciphers the text by performing the inverse substitution process to extract the original message.

In cryptography, a transposition cipher is a method of encryption which scrambles the positions of characters (transposition) without changing the characters themselves. Transposition ciphers reorder units of plaintext according to a regular system to produce a ciphertext which is a permutation of the plaintext. They differ from substitution ciphers, which do not change the position of units of plaintext but instead change the units themselves. Despite the difference between transposition and substitution operations, they are often combined, as in historical ciphers like the ADFGVX cipher or complex high-quality encryption methods like the modern Advanced Encryption Standard (AES).

<span class="mw-page-title-main">Vigenère cipher</span> Simple type of polyalphabetic encryption system

The Vigenère cipher is a method of encrypting alphabetic text by using a series of interwoven Caesar ciphers, based on the letters of a keyword. It employs a form of polyalphabetic substitution.

The poem code is a simple, and insecure, cryptographic method which was used during World War II by the British Special Operations Executive (SOE) to communicate with their agents in Nazi-occupied Europe.

<span class="mw-page-title-main">Tabula recta</span> Fundamental tool in cryptography

In cryptography, the tabula recta is a square table of alphabets, each row of which is made by shifting the previous one to the left. The term was invented by the German author and monk Johannes Trithemius in 1508, and used in his Trithemius cipher.

<span class="mw-page-title-main">Frequency analysis</span> Study of the frequency of letters or groups of letters in a ciphertext

In cryptanalysis, frequency analysis is the study of the frequency of letters or groups of letters in a ciphertext. The method is used as an aid to breaking classical ciphers.

<span class="mw-page-title-main">Playfair cipher</span> Early block substitution cipher

The Playfair cipher or Playfair square or Wheatstone–Playfair cipher is a manual symmetric encryption technique and was the first literal digram substitution cipher. The scheme was invented in 1854 by Charles Wheatstone, but bears the name of Lord Playfair for promoting its use.

The affine cipher is a type of monoalphabetic substitution cipher, where each letter in an alphabet is mapped to its numeric equivalent, encrypted using a simple mathematical function, and converted back to a letter. The formula used means that each letter encrypts to one other letter, and back again, meaning the cipher is essentially a standard substitution cipher with a rule governing which letter goes to which. As such, it has the weaknesses of all substitution ciphers. Each letter is enciphered with the function (ax + b) mod 26, where b is the magnitude of the shift.

In cryptography, the ADFGVX cipher was a manually applied field cipher used by the Imperial German Army during World War I. It was used to transmit messages secretly using wireless telegraphy. ADFGVX was in fact an extension of an earlier cipher called ADFGX which was first used on 1 March 1918 on the German Western Front. ADFGVX was applied from 1 June 1918 on both the Western Front and Eastern Front.

In classical cryptography, the bifid cipher is a cipher which combines the Polybius square with transposition, and uses fractionation to achieve diffusion. It was invented around 1901 by Felix Delastelle.

In cryptography, a classical cipher is a type of cipher that was used historically but for the most part, has fallen into disuse. In contrast to modern cryptographic algorithms, most classical ciphers can be practically computed and solved by hand. However, they are also usually very simple to break with modern technology. The term includes the simple systems used since Greek and Roman times, the elaborate Renaissance ciphers, World War II cryptography such as the Enigma machine and beyond.

Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts. The term "probabilistic encryption" is typically used in reference to public key encryption algorithms; however various symmetric key encryption algorithms achieve a similar property, and stream ciphers such as Freestyle which are inherently random. To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.

<span class="mw-page-title-main">Hill cipher</span> Substitution cipher based on linear algebra

In classical cryptography, the Hill cipher is a polygraphic substitution cipher based on linear algebra. Invented by Lester S. Hill in 1929, it was the first polygraphic cipher in which it was practical to operate on more than three symbols at once.

<span class="mw-page-title-main">Rail fence cipher</span> Type of transposition cipher

The rail fence cipher is a classical type of transposition cipher. It derives its name from the manner in which encryption is performed, in analogy to a fence built with horizontal rails.

The Two-square cipher, also called double Playfair, is a manual symmetric encryption technique. It was developed to ease the cumbersome nature of the large encryption/decryption matrix used in the four-square cipher while still being slightly stronger than the single-square Playfair cipher.

In cryptography, an interpolation attack is a type of cryptanalytic attack against block ciphers.

The Beaufort cipher, created by Sir Francis Beaufort, is a substitution cipher similar to the Vigenère cipher, with a slightly modified enciphering mechanism and tableau. Its most famous application was in a rotor-based cipher machine, the Hagelin M-209. The Beaufort cipher is based on the Beaufort square which is essentially the same as a Vigenère square but in reverse order starting with the letter "Z" in the first row, where the first row and the last column serve the same purpose.

The Smithy code is a series of letters embedded, as a private amusement, within the April 2006 approved judgement of Mr Justice Peter Smith on The Da Vinci Code copyright case. It was first broken, in the same month, by Dan Tench, a lawyer who writes on media issues for The Guardian, after he received a series of email clues about it from Justice Smith.

In cryptography, M8 is a block cipher designed by Hitachi in 1999. It is a modification of Hitachi's earlier M6 algorithm, designed for greater security and high performance in both hardware and 32-bit software implementations. M8 was registered by Hitachi in March 1999 as ISO/IEC 9979-0020.

References

  1. William Maxwell Bowers (1959). Digraphic substitution: the Playfair cipher, the four square cipher. American Cryptogram Association. p. 25.

See also