Elementary cryptanalysis

Square units, in actual use, are less convenient than those rectangular encipherments in which only one dimension of the block is restricted, thus permitting that a single key govern messages of many different lengths. We have a more practical cipher in the columnar transposition of Chapter IV, and this can be rendered somewhat safer if care be taken to avoid completing the rectangle. The preparation of such a block is illustrated in Fig. 28, where the key-word PARADISE is being used to encipher the following text: REGRET CHANGE IN SYSTEMS BUT THOUGHT ADVISABLE ACCOUNT INCREASED VOLUME SENT BY AIR.

First, let us understand the purpose of the four nulls. It is customary, when cryptograms are to be transmitted by wire or radio, to make them evenly divisible into five-letter groups. This usually means the addition of from one to four nulls, and since the nature of the cipher makes it inadvisable that additional letters be added to the enciphered cryptogram, any desired nulls must be added in the block before the columns are taken off. Another precaution usually recommended is the avoidance altogether of key-lengths which are divisible by 5, so that an encipherer is practically never compelled to add a complete five-letter group in order to leave his rectangle incomplete. It might be added that our use of letters XXXX is for emphasis only; a better series would be one of the nature AAEO.

The decipherer’s only problem is illustrated in Fig. 29. Knowing the key, the decipherer knows that there must be eight columns. The number of letters, 75, divided by 8, results in 9, with remainder 3; thus, the short columns are to contain nine letters, and there will be three which contain ten letters. He lays out an 8 x 10 block, cancels the last five cells, writes his key-numbers across the tops of the columns, and then begins to copy letters, filling the column numbered 1, then the column numbered 2, and so on, finally reading his message by straight horizontals.

The cryptogram from this block is shown as Fig. 30, and illustrates the manner in which the decryptor will number the letters of practically all cryptograms in order that he may quickly locate any desired letter, or learn, by subtraction, the distance apart of any two letters. The decryptor, of course, does not know how many columns the cryptogram contains, and even after he finds out the key-length, he still does not know exactly the point at which any one column ends and another begins.

This form of transposition is among the most fascinating of decryptment problems, and we shall look at it from several angles. The simplest case is that in which the decryptor correctly assumes the presence in his cryptogram of some word or phrase whose length is greater than that of the key; if this probable word is long enough, he is able to learn, not only the key-length, but the order in which to write his columns. Our present cryptogram, for instance, has key-length 8, and contains

two nine-letter words, ADVISABLE and INCREASED. These two words, repeated in Fig. 31, will show what happens when a word is long enough to overlap the block. With the word ADVISABLE, the final E falls below the initial A, and when this column is taken off, the letters A E will stand in sequence in the cryptogram. Similarly, the word INCREASED will provide, in the cryptogram, a digram ID. Should the decryptor suspect the presence of either of these words, he would look at once for sequences of this kind in his cryptogram, and the presence of AE (or ID) would tell him that the key-length is probably 8, which is the distance apart of the two letters in his probable word.

The ideal case is that in which the probable word is long enough to furnish more than one of these overlapping letters, as shown in Fig. 32 in connection with the “word” INCREASED VOLUME. Suppose that we have suspected the presence of this expression in our cryptogram, and have ascertained that the necessary letters are present for forming it. We consider its letters one by one, in the order I, N, C, R . . . . and go through the cryptogram, underscoring (or otherwise noting) all cases in which the given letter is followed immediately by another of the letters found in the same probable “word.” But, in considering any one letter, say the letter N, we ignore such sequences as NT, NB, NX, whose second letters, T, B, X, do not occur in the expression INCREASED VOLUME. Fig. 33 shows exactly what digrams of this kind can be found in connection with letters I, N, C, R, E, and also the distance (or distances) apart of the two given letters as found in the probable word. Notice that in connection with every letter there is one digram in which this distance is 8, the correct key-length of our present cryptogram. And when these digrams are selected from the tabulation, and set up vertically with top letters in the order I N C R E, the lower five letters prove up in the order D V O L U. In actual work, the tabulation must sometimes be made, though ordinarily it will suffice to start directly with the “proving up.”

Now let us go ahead and solve the cryptogram, as shown in Fig. 34. We will assume, to begin with, that our cryptogram has been prepared at the top of a sheet, and that our various trials are being made on the blank space beneath it. We will assume also that, having discovered key-length 8, we have divided this cryptogram roughly into eight segments, three of which contain ten letters and the rest nine.

First, we are in possession of a series of embryo columns, shown at (a), and these can be set up without looking at the cryptogram at all. Having done this, we turn to the cryptogram, find each one of the sequences again, and lengthen the columns of our beginning block by adding to each pair of letters a few of the letters which immediately precede and follow it. Thus, our block begins to build up as at (b); and, for each time that a partial column is set up in (b), the segment which contained it is promptly circled out of the cryptogram itself, which now begins to assume the appearance indicated at (c). Thus some words have automatically formed on the new lines which tell us plainly that the final column must contain a sequence L T E, followed by S or W, and the appearance of the cryptogram tells us plainly where to look for it; the final segment is the only one having enough letters to furnish another nine- or ten-letter column.

At stage (c), we are practically in possession of the numerical key, and to show this, the cryptogram segments have been numbered. The first one, containing V C C O T X, has been set up in the partial block as column 3; thus the third column of (b) should have key-number 1. The second segment, containing S O E U Y E, has been set up as column 5, showing that the fifth column of (b) should have key-number 2. And so on with the rest, until the eight key-numbers are standing in the order 4-6-1-7-2-3-5-8. This is shown at (d), and directly below this, at (e) is the encipherer’s original key. It can be seen that we are now in very much the same position as the legitimate decipherer; by making a few trials, each time shifting one key-number from the left side to the right, we need do little more than decipher. Usually, however, it is quicker simply to go on and rough out the block we have already started, and then make the necessary adjustments, approximately as shown in Fig. 35. Having noted, in the cryptogram, that there are some unused letters,

E N T H, on the left side of segment 1, we assume temporarily that all other unused letters belong to the segment which follows them, and add them all, indiscriminately, at the top of the block. Where this is shown, at the left side of Fig. 35, the true key-numbers, as found in the cryptogram, have been added above the original reference numbers, and similarly with the adjusted block on the right.

With the block roughed out, and knowing that a cryptogram of 75 letters using key-length 8 cannot have columns of any other length than 9 and 10, the first obvious maladjustment is seen in column 1 (key 4), which has only 8 letters. Since this is the 4th segment of the cryptogram, its remaining letter (or its remaining two letters) will have to be found at the end of the third segment or at the beginning

of the fifth (keys 3 and 5), that is, at the bottom, or at the top, respectively, of the columns originally set up as columns 6 and 7. The selection of H from the bottom of column 6 leaves this column too short, while the top row of the block shows a gap in sequence, and evidently needs the E at the end of the second segment. The lone R which remains at the bottom of column 7 is then erased and written at the top of column 2, and thus we arrive at the adjustment shown on the right side of the figure, where the only remaining operation will be that of transferring the misplaced nine-letter column to its own side of the block. This final adjustment shows us the segments of the cryptogram in their key order: 6-1-7-2-3-5-8-4.

Having seen the ideal case, the student will understand how the less perfect example would be handled, or the case in which the probable word is not long enough to overlap at all. For the latter, he would attempt to find some word like CRYPTOGRAM, in which there are letters such as C, Y, P, G, M, not likely to appear more than once or twice in a short text. We need not discuss this latter case, since we are to see something very much like it before the present chapter ends.

Now, as a preliminary to those cases in which we are unable to find a probable word, suppose we turn to the back of the book, and make an inspection of the tool chest. First in importance, and valuable in ciphers of all kinds, is the digram chart which O. Phelps Meaker has been kind enough to prepare especially for this text. To learn how often he encountered any given digram in his 10,000-letter count, note its first letter in the horizontal alphabet, at the top of a column, then note its second letter in the vertical alphabet, at the beginning of a row, and observe the figure which occupies the cell at the intersection of this column and row. If the digram is TH, its frequency was 315; if the digram is JN, the cell is blank. This does not mean that the digram TH will appear exactly 315 times in any other 10,000-letter text, or that JN will never be found (occurring, say, as initials). It merely shows that the digram TH is of remarkably high frequency, while a digram JN is so rare that it practically never appears. The most commonly occurring digrams of this chart have been listed on another page in the order of decreasing frequencies. A list of the principal reversals is also given, with other data which will be found useful in the majority of ciphers. Meaker’s digram chart shows also the frequencies found for single letters in the same text. These are shown at the extreme right, and were obtained by adding the figures found on the 26 rows of the chart proper. When such counts are made, every letter in the text is considered to be the first letter of a digram, and no attention is paid to the separations between words. Thus the single-letter frequencies can be found by totalling either the columns or the rows, which, except for minor discrepancies, will check against each other.

So much for frequencies. Now let us take a closer look at sequence. Certain letters, ordinarily those of lowest frequency, are peculiar in their contacts with other letters. The shining example, in most languages, is the letter Q, followed, almost 100% of the time, by U plus another vowel; and if it seems, in the present text, that the significance of QU is being overlooked, this is simply because the individuality of this digram, like that of the German CH (CK), is so well advertised that even the novice encipherer finds a way to avoid using it. It is impossible, however, to avoid all letters having individual preferences. We still have J and V, practically sure to be followed by vowels, and Z, almost as sure. We have X, nearly always preceded by a vowel, but more often followed by a consonant. If these are missing from the cryptogram, we may have letters like K, B, and P, which confine an enormous percentage of their contacts to vowels; or to vowels and liquids; or to letters from the high-frequency group E T A O N I R S H. Even among the high-frequency letters themselves we find that H is followed about 75% of the time by either E or A, and that it is preceded largely by T, with S, C, and W as the next favorites; or we find that N is inordinately fond of vowels on its left, though with some preference for consonants on its right. All information of this kind is present in the digram chart, and usually is known to the decryptor without recourse to a chart.

For the beginner, however, who might like to have it in a more visible form, another chart, of a kind which we believe has never before been published, appears on page 220. This is F. R. Carter’s contact chart, on which every letter of the alphabet has been listed in the center of the page, with its favorite contact-letters beside it. The arrangement here is from the center outward; the letters shown on the left of any given letter are those which most often precede it, with percentages as found in Ohaver’s digram chart; letters shown on the right are those which most often follow, with percentages from the same digram chart. This information was not completed to the end for every letter, since the only information wanted is the actual preferences of each letter, or the fact that it has none. However, the outermost columns will show the complete percentages of vowel and consonant contacts for all letters as these were found in one 10,000-letter text. With such a chart before us, it becomes very easy, in the absence of Q, and other particularly vulnerable letters, to make good use of whatever letters we happen to have; and it is hoped that this new “contact chart” will prove sufficiently valuable to justify Carter’s labor in having compiled it for us. As to the other data in the appendix, the student will do well to look it over. The list of trigrams is that of the Parker Hitt Manual, where THE was shown as having been found 89 times in 10,000 letters, the others graduating downward to MEN, found 20 times. Now let us return to our columnar transposition.

When a digram QU is actually present in a text, or when it is fairly certain that some other digram may be present, such as the YP of CRYPTOGRAM (that is, one composed of two infrequent letters), it is possible to discover (or limit) the key-length by observing the distance apart of these two letters in the cryptogram. To approximate such a case, using the foregoing cryptogram (Fig. 30), we will make use of the digram VI, and, in order to be brief, we will assume that the letter V, position 5, is the only one in the cryptogram, and that the only I’s present are those at positions 46 and 61. In one case the interval which separates V from I is 41, and, in the other, 56. As a preliminary step, we may discard all key-lengths which are factors of 75: 3, 5, 15, 25. In addition, we may discard, for the time being, the key-lengths 10, 20, etc., which are multiples of 5. Of those left, any very short length, as 2 or 4, is very improbable. We may consider, then, possible key-lengths of 6, 7, 8, 9, 11, etc., as far as we care to take them.

To make ready for the investigation, we first prepare a sheet of the kind shown as Fig. 36, where each possible key-length has been used as a divisor in order to learn the column-lengths for each one in a 75-letter cryptogram.

Now let us picture any text written into any block, as in Fig. 37, where long columns have five letters and short columns have four. Considering any digram in the text, as QU at the beginning, its two letters are separated by exactly one column of length, provided the letters are counted straight down the columns and columns are taken in one straight direction, or provided the counting is done strictly upward with columns always taken in one direction. In the case of QU, this column of separation is a long one (five letters), while, in the case of AF, on the right-hand side of the block, it is a short one (four letters), but in both cases it is a full column. This is true, also, of the digram FE, which is on two different lines, presuming that, having counted all the way to the end of the last column, we start again with the first. If both letters are in short columns, the interval which separates them is that of a short column, and if both are in long columns, this interval is that of a long column. But if one letter is in a long column and the other in a short column, the separating interval may be long or short, according to whether the columns are taken in straight order or in reverse order.

If the columns of Fig. 37 should be cut apart, and placed in some other order, then other columns might be placed between the one containing Q and its neighbor containing U, but these would be full columns, never fractional columns, so that the interval from Q to U would always be an exact number of full columns.

This is what happens in columnar transposition. If the digram VI, which we intend to consider, was actually present in the original encipherment block, then, in the cryptogram, its letters V and I are separated by an exact number of columns, long or short or mixed. Also, if the column containing V was taken off first, the distance from V to I may include the full number of long columns permitted by the key-length, but must fall one short of including all of the short columns; but if the I comes first, the opposite is true. Now, assuming that the only V’s and I’s in our cryptogram are those appearing at positions 5, 46, and 61, we find that if the first of the I’s is considered, the distance from V to I is 41, while, if the other is the one considered, then this distance is 56. We will investigate, first, the interval 41.

If V and the first I stood in sequence in the encipherment block, either as VI or as IV, then the interval 41 represents a certain number of complete columns, and if the digram was VI (since the V-column was evidently taken off first), this interval 41 must not include the full number of short columns, but may include the full number of long ones.

Consulting Fig. 36, we find that key-length 6 calls for columns having 12 and 13 letters, and it is impossible to divide an interval 41 into columns of such lengths. The key-length 7 calls for columns having 10 or 11 letters, of which only two columns may have the shorter length; an interval 41 can be divided into the right lengths, but only if three of the columns are short. Thus, if the first I is the correct one, the key-lengths 6 and 7 are totally impossible, as is also key-length 8. The key-length 9, however, calls for columns having 8 and 9 letters, of which six have the shorter length. An interval 41 can be divided to produce four short columns and one long column. Again, the key-length 11 calls for columns having 6 and 7 letters, of which two columns may be short; and an interval 41 will provide five long columns and one short column. These two key-lengths, then, 9 and 11, are possible, presuming that the first I is the one which actually followed V. When the other I, interval 56, is investigated in the same way, it is found that the only key-lengths possible are 8 and 11.

So that if the digram VI is present at all, the key-length must be 8, 9, 11, or something longer. Since the key-length 11 is possible in both cases, this is the one which tempts; when it fails, the remaining two can be tried. The student may decide for himself whether a trigram IVI is possible, considering the distance apart of the two I’s. It will be readily understood how this method, in combination with the one first explained, could be used, say, in a cryptogram where the suspected word is CIPHER, with the low-frequency letter P occurring only once.

Totally aside from analysis, there are many ways in which the key-length can become known, or suspected. If the correspondence is a military one, it may have been learned by espionage, perhaps through careless talk on the part of an enlisted man; or, because of careless habits on the part of the authority providing the keys, in having confined himself always to certain lengths. Knowing the key-length is two-thirds of the battle. It enables us, as in our former case, to mark off the cryptogram into its approximate column-lengths, making it easier to know the approximate whereabouts of any several letters supposed to form a sequence. It even enables us to prepare a block, which, cut apart to form paper strips, will effect a mechanical solution almost as easily as in the case of the completed unit.

Such a block, for our foregoing cryptogram (Fig. 30), can be studied in Fig. 38, and is explained as follows: An 8-unit key, used on a 75-letter text, calls definitely for three 10-letter columns and five 9-letter columns, and these columns have become eight segments in the cryptogram. If all three of the long columns were taken off first, then the arrangement shown at (a) has every letter in its proper column. And if all three of these were taken off last, then the arrangement shown at (b) has every letter in its proper column. With blocks shown for the two extreme cases, it can be seen that the block at (c) is a combination-block, in which one of

the two extremes has been superimposed upon the other, so that every column in block (c) shows every letter which it could possibly have contained. By concealing the letters of the “cap,” we have a duplicate of block (a); and by changing the alignment, so as to bring all of the topmost letters into the same row, we have block (b), with a “cap” attached at the bottom.

Comparing block (c) with the two above it: If the first column of (a) was actually a short one, then its last letter, X, belongs at the top of the second column. The making of this transfer would cause the second column to have eleven letters, so that it would become necessary also to transfer the last letter of the second column to the top of the third; this third column would then have too many letters, and its last letter would have to be transferred to the top of the fourth, which at present has only nine and may have another. But if the second column was also short, then there are two of its letters which belong at the top of column 3. And if this column, too, was a short one, it has three transferable letters at the bottom.

To prepare such a block, first write the cryptogram as at (a), and mark off its transferable (uncertain) letters by the following rule: One for the first column, two for the second, and so on, until the number is equal to the number of long columns, which is the maximum number possible. But if the final row is more than half filled, the maximum will not be reached, and a check may be made by marking off letters from right to left: zero for the last column, one for the next-to-last, two for the third-to-last, and so backward to the number which equals the number of long columns. Having marked off the transferable letters, form the “bonnet” by copying these, in each case, at the top of the following column, preferably making some clear distinction to show the duplication. For this latter purpose, many solvers use red ink. In this kind of work, as we saw in a previous case, the spacing must be accurate both laterally and vertically, since many of the letters belonging to the same sequence are not found on the same row. A few of the strips cut from block (c) have been matched at (d), where the beginning was made from the common suffix -ABLE. The duplicated letters A H Y have shown up plainly, partly by the style in which the letters are written, and partly, too, by the fact of consecutive column-numbers, 3 and 4. This same thing is true of the letters X T N, column-numbers 4 and 5. These numbers, it must not be forgotten, are also the serial numbers of the cryptogram segments, and thus are the key-numbers. With the eight strips correctly matched, and any misplaced columns transferred to their own side of the block, the strip-numbers as they stand across the top will reproduce the numerical key.

The matching of strips is generally a purely mechanical process, in which impossibilities are not considered. However, having before us a block (a) or (b), it is possible to apply the principle used with our former digram VI, and find out in advance whether certain letters found on two strips can possibly have stood in sequence. Nor is the cutting apart of the strips really necessary; it is merely a convenient method for dispensing with mental effort.

Now suppose we consider this same cryptogram on the theory that its key-length cannot be determined, or restricted to certain possibilities. Our first step is to select, somewhere in the cryptogram, a segment which is to be set up vertically on a sheet of paper to act as a trial column. If we select it from the body of the cryptogram, we shall have to make it a rather long segment, since we are uncertain as to whether it represents one column or parts of two. We should do this, however, if the body of the cryptogram shows Q, or any other letter or series of letters likely to be vulnerable. Otherwise, we know definitely that one of the columns begins with the first letter of the cryptogram, and that another column ends with the final letter of the cryptogram, and one or the other of these two segments is usually chosen, preferably the one containing the largest number of vulnerable letters. If we have a probable word, and find that its letter P, or M, or G, is the only one in the cryptogram, we select the segment which contains this P, or M, or G.

Wherever the trial segment is taken, there is always the question as to how many letters ought to be included. In Fig. 39, the decryptor has decided to take the beginning segment of the cryptogram, and has started with 15 letters. He has written beside it another 15-letter segment, chosen because of NG, HO, VI, and is attempting to tell, by the appearance of his digrams, and their frequencies as taken from two different digram charts, just about how far his digrams are uniformly good. If the nulls in use are actually XX, he knows immediately that this is the end of his two columns; otherwise, his digrams are acceptable throughout. If he sets down beside each digram its frequency as taken from Meaker’s chart, he might decide that his digrams are

good as far as UT, depending somewhat on the letters represented in our XX. Using Ohaver’s frequencies, he would feel sure that his digrams are good as far as OL. In many cases the frequencies shown for the lower digrams will grow so erratic as to be plainly unlikely; and in other cases, more difficult than the present one, a check on the probable column-length can be had by preparing a similar set-up for the end-segment of the cryptogram, in which the lower digrams are excellent, while those extending upward may grow erratic. This decryptor is safe, however, in accepting as much or as little of the length as he likes; there will be a more definite line of demarcation when he attempts to write beside these a third column of 15 letters. The only cases which ever give trouble are those in which a short text has been enciphered with a long key. Key-lengths, generally speaking, hardly ever run outside of limits 5 to 15, that is, lengths which come from single words. Thus a tentative key-length 10, 11, 12, lying half-way between these extremes, is always safe to try. The key-length 10, applied to 75 letters, gives columns of 7 or 8, and, in the discussion which follows, the tentative column-length was fixed at 8 letters.

Usually these trials are made by setting up the trial column (in pencil) several times in succession, so that several of the possible combinations can be seen side by side, in order to determine which is best. Sometimes this can be decided by simple observation. Otherwise, the combinations can be subjected to a digram test. This is made by setting down beside each digram, as formed by each pair

of columns, its frequency as taken from a digram chart. These figures are then added in each of the set-ups, and the supposition is that the combination furnishing the highest frequency-total will be the correct one, provided this high total has been produced by all of its digrams collectively, and not by some one or two individual digrams. With short columns, such tests are never conclusive, but with as many as ten or twelve digrams they are nearly always dependable, and even with only five or six digrams they will often select a correct combination.

It was decided here to choose as the trial column the first eight letters of the cryptogram: E N T H V C C O. This column is filled with consonants, indicating that those which follow or precede it might contain a number of vowels; and of the six consonants present, practically every one could be called a “vulnerable” letter, or, as we say in the Association, a “clue-letter.” If we wish, for instance, to choose a column which will fit well on the right-hand side of this trial column, we can search the rest of the cryptogram for two consecutive vowels to follow, respectively, H and V, and these two vowels we should expect to find followed, either immediately or at interval 2 by some letter (usually a high-frequency one) which will follow at least one of the C’s. This kind of pattern, unfortunately, was found eleven times. In practice, we should probably abandon it rather than copy down

and test eleven combinations; here, however, the eleven set-ups can all be seen in Fig. 40, accompanied by serial numbers to show the order in which their second columns were taken from the cryptogram. Some of these have not been tested. Of the five retained, particular attention is called to the fact that the one having the very lowest total is actually the correct one, as may be seen by turning back to the encipherment block. But when a single row of corresponding digrams (HE in the first four set-ups and HO in No. 11), has been subtracted throughout, it is seen that No. 11 moves upward toward its proper rank, having now the second highest total. In practice, it might even be selected in preference to No. 8, which grows erratic after its fifth digram (frequencies of 0, 55, 0). But the column-length 5, in practice, is not unlikely, so that a test made on the right-hand side of our trial column has not been at all conclusive.

Postponing the decision, then, let us take a fresh sheet of paper and make some tests for columns which can be fitted on the left-hand side of our trial column. Here, we find that the best “clue-letters” are N and H, standing at interval 2. To precede N, we should like to find one of the vowels of which it is so fond, and to precede H, we hope to find either T or one of the letters S, C, W. That is, we hope to find a pattern in the rest of the cryptogram in which some vowel, other than Y, is followed at interval 2 by one of the letters T, S, C, W. This time we find only four segments, and when the test is made for these, as shown in Fig. 41, the resulting totals point decisively to the correct combination, which is No. 3. Notice, in both of these tests, that results are identical whether the frequency-figures are those counted by Meaker or those counted by Ohaver: In the test of Fig. 40, the five combinations (using either chart) are ranked in the order 8, 11, 10, 1, 9, while the test of Fig. 41 has ranked its four combinations in the order 3, 2, 4, 1. Selecting, then, combination No. 3 of Fig. 41, let us return to the doubtful tests of Fig. 40 and attempt to effect a combination between our No. 3 and some one of the five previously considered worth retaining. Thus we can make an observation of trigrams, as shown in Fig. 42.