NationMaster - Encyclopedia: Frequency analysis

In mathematics, physics and signal processing, frequency analysis is a method to decompose a function, wave, or signal into its frequency components so that it is possible to have the frequency spectrum. Wikibooks Wikiversity has more about this subject: School of Mathematics Wikiquote has a collection of quotations related to: Mathematics Look up Mathematics on Wiktionary, the free dictionary Wikimedia Commons has more media related to: Mathematics Bogomolny, Alexander: Interactive Mathematics Miscellany and Puzzles. ... Since antiquity, people have tried to understand the behavior of matter: why unsupported objects drop to the ground, why different materials have different properties, and so forth. ... Signal processing is the processing, amplification and interpretation of signals. ... In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique element of another (possibly the same) set (the codomain, not to be confused with the range). ... A wave is a disturbance that propagates, carrying energy. ... Signaling, or signal, may mean: Look up signal in Wiktionary, the free dictionary. ... In mathematics, physics and signal processing, the frequency spectrum is a representation of a signal or other function in terms of frequency (in the frequency domain). It is the projection of the function onto a set of sinusoidal basis functions. ...

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. English single letter frequencies. ... English single letter frequencies. ... The English language is a West Germanic language that originates in England. ... Cryptanalysis (from the Greek kryptÃ³s, hidden, and analÃ½ein, to loosen or to untie) is the study of methods for obtaining the meaning of encrypted information without access to the secret information which is normally required to do so. ... The frequency of letters in text messages has often been studied for use in cryptography, and frequency analysis in particular. ... This article is about algorithms for encryption and decryption. ... In cryptography, a classical cipher is a type of cipher used historically but which now have fallen, for the most part, into disuse. ...

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, E tends to be very common, while X is very rare. Likewise, ST, NG, TH, and QU are common pairs of letters (termed bigrams or digraphs), while NZ and QJ are rare. The mnemonic phrase "ETAOIN SHRDLU" encodes the 12 most frequent letters in typical English language text. The English language is a West Germanic language that originates in England. ... Bigrams are groups of two written letters, two syllables, or two words, and are very commonly used as the basis for simple statistical analysis of text; one of the most successful language models for Speech Recognition (Collins, 1996). ... ETAOIN SHRDLU is the approximate order of frequency of the twelve most commonly used letters in the English language. ...

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. In cryptography, a ciphertext-only attack is a form of cryptanalysis where the attacker is assumed to have access only to a set of ciphertexts. ...

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, all e's will turn into X's. A ciphertext message containing lots of X's would suggest to a cryptanalyst that X represented e. In cryptography, a substitution cipher is a method of encryption by which units of plaintext are substituted with ciphertext according to a regular system; the units may be single letters (the most common), pairs of letters, triplets of letters, mixtures of the above, and so forth. ... The plain text term has shit a different meaning. ...

The basic use of frequency analysis is to first count the frequency of ciphertext letters and then associate guessed plaintext letters with them. More X's in the ciphertext than anything else suggests that X corresponds to e in the plaintext, but this is not certain; t and a are also very common in English, so X might be either of them also. It is unlikely to be a plaintext z or 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, or triplets (trigrams), and so on. This is done to provide more information to the cryptanalyst, for instance, Q and U nearly always occur together in that order in English, even though Q itself is rare.

An example

Suppose Eve has intercepted the cryptogram below, and it is known to be encrypted using a simple substitution cipher: A cryptogram is a type of word puzzle popularly printed in some newspapers and magazines. ...

For this example, uppercase letters are used to denote ciphertext, lowercase letters are used to denote plaintext (or guesses at such), and X~t is used to express a guess that ciphertext letter X represents the plaintext letter t.

Eve could use frequency analysis to help solve the message along the following lines: counts of the letters in the cryptogram show that I is the most common single letter, XL most common bigram, and XLI is the most common trigram. e is the most common letter in the English language, th is the most common bigram, and the the most common trigram. This strongly suggests that X~t, L~h and I~e. The second most common letter in the cryptogram is E; since the first and second most frequent letters in the English language, e and t are accounted for, Eve guesses that E~a, the third most frequent letter. Tentatively making these assumptions, the following partial decrypted message is obtained.

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

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

In this example, 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 backtrack incorrect guesses or to analyse the available statistics in much more depth than the somewhat simplified justifications given in the above example. Backtracking is a strategy for finding solutions to constraint satisfaction problems. ...

It is also 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 "e" altogether — a form of literature known as a lipogram. A lipogram (from Greek lipagrammatos, missing letter) is a kind of writing with constraints or word game consisting of writing paragraphs or longer works in which a particular letter or group of letters is missing, usually a common vowel, the most common in English being e (McArthur, 1992). ...

History and usage

The first known recorded explanation of frequency analysis (indeed, of any kind of cryptanalysis) was given by 9th century Arab polymath Abu Yusuf Yaqub ibn Ishaq al-Sabbah Al-Kindi in A Manuscript on Deciphering Cryptographic Messages (Ibraham, 1992). It has been suggested that close textual study of the Qur'an first brought to light that Arabic has a characteristic letter frequency. Its use spread, and was so widely used by European states by the Renaissance that several schemes were invented by cryptographers to defeat it. These included The first page of al-Kindis manuscript On Deciphering Cryptographic Messages, containing the oldest known description of cryptanalysis by frequency analysis. ... The first page of al-Kindis manuscript On Deciphering Cryptographic Messages, containing the oldest known description of cryptanalysis by frequency analysis. ... Abū-Yūsuf Ya’qūb ibn Ishāq al-Kindī (c. ... This earthenware dish was made in 9th century Iraq. ... The Arabs (Arabic: Ø¹Ø±Ø¨ Ê»arab) are an originally Arabian ethnicity widespread in the Middle East and North Africa. ... Leonardo da Vinci A polymath (also known as a polyhistor) is a person who excels in multiple fields, particularly in both arts and sciences. ... Al-Kindi (Arabic: أبو يعقوب يوسف بن إسحاق الكندي) was a Arabn philosopher, scientist and ophthalmologist. ... The Quran (Arabic: al-qurÄn literally the recitation; also called Al QurÄn Al KarÄ«m or The Noble Quran; or transliterated Quran, Koran, and less commonly Alcoran) is the holy book of Islam. ... Arabic (Ø§Ù„Ø¹Ø±Ø¨ÙŠØ© al-arabiyyah, or less formally arabi) is the largest member of the Semitic branch of the Afro-Asiatic language family (classification: South Central Semitic) and is closely related to Hebrew and Aramaic. ...

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 attaches could never learn it!'. A polyalphabetic cipher is any cipher based on substitution, using multiple substitution alphabets. ... Leone Battista Alberti (February 1404 - 25th April 1472), Italian painter, poet, linguist, philosopher, cryptographer, musician, architect, and general Renaissance polymath . ... The Playfair system was invented by Charles Wheatstone, first described in 1854. ... Sir Charles Wheatstone (February 6, 1802 - October 19, 1875) was the British inventor of many innovations including the English concertina the Stereoscope an early form of microphone the Playfair cipher (named for Lord Playfair, the person who publicized it) and the Wheatstone bridge. ...

The rotor machines 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. In cryptography, a rotor machine is a electro-mechanical device used for encrypting and decrypting secret messages. ... In the history of cryptography, the Enigma was a portable cipher machine used to encrypt and decrypt secret messages. ...

Frequency analysis requires only a basic understanding of the statistics of the plaintext language and some problem solving skills, and, if performed by hand, some tolerance for extensive letter bookkeeping. During World War II (WWII), both the British and the 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 WWII, possibly by the US Army's SIS. There are lurid tales of midnight expeditions by the cryptographers to machines in another Department. Today, the hard work of letter counting and analysis has been replaced by computer software, which can carry out such analyses in seconds. With modern computing power, classical ciphers are unlikely to provide any real protection for confidential data. World War II was a truly global conflict with many facets: immense human suffering, fierce indoctrinations, and the use of new, extremely devastating weapons like the atom bomb World War II, also known as the Second World War, was a mid-20th-century conflict that engulfed much of the globe... The crossword is the most common variety of word puzzle in the world. ... This article needs to be cleaned up to conform to a higher standard of quality. ... The Signals Intelligence Service (SIS) was the Armys codebreaking division. ... A computer is a device or machine for processing information according to a program â€” a compiled list of instructions. ... Computer software (or simply software) refers to one or more computer programs and data held in the storage of a computer for some purpose. ...

Frequency analysis in fiction

Frequency analysis has been described in fiction. Edgar Allan Poe's The Gold Bug, and 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. From The Adventure of the Dancing Men Sherlock Holmes story. ... This daguerreotype of Poe was taken less than a year before his death at the age of 40. ... The Gold Bug is a short story by one of the masters of the genre, Edgar Allan Poe. ... Arthur Conan Doyle Sir Arthur Ignatius Conan Doyle (May 22, 1859 â€“ July 7, 1930) is the British author most famously known for his stories about the detective Sherlock Holmes, which are generally considered a major innovation in the field of crime fiction. ... Sherlock Holmes Sherlock Holmes (1854-1957, according to William S. Baring-Gould) is a fictional detective of the late 19th and early 20th centuries, created by British author and physician Sir Arthur Conan Doyle. ... The Adventure of the Dancing Men, one of the 56 Sherlock Holmes short stories written by British author Sir Arthur Conan Doyle, is one of 13 stories in the cycle collected as The Return of Sherlock Holmes. ...

See also

ETAOIN SHRDLU is the approximate order of frequency of the twelve most commonly used letters in the English language. ... This article is intended to be an analytic glossary, or alternatively, an organized collection of annotated pointers. ... This article may be too technical for most readers to understand. ...

References

External links

Categories: Cryptography In cryptography, the ADFGVX cipher was a field cipher used by the German Army during World War I. ADFGVX was in fact an extension of an earlier cipher called ADFGX. Invented by Colonel Fritz Nebel and introduced in March 1918, the cipher was a fractionating transposition cipher which combined a... The Affine cipher is a special case of the more general substitution cipher. ... Atbash is a simple substitution cipher for the Hebrew alphabet. ... An autokey cipher, or self-synchronizing stream cipher, is a cipher which incorporates the message (the plaintext) into the key. ... In classical cryptography, the bifid cipher is a cipher which combines the Polybius square with transposition, and uses fractionation to achieve diffusion. ... A book cipher is a cipher in which the key is the identity of a book. ... The action of a Caesar cipher is to move each letter a number of places down the alphabet. ... The Four-square cipher is a manual symmetric encryption technique. ... Hills cipher machine, from figure 4 of the patent In classical cryptography, the Hill cipher is a polygraphic substitution cipher based on linear algebra. ... In classical cryptography, a permutation cipher is a transposition cipher in which the key is a permutation. ... The Pigpen Cipher is a simple substitution cipher exchanging letters for symbols, using a grid. ... The Playfair system was invented by Charles Wheatstone, first described in 1854. ... A polyalphabetic cipher is any cipher based on substitution, using multiple substitution alphabets. ... The Reihenschieber was a hand cipher system used by Germany. ... In classical cryptography, the runnning key cipher is a type of polyalphabetic substitution cipher in which a text, typically from a book, is used to provide a very long key stream. ... In cryptography, a substitution cipher is a method of encryption by which units of plaintext are substituted with ciphertext according to a regular system; the units may be single letters (the most common), pairs of letters, triplets of letters, mixtures of the above, and so forth. ... In classical cryptography, a transposition cipher changes one character from the plaintext to another (to decrypt the reverse is done). ... In classical cryptography, the trifid cipher is a cipher invented around 1901 by Felix Delastelle, which extends the concept of the bifid cipher to a third dimension, allowing each symbol to be fractionated into 3 elements instead of two. ... The Two-square cipher is a manual symmetric encryption technique. ... The VigenÃ¨re cipher is named for Blaise de VigenÃ¨re (pictured), although the cipher had been invented earlier by Giovan Batista Belaso. ... In cryptography, coincidence counting is the technique (invented by William F. Friedman) of putting two texts side-by-side and counting the number of times that a letter appears next to itself in both copies. ... A cryptogram is a type of word puzzle popularly printed in some newspapers and magazines. ... In cryptography, the Polybius square is a device invented by the Ancient Greek historian and scholar Polybius, described in Hist. ... This article is about the encryption device; for the Dune character, see Scytale (Dune). ... In cryptography, a straddling checkerboard is a device for converting an alphabetic plaintext into digits whilst simultaneously achieving fractionation (a simple form of information diffusion) and homophony (a simple method for suppressing peaks of the frequency distribution). ... Tabula recta In cryptography, the tabula recta is a square table of alphabets, each one made by shifting the previous one to the left. ...