Editing Playfair cipher

{{short description|Early block substitution cipher}}
{{Distinguish|Wadsworth's cipher}}
[[File:Playfair Cipher 01 HI to BM (cropped).png|thumb|The Playfair cipher uses a 5×5 grid of letters, and encrypts a message by breaking the text into pairs of letters and swapping them according to their positions in a rectangle within that grid: "HI" becomes "BM".]]

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

The technique encrypts pairs of letters (''[[bigram]]s'' or ''digrams''), instead of single letters as in the simple [[substitution cipher]] and rather more complex [[Vigenère cipher]] systems then in use. The Playfair cipher is thus significantly harder to break since the [[frequency analysis]] used for simple substitution ciphers does not work with it.  The frequency analysis of bigrams is possible, but considerably more difficult. With 600<ref>No duplicate letters are allowed, and one letter is omitted (Q) or combined (I/J), so the calculation is 600 = 25×24.</ref> possible bigrams rather than the 26 possible monograms (single symbols, usually letters in this context), a considerably larger cipher text is required in order to be useful.

==History==
[[Image:Lyon Playfair.jpg|thumbnail|[[Lord Playfair]], who heavily promoted its use.]]
Playfair cipher was the first cipher to encrypt pairs of letters in cryptologic history.<ref>[https://books.google.com/books?id=3S8rhOEmDIIC&dq=%22the+cipher+is+the+first+literal+one%22&pg=PT220 ''The Codebreakers''] (1996) David Kahn, Scribner Books from Simon & Schuster </ref> [[Charles Wheatstone|Wheatstone]] invented the cipher for secrecy in [[telegraphy]], but it carries the name of his friend [[Lord Playfair]], first Baron Playfair of St. Andrews, who promoted its use.<ref name=":0">{{Cite web|url=https://www.nku.edu/~christensen/section%2019%20playfair%20cipher.pdf|title=Polygraphic Ciphers|last=Christensen|first=Chris|date=2006|website=Northern Kentucky University, Chris Christensen|access-date=January 9, 2018}}</ref><ref name=":1" /><ref name=":2" /> The first recorded description of the Playfair cipher was in a document signed by Wheatstone on 26 March 1854. 

It was initially rejected by the [[British Foreign Office]] when it was developed because of its perceived complexity. Wheatstone offered to demonstrate that three out of four boys in a nearby school could learn to use it in 15 minutes, but the Under Secretary of the Foreign Office responded, "That is very possible, but you could never teach it to attachés."<ref>{{Cite book|url=https://books.google.com/books?id=YpbKDTpVOAcC|title=Memoirs and Correspondence of Lyon Playfair: First Lord Playfair of St. Andrews ...|last=Reid|first=Thomas Wemyss|date=1899|publisher=Harper & Brothers|pages=158–159|language=en}}</ref> 

It was however later used for tactical purposes by British forces in the [[Second Boer War]] and in [[World War I]] and for the same purpose by the British and Australians during [[World War II]].<ref name=":1">{{cite book|last1=Kahn|first1=David|title=The Codebreakers: The comprehensive history of secret communi cation from ancient times to the internet|date=1996|publisher=Scribner|isbn=978-0684831305}}</ref><ref name=":2">{{Cite web|url=http://www.appstate.edu/~klimare/MAT3530_2_3.pdf|title=Secret Codes Through World War II|last=Klima|first=Rick|date=2018|website=Appalachian State University, Dr. Rick Klima|access-date=2018-01-09|archive-date=2017-10-13|archive-url=https://web.archive.org/web/20171013122801/http://www.appstate.edu/~klimare/MAT3530_2_3.pdf|url-status=dead}}</ref> This was because Playfair is reasonably fast to use and requires no special equipment - just a pencil and some paper. A typical scenario for Playfair use was to protect important but non-critical secrets during actual combat e.g. the fact that an artillery barrage of [[White phosphorus munitions|smoke shells]] would commence within 30 minutes to cover soldiers' advance towards the next objective. By the time enemy cryptanalysts could decode such messages hours later, such information would be useless to them because it was no longer relevant.<ref>{{cite book |last1=Lord |first1=Walter |title=Lonely Vigil: Coastwatchers of the Solomons |date=2012 |publisher=Open Road Media. Kindle Edition. |page=6 }}</ref> 

During World War II, the [[Government of New Zealand]] used it for communication among [[New Zealand]], the [[Chatham Islands]], and the [[coastwatchers]] in the Pacific Islands.<ref>[http://rnzncomms.org/ourhistory/chapter8/ "A History of Communications Security in New Zealand By Eric Mogon"], Chapter 8</ref><ref>{{cite web| title =The History of Information Assurance (IA)| work =Government Communications Security Bureau| publisher =New Zealand Government| url =http://www.gcsb.govt.nz/about-us/history-ia.html| access-date =2011-12-24| url-status =dead| archive-url =https://web.archive.org/web/20111112144636/http://www.gcsb.govt.nz/about-us/history-ia.html| archive-date =2011-11-12}}</ref> [[Coastwatchers]] established by [[Royal Australian Navy]] Intelligence also used this cipher.<ref>{{cite book |last1=Lord |first1=Walter |title=Lonely Vigil: Coastwatchers of the Solomons |date=2012 |publisher=Open Road Media. Kindle Edition. |page=6 }}</ref>

== Superseded ==
Playfair is no longer used by military forces because of known insecurities and of the advent of automated encryption devices. This cipher is regarded as insecure since before [[World War I]].

The first published solution of the Playfair cipher was described in a 19-page pamphlet by Lieutenant [[Joseph O. Mauborgne]], published in 1914.<ref>{{cite book |last=Mauborgne |first=Joseph Oswald |author-link=Joseph Mauborgne |date=1914 |title=An Advanced Problem in Cryptography and Its Solution |url= |location=Fort Leavenwoth, Kansas |publisher=Army Service Schools Press |page= |isbn=}}</ref> [[William Friedman]] described it in 1942 as providing very little security.<ref>{{cite book |url=https://www.nsa.gov/Portals/75/documents/news-features/declassified-documents/friedman-documents/publications/FOLDER_267/41784809082383.pdf |title=American Army Field Codes In the American Expeditionary Forces During The First World War |last=Friedman |first=William |author-link=William F. Friedman |date=June 1942 |publisher=U.S. War Department |access-date= |page=4}}</ref>

== Description ==
[[Image:Charles Wheatstone - Project Gutenberg etext 13103.jpg|thumbnail|left|The Playfair system was invented by [[Charles Wheatstone]], who first described it in 1854.]]
The Playfair cipher uses a 5 × 5 table containing a [[Key (cryptography)|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 (a modified [[Polybius square]]) 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 "J" or "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 digrams (groups of 2 letters) such that, for example, "HelloWorld" becomes "HE LL OW OR LD". These digrams will be substituted using the key table. Since encryption requires pairs of letters, messages with an odd number of characters usually append an uncommon letter, such as "X", to complete the final digram. The two letters of the digram are considered opposite corners of a rectangle in the key table. To perform the substitution, 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 letter, itself uncommon as a repeated pair, 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 two shift rules, selecting the letter to the left or upwards as appropriate. The last rule remains unchanged, as the transformation switches the selected letters of the rectangle to the opposite diagonal, and a repeat of the transformation returns the selection to its original state. The first rule can only be reversed by dropping any extra instances of the chosen insert letter — generally  "X"s or "Q"s — that do not make sense in the final message when finished.

There are several minor variations{{which|date=November 2022}} of the original Playfair cipher.<ref>{{harvnb|Gaines|1956|page=201}}</ref>

== Example ==
<!-- The images need to be shrunk by 20% to 50% to work at different screen sizes, using the image tag that specifies image size -->
Using "playfair example" as the key (assuming that I and J are interchangeable), the table becomes (omitted letters in red):

[[File:Playfair Cipher building grid omitted letters.png|frameless|upright=1.5]]

The first step of encrypting the message "hide the gold in the tree stump" is to convert it to the pairs of letters "HI DE TH EG OL DI NT HE TR EX ES TU MP" (with the null "X" used to separate the repeated "E"s). Then:

{| class="wikitable"
|-
| 1. The pair HI forms a rectangle, replace it with BM || [[File:Playfair Cipher 01 HI to BM.png|frameless|upright=1.5]]
|-
| 2. The pair DE is in a column, replace it with OD || [[File:Playfair Cipher 02 DE to OD.png|frameless|upright=1.5]]
|-
| 3. The pair TH forms a rectangle, replace it with ZB || [[File:Playfair Cipher 03 TH to ZB.png|frameless|upright=1.5]]
|-
| 4. The pair EG forms a rectangle, replace it with XD || [[File:Playfair Cipher 04 EG to XD.png|frameless|upright=1.5]]
|-
| 5. The pair OL forms a rectangle, replace it with NA || [[File:Playfair Cipher 05 OL to NA.png|frameless|upright=1.5]]
|-
| 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 || [[File:Playfair Cipher 10 EX to XD.png|frameless|upright=1.5]]
|-
| 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 ||
|}

Thus the message "hide the gold in the tree stump" becomes "BM OD ZB XD NA BE KU DM UI XM MO UV IF", which may be restructured as "BMODZ BXDNA BEKUD MUIXM MOUVI F" for ease of reading the cipher text.

== Clarification with picture ==
Assume one wants to encrypt the digram OR.  There are five general cases:
{| border="0" cellspacing="" cellpadding="0" style="border-collapse: collapse"
| width="10%" | 1)
 * * * * *
 * O Y R Z
 * * * * *
 * * * * *
 * * * * *

Hence, OR → YZ
| width="6%" |
| width="10%" | 2)
 * * O * *
 * * B * *
 * * * * *
 * * R * *
 * * Y * *

Hence, OR → BY
| width="6%" |
| width="10%" | 3)
 Z * * O *
 * * * * *
 * * * * *
 R * * X *
 * * * * *
Hence, OR → ZX
| width="6%" |
| width="10%" | 4)
 * * * * *
 * * * * *
 * O R W *
 * * * * *
 * * * * *
Hence, OR → RW
| width="6%" |
| width="10%" | 5)
 * * * * *
 * * R * *
 * * O * *
 * * I * *
 * * * * *
Hence, OR → IO
|}

== Cryptanalysis ==
Like most classical 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 [[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.<ref>{{harvnb|Gaines|1956|page=201}}</ref>

Cryptanalysis of Playfair is similar to that of [[four-square cipher|four-square]] and [[two-square cipher|two-square]] 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 [[Random-restart hill climbing|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 digrams 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 digram, e.g. EE.  If there are no double letter digrams 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. Another cryptanalysis of a Playfair cipher can be found in Chapter XXI of Helen Fouché Gaines' ''Cryptanalysis / a study of ciphers and their solutions''.<ref>{{harvnb|Gaines|1956|pages=198–207}}</ref>

A detailed cryptanalysis of Playfair is undertaken in chapter 28 of [[Dorothy L. Sayers]]' 1932 mystery novel ''[[Have His Carcase]]''. 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]] cipher as a medium-grade cipher in WWII, based on the British Playfair cipher they had broken early in WWI.<ref name="NCB">{{cite journal|doi=10.1080/02684528708431890|author=Currer-Briggs, Noel|title=Some of ultra's poor relations in Algeria, Tunisia, Sicily and Italy|journal=Intelligence and National Security|volume=2|number=2|pages=274–290|year = 1987}}</ref> 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]] messages, they were broken at [[Bletchley Park]]. Messages were preceded by a sequential number, and numbers were spelled 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 (magazine)#Crossword|''The Listener'' Crossword]] (published in the Saturday edition of the British newspaper ''[[The Times]]'') occasionally incorporate Playfair ciphers.<ref>[http://www.listenercrossword.com/List_Puzzles.html Listener crossword database]</ref> Normally between four and six 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 digrams (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 1932 novel ''[[Have His Carcase]]'' by [[Dorothy L. Sayers]] gives a blow-by-blow account of the cracking of a Playfair cipher.
*The 1940 World War 2 thriller ''[[The Trojan Horse (novel)|The Trojan Horse]]'' by [[Hammond Innes]] conceals the formula for a new high-strength metal alloy using the Playfair cipher.
*In the 2007 film ''[[National Treasure: Book of Secrets]]'', a treasure hunt clue is encoded as a Playfair cipher.
*In the 2007 audio book ''[[Rogue Angel]]:'' ''God of Thunder'', a Playfair cipher clue is used to send Anja Creed to Venice.
*In 2018 the serie [[Blindspot (TV series)]] season 4 episode 01 the cipher was mentioned during analysis of a clue.
*In the 2020 novel ''York: The Map of Stars'' (part three of a trilogy for children) by [[Laura Ruby]], a clue to solving the Morningstarr cipher is encrypted using the Playfair cipher.
* In 2021, the Playfair cipher serves as a plot device in a season 2 episode of [[Batwoman (TV series)]].
* In the 2013 novel ''[[S. (Dorst novel)|S.]]'', by [[Doug Dorst]] and conceived by [[J. J. Abrams]], a Playfair cipher is discovered in the footnotes of the story.

== See also ==
* [[Topics in cryptography]]

==Notes==
{{Reflist}}

==References==
* {{citation|first=Helen Fouché|last=Gaines|title=Cryptanalysis / a study of ciphers and their solutions|year=1956|orig-year=1939|publisher=Dover|isbn=0-486-20097-3|url-access=registration|url=https://archive.org/details/cryptanalysis00hele}}
* Smith, Michael ''Station X: The Codebreakers of Bletchley Park'' (1998, Channel 4 Books/Macmillan, London) {{ISBN|0-7522-2189-2}}
* {{citation|first=David|last=Kahn|title=The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet|year=1996|publisher=Scribner|isbn=978-0684831305}}

== External links ==
* [http://www.simonsingh.net/The_Black_Chamber/playfair_cipher.html Online encrypting and decrypting Playfair with JavaScript]
* [https://web.archive.org/web/20030212185742/http://www.wisdom.weizmann.ac.il/~albi/cryptanalysis/lect3.htm Extract from some lecture notes on ciphers – Digraphic Ciphers: Playfair]
* [http://rumkin.com/tools/cipher/playfair.php Playfair Cipher]
* [https://sourceforge.net/projects/cryptographytools/files/Playfair%20Cipher/ Cross platform implementation of Playfair cipher]
* [https://web.archive.org/web/20180110054602/http://kevinselwyn.com/fairplay/ Javascript implementation of the Playfair cipher]
* [https://share.streamlit.io/shameinew/pmath/streamlit-app/app.py Python and streamlit implementation of Playfair cipher]
{{Clear}}
{{Cryptography navbox | classical}}

[[Category:Classical ciphers]]
[[Category:English inventions]]