Elementary cryptanalysis

For this kind of case, however, many solvers have a preference for the purely mechanical method which is detailed in Fig. 112. Sheet 1 of this figure has been prepared from the first column of our cryptogram, which included the letters Z U Z O E. Sheet 2 has been prepared from the second column, which included the letters I I I I U; and sheet 3 has been prepared from the third column, which included the letters L Y L E K. In each case, the column of cryptogram letters, as it first stands, is also the A-decipherment. With each letter used as a point of beginning, a series of normal alphabets may be laid out, as in the figure, and the resulting 25 new columns on every sheet will show the other 25 possible decipherments. But if these decipherments have been caused to progress in the normal alphabetical direction,

and if the cipher is Vigenère, the key-letters which produce these deciphered columns will have to run backward in the alphabet. These can be added at the tops or bottoms of their columns, and can, if desired, be written in red ink, or otherwise distinguished.

Fig. 113 shows what modifications would be necessary if the sheets were being prepared for one of the Beauforts. For the variant Beaufort, the only difference lies in the fact that key-letters must progress in the same alphabetical direction as their decipherments. With the true Beaufort, however, the making of an A-decipherment does not mean a simple copying of cryptogram letters, as in the other two ciphers; this A-decipherment must first be made; after that, the series of normal alphabets can be extended as before, and the key-letters will progress in the same alphabetical direction as their deciphered columns.

Now, assuming that these sheets have actually been prepared, say on quadrille paper, the various columns of decipherment may be examined, and a check-mark placed beside each column in which the series of letters appears to represent a “good” decipherment. With longer columns, those may be checked which contain the largest percentages of letters E T A O N I R S H, without too many of the letters J K Q X Z; with shorter columns, perhaps those are “best” in which any repeated letters are chiefly vowels, it being remembered that when the cryptogram contains repeated sequences, as well as repeated single letters, the possible identity of these repeated digrams or trigrams must also be taken into consideration. With all of the apparently good columns checked for attention, sheet 1 may be creased vertically so as to place any desired column on the extreme right, and this column may then be laid directly against any desired column of sheet 2 for an observation of the resulting digrams. If these appear to be satisfactory, then sheet 2 may also be creased vertically, and the series of apparently good digrams may be laid directly against any desired column of sheet 3 for an observation of the resulting trigrams. And so on, if desired, to a possible sheet 4, or 5, or 6, though, as a rule, the first three sheets will be found sufficient. While the method, as indicated, is intended to be mechanical, that is, largely visual, it would be possible, where uncertainty exists between two given combinations, to copy these and subject them to a digram test. But this should not be necessary in a case where key-letters, as well as their

deciphered columns, are expected to set up good combinations in order to form a plaintext key-word.

An interesting version of this method, as shown by Admiral Elliott Snow, included the following variations: To begin with, in extending the alphabets, the decryptor omits altogether the letters J K Q X Z, and perhaps one or two others of extremely low frequency, simply leaving the blank spaces which indicate their alphabetical positions. This makes the work more rapid, and, in addition, the presence of these blank spaces in any column of decipherment, advertises at once that the column is probably not a very good one. But Admiral Snow’s columns were not columns; they were rows. A given series of letters: as Z U Z O E of our foregoing sheet 1, is laid out horizontally, and its decipherments are extended vertically. The spacing on each row is arranged to correspond with the period; that is, the letters Z U Z O E, instead of being continuous, are spaced six columns apart if the period is 6, and their decipherments, of course, are spaced in the same way. The sheets may now be creased horizontally between rows, and one sheet placed against another in such a way that the resulting digrams are all standing on diagonals, but have appeared at exactly their cryptogram distance apart. The student should experiment with both arrangements and decide which one he likes.

It has been pointed out by C. A. Castle, another of our members, that the foregoing method will find its chief application, not on a single cryptogram, but as applied to a case which, so far, we have not considered in connection with the substitution ciphers: One in which the decryptor has in his possession five or six cryptograms, all very brief, but all enciphered with the same key. Here, we have the common practical case, to be handled in somewhat the same way as the last of our transposition examples; the cryptograms can be written one below another, thus forming a series of columns in which every column has been enciphered with the same cipher alphabet. If this case happens to involve a comparatively short period, it is possible to take intervals between repeated sequences found in two different cryptograms, using the intervals indicated by the number of columns between the first letter of one sequence and the first letter of its repetition. Castle’s example, however, was not based on a short key, but upon an extremely long one, and his five or six messages were merely fragments, each one of which was known to be the beginning of an English sentence. In the English language, about half of all initial letters used are found in the group T A O S H I and more than another one-fourth are found in the group W C B P F D M. Thus, having a series of beginnings in which the first column will include only initial letters, the number of truly acceptable decipherments on any sheet 1 will usually be quite limited. In addition, with vowels known to have a fondness for second and third positions in words, there should be little difficulty in selecting decipherments from sheets 2 and 3.

While we have described this device as having been written out on sheets of paper, there are many persons who prefer to have at hand a series of cardboard strips which will set up the “sheets” mechanically. If each of the strips carries

the normal alphabet written twice in succession, it is possible to adjust five of the strips so as to place the letters Z U Z O E one below another in the form of a column and automatically set up the other 25 columns. The strips can be loose, or may form part of a slide. Slides, in fact, may be used for many purposes, and are well worth preparing for any kind of cipher which the decryptor expects to encounter a great many times. The members of the American Cryptogram Association, who solve a great many Vigenères, Beauforts, and so on, as a matter of recreation, have practically all “invented” slides (or tableaux) which will, to some extent, do away with the irksome task of carrying out a trigram-search. These are prepared in various ways, and variously used, though the principle for all is about the same as that indicated in Fig. 114. They are usually referred to as decrypting slides, and the single stationary alphabet, sometimes a list of key-letters and sometimes not, will be called “the decrypting alphabet.” C. Stanley Lamb, who is by no means the only “inventor” of the device illustrated, has this in several different forms, according to the purpose for which he intends to use it. Notice that the card, as we have placed it, shows the stationary single alphabet running contrary to the others, for use on the Vigenère cipher, and that this card need merely be reversed in order to have a single stationary alphabet running parallel to the others, for use on the two Beauforts. As to the sliding double alphabets, there may be as many of these as the operator feels like setting up; if the device is being used to assist in the trigram search, three will be needed.

To explain its use: The decryptor here is dealing with a sheet of trigrams. Each one of these trigrams is to be deciphered as THE, AND, THA, and so on, following the list of normally frequent trigrams, and the resulting key-fragments are to be written down for comparison with one another, in the hope that some two or more will be duplicates, or will contain overlapping letters. The first of these cipher trigrams is HDG. These three cipher-letters, found on the three slides, are placed, in order, below A. Now, on the first of the slides, every possible decipherment for H is standing opposite its key-letter, found in the “decrypting alphabet”; on the second slide, every possible decipherment for D is standing opposite the the proper key-letter; and on the third slide, every possible decipherment for G. To know, then, what key-letters will be deciphered by THE, find T on the first slide and note key-letter O; find H on the second slide and note key-letter W; find E on the third slide and note key-letter C; the complete key-fragment is OWC. This may be written down, Then, without changing the adjustment of the device: For AND, key-fragment HQD, and so on down the list.

Where the cipher is Vigenère, the text-letters may be found in the “decrypting alphabet” and their keys on the slides, without changing results. But with either of the Beauforts, a key is specifically a key and not a text-letter. Thus, when the card is reversed, and the same process applied for one of the Beauforts, the student must be careful as to where he finds his letters T H E in each of the two ciphers. This peculiar relationship of Vigenère-variant-Beaufort is not hard to untangle if all three of the encipherments are considered to be purely mathematical operations of addition and subtraction. If we must add two numbers, as 5 and 10, it makes no difference whether we call it the sum of 5 plus 10 or the sum of 10 plus 5. But where we must perform a subtraction, there are two separate cases.

In straight Vigenère encipherment, the process is addition, in which text-letters may be considered to have the values 1 to 26 (their serial positions in the normal alphabet), while key-letters may be considered to have the values 0 to 25 (the amount of alphabetical shift represented by each one). Thus, the encipherment of J by P (10 plus 15) will not result differently from the encipherment of P by J (16 plus 9); in both cases, we obtain Y, alphabetical value 25.

In variant Beaufort, we have one of the subtractions: Message minus key, with the occasional necessity for “borrowing” 26 in order to make a subtraction possible. Thus, J enciphered by P (10 minus 15) does not give the same result as P enciphered by J (16 minus 9). In the first case (after borrowing 26), we obtain U, or 21, while in the other case we obtain G, or 7.

In the true Beaufort, we have the other subtraction: Key minus message. This time, we value the key-letters 1 to 26, and the text-letters 0 to 25. Thus, J enciphered by P (9 taken from 16) results in G, or 7, while P enciphered by J (16 taken from 9) results in U, or 21. Our results, then, are exactly the reverse of those obtained in the other subtraction.

If these mathematical comparisons be understood, or simply kept in mind, it will always be possible, whenever a decryptment process has been explained in connection with only one of the encipherments, to examine its “mathematical” details and learn from these in just what respects it would have to be modified in order that it may be applied with equal success to the other two encipherments. There is another interesting possibility which may have escaped the student’s notice. If he will turn back to Fig. 98, in which the same message, using the same key, was enciphered in both of the Beauforts, one encipherment coming out as K K Z B B I Z. . . . . and the other as Q Q B Z Z S B. . . . . , he will notice that these two cryptograms are complementary from beginning to end. If we saw any reason for doing so, we might convert either one of the Beaufort cryptograms to the other form, and apply its probable word with its own slide.

Now, having seen the great vulnerability of the famous “indecipherable cipher,” suppose we glance at some of the devices which have been used for doing away with its periodicity. One such device, that of auto-encipherment (autokey, autoclave), has been given its own separate chapter (the one immediately following), not because of its value as a cipher, but because of the very interesting decryptment problem it presents. A second device, the details of which may be examined in Fig. 115, consists in the use of a very long nonrepeating key, the popular name for which is “running key.” The value of such a key, for practical purposes, we have already seen; it was a key of this kind which Castle had used on his five or six cryptogram-beginnings. In single examples, however, it gives more trouble. Unless there is a probable word, its message and key must be dug out bit by bit, and if the encipherment is Vigenère, any recovered fragments can belong equally well to the

message or to the key. However, with its key known to be purely plaintext, no fragments need be considered except those which are usable combinations, and since the “running key cipher” makes a fascinating puzzle, a specimen has been included among the practice cryptograms. The original of this, apparently, was the Hermann cipher. This employed a slide which was identical with the Saint-Cyr slide except that the stationary alphabet carried an extra cell (position) marked “index” to be used instead of the Saint-Cyr index A. As the writer saw this, the index-cell was standing just ahead of A, so that the resulting encipherment would have been that of a Saint-Cyr slide on which the letter Z was serving as index-letter.

Of other devices aimed at destroying periodicity, quite a few have been based in some way on key-interruption. A key-word is selected, as INDEPENDENCE, but the encipherer breaks off before completely using his rotation, so that the completed cryptogram will be enciphered very irregularly by such a key as INDEP INDEPEND I IN INDEPENDENC IND INDEPEN. . . . . . Sometimes this is found as a word-spacing device, the key beginning over with each new word, though naturally not with word-separations showing in the cryptograms. But in the average case, the key-interruption takes place at the discretion of the encipherer; sometimes the agreement with his correspondent allows him to break off as he pleases without any sort of signal, leaving the decipherer to discover the interruptions through the fact that he can no longer decipher; again, he may use an indicator, as J. In the latter case, he must encipher any J’s which may happen to occur in his message by using the I-substitute; then, whenever he decides to break the key, he first enciphers a J. Thus, whenever the decipherer brings out the letter J, he knows that his key is to begin over with the encipherment of the next letter. It will be noticed that in all of these cases, the decipherer will have to do his work one letter at a time.

There is another of these devices which apparently destroys periodicity and is aimed at throwing all of this onerous work upon the shoulders of the decryptor without at the same time punishing the legitimate decipherer. This consists in shortening the two alphabets of the key, so as to leave some extra letter, which will never be used in any cryptogram. Encipherment, in this case, is accomplished in the regular way, producing a periodic cryptogram. The extra letter may then be inserted at points throughout the cryptogram wherever it can do the most harm. The decipherer, knowing that this one letter is always null, need merely erase it. But if this device is to be really useful, the omitted letter must not be always the same, and this trouble can be overcome as follows: In the shortening of the plaintext alphabet, we omit always the unwanted letter, as J. But in shortening the cipher alphabet, we omit first one letter and then another, according to agreement, and insert J in its place. The decipherer, knowing what letter is null, erases it; but the decryptor, granting that he knows what the process is, will still have to experiment with various letters before he learns which one (or more) of the 26 is the null of the moment.

Shortened alphabets are not uncommon in ordinary use. We meet with 25-letter alphabets in European examples, the letter W having been omitted for telegraphic reasons. This case can usually be distinguished from the one which precedes by the fact that the letter W is never found in a frequency count, and it presents only the minor trouble that the ordinary 26-letter slide will not make the decipherments, so that it becomes necessary to prepare another on which the letter W is not present. This case can, of course, be simulated by making use of a 24-letter alphabet.

These devices, taken as a whole, have added little, if at all, to the security of the straight-alphabet ciphers, though, for the most part, they have succeeded admirably in rendering their ciphers totally unfit for general purposes. Considered as single examples, they can, of course, prove troublesome. We trust that this will not be the case with some one or two of the appended practice cryptograms, but if so, we recommend that the student postpone them for a later investigation. Concerning example No. 122, he may find that some of the material presented in Chapter XVI applies also to the “running key” encipherment; with others, a trigram-search may assist in developing the interrupted key-word; and in one case, a clever decryptor should find a way for applying his Kasiski method.

The case of probable words, on the other hand, presents some interesting possibilities inherent in the auto-encipherment itself. When the probable word is short (or if a search is to be made for normally frequent trigrams), the task of bringing out and testing the possible key-fragments is made much less onerous by the fact of the purely plaintext key. Being sure of an abundance of excellent sequences, we need consider none but the very best of the deciphered fragments; and for any one considered, the trials need be made only within a very short range of the spot at which it was found. All of this work may be done directly on the cryptogram. A correct sequence, correctly applied, can be followed out in both directions, and will yield, in full, several of the “columns,” and several consecutive letters of the initial key. But if it so happens that the probable word is longer than the initial key, its first few letters must become the keys for enciphering its last few. Consider, for instance, the word SIMPLICITY, which has a length of ten letters. If the preliminary key contains only five letters, then, beginning at -ICITY, the keys SIMPL- will begin to encipher, causing a certain long cryptogram-sequence which, for Vigenère, will always be A K U I J. If the preliminary key has

six letters, the same word causes a sequence U Q F N when the cipher is Vigenère; if it has seven letters, the cryptogram-sequence will be A B K; and even an eight-letter key brings out one certain digram, L G. Thus, knowing what the cipher is, and having at our disposal any comparatively long probable words, we may write out these sequences in advance and be ready to look for them in the cryptograms. In addition to whatever words we consider probable, it is obvious that any other long word may encipher itself in the same way, and, if it is one important to the subject matter, is likely to be repeated, causing the cryptogram to show a long repeated sequence. Thus, if we find a long repeated sequence in a cryptogram, we are able to try this as a common suffix, TION, MENT, ENCE, ABLE, etc., in the expectation of bringing out some common prefix, CON, PRE, etc.

More fascinating, by far, than its practical aspects, however, are the possibilities presented by the autokeyed cryptogram for analytical attack. The devices immediately to follow are described by General Givierge in his Cours de cryptographie, and are credited by him to Commandant Bassières.

First, it is possible to discover the length of the short preliminary key, or, at any rate, to confine this to certain definite probabilities. This key, as we have seen, governs a definite group-length, or “period.” If this group-length, say, is 5, then, barring the first and final groups, every plaintext letter will be enciphered by the letter standing five positions to its left, and will, in its own turn, serve to encipher the one standing five positions to its right. Since all plaintexts are filled with repeated letters, roughly half of them separated by even intervals, it stands to reason that there will be many occasions on which the letter standing five positions to the left and the one standing five positions to the right will be the same letter. That is, we must often find the encipherment pattern of Fig. 118. Some one letter, as S, is repeated at an interval of exactly twice the group-length, with some other letter, as R, standing at exactly the group-length interval from both of the S’s. The first S enciphers R, and R enciphers the second S. Or, if the repeated letter is T and the intermediate one is L, then T enciphers L, and L afterward enciphers T. Where the cipher is Vigenère, the result, in the cryptogram, is a repeated letter standing at exactly the group-length interval. If the cipher is one of the Beauforts, the same pattern produces a pair of complementary letters separated by exactly the group-length interval.

Now, in order to consider the value of this observation, let us examine the cryptogram of Fig. 119, an autokeyed Vigenère, which, for convenience, is presented in groups of the correct length, 7. According to Bassières, should we inspect this cryptogram for repeated single letters, noting, in each case, the interval of separation, the correct group-length, 7, will be present among those intervals which are noted oftenest, and, in many cases, will be the one which predominates. For making such an examination, perhaps the simplest plan would be that of listing the possible group-lengths at the tops of a series of columns, beginning with group-length 1 and carrying them as far as desired. The counts could then be made by placing a tally mark in the proper column for each time that a given interval is noted. The results of this examination, as compared with the Kasiski examination for a period, may be studied in Fig. 120. At (a), where the leading intervals of our cryptogram have been listed with their frequencies, it is noticeable that the correct group-length, 7, is not represented by the predominating interval or even by the one which is second in frequency; it is merely present among the five leaders. But we find other cryptograms, not necessarily of great length, in which some one letter, as V, will be repeated five or six times in succession at exactly the group-length interval, and its evidence amply confirmed in other repetitions. Then, as at (b),

we may find some fairly good clue, leading us to give the first trial to the correct group-length; and again we are left, clueless, to try out five or six different group-lengths before striking the correct one. Results, then, are variable, and the only certainty, at any rate in a short cryptogram, is that of being able to limit the group-length to a given few. With the group-length determined, or with one selected for trial, we may take our choice of two processes.

Process 1 (Bassières). With group-length 7, as we have seen, our cryptogram includes seven independent series, or “columns,” of letters. By beginning at the 1st letter, and taking the 1st, 8th, 15th, 22d, etc., letters, we may decipher series 1 independently of the others; or, by beginning at the 2d letter, and taking the 2d, 9th, 16th, etc., letters, we may decipher series 2; and so with the other five series. Many persons, before doing this, will rewrite this cryptogram into seven columns, which permits that the decipherment of a series be done straight down its column, and for that reason the word “column” is sometimes used to describe what we have called here a “series.” In order to understand the first of the Bassières processes, we need consider only series 1, it being understood that whatever applies to any one of the seven series applies equally well to the other six.

Now, considering Fig. 121: If the unknown first key-letter was A, then the first plaintext letter, found by deciphering with key A, was L, and this became the key for enciphering the eighth letter. If the key which enciphered the eighth letter was L, then the eighth letter, found by deciphering with key L, was A, and this became the key for enciphering the fifteenth letter. Following out this decipherment to the end of series 1, we find that the plaintext letters must have been L A B R Z Z B, etc., as given in full in the figure. A glance at the complete series will show that this decipherment is not a particularly good one. If another decipherment be carried out, on the hypothesis that the original first key-letter was B, we obtain the series K B A S Y A A, etc., which starts out fairly well, but which, when completed, will contain two K’s, one Z, two B’s, and one P. If a third decipherment be carried out, on the hypothesis that the original first key-letter was C, we obtain the series J C Z T X B Z, etc., which is a poor decipherment from the beginning. A trial and error method might consist in making these decipherments one at a time directly on the cryptogram, erasing one when it is obviously poor, and trying to add the next series whenever one proves acceptable.

The Bassières process, however, consists in setting up the entire 26 possible decipherments as these are shown in Fig. 122. In this figure, the original cryptogram-letters of series 1 are standing in a column at the extreme left. The 26 possible decipherments are also standing in the form of columns, each decipherment headed by the key with which it was initiated. If the group-length 7 is correct, then one of these 26 columns shows the original plaintext letters.

Now let us examine, not the columns, but the rows, of this tableau, and find out just how troublesome it is going to be to prepare tableaux of the same kind for series 2, series 3, and possibly others. The key-letters, across the top, constitute a normal alphabet, and below this each row contains the 26 decipherments for some one letter of series 1. On the odd-numbered rows, the decipherments for the odd-numbered letters are alphabetically arranged, but progressing in a direction contrary to that of their keys, as if these odd letters represented Vigenère encipherment. On the even-numbered rows, the decipherments for the even-numbered letters are also alphabetically arranged, but are progressing parallel to their keys, as if these even-numbered letters might represent variant Beaufort encipherment. Evidently, then, the A-decipherment is the only one which must actually be carried out; afterward, the preparation of the tableau is a matter of extending alphabets. With similar tableaux prepared for the remaining six series, we have seven sheets, and on each one of these there is one column showing the correct decipherment of the series, headed by the correct key-letter. Thus, our solution is to be the mechanical one of the preceding chapter. On each one of the tableaux, the apparently “good” decipherments may be checked for attention; the sheets may be creased between columns, and the “good” decipherments of one tableau may be placed directly in contact with those of another.

Process 2 (Bassières). Fig. 123 shows the second of the Bassières processes. With 7 decided upon as the group-length, we make up a trial key having the right number of A’s, and decipher the cryptogram. The new cryptogram, produced in this way, is periodic, and its period, for Vigenère, will be twice the group-length, in the present case 14. In Fig. 124, where this new cryptogram has been repeated, written into its period, it is possible to check its periodicity: It has two repeated sequences, C J B and W G, at suitable intervals, and while these are very few, their evidence is amply supported by the fact of repeated single letters in every column. When the periodicity is not confirmed in this way, it can be assumed that the chosen group-length was not correct.

The make-up of this new cryptogram is not hard to understand if it is noticed that what we have done is to carry out simultaneously the seven A-decipherments of seven tableaux like that of Fig. 122. We saw there that the odd-numbered letters of a series react as Vigenère encipherment and the even-numbered letters as variant Beaufort. With seven A-decipherments made at once, the same will apply to odd-numbered and even-numbered groups. Thus, our new cryptogram has seven columns enciphered in Vigenère and another seven enciphered in variant Beaufort. The original seven-letter initial key-word will decipher both sets of columns; for the first seven, it must be applied in the Vigenère manner, and, for the other seven, in the variant Beaufort manner.

As to why this encipherment reduces to alternate Vigenère and variant Beaufort groups, this is best understood by resorting once more to the “mathematical” aspects of the Vigenère cipher. In a previous discussion, we have said that Vigenère encipherment consists in the “addition” of key to message, and that variant Beaufort encipherment (which, in Vigenère, would be decipherment), consists in the “subtraction” of key from message. In the beginning, our plaintext is a series of groups, as A, B, C, D, E, etc. and the first encipherment operation consists in the addition of a key, as X, but only to the first group, A. To encipher group B, we add A; to encipher group C, we add B, and so on, so that when the auto-encipherment is complete, we have a cryptogram in which the groups are made up as follows:

Now, remembering what the mathematical valves were for key-letters, the trial key, made up entirely of A’s, is made up entirely of zeros. When we subtract zero from the first group, we leave it unchanged, that is, the first cryptogram group is still A plus X (plaintext plus key, or Vigenère). When we subtract A plus X from the second group, this cancels the A of both, and leaves B minus X (plaintext minus key, or variant). When we subtract this from the third group, we cancel the two B’s, leaving C plus X, again Vigenère. When we subtract this from the fourth group, we cancel the two C’s, leaving D minus X, again variant Beaufort. And so to the end. Always we come out with the original plaintext group plus or minus X, the key. Those groups which are plus X are Vigenère, and those which are minus X are variant. And X, in all, is the same: the original preliminary key. A comparison