TRANSPOSITION SPECIAL SOLUTIONS

Special Exploitable Situations

13-1.

Military forces are rarely equipped to change cryptosystem keys with every message

transmitted. The logistics and management problems of providing enough different

keys and controlling their use are difficult to handle. Normally, keys will be reused for

a period before they are changed. With transposition systems, several special situa-

tions can arise when keys are reused that make a solution possible when the system

might otherwise resist successful analysis. One of these situations arises in columnar

transposition whenever similar beginnings and endings are used with the same width

matrix. The keys do not have to be the same in this case as long as the width is the

same. Another more general situation occurs whenever two or more different messages

of the same length occur using exactly the same keys. Each of these situations is

explained in the following paragraphs.

Similar Beginnings and Endings

13-2.

With columnar transposition, repeated message beginnings or endings can cause an

easily recognizable and exploitable situation. When the same width keys are used and

the beginnings are the same, the tops of the columns in each message will consist of the

same letters. When the length of the repeated beginning is several times as long as the

width of the matrix, these repeated letters are easy to spot.

a. The next two messages demonstrate the techniques that can be used when similar

beginnings are encountered. Repeated segments between the two messages are

underlined.

13-1

(1) There are eight repeated segments in each, which shows that the messages are

each eight columns wide. The repeated segments are not in the same order,

which shows that the two messages use different numerical keys.

(2) Message 1 has 95 letters. Dividing 8 into 95 gives 11 with a remainder of 7. This

means that all but one column must have 12 letters. The distance between

repeats shows that this is true. All segments have 12 letters except for the fifth

segment, which has 11 letters. The fifth segment, beginning IFA, must be the

right-hand column of the matrix.

(3) Message 2 has 92 letters. Four columns have 12 letters and four columns have

11 letters.

(4) All repeated segments contain three letters except for the ASOL segment. The

column beginning ASOL is probably the left-hand column.

(5) As a result of these observations, we can place the first and last columns in each

matrix, and we can separate the middle six columns into two groups of three,

based on the length of the columns in message 2.

(6) Completion of the solution from here is straightforward. Anagram each group of

three columns in each message, and the solution is complete. The similar begin-

ning is ALL REQUISITIONS FOR MEDICAL.

b. Messages with similar endings, such as a repeated signature block, show repeated

segments which represent the bottoms of columns instead of the top. The solution is

approached the same way, except that the text will not necessarily appear in the

same columns in both messages.

13-2

Messages With the Same Length and Keys

13-3.

Whenever two or more messages have the same length and are transposed with the

same keys, they can be solved together. The more messages you find that are the same

length and use the same keys, the easier they are to solve. This technique can be used

regardless of the type of transposition system.

a. Solving messages with the same length and keys is particularly effective with

columnar transposition. The next example shows how the solution can be

approached. The five messages all use the same keys. Their positions have been

numbered for easy reference and to aid in key recovery.

(1) The Q in message 2 in position 1 must certainly be followed by the U in

position 8.

(2) Position 1 must be at the top of a column in the original matrix, since columns

are extracted beginning at the top. Position 8 is also probably at the top of a

column. This applies not just to message 2, but to all five messages. The

position 1 column can be written next to position 8.

(3) Position 2 must be from the second row of the matrix. If position 8 is from the

top row, then position 9 must be from the second row, also. Similarly, positions

13-3

3 and 10 are from the third row. Positions 4 and 11 are from the fourth row. Posi-

tions 5 and 12 are probably from the fifth row, although these are short messages

and there might not be as many as five rows.

(4) Now the task is to find additional columns to add to the fragments already

started. For example, the QU in message 2 should be followed by a vowel, and

the most likely letter after JU in message 5 is N. There are three columns with

an N in message 5, and only one of these, position 19, has a vowel in message 2.

Therefore, we will add columns 19, 20, 21, 22, and 23 to our fragments.

(5) All of the fragments produce good plaintext except, possibly, the last one. QUA

will usually be followed by an R. Of the two columns with an R in message 2,

column 12 provides the best combinations.

13-4

(6) All of the matches give good plaintext, except the fifth set, which clearly does

not belong now. It is easy now to see words to build on, such as ARTILLERY,

QUARTERS or HEADQUARTERS, JUNCTION, SUPPORT, FIVE, and

others. All of these leads are added to the completely anagrammed messages.

(7) The final step in the solution is to recover the numerical keys. Looking at the

beginning, the pattern starts to repeat after seven letters, so the original matrix

was seven letters wide. The numerical key, derivable by observing the order in

which the columns were extracted, was 4275136.

b. The technique of solving messages of the same length and keys can be used with

any transposition system. It can be used as the basis for recovery of more difficult

transposition systems such as large grilles and double transposition. The cyclic pat-

tern of columnar transposition aided the solution of the example above. Given four

or more messages of the same length and keys, however, the complete messages can

often be anagrammed without the help of the cyclic pattern.

13-5