Playfair cipher
Encyclopedia
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
technique and was the first literal digraph substitution
Polygraphic substitution
A polygraphic substitution is a cipher in which a uniform substitution is performed on blocks of letters. When the length of the block is specifically known, more precise terms are used: for instance, a cipher in which pairs of letters are substituted is bigraphic.As a concept, polygraphic...
cipher. The scheme was invented in 1854 by Charles Wheatstone
Charles Wheatstone
Sir Charles Wheatstone FRS , was an English scientist and inventor of many scientific breakthroughs of the Victorian era, including the English concertina, the stereoscope , and the Playfair cipher...
, but bears the name of Lord Playfair who promoted the use of the cipher.
The technique encrypts pairs of letters (digraphs), instead of single letters as in the simple substitution cipher
Substitution cipher
In cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a regular system; the "units" may be single letters , pairs of letters, triplets of letters, mixtures of the above, and so forth...
and rather more complex Vigenère cipher
Vigenère cipher
The Vigenère cipher is a method of encrypting alphabetic text by using a series of different Caesar ciphers based on the letters of a keyword. It is a simple form of polyalphabetic substitution....
systems then in use. The Playfair is thus significantly harder to break since the frequency analysis
Frequency analysis
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....
used for simple substitution ciphers does not work with it. Frequency analysis can still be undertaken, but on the 600 possible digraphs rather than the 26 possible monographs. The frequency analysis of digraphs is possible, but considerably more difficult – and it generally requires a much larger ciphertext in order to be useful.
History
The first recorded description of the Playfair cipher was in a document signed by Wheatstone on 26 March 1854.
It was rejected by the British Foreign Office when it was developed because of its perceived complexity. When Wheatstone offered to demonstrate that three out of four boys in a nearby school could learn to use it in 15 minutes, the Under Secretary of the Foreign Office responded, "That is very possible, but you could never teach it to attachés."
It was used for tactical purposes by British
United Kingdom
The United Kingdom of Great Britain and Northern IrelandIn the United Kingdom and Dependencies, other languages have been officially recognised as legitimate autochthonous languages under the European Charter for Regional or Minority Languages...
forces in the Second Boer War
Second Boer War
The Second Boer War was fought from 11 October 1899 until 31 May 1902 between the British Empire and the Afrikaans-speaking Dutch settlers of two independent Boer republics, the South African Republic and the Orange Free State...
and in World War I
World War I
World War I , which was predominantly called the World War or the Great War from its occurrence until 1939, and the First World War or World War I thereafter, was a major war centred in Europe that began on 28 July 1914 and lasted until 11 November 1918...
and for the same purpose by the Australia
Australia
Australia , officially the Commonwealth of Australia, is a country in the Southern Hemisphere comprising the mainland of the Australian continent, the island of Tasmania, and numerous smaller islands in the Indian and Pacific Oceans. It is the world's sixth-largest country by total area...
ns and Germans
Germany
Germany , officially the Federal Republic of Germany , is a federal parliamentary republic in Europe. The country consists of 16 states while the capital and largest city is Berlin. Germany covers an area of 357,021 km2 and has a largely temperate seasonal climate...
during World War II
World War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
. This was because Playfair is reasonably fast to use and requires no special equipment. A typical scenario for Playfair use would be to protect important but non-critical secrets during actual combat. By the time the enemy cryptanalysts could break the message, the information would be useless to them.
Playfair is no longer used by military forces because of the advent of digital encryption devices. Playfair is now regarded as insecure for any purpose, because modern computers could easily break the cipher within seconds.
The first published solution of the Playfair cipher was described in a 19-page pamphlet by Lieutenant Joseph O. Mauborgne, published in 1914.
Description
The Playfair cipher uses a 5 by 5 table containing a key word or phrase. Memorization of the keyword and 4 simple rules was all that was required to create the 5 by 5 table and use the cipher.To generate the key table, one would first fill in the spaces in the table with the letters of the keyword (dropping any duplicate letters), then fill the remaining spaces with the rest of the letters of the alphabet in order (usually omitting "Q" to reduce the alphabet to fit, other versions put both "I" and "J" in the same space). 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.
To encrypt a message, one would break the message into digraphs (groups of 2 letters) such that, for example, "HelloWorld" becomes "HE LL OW OR LD", and map them out on the key table. The two letters of the digraph are considered as the opposite corners of a rectangle in the key table. Note the relative position of the corners of this rectangle. Then apply the following 4 rules, in order, to each pair of letters in the plaintext:
- If both letters are the same (or only one letter is left), add an "X" after the first letter. Encrypt the new pair and continue. Some variants of Playfair use "Q" instead of "X", but any uncommon monograph will do.
- If the letters appear on the same row of your table, replace them with the letters to their immediate right respectively (wrapping around to the left side of the row if a letter in the original pair was on the right side of the row).
- If the letters appear on the same column of your table, replace them with the letters immediately below respectively (wrapping around to the top side of the column if a letter in the original pair was on the bottom side of the column).
- If the letters are not on the same row or column, replace them with the letters on the same row respectively but at the other pair of corners of the rectangle defined by the original pair. The order is important – the first letter of the encrypted pair is the one that lies on the same row as the first letter of the plaintext pair.
To decrypt, use the INVERSE (opposite) of the last 3 rules, and the 1st as-is (dropping any extra "X"s (or "Q"s) that don't make sense in the final message when finished).
Example
Using "playfair example" as the key, (assuming I and J are interchangeable) the table becomes:P L A Y F
I R E X M
B C D G H
K N O Q S
T U V W Z
Encrypting the message "Hide the gold in the tree stump":
HI DE TH EG OL DI NT HE TR EX ES TU MP
^
| 1. The pair HI forms a rectangle, replace it with BM | |
| 2. The pair DE is in a column, replace it with OD | |
| 3. The pair TH forms a rectangle, replace it with ZB | |
| 4. The pair EG forms a rectangle, replace it with XD | |
| 5. The pair OL forms a rectangle, replace it with NA | |
| 6. The pair DI forms a rectangle, replace it with BE | |
| 7. The pair NT forms a rectangle, replace it with KU | |
| 8. The pair HE forms a rectangle, replace it with DM | |
| 9. The pair TR forms a rectangle, replace it with UI | |
| 10. The pair EX (X inserted to split EE) is in a row, replace it with XM | |
| 11. The pair ES forms a rectangle, replace it with MO | |
| 12. The pair TU is in a row, replace it with UV | |
| 13. The pair MP forms a rectangle, replace it with IF |
BM OD ZB XD NA BE KU DM UI XM MO UV IF
Thus the message "Hide the gold in the tree stump" becomes "BMODZBXDNABEKUDMUIXMMOUVIF".
Clarification with pictures
Assume one wants to encrypt the digraph OR. There are three general cases:| 1) * * * * * * O Y R Z * * * * * * * * * * * * * * * Hence, OR -> YZ |
2) * * O * * * * B * * * * * * * * * R * * * * Y * * Hence, OR -> BY |
3) Z * * O * * * * * * * * * * * R * * X * * * * * * Hence, OR -> ZX |
Cryptanalysis
Like most pre-modern era ciphers, the Playfair 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 cryptanalysisCryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
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 Playfair is similar to that of four-square
Four-square cipher
The four-square cipher is a manual symmetric encryption technique. It was invented by famous French cryptographer Felix Delastelle.The technique encrypts pairs of letters , and thus falls into a category of ciphers known as polygraphic substitution ciphers...
and two-square
Two-square cipher
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 Playfair cipher.The technique...
ciphers, though the relative simplicity of the Playfair system makes identifying candidate plaintext strings easier. Most notably, a Playfair digraph and its reverse (e.g. AB and BA) will decrypt to the same letter pattern in the plaintext (e.g. RE and ER). In English, there are many words which contain these reversed digraphs such as REceivER and DEpartED. Identifying nearby reversed digraphs in the ciphertext and matching the pattern to a list of known plaintext words containing the pattern is an easy way to generate possible plaintext strings with which to begin constructing the key.
A different approach to tackling a Playfair cipher is the shotgun hill climbing method. This starts with a random square of letters. Then minor changes are introduced (i.e. switching letters, rows, or reflecting the entire square) to see if the candidate plaintext is more like standard plaintext than before the change (perhaps by comparing the digraphs to a known frequency chart). If the new square is deemed to be an improvement, then it is adopted and then further mutated to find an even better candidate. Eventually, the plaintext or something very close is found to achieve a maximal score by whatever grading method is chosen. This is obviously beyond the range of typical human patience, but computers can adopt this algorithm to crack Playfair ciphers with a relatively small amount of text.
Another aspect of Playfair that separates it from four-square and two-square ciphers is the fact that it will never contain a double-letter digraph, e.g. EE. If there are no double letter digraphs in the ciphertext and the length of the message is long enough to make this statistically significant, it is very likely that the method of encryption is Playfair.
A good tutorial on reconstructing the key for a Playfair cipher can be found in chapter 7, "Solution to Polygraphic Substitution Systems," of Field Manual 34-40-2, produced by the United States Army.
A detailed cryptanalysis of Playfair is undertaken in chapter 28 of Dorothy L. Sayers
Dorothy L. Sayers
Dorothy Leigh Sayers was a renowned English crime writer, poet, playwright, essayist, translator and Christian humanist. She was also a student of classical and modern languages...
' mystery novel Have His Carcase
Have His Carcase
Have His Carcase is a 1932 novel by Dorothy L. Sayers, her seventh featuring Lord Peter Wimsey and her second novel in which Harriet Vane appears...
. In this story, a Playfair message is demonstrated to be cryptographically weak, as the detective is able to solve for the entire key making only a few guesses as to the formatting of the message (in this case, that the message starts with the name of a city and then a date). Sayers' book includes a detailed description of the mechanics of Playfair encryption, as well as a step-by-step account of manual cryptanalysis.
The German Army, Air Force and Police used the Double Playfair system as a medium-grade cipher in WWII, but as they had broken the cipher early in WWI, they adapted it by introducing a second square from which the second letter of each bigram was selected, and dispensed with the keyword, placing the letters in random order. But with the German fondness for pro forma
Pro forma
The term pro forma is a term applied to practices or documents that are done as a pure formality, perfunctory, or seek to satisfy the minimum requirements or to conform to a convention or doctrine...
messages, they were broken at Bletchley Park
Bletchley Park
Bletchley Park is an estate located in the town of Bletchley, in Buckinghamshire, England, which currently houses the National Museum of Computing...
. Messages were preceded by a sequential number, and numbers were spelt out. As the German numbers 1 (eins) to twelve (zwölf) contain all but eight of the letters in the Double Playfair squares, pro forma traffic was relatively easy to break (Smith, page 74-75)
Use in modern crosswords
Advanced thematic cryptic crosswords like The Listener Crossword (published in the Saturday edition of The TimesThe Times
The Times is a British daily national newspaper, first published in London in 1785 under the title The Daily Universal Register . The Times and its sister paper The Sunday Times are published by Times Newspapers Limited, a subsidiary since 1981 of News International...
(UK) newspaper) occasionally incorporate Playfair ciphers . Normally between 4 and 6 answers have to be entered into the grid in code, and the Playfair keyphrase is thematically significant to the final solution. The cipher lends itself well to crossword puzzles, because the plaintext is found by solving one set of clues, while the ciphertext is found by solving others. Solvers can then construct the key table by pairing the digraphs (it is sometimes possible to guess the keyword, but never necessary).
Use of the Playfair cipher is generally explained as part of the preamble to the crossword. This levels the playing field for those solvers who have not come across the cipher previously. But the way the cipher is used is always the same. The 25-letter alphabet used always contains Q and has I and J coinciding. The key table is always filled row by row.
In popular culture
- The novel Have His CarcaseHave His CarcaseHave His Carcase is a 1932 novel by Dorothy L. Sayers, her seventh featuring Lord Peter Wimsey and her second novel in which Harriet Vane appears...
by Dorothy L. SayersDorothy L. SayersDorothy Leigh Sayers was a renowned English crime writer, poet, playwright, essayist, translator and Christian humanist. She was also a student of classical and modern languages...
gives a blow-by-blow account of the cracking of a Playfair cipher. - In the film National Treasure: Book of Secrets, a treasure hunt clue is encoded as Playfair cipher.
- In the audio book Rogue AngelRogue AngelRogue Angel is a paper back series of novels published bi-monthly since July 2006 by Harlequin Publishing's Gold Eagle division and written under the house name of Alex Archer. Actual authors are credited with small notes inside the books, but not on the front covers or spines. The main character...
: God of Thunder, a Playfair cipher clue is used to send Anja Creed to Venice.