Editing Frequency analysis

{{short description|Study of the frequency of letters or groups of letters in a ciphertext}}
{{Other uses|Frequency analysis (disambiguation)}}

[[File:English letter frequency (alphabetic).svg|right|340px|thumbnail|A typical distribution of letters in [[English language]] text. Weak ciphers do not sufficiently mask the distribution, and this might be exploited by a cryptanalyst to read the message.]]

In [[cryptanalysis]], '''frequency analysis''' (also known as '''counting letters''') is the study of the [[letter frequencies|frequency of letters]] or groups of letters in a [[ciphertext]]. The method is used as an aid to breaking [[classical cipher]]s.

Frequency analysis is based on the fact that, in any given stretch of written language, certain letters and combinations of letters occur with varying frequencies. Moreover, there is a characteristic distribution of letters that is roughly the same for almost all samples of that language. For instance, given a section of [[English language]], {{samp|E}}, {{samp|T}}, {{samp|A}} and {{samp|O}} are the most common, while {{samp|Z}}, {{samp|Q}}, {{samp|X}} and {{samp|J}} are rare. Likewise, {{samp|TH}}, {{samp|ER}}, {{samp|ON}}, and {{samp|AN}} are the most common pairs of letters (termed ''[[bigram]]s'' or ''digraphs''), and {{samp|SS}}, {{samp|EE}}, {{samp|TT}}, and {{samp|FF}} are the most common repeats.<ref>{{ Cite web | last = Singh | first = Simon | author-link = Simon Singh | title = The Black Chamber: Hints and Tips | url = http://www.simonsingh.net/The_Black_Chamber/hintsandtips.html | access-date = 26 October 2010 }}</ref> The nonsense phrase "[[ETAOIN SHRDLU]]" represents the 12 most frequent letters in typical English language text.

In some ciphers, such properties of the natural language plaintext are preserved in the ciphertext, and these patterns have the potential to be exploited in a [[ciphertext-only attack]].

== Frequency analysis for simple substitution ciphers ==
In a simple [[substitution cipher]], each letter of the [[plaintext]] is replaced with another, and any particular letter in the plaintext will always be transformed into the same letter in the ciphertext. For instance, if all occurrences of the letter {{samp|e}} turn into the letter {{samp|X}}, a ciphertext message containing numerous instances of the letter {{samp|X}} would suggest to a cryptanalyst that {{samp|X}} represents {{samp|e}}.

The basic use of frequency analysis is to first count the frequency of ciphertext letters and then associate guessed plaintext letters with them. More {{samp|X}}s in the ciphertext than anything else suggests that {{samp|X}} corresponds to {{samp|e}} in the plaintext, but this is not certain; {{samp|t}} and {{samp|a}} are also very common in English, so {{samp|X}} might be either of them. It is unlikely to be a plaintext {{samp|z}} or {{samp|q}}, which are less common. Thus the cryptanalyst may need to try several combinations of mappings between ciphertext and plaintext letters.

More complex use of statistics can be conceived, such as considering counts of pairs of letters (''bigrams''), triplets (''trigrams''), and so on. This is done to provide more information to the cryptanalyst, for instance, {{samp|Q}} and {{samp|U}} nearly always occur together in that order in English, even though {{samp|Q}} itself is rare.

=== An example ===

<!-- decryption alphabet
ABCDEFGHIJKLMNOPQRSTUVWXYZ
kxpqaycdefbhijvlwsouzrntgm
-->
Suppose [[Alice and Bob|Eve]] has intercepted the [[cryptogram]] below, and it is known to be encrypted using a simple substitution cipher:     
 {{not a typo|LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM
 WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ
 GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV
 IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE
 PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP
 XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX}}
For this example, uppercase letters are used to denote ciphertext, lowercase letters are used to denote plaintext (or guesses at such), and {{samp|X}}~{{samp|t}} is used to express a guess that ciphertext letter {{samp|X}} represents the plaintext letter {{samp|t}}.

Eve could use frequency analysis to help solve the message along the following lines: counts of the letters in the cryptogram show that {{samp|I}} is the most common single letter,<ref>{{Cite web |url=http://www.asecuritysite.com/security/Challenges/scramb |title=A worked example of the method from bill's "A security site.com" |access-date=2012-12-31 |archive-url=https://web.archive.org/web/20131020173206/http://www.asecuritysite.com/security/Challenges/scramb |archive-date=2013-10-20 |url-status=dead }}</ref> {{samp|XL}} most common [[bigram]], and {{samp|XLI}} is the most common [[trigram]]. {{samp|e}} is the most common letter in the English language, {{samp|th}} is the most common bigram, and {{samp|the}} is the most common trigram. This strongly suggests that {{samp|X}}~{{samp|t}}, {{samp|L}}~{{samp|h}} and  {{samp|I}}~{{samp|e}}. The second most common letter in the cryptogram is {{samp|E}}; since the first and second most frequent letters in the English language, {{samp|e}} and {{samp|t}} are accounted for, Eve guesses that {{samp|E}}~{{samp|a}}, the third most frequent letter. Tentatively making these assumptions, the following partial decrypted message is obtained.

 {{not a typo|heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM
 WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ
 GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV
 eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha
 PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP
 thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt}}

Using these initial guesses, Eve can spot patterns that confirm her choices, such as "{{samp|that}}". Moreover, other patterns suggest further guesses. "{{samp|Rtate}}" might be "{{samp|state}}", which would mean {{samp|R}}~{{samp|s}}. Similarly "{{samp|atthattMZe}}" could be guessed as "{{samp|atthattime}}", yielding {{samp|M}}~{{samp|i}} and {{samp|Z}}~{{samp|m}}. Furthermore, "{{samp|heVe}}" might be "{{samp|here}}", giving {{samp|V}}~{{samp|r}}. Filling in these guesses, Eve gets:

 {{not a typo|hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei
 WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ
 GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr
 emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha
 PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP
 thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit}}

In turn, these guesses suggest still others (for example, "{{samp|remarA}}" could be "{{samp|remark}}", implying {{samp|A}}~{{samp|k}}) and so on, and it is relatively straightforward to deduce the rest of the letters, eventually yielding the plaintext.

 {{not a typo|hereuponlegrandarosewithagraveandstatelyairandbroughtmethebeetlefromaglasscasei
 nwhichitwasencloseditwasabeautifulscarabaeusandatthattimeunknowntonaturalistsof
 courseagreatprizeinascientificpointofviewthereweretworoundblackspotsnearoneextr
 emityofthebackandalongoneneartheotherthescaleswereexceedinglyhardandglossywitha
 lltheappearanceofburnishedgoldtheweightoftheinsectwasveryremarkableandtakingall
 thingsintoconsiderationicouldhardlyblamejupiterforhisopinionrespectingit}}

At this point, it would be a good idea for Eve to insert spaces and punctuation:

 Hereupon Legrand arose, with a grave and stately air, and brought me the beetle
 from a glass case in which it was enclosed. It was a beautiful scarabaeus, and, at
 that time, unknown to naturalists&mdash;of course a great prize in a scientific point
 of view. There were two round black spots near one extremity of the back, and a
 long one near the other. The scales were exceedingly hard and glossy, with all the
 appearance of burnished gold. The weight of the insect was very remarkable, and,
 taking all things into consideration, I could hardly blame Jupiter for his opinion
 respecting it.

In this example from "[[The Gold-Bug]]", Eve's guesses were all correct. This would not always be the case, however; the variation in statistics for individual plaintexts can mean that initial guesses are incorrect. It may be necessary to [[backtracking|backtrack]] incorrect guesses or to analyze the available statistics in much more depth than the somewhat simplified justifications given in the above example.

It is possible that the plaintext does not exhibit the expected distribution of letter frequencies. Shorter messages are likely to show more variation. It is also possible to construct artificially skewed texts. For example, entire novels have been written that omit the letter {{samp|e}} altogether &mdash; a form of literature known as a [[lipogram]].

== History and usage ==
[[File:Al-kindi-cryptanalysis.png|thumb|right|First page of [[Al-Kindi]]'s 9th century ''Manuscript on Deciphering Cryptographic Messages'']]

[[File:HurufUNCsort.png|thumb|right|[[Arabic Letter Frequency]] distribution]]

The first known recorded explanation of frequency analysis (indeed, of any kind of cryptanalysis) was given in the 9th century by [[Al-Kindi]], an [[Arab]] [[polymath]], in ''A Manuscript on Deciphering Cryptographic Messages''.<ref>[[Al-Kindi|Ibrahim A. Al-Kadi]] "The origins of cryptology: The Arab contributions", ''[[Cryptologia]]'', 16(2) (April 1992) pp. 97&ndash;126.</ref> It has been suggested that a close textual study of the [[Qur'an]] first brought to light that [[Arabic language|Arabic]] has a characteristic letter frequency.<ref>{{cite web|title=In Our Time: Cryptography|url=http://www.bbc.co.uk/programmes/p004y272|publisher=BBC Radio 4|access-date=29 April 2012}}</ref> Its use spread, and similar systems were widely used in European states by the time of the [[Renaissance]]. By 1474, [[Cicco Simonetta]] had written a manual on deciphering encryptions of [[Latin language|Latin]] and [[Italian language|Italian]] text.<ref name="isbn0-684-83130-9">{{ Cite book | last = Kahn | first = David L. | author-link = David Kahn (writer) | title = The codebreakers: the story of secret writing | publisher = Scribner | year=1996 | location = New York | isbn = 0-684-83130-9 }}</ref>

Several schemes were invented by cryptographers to defeat this weakness in simple substitution encryptions. These included:

* ''[[Homophonic substitution cipher|Homophonic substitution]]'': Use of ''homophones'' &mdash; several alternatives to the most common letters in otherwise monoalphabetic substitution ciphers. For example, for English, both X and Y ciphertext might mean plaintext E.
* ''[[Polyalphabetic cipher|Polyalphabetic substitution]]'', that is, the use of several alphabets &mdash; chosen in assorted, more or less devious, ways ([[Leone Alberti]] seems to have been the first to propose this); and
* ''[[Polygraphic substitution]]'', schemes where pairs or triplets of plaintext letters are treated as units for substitution, rather than single letters, for example, the [[Playfair cipher]] invented by [[Charles Wheatstone]] in the mid-19th century.

A disadvantage of all these attempts to defeat frequency counting attacks is that it increases complication of both enciphering and deciphering, leading to mistakes. Famously, a British Foreign Secretary is said to have rejected the Playfair cipher because, even if school boys could cope successfully as Wheatstone and Playfair had shown, "our attachés could never learn it!".

The [[rotor machine]]s of the first half of the 20th century (for example, the [[Enigma machine]]) were essentially immune to straightforward frequency analysis.
However, other kinds of analysis ("attacks") successfully decoded messages from some of those machines.<ref>{{Cite journal |last1=Kruh |first1=Louis |last2=Deavours |first2=Cipher |title=The Commercial Enigma: Beginnings of Machine Cryptography |date=January 2002 |url=http://www.tandfonline.com/doi/abs/10.1080/0161-110291890731 |journal=Cryptologia |language=en |volume=26 |issue=1 |pages=1–16 |doi=10.1080/0161-110291890731 |s2cid=41446859 |issn=0161-1194}}</ref>

[[File:Frecuencia de uso de letras en español.PNG|thumb|Letter frequency in Spanish]]
Frequency analysis requires only a basic understanding of the statistics of the plaintext language and some problem-solving skills, and, if performed by hand, tolerance for extensive letter bookkeeping. During [[World War II]], both the [[United Kingdom|British]] and the [[United States|Americans]] recruited codebreakers by placing [[crossword]] puzzles in major newspapers and running contests for who could solve them the fastest. Several of the ciphers used by the [[Axis powers]] were breakable using frequency analysis, for example, some of the consular ciphers used by the Japanese. Mechanical methods of letter counting and statistical analysis (generally [[IBM]] card type machinery) were first used in World War II, possibly by the US Army's [[Signals Intelligence Service|SIS]]. Today, the work of letter counting and analysis is done by [[computer]] [[software]], which can carry out such analysis in seconds. With modern computing power, classical ciphers are unlikely to provide any real protection for confidential data.

== Frequency analysis in fiction ==
[[File:Dancing men.svg|thumb|right|Part of the cryptogram in ''The Dancing Men'']]
Frequency analysis has been described in fiction. [[Edgar Allan Poe]]'s "[[The Gold-Bug]]" and [[Arthur Conan Doyle|Sir Arthur Conan Doyle's]] [[Sherlock Holmes]] tale "[[The Adventure of the Dancing Men]]" are examples of stories which describe the use of frequency analysis to attack simple substitution ciphers. The cipher in the Poe story is encrusted with several deception measures, but this is more a literary device than anything significant cryptographically.

==See also==
* [[Index of coincidence]]
* [[Topics in cryptography]]
* [[Zipf's law]]
* [[A Void]], a novel by [[Georges Perec]]. The original French text is written without the letter ''e'', as is the English translation. The Spanish version contains no ''a''.
* [[Gadsby (novel)]], a novel by [[Ernest Vincent Wright]]. The novel is written as a [[lipogram]], which does not include words that contain the letter E.

== Further reading ==
* Helen Fouché Gaines, "Cryptanalysis", 1939, Dover. {{ISBN|0-486-20097-3}}.
* [[Abraham Sinkov]], "Elementary Cryptanalysis: A Mathematical Approach", The Mathematical Association of America, 1966. {{ISBN|0-88385-622-0}}.

== References ==
<references/>

==External links==
* [https://www.dcode.fr/frequency-analysis Online frequency analysis tool]
* [https://www.sttmedia.com/characterfrequencies Character] and [https://www.sttmedia.com/syllablefrequencies syllable] frequencies of 41 languages and a portable tool to create frequency and syllable distributions
* [https://www.intellaren.com/articles/en/a-study-of-arabic-letter-frequency-analysis Arabic letter frequency analysis]
* [https://web.archive.org/web/20040603075055/http://www.data-compression.com/english.html Conditional probabilities for characters in English text]
* [https://web.archive.org/web/20141014173341/http://nlp.fi.muni.cz/web3/cs/FrekvencePismenBigramu Czech letter/bigram/trigram frequency]

{{Cryptography navbox | classical}}

{{DEFAULTSORT:Frequency Analysis}}
[[Category:Cryptographic attacks]]
[[Category:Frequency distribution]]
[[Category:Arab inventions]]
[[Category:Quantitative linguistics]]