Editing Cryptanalysis (section)

===Classical ciphers===
[[Image:Al-kindi-cryptanalysis.png|thumb|right|First page of [[Al-Kindi]]'s 9th century ''Manuscript on Deciphering Cryptographic Messages.'']]
{{See also|Frequency analysis|Index of coincidence|Kasiski examination}}

Although the actual word "''cryptanalysis''" is relatively recent (it was coined by [[William Friedman]] in 1920), methods for breaking [[code (cryptography)|codes]] and [[cipher]]s are much older. [[David Kahn (writer)|David Kahn]] notes in ''[[The Codebreakers]]'' that [[Arab scholars]] were the first people to systematically document cryptanalytic methods.<ref>{{cite book|last1=Kahn|first1=David|title=The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet|date=1996|publisher=Simon and Schuster|isbn=9781439103555|url=https://books.google.com/books?id=3S8rhOEmDIIC&q=david+kahn+the+codebreakers}}</ref>

The first known recorded explanation of cryptanalysis was given by [[Al-Kindi]] (c. 801–873, also known as "Alkindus" in Europe), a 9th-century Arab [[polymath]],<ref>{{Cite book|url=https://books.google.com/books?id=3xJjNG5CNdwC&dq=Al+Kindi+Arab%2F&pg=PA199|title=History of Islamic Philosophy: With View of Greek Philosophy and Early History of Islam|first=I. M. N.|last=Al-Jubouri|date=February 22, 2004|publisher=Authors On Line Ltd|isbn=9780755210114|via=Google Books}}</ref><ref>{{Cite book|url=https://books.google.com/books?id=2wS2CAAAQBAJ&dq=al+kindi+Arab%2F&pg=PA279|title=The Biographical Encyclopedia of Islamic Philosophy|first=Oliver|last=Leaman|date=July 16, 2015|publisher=Bloomsbury Publishing|isbn=9781472569455|via=Google Books}}</ref> in ''Risalah fi Istikhraj al-Mu'amma'' (''A Manuscript on Deciphering Cryptographic Messages''). This treatise contains the first description of the method of [[frequency analysis]].<ref name=Kadi>Ibrahim A. Al-Kadi (April 1992), "The origins of cryptology: The Arab contributions", ''[[Cryptologia]]'' '''16''' (2): 97–126</ref> Al-Kindi is thus regarded as the first codebreaker in history.<ref name="Sahinaslan">{{cite journal |last1=Sahinaslan |first1=Ender |last2=Sahinaslan |first2=Onder |title=Cryptographic methods and development stages used throughout history |journal=AIP Conference Proceedings |date=2 April 2019 |volume=2086 |issue=1 |pages=030033 |doi=10.1063/1.5095118 |bibcode=2019AIPC.2086c0033S |issn=0094-243X |quote=Al-Kindi is considered the first code breaker|doi-access=free }}</ref> His breakthrough work was influenced by [[Al-Khalil ibn Ahmad al-Farahidi|Al-Khalil]] (717–786), who wrote the ''Book of Cryptographic Messages'', which contains the first use of [[wikt:permutation|permutations and combinations]] to list all possible [[Arabic language|Arabic]] words with and without vowels.<ref name="LB">{{cite journal|last=Broemeling|first=Lyle D.|title=An Account of Early Statistical Inference in Arab Cryptology|journal=The American Statistician|date=1 November 2011|volume=65|issue=4|pages=255–257|doi=10.1198/tas.2011.10191|s2cid=123537702}}</ref>

Frequency analysis is the basic tool for breaking most [[classical cipher]]s. In natural languages, certain letters of the [[alphabet]] appear more often than others; in [[English language|English]], "[[E]]" is likely to be the most common letter in any sample of [[plaintext]]. Similarly, the [[Digraph (orthography)|digraph]] "TH" is the most likely pair of letters in English, and so on. Frequency analysis relies on a cipher failing to hide these [[statistics]]. For example, in a [[simple substitution cipher]] (where each letter is simply replaced with another), the most frequent letter in the [[ciphertext]] would be a likely candidate for "E". Frequency analysis of such a cipher is therefore relatively easy, provided that the ciphertext is long enough to give a reasonably representative count of the letters of the alphabet that it contains.<ref>{{Harvnb|Singh|1999|p=17}}</ref>

Al-Kindi's invention of the frequency analysis technique for breaking monoalphabetic [[substitution cipher]]s<ref>{{cite book|url=https://books.google.com/books?id=2wS2CAAAQBAJ&q=al+kindi+Arab&pg=PA279|title=The Biographical Encyclopedia of Islamic Philosophy|first=Oliver|last=Leaman|date=16 July 2015|publisher=Bloomsbury Publishing|access-date=19 March 2018|via=Google Books|isbn=9781472569455}}</ref><ref>{{cite book|url=https://books.google.com/books?id=3xJjNG5CNdwC&q=Al+Kindi+Arab&pg=PA199|title=History of Islamic Philosophy: With View of Greek Philosophy and Early History of Islam|first=I. M. N.|last=Al-Jubouri|date=19 March 2018|publisher=Authors On Line Ltd|access-date=19 March 2018|via=Google Books|isbn=9780755210114}}</ref> was the most significant cryptanalytic advance until World War II. Al-Kindi's ''Risalah fi Istikhraj al-Mu'amma'' described the first cryptanalytic techniques, including some for [[polyalphabetic cipher]]s, cipher classification, Arabic phonetics and syntax, and most importantly, gave the first descriptions on frequency analysis.<ref>[[Simon Singh]], ''[[The Code Book]]'', pp. 14–20</ref> He also covered methods of encipherments, cryptanalysis of certain encipherments, and [[statistical analysis]] of letters and letter combinations in Arabic.<ref>{{cite web | url = http://www.muslimheritage.com/topics/default.cfm?ArticleID=372 | title = Al-Kindi, Cryptgraphy<!--sic?-->, Codebreaking and Ciphers | access-date = 12 January 2007 | archive-date = 5 February 2014 | archive-url = https://web.archive.org/web/20140205102439/http://www.muslimheritage.com/topics/default.cfm?ArticleID=372 | url-status = dead }}</ref><ref name=Kadi/> An important contribution of [[Ibn Adlan]] (1187–1268) was on [[sample size]] for use of frequency analysis.<ref name="LB"/>

In Europe, [[Italy|Italian]] scholar [[Giambattista della Porta]] (1535–1615) was the author of a seminal work on cryptanalysis, ''[[De Furtivis Literarum Notis]]''.<ref>{{Cite web|url=http://www.cryptool.org/content/view/28/54/lang,english/|archiveurl=https://web.archive.org/web/20080828190150/http://www.cryptool.org/content/view/28/54/lang%2Cenglish/|url-status=dead|title=Crypto History|archivedate=August 28, 2008}}</ref>

Successful cryptanalysis has undoubtedly influenced history; the ability to read the presumed-secret thoughts and plans of others can be a decisive advantage. For example, in England in 1587, [[Mary, Queen of Scots]] was tried and executed for [[treason]] as a result of her involvement in three plots to assassinate [[Elizabeth I of England]]. The plans came to light after her coded correspondence with fellow conspirators was deciphered by [[Thomas Phelippes]].

In Europe during the 15th and 16th centuries, the idea of a [[Polyalphabetic cipher|polyalphabetic substitution cipher]] was developed, among others by the French diplomat [[Blaise de Vigenère]] (1523–96).<ref>{{Harvnb|Singh|1999|pp=45–51}}</ref> For some three centuries, the [[Vigenère cipher]], which uses a repeating key to select different encryption alphabets in rotation, was considered to be completely secure (''le chiffre indéchiffrable''—"the indecipherable cipher"). Nevertheless, [[Charles Babbage]] (1791–1871) and later, independently, [[Friedrich Kasiski]] (1805–81) succeeded in breaking this cipher.<ref>{{Harvnb|Singh|1999|pp=63–78}}</ref> During [[World War I]], inventors in several countries developed [[rotor cipher machine]]s such as [[Arthur Scherbius]]' [[Enigma machine|Enigma]], in an attempt to minimise the repetition that had been exploited to break the Vigenère system.<ref>{{Harvnb|Singh|1999|p=116}}</ref>