Elementary cryptanalysis

With mixed alphabets of any kind, a number of cases may arise, according to whether groups are of uniform length, or of varying lengths, or, in fact, represent word-lengths; or, in the one case of uniform groups, according to the length of these groups, or the amount of material available, or as to how much is known in advance, and so on. From among so many possibilities, suppose we select the case of accumulated short messages, and, at the same time, take a brief look at a cipher which, according to its description, was actually intended for group-by-group application. This cipher, which may be examined in Fig. 149, was described in an early issue of The Cryptogram as having been used for military purposes, and was called the “Phillips” system. The text of the figure “Try Macdonald on that Murphy proposition. Curly” includes eight five-letter groups, thus requiring eight cipher alphabets. The key, as originally prepared, is a mixed 25-letter alphabet written into a 5 x 5 square, of which the five rows can be cut apart to form five horizontal strips. It may also be set up with anagram blocks. This is alphabet 1 (or block 1), and serves to encipher the first five-letter group. The method of substitution will be explained in a moment. Alphabet 2 (block 2) is derived from the first by moving line 1 so that it stands between lines 2 and 3. Alphabets 3, 4, and 5 are derived by continuing to move the original line 1 so that it stands, successively, between lines 3 and 4, between lines 4 and 5, and at the bottom of the square. Alphabets 6, 7, and 8 are derived by moving the original line 2 according to the same plan. For puzzle purposes, these movements may continue as they apparently began. Line 2 may be given its one remaining shift, which places it at the bottom of the square, and lines 3, 4, and 5 may then be moved downward in the same way as the first two; some puzzlers, in fact, will afterward continue by treating columns. But according to the description (the only one the writer has ever seen of this cipher), the eighth cipher alphabet is the last. For the encipherment of the next eight groups, either the square is restored to its original set-up and the same eight alphabets used again, or the first key is abandoned altogether in favor of an entirely new one.

Now, considering any one block, as No. 1, the method of substitution is as follows: Each letter is to be replaced by the one standing immediately to its right on the descending diagonal. If the given letter happens to stand at the extreme right side of the square, it is to be replaced by one standing at the extreme left and on the next line below. If it happens to stand on the bottom row of the square, it is to be replaced by one standing on the top row and in the next column to the right. One letter, in fact, requires both of these (mental) adjustments; the letter which occupies the lower right-hand corner is to be replaced by the one occupying the upper left-hand corner. If the foregoing is well understood, is is quite obvious that our key-square is, to all intents and purposes, a rhombus formed with five diagonals. One diagonal is complete, as C Z S I A of block 1. The other four break off at the right and are continued from the left, as L X O N F of block 1; or, if you prefer, break off at the bottom and are continued from the top, as N F L X O of block 1. It should be obvious, also, that any one of these five diagonals can be considered as beginning with any one of its five letters without in the least changing the encipherment. Thus, each diagonal furnishes what is called cyclical encipherment. But, as a matter of fact, the entire square involves cyclical encipherment: The placing of line 1 at the bottom of the square, or of column 1 on the right side of the square, or the transfer of several lines or columns, or of both, will not have any influence whatever on substitutes; for this, it is necessary to alter the 1-2-3-4-5 order of these rows or columns. Alphabet 5, then, will be the same as alphabet 1; and if the plan of the puzzlers be followed, this same alphabet continues to reappear for the encipherment of each fourth group, blocks 1, 5, 9, 13, 17, and so on, of a long cryptogram, eventually giving a great deal of material in one cipher alphabet. Moreover, groups having a length of five letters will carry some very visible simple substitution patterns. Now suppose we look at Fig. 150.

These eight cryptograms have all come from one source. The general frequency count has shown a missing letter, J, suggesting the use of a square, and we have suspected the cipher as “Phillips.” With cryptograms arranged one below another, as shown, the first five columns are presumably enciphered with block 1 of that cipher, the next five columns with block 2, and so on; thus, we presumably have 40 letters each belonging to alphabets 1, 2, and 3, and almost that number belonging to alphabet 4, that is, enough material for frequency counts which will show whether or not they have been taken on simple substitution alphabets. While 40 letters of text are very few, we could, eventually, solve any simple substitution cryptogram of that length, or any mixed-alphabet periodic whose alphabets have furnished 40 letters each. In the present case, our first alphabet has furnished eight known word-beginnings; we have one column known to contain only initials, and followed by two others which are very likely to be the hiding-place of vowels. This does not mean that we should have no preliminary struggles, but in the end there are plenty of clues to set us on the right road: The predominant letters of alphabet 1 are A, B, O, K, U (practically sure to contain e, t, and one of the vowels a or o). The column of initials repeats both A and T (to be compared against a list t s a. . . .). The second and third columns, combined, include B and O, three times each, with O found in the initial column also (both could be vowels, and O probably represents a, though i is also frequently found as an initial). If A, by frequency and initial position, be tried as t, then the other repeated initial, T, can be tried as s. This assumption brings out, in the fourth message, a pattern s - t t -, in which the second letter, B, would have to be a vowel, either e or o, since it has been doubled, with e appearing more likely in the given pattern and also in that of the sixth message, s - - - s. The letter O, which under the encipherment scheme could

not possibly be its own substitute, can be assumed, by frequency, as a, rather than i.

These first correct substitutions are all shown on the left side of Fig. 151, on the lines marked (a). Surely the next identification would be the m of seems, and probably, too, the l of settl. . . With the vowel a already identified, the repeated OU would be tried as an, and the repeated KO as ha, using the digram list. These are the substitutions marked (b), and from this it is but a step to the assumptions marked (c). On the right side of this figure, we are proceeding into alphabet 2. A frequency count here has shown that the leading letters of this alphabet are A, O, Y, two of which, A and O, were also leaders in alphabet 1. It is one peculiarity of the “Phillips” cipher that a change in alphabets means a change in only fifteen of the substitutes, the remaining ten continuing to represent the same originals as in the preceding alphabet. Concerning A, we can see, from the third and fourth messages, that it has not continued to represent t; but O, in the sixth message, has rather suggested the word all and even the expression all right, which would carry us on into the third alphabet. From this point onward, then, we are in the same fortunate position as the decryptor who intercepts his message partly in cipher and partly in plaintext. With the context as a guide, we need not worry as to what happens at the ninth group.

Presumably, during all of this time, we have been recording substitutes in a

key-frame. We have recovered fifteen of these in alphabet 1, and also a number in alphabet 2. Those recovered from alphabet 1 are shown at the top of Fig. 152. O is the substitute for a, A is the substitute for t, T is the substitute for s, and S is the substitute for y. Thus, if the cipher is “Phillips,” then, in the original key-square, the two letters A O were consecutive on one of the diagonals, the two letters T A were consecutive, the two letters S T, and the two letters Y S, so that the complete diagonal must have been Y S T A O, and even though the letter o was not used at all in alphabet 1, we know that its substitute must have been Y, since these diagonals may be considered to begin with any one of the five letters. By beginning at c-H, and following out another such chain, we may find another complete diagonal, C H K W D; and, in addition, we may find parts of diagonals. All of these are shown at (b).

Whether or not we can go further than this, without consulting other cipher alphabets, depends upon whether or not the original key-square contained some of those alphabetical, or nearly alphabetical, sequences which so often betray the poorly-mixed alphabet; usually, these are most easily found toward the X Y Z end

of the normal alphabet. In the given case (b), we are able to find the letters V, W, X, and Y, each standing on a separate diagonal; thus, by readjusting the beginning-points of their diagonals so as to place these letters at the bottom, we are able to set together four of these diagonals in the order shown at (c), leaving only the part-diagonals E B and I R F still to be added. Their length will show that I R F belongs to the missing diagonal, but E B, by its length, could belong to any one of three diagonals. Further developments can be carried out with the rhomboid adjustment of (c), or, if this is confusing, the conversion to a square can be made immediately. The student may decide for himself which he prefers of the two developments marked (d) and (e). Notice that this restoration of the key-square can take place not only from a single alphabet, but with only 15 substitutes known in that alphabet. But without the aid of alphabetical sequences, we must, in the first place, have 20 substitutes, four for each diagonal, in order to recover the full diagonals, after which, each one is entirely independent of the other four, so that they cannot be adjusted and combined without consulting one or more of the other alphabets. Here, the method varies a little, according to just what we can recover, though a hasty glance at the perfect case will serve to show the general path for all. To see this as rapidly as possible, we will assume that we have recovered from alphabet 1 the full five diagonals, and that, in alphabets 2, 3, and 4, we have discovered the substitutes for e, and also the originals for which E has been the substitute.

A careful consideration of the cipher itself will show that no letter can have more than four different substitutes: the four letters in the next column to its right which are not on the same line with itself. Also, that no letter may act for more than four different originals: the four letters in the next column to its left which are not on the same line with itself. Any letter, in order to take all four substitutes and act for all four originals in four successive alphabets, must have started on the top line, which is the moving one.

Now, considering Fig. 153: Our five recovered diagonals are imagined to be those of a well-mixed square, so that we have no discoverable sequences. It has

been found that the letter e, in alphabets 1, 2, 3, and 4, has taken, successively, the substitutes B, H, Q, and Z, and that the cipher-letter E has served, successively, as the substitute for x, u, f, and o. The four letters B H Q Z, then, must all have stood in a single column in exactly the order named; and the four letters X U F O must have stood in another column, two positions to the left of the first, but with a minor difference in the order: some other letter (the one on the same line as E) must have intervened between X and U. The order in this column, then, must have been U F O X. Our first step toward combining the five diagonals is that of adjusting four of them so as to set up the column B H Q Z. This automatically sets up four letters of the other column U F * X (D) — in the figure, the X D is present, but has not been adjusted to the U F * — after which, the fifth diagonal can be added to the others by placing the O of the column U F O X (D). Now, since the letter E has taken, successively, all four of its substitutes and all four of its originals, it must, in alphabet 1, have been standing on the top row. Two parallel lines (if desired) can be ruled across the set-up to show the top and bottom of the square, and two others (placed anywhere, so long as they mark a width of five columns) may be ruled to show the two sides. The outside letters, Y, V, and D, may all be transferred to the opposite ends of their diagonals, after which the rhomboid is easily adjusted to the form of a square.

It will be seen from what precedes that group-by-group encipherment offers little, if anything, that is new, and no problems or theories which the student could not figure out with what he has learned of substitutions. Solving the actual cryptograms, of course, could present some difficulties, according to the individual case.

Of the practice cryptograms to follow, No. 140 follows the plan of the puzzlers, and should not prove very difficult in spite of its brevity. No. 141 is also a “Phillips,” while No. 142 has been enciphered with a mixed-alphabet slide applied to five-letter groups.

Substantially the same encipherment as the foregoing can be had with a slide and a key-word, as indicated in Fig. 155. The progression index, in this figure, is 1. The preliminary key-word, CULPEPER, enciphers the first eight letters, then moves forward in the alphabet and becomes D V M Q F Q F S for the encipherment of the next eight, E W N R G R G T for the encipherment of the third eight, and so on. In its practical application, one column could be taken at a time. Notice, however, in Fig. 156, that when a key-letter progresses in the alphabet, the possible substitutes for any one letter will also progress, and to exactly the same extent. If the encipherment is Vigenère or Beaufort proper, this progression is in the same alphabetical direction as that of key-letters, while the variant encipherment causes the substitutes to progress in the contrary direction. Probably, then, the

most convenient method of application, and the one least likely to result in errors, would be that of Fig. 157. The cryptogram is first enciphered as an ordinary periodic, and the progression is added later, using group-by-group encipherment. Thus, as we receive the cryptogram, our repeated ther has been enciphered once as V B P G, again as W C Q H, and possibly, later on, as A G U L, and the only period we shall be able to find, using the regular methods, will be 26 x 8, or, if the progression index is an even number, 13 x 8. But notice, in the same figure, comparisons (a) and (b).

Vigenère, it will be remembered, has been compared to the mathematical process of addition. If the key-digram CU be added to the plaintext digram TH, their sum is the cipher-digram VB. The alphabetical distance from C to U is 18, the alphabetical distance TH is 14, and the alphabetical distance VB is 6 or could be 26 plus 6, 52 plus 6, and so on. It is a fact that when we “add” the two digrams CU and TH, we actually do add their separating intervals, 18 and 14, since we obtain a sum 32 in that of the cipher digram VB. It is also an easily verified fact that the same reasoning applies to the subtractions of the two Beauforts. The student who cares to investigate may make use of the tableau shown as Fig. 158; to find quickly the distance from one letter to another, find the first of these at the left, the second at the top, and the alphabetical interval between the two is shown in the cell of intersection. If it is desired to know the reverse interval, find the first letter at the top and the second at the side. Now notice, carefully, that when any digram progresses in the alphabet, as CU would become DV, EW, FX, and so on, in a series of periods, it does not change its alphabetical interval; in all of these digrams, the distance apart of the two component letters is still 18. Thus, while our period vanishes, the alphabetical intervals which represent it are still present in the cryptogram; we have only to find these intervals, subject them to a Kasiski examination, and convert the cryptogram to an ordinary Vigenère.

Fig. 159 shows the preparation of the cryptogram: The alphabetical interval

from K to O is 4, that from O to S is 4, that from S to X is 5, and so on. If these numbers are placed directly below the first letter, as shown, the computation of their lineal intervals apart is less confusing than when they are placed between the two. As to repetitions, each repeated single number may represent a repeated digram, each repeated sequence of two numbers may represent a repeated trigram, and so on. Only the longer of these possibilities have been underscored.

Fig. 160 shows the application of a modified Kasiski examination. Notice the prominence of small factors 2 and 3, caused, often, by repeated alphabetical intervals in the key itself. In the given case, the period 10 would probably be the choice, though period 5 is correct; in practice, we should probably consider possible digrams as well as longer sequences. Accepting period 10, we have still to learn the progression index, and for this we must consider letters, all of which are shown in the second column of the same figure. Taking the longest repetition, most likely to be reliable, the two first letters are Y and I; their alphabetical distance apart is 10, and their lineal distance apart in the cryptogram is 50. If the accepted period, 10, is correct, it has taken five periods to produce the alphabetical shift of 10, therefore the shift per period (the progression index) is 10 divided by 5; or 2. This, of course, has taken for granted that the encipherment is either Vigenère or Beaufort. Considered as a possible variant Beaufort, where the progression

is backward, the alphabetical interval from Y to I is 16, which is not divisible by 5, the number of periods. But this progression might have covered the entire alphabet and then included 16, or it might have covered the alphabet twice, and so on, before including 16. We must make it divisible by 5, adding 26, then another 26, and so on, until we obtain a total progression of 120. This, divided by 5, gives the progression index as “minus 24” — the same as a normal progression of 2. In Fig. 161, the cryptogram has been re-written into the accepted period 10, and the figures in parentheses at the right of each group will indicate the amount of alphabetical shift when the progression index is 2. A constant progression of 2 per group would correspond to the application of a Vigenère key A C E G. . . . . , so that the Saint-Cyr slide will serve for quickly converting the cryptogram to its

periodic form, and this is shown in Fig. 162. The period, as mentioned, is actually 5, though this makes no difference in the final results.

For those who like mathematics, Fig. 163 shows a method used by one of our collaborators for determining both the period and the progression index directly from the cryptogram. Price also preferred to find alphabetical intervals by writing the normal alphabet into a block, five letters to the line, with Z standing alone on the last line; thus, except for watching Z occasionally, the distance from one letter to another could be counted by fives. It is understood, of course, that we do not accept the evidence obtained from only one of the supposed repeated sequences; too many of these will be accidental, and many of those which are actually periodic have not represented repeated digrams, but merely repeated intervals. Naturally, too, the progression index need not be a small number; the disk encipherment, mentioned in the beginning, showed a progression of 17 for each period 5. This disk encipherment, incidentally, has been dealt with in a most interesting manner in Givierge’s Cours de cryptographie.

We have seen, then, all of the essentials of polyalphabetical encipherment. With the cipher alphabets known to the decryptor, practically all of the multiple-alphabet ciphers will be solved by suitable modifications of processes described for Vigenère. When alphabets are not known, his problem, always, is that of collecting as many as possible of the substitutes belonging to each alphabet, so that he may determine both the order of the letters and the relationship of alphabets to one another.