플레이페어 암호

Playfair cipher
Wadsworth의 암호와 혼동하지 않기 위해서입니다.
Playfair 암호는 5×5 그리드의 문자를 사용하며, 문자를 쌍으로 쪼개어 그 그리드 내의 직사각형에서 위치에 따라 교환함으로써 메시지를 암호화한다: "HI"는 "BM"이 된다.
플레이페어 시스템은 찰스 휘트스톤에 의해 발명되었는데, 그는 1854년에 처음으로 그것을 묘사했다.

플레이페어 암호 또는 플레이페어 사각형 또는 휘트스톤-플레이페어 암호는 수동 대칭 암호화 기법으로, 최초의 문자 그대로 디그람 대체 암호였다. 이 계획은 찰스 휘트스톤에 의해 1854년에 발명되었지만, 사용을 장려하기 위해 플레이페어 경이라는 이름이 붙어 있다.

이 기술은 단순한 대체 암호와 다소 복잡한 Vigener 암호 시스템에서와 같이 문자 쌍(빅그램 또는 디그람)을 암호화한다. 따라서 플레이페어는 단순한 대체 암호에 사용되는 주파수 분석이 그것과 함께 작동하지 않기 때문에 깨뜨리기가 상당히 어렵다. 빅그램의 주파수 분석은 가능하지만 상당히 더 어렵다. 26개의 가능한 모노그램(단일 기호, 대개 이 맥락에서 문자)이 아닌 600개의[1] 가능한 빅그램으로, 유용하기 위해서는 상당히 큰 암호문이 필요하다.

역사

플레이페어 경, 그 사용을 크게 홍보한 사람.

플레이페어 암호는 암호역사에서 문자 쌍을 암호화한 최초의 암호였다.[2][3] 휘트스톤은 전보에서 비밀을 위해 암호를 발명했지만, 그것은 그의 친구인 세인트의 남작 플레이페어 경의 이름을 가지고 있다. 앤드류스는 그 사용을 홍보했다.[3][4][5] 플레이페어 암호에 대한 최초의 기록은 1854년 3월 26일 휘트스톤이 서명한 문서에 있었다.

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."[6]

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.[4][5] 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 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.[7]

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.[8][9] Coastwatchers established by Royal Australian Navy Intelligence also used this cipher.[10]

Superseded

Playfair is no longer used by military forces because of the advent of digital encryption devices. This cipher is now regarded as insecure for any purpose, because modern computers could easily break it within microseconds.

The first published solution of the Playfair cipher was described in a 19-page pamphlet by Lieutenant Joseph O. Mauborgne, published in 1914.[11]

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

메시지를 암호화하려면 메시지를 digram(두 글자의 그룹)으로 구분하여 예를 들어 "HE LL OW OW 또는 LD"가 된다. 이 digram들은 키 테이블을 사용하여 대체될 것이다. 암호화는 한 쌍의 문자를 필요로 하기 때문에 문자 수가 홀수인 메시지는 보통 "X"와 같은 흔치 않은 문자를 추가하여 최종 디그람을 완성한다. 디그람의 두 글자는 키 테이블에서 사각형의 반대쪽 모서리로 간주된다. 대체를 수행하려면 일반 텍스트의 각 문자 쌍에 다음 4가지 규칙을 순서대로 적용하십시오.

  1. 두 문자가 같은 경우(또는 한 글자만 남은 경우) 첫 번째 문자 뒤에 "X"를 추가하십시오. 새 쌍을 암호화하고 계속하십시오. 플레이페어의 일부 변형에서는 "X" 대신 "Q"를 사용하지만, 그 자체로 반복된 쌍처럼 흔하지 않은 어떤 문자도 사용할 수 있을 것이다.
  2. 문자가 테이블의 같은 행에 나타나면, 각각 바로 오른쪽에 있는 문자로 대체하십시오(원래 쌍의 문자가 행 오른쪽에 있는 경우 행의 왼쪽을 감싼다).
  3. 문자가 테이블의 같은 열에 나타나는 경우, 각각 아래의 문자로 대체하십시오(원래 쌍의 문자가 열의 맨 아래에 있는 경우 열의 맨 위로 감싸기).
  4. 문자가 같은 행이나 열에 없으면 각각 같은 행에 있는 문자로 교체하되, 원래 쌍으로 정의된 사각형의 다른 한 쌍의 모서리에 있는 문자로 교체하십시오. 순서가 중요하다 – 암호화된 쌍의 첫 글자는 일반 텍스트 쌍의 첫 글자와 같은 행에 놓여 있는 글자다.

암호를 해독하려면 마지막 세 가지 규칙의 역(반대)과 첫 번째 현재(완료 시 최종 메시지에서 이치에 맞지 않는 추가 "X" 또는 "Q"를 삭제)를 사용하십시오.

원래의 플레이페어 암호에는 몇 가지 사소한 변형이 있다.[12]

예

키로 "playfair example"을 사용(I와 J가 상호 호환된다고 가정)하면 테이블이 된다(빨간색으로 입력됨).

Playfair Cipher building grid omitted letters.png

"나무 그루터기에 금을 숨기다"라는 메시지를 암호화한 첫 번째 단계는 문자 쌍으로 변환하는 것이다.HI DE TH EG OL DI NT HE TR EX ES TU MP(반복된 "E"를 분리하는 데 null "X"가 사용됨). 다음:

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

1) 
* * * * * * O Y R Z * * * * * * * * * * * * * * *

Hence, OR → YZ

2) 
* * O * * * * B * * * * * * * * * R * * * * Y * *

Hence, OR → BY

3) 
Z * * O * * * * * * * * * * * R * * X * * * * * *

Hence, OR → ZX

4) 
* * * * * * * * * * * O R C * * * * * * * * * * *

Hence, OR → RC

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.[13]

Cryptanalysis of Playfair is similar to that of four-square and 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 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.[14]

A detailed cryptanalysis of Playfair is undertaken in chapter 28 of Dorothy L. Sayers' 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.[15] 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 Crossword (published in the Saturday edition of the British newspaper The Times) occasionally incorporate Playfair ciphers.[16] 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 novel Have His Carcase by Dorothy L. Sayers gives a blow-by-blow account of the cracking of a Playfair cipher.
  • The World War 2 thriller The Trojan Horse by Hammond Innes conceals the formula for a new high-strength metal alloy using the Playfair cipher.
  • In the film National Treasure: Book of Secrets, a treasure hunt clue is encoded as a Playfair cipher.
  • In the audio book Rogue Angel : God of Thunder, a Playfair cipher clue is used to send Anja Creed to Venice.
  • In the 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.
  • The Playfair cipher serves as a plot device in a season 2 episode of the 2019 Batwoman (TV series).
  • In the novel The Sinclair Betrayal by M J Lee, a character who is preparing to drop into France during WW2 is taught the three types of ciphers: double transposition, Playfair, and Ironside.

See also

Notes

  1. ^ No duplicate letters are allowed, and one letter is omitted (Q) or combined (I/J), so the calculation is 600 = 25×24.
  2. ^ Cohen, Fred. "A Short History of Cryptography". Introductory Information Protection. Retrieved 9 January 2018.
  3. ^ a b Christensen, Chris (2006). "Polygraphic Ciphers" (PDF). Northern Kentucky University, Chris Christensen. Retrieved January 9, 2018.
  4. ^ a b Kahn, David (1996). The Codebreakers: The comprehensive history of secret communi cation from ancient times to the internet. Scribner. ISBN 978-0684831305.
  5. ^ a b Klima, Rick (2018). "Secret Codes Through World War II" (PDF). Appalachian State University, Dr. Rick Klima.
  6. ^ Reid, Thomas Wemyss (1899). Memoirs and Correspondence of Lyon Playfair: First Lord Playfair of St. Andrews ... Harper & Brothers. pp. 158–159.
  7. ^ Lord, Walter (2012). Lonely Vigil: Coastwatchers of the Solomons. Open Road Media. Kindle Edition. p. 6.
  8. ^ "A History of Communications Security in New Zealand By Eric Mogon", Chapter 8
  9. ^ "The History of Information Assurance (IA)". Government Communications Security Bureau. New Zealand Government. Archived from the original on 2011-11-12. Retrieved 2011-12-24.
  10. ^ Lord, Walter (2012). Lonely Vigil: Coastwatchers of the Solomons. Open Road Media. Kindle Edition. p. 6.
  11. ^ Mauborgne, Joseph Oswald, An Advanced Problem in Cryptography and Its Solution (Fort Leavenwoth, Kansas: Army Service Schools Press, 1914).
  12. ^ Gaines 1956, p. 201
  13. ^ Gaines 1956, p. 201
  14. ^ Gaines 1956, pp. 198–207
  15. ^ Currer-Briggs, Noel (1987). "Some of ultra's poor relations in Algeria, Tunisia, Sicily and Italy". Intelligence and National Security. 2 (2): 274–290. doi:10.1080/02684528708431890.
  16. ^ Listener crossword database

References

External links