| Viewing Single Post From: Contact Analysis | |
|---|---|
| jdege | May 18 2008, 06:40 PM |
Elite member
  ![]](http://209.85.122.85/static/1/pip_r.png)
|
Contact Analysis In cryptanalysis, contact analysis is the study of the frequency with which certain symbols precede or follow other symbols. The method is used as an aid to breaking classical ciphers. Contact analysis is based on the fact that, in any sample of any written language, certain symbols appear adjacent to other symbols with varying frequencies. Moreover, these frequencies are roughly the same for almost all samples of that language, even when the distribution of the symbols themselves differs significantly from normal. This is true regardless of whether the symbols being used are words or letters. In some ciphers, these properties of the natural language plaintext are preserved in the ciphertext, and have the potential to be exploited in a ciphertext-only attack. Although in a sense contact analysis can be considered a type of frequency analysis, most discussions of frequency analysis concern themselves with the simple probabilities of the symbols in the text: P(X(i) = a) or P(X(i) = a ∩ X(i + 1)= b) Contact analysis is based on the conditional probability that certain letters will precede or succeed other letters: P(X(i) = b | X(i − 1) = a), or P(X(i) = c | X(i − 2) = a ∩ X(i − 1) = b), or even P(X(i) in S | X(i-1) in T ∩ X(i+1) in T), where S and T are subsets of the alphabet being used. Where frequency analysis is based on first-order statistics, contact analysis is based on second or third-order statistics. The process of contact analysis often begins with an attempt to categorize the symbols into classes that have different contact behavior. When the symbols represent letters, the first attempted categorization is usually between vowels and consonants, which have very different contact behaviors in all alphabetic languages. Contact analysis for simple substitution ciphers A common technique for applying the principles of contact analysis to simple substitution ciphers is the consonant line method. In this, the cryptanalyst first creates a chart indicating which ciphertext letters appear next to which other ciphertext letters. From this, a determination is made as to which letters are vowels and which are consonants. English, as with other alphabetic languages, uses letters to spell out phonetically pronounceable words. This places limitations on the sequence of letters. Vowels and consonants tend to alternate, and when we see consecutive vowels or consonants, they are limited to those which can be pronounced. Vowels tend to occur adjacent to consonants, and consonants tend to occur next to vowels. Each will be found in contact with the letters of other class rather than in contact with its own. Vowels tend to contact more distinct letters than do consonants. Vowels commonly contact the many different consonants, consonants most commonly contact the much fewer number of vowels. When vowels contact other vowels they show typical patterns: e rarely contacts o, ea is common, ae is rare. ei and ie are both common. Using these relationships, many letters within the ciphertext can be classified as vowels (AEIOUY), high-frequency consonants (TNSHRDL), medium-frequency consonants (CMWFGPB), and low-frequency consonants (VKJXQZ), and certain letters within each group can be given provisional identifications. An example (For this example, uppercase letters are used to denote ciphertext, lowercase letters are used to denote plaintext or guesses at plaintext, and X~t is used to express a guess that ciphertext letter X represents the plaintext letter t.) Suppose Eve has intercepted the cryptogram below, and suspects that it is an English text encrypted using a simple substitution cipher: She will have prepared herself with charts describing the conditional probabilities for the plaintext language. Her first task is to create a contact chart. Contact Chart A contact chart is a table with a column for every letter in the ciphertext, under which is written a pair of letters for each instance of that letter in the plaintext, the first being the letter prior to that instance of the letter, the second being the letter after. At the top of each column two numbers are written, the number of times that letter appears in the ciphertext (the letter frequency, which is the same as the number of letter pairs in that column), and the number of distinct letters that appear in that column, called the Variety of Contact or VOC. Notice how in the column for H, there are 26 letter pairs, which indicates that appears 26 times, but there are only 16 distinct letters in that column, giving H a VOC of 16. While preparing this chart would have taken Eve a bit longer than generating a simple frequency count, it provides her with far more information about the structure of the text. It includes the single character frequency count as the top line of chart. She can easily calculate the digram frequencies by counting the number of times each distinct letter appears in the left position in each column. HK appears six times. She can calculate the trigram frequency by counting the number of times each distinct letter pair appears in each column. HKR appears three times. In practice, she would not list all of the trigram and digram frequencies, but would simply identify the highest, by visual inspection of the chart, and perhaps highlighting those of interest. In this ciphertext, the most frequent letters are R, H, and X, the most frequent digrams are CR, HK, and RO, and the most frequent trigrams are GYN, HKR and YNV. Just as a ciphertext can sometimes be broken only simple examination, or using only simple frequency distributions, sometimes the contact chart alone will provide sufficient insight into the text as to provide the crack necessary to break it. But for the sake of continuing the example, Eve failed to accomplish this. Identifying vowels and consonants Eve's next step would be to make a guess as to whether one or more letters were a consonant or a vowel. In the ciphertext, Eve might assume that R is a vowel. It has a very high contact number - 20 - indicating that it contacts every letter in the ciphertext save four. But Eve knows that the most reliable assumption is usually that low-frequency, low-contact letters are consonants. The low-frequency consonants make up around 20% of the a typical text. There are 314 characters in the ciphertext, 20% of which is 62. Using the chart, Eve identifies the lowest-contact letters that have a combined frequency of as close to 62 as possible, without going over. From these, Eve would begin to build her vowel and consonant lines. Vowel and Consonant Lines A Consonant Line takes the form of a tee, with the letters thought to be consonants above the top line, and with the letters that precede or follow the letters at the top written below on each side of the vertical line. A Vowel Line is analogous. Eve has identified a number of probable consonants. She would have created a consonant line by taking each probable consonant in turn, writing it at the top of the line, and then going down the column for that letter in the contact chart, taking each letter pair and writing the left letter on the left side of the consonant line and the right on the right. This shows which letters contact the low-frequency consonants. Those that do so the most are likely to be vowels. Any letter that does not contact the low-frequency consonants at all is likely to be a consonant itself, and can be added to the line. In this case, there are none. This first consonant line gives Eve two probable vowels, R and X. R had been strongly suggested simply by it's high VOC. Eve decides to classify R and X as a vowels in this pass. So she prepares a vowel line. This convinces Eve that O and H are consonants. C also shows up as frequently contacting vowels, but the consonant line shows it contacting consonants about as often, so she'll make no determination for it, yet. Adding O and H produces a second consonant line. Examining this second consonant line convinces Eve that B and N are the other two high-frequency vowels. Vowel spacing As Eve was identifying vowels, she was marking up the ciphertext, putting a bar over ever letter that represents a vowel. Long consonant clusters are rare in English. Five sequential consonants happen rarely (e.g., "running through"), more than five happen almost not at all. Similarly, long sequences of vowels are rare. She used these sequences, along with the number of contacts shown in the consonant line and the vowel line, in determining which letters were vowels and consonants. After having identified the four high-frequency vowels, Eve sees that there are no instances of more than two vowels in sequence. Had there been any, it would have been an indication that she had decided incorrectly. She finds only four five-long non-vowel sequences, EZGHQK. Of these, she has already identified E, Z, G, H, and Q as consonants. Either K is a vowel, or one of the others was mistakenly identified. (it's not uncommon for u and y to appear in the low 20%, and to be picked as consonants in the initial division.) Vowel-vowel contact Eve's next step is to try to determine which of the four high frequency vowels are which. She does this by looking at the frequencies of the digrams containing only these four letters. Eve knows that e is the vowel that is by far most likely to contact other vowels. She provisionally assigns R~e. The vowel that is most likely to precede e is i, which might be N, though the counts are so small as to make it uncertain. She leaves the others, for now, and moves on to the trigrams to see if she can identify the high-frequency consonants. High-Frequency Consonants The high-frequency letters in the ciphertext are R, H, X, B, O, C, Y, N, J, and I. Eve has identified R as e, and B, N, and X as high-frequency vowels. Remaining are H, O, C, Y, J, and I, and the high-frequency consonants, t, n, s, r and d are likely among them. Eve examines the high-frequency trigrams, to see if they can help her identify the remaining high-frequency consonants,. The one she immediately notices is HKR. She knows R~e, that H is a consonant, and that K is not a, e, i or o,. Of the trigrams consisting of two consonants followed by e, the is overwhelmingly the most common. She also sees that HH appears as a double letter, which doesn't contradict the assumption. So she provisionally assigns HKR~the. Now she looks at the digrams; She looks at BH. She has assumed that H is t, and is pretty sure that B is a vowel other than e. Of the four possibilities, at, it, ot, and ut, at is the most common. She decides to give B~a a try. At this point, she has two high-frequency vowels left, i and o, which have to be either XN or NX. Purely arbitrarily, she tries NX~oi. Examining the partial plaintext, she sees that the message ends: BHNXY~atoi_, which doesn't seem right. Both oi and io are reasonably common, but as the ending of a word, ation is common, and atoi? is not. So she changes her mind and tries NXY~ion. She now has the four high-frequency vowels BENX~aeio, and three consonants, KYH~hnt. The remaining high-frequency letters in the ciphertext are: O, C, J, and I. The unidentified high-frequency consonants are s, r and d. She looks through the partial plaintext, looking to see where these might fit. She notices: Most particularly, she notices that the unknown letters in this sequence include repeats of the high-frequency ciphertext letters, O and I. O is the higher-frequency of the two, so she mentally replaces it with the unidentified high-frequency consonants. The assignment O~r immediately leads to I~m, and the plaintexttext Which is, of course:
At which point her plaintext is:
And from there, breaking the rest is trivial. |
| When cryptography is outlawed, bayl bhgynjf jvyy unir cevinpl. | |
 |
|
| Contact Analysis · General | |
9:39 AM Nov 28
