Manual / Guide · 1941
Military Cryptanalysis, Part IV: Transposition and Fractionating Systems
SIS training text, Part IV (112 pp)
Manual / Guide · 1941
SIS training text, Part IV (112 pp)
Resl1 ir:ted ~-.-====~~.~AB~D~~o~nmn~~====~~=tl!_ · Ii I I MILITARY CRYPTANAIXSIS I omcs m TD CBJBP BIGKAL OIPl\3ll WM1m19l'Oll u PART IV iL.-- •·;;;==========~·_J;;JJ . . .._.. ••4'!1"11+.t- - WW 11 Restrieted WAR DEPARTMENT OFFICE OF THE CHIEF SIGNAL OFFICER WASHINGTON MILITARY CRYPTANALYSIS Part IV TRANSPOSITION AND FRACTIONATING SYSTEMS By WILLIAM F. FRIEDMAN Principal Cryptanalyst Signal Intelligence Service PREPARED UNDER THE DIRECTION OF THE CHIEF SIGNAL OFFICER UNITED STATES GOVERNMENT PRINTING OFFICE WASHINGTON 1941 MILITARY CRYPTANALYSIS, PART IV. TRANSPOSITION AND FRACTIONATING SYSTEMS Section The Golden Guess Is Morning-Star to the full round of Truth -Ttnn111on CONTENTS Paragraphs Pages I General_ -------------- ------------------ ---------------------------------------------------- ------------- ---1-3 1-2 II Solution of sunple transposition ciphers--------------------------------------------------------------- 4-11 3-17 III Incompletely-filled rectangles ____ ------------------------------------------------------------------------- 12-16 18-36 IV Opportumties afforded by studymg errors and blunders made by enemy cryptographers --- 17-19 37-39 V Special solutions for transposition ciphers___ __ _ ---------------------------------------------------- 20-29 40-79 VI Pnnmples of matrix reconstruction _______________ -------------- ___ ------------------------ ------- 30-31 80-84 VII Solution of grilles___ ------------------------------------------------------------------------------------------ 32-34 85-93 VIII Combmed substitutmn-transposition systems ------------------------------------------------------ 35-36 94-96 IX Solution of the ADFGVX system..·---------------------------------------------------------------------------- 37-43 97-143 X Solution of bifid fractionatmg systems ----------------------------------------------------------------- 44-56 144-184 XI Analytical key --------------------------------------------------------- --------------------------------------57 185 Index ----------------- -------- ___ ------------------------------------------------ ----------- __ -------------------- 186-188 (III) SECTION I GENERAL Paragraph Introductory remarks concerning transposition ciphers Basic mechanism of transposition ciphers Monophase and polyphase transposition __ 1 - ----- -- 2 3 1 Introductory remarks concerning transpoSltlon ciphers -a As stated ma prevtous text, transposition ciphers are roughly analogous to "Jigsaw puzzles" m that all the pieces of which the origmal is composed are present but are merely disarranged The pieces mto which the picture formmg the basis of a Jlgsaw puzzle may be divtded are usually qmte irregular m size and shape, the greater the amount of irregularity, as a rule, the greater the difficulty m rea.ssembhng the pieces m proper order In this respect, too, transpoSition ciphers are analogous to Jlgsaw puzzles, for the greater the amount of dIStortion to which the plam text lS subJerted m the transposition process, the more difficult becomes the solution b In Jigsaw puzzles there is usually no regularity a.bout the size of the mdiv1dual pieces mto which the origmal picture has been cut, and this feature, of course, materially contubutes to the dllficulty m reconstructmg the picture There are, to be sure, llIDlts (dictated by conSiderations of practicability) which serve to prevent the pieces bemg made too small, for then they would become unmanageable, on the other hand, there are also llIDlts which must be observed m respect to the upper magmtude of the pieces, for if they are made too large the puzzle becomes too easy to solve These features of Jigsaw puzzles also have their analogies m transposition methods In the latter, if the textual units to be subJected to transposition are made qmte large, say entire sentences, the difficulties a cryptanalyst will have m reconstructmg the text are practically ml, on the other hand, if these textual umts me made quite small, even smaller than smgle letters, 1 then the reconstruction of the transposition text by a cryptanalyst often becomes a very difficult matter In between these two extremes there may be various degrees of fragmentation, limited only by considerations of practicability c It is fortunate, however, that the cryptanalyst does not, as a rule, have to contend with problems m which the size of the textual umts varies withm the same message, as is the case m Jigsaw puzzles It is perhaps possible to devise a transposition system m which the text is divided up m su<.,h a manner that entire sentences, whole words, syllables, mdividual letters, and fractions of letters form the units for transpoSition, but it is not difficult to rmagme how impractical such a scheme would be for regular commumcation, and it may be taken for granted that such irregularity m size of te:i>.tual umts will not be encountered m practical commumcation d The days \\hen the S1IDple methods of word transposition were sufficient for military purposes have long smce passed by, and it IS hardly to be expected that cryptograms of such meffectual nature will be encountered m the military commumcations of even the smaller armies of today However, m time of emergency, when a counter-espionage censorship is exercISed over mternal commurucations, it is posSible that isolated mstances of simple word transposition may be encountered The solution of such cases should present no difficulties, unless numerous code names and nulls are also used m the cryptograms Mere experimentation with the cryptograms, trymg various types and sizes of rectangles, will usually dlSclose the secret text If code names 1 Reference 18 here made to so-called fractionating systems Cryptography, sec XI (1) See SpecJ.&l Text No 166, AdWJnced Military 2 are used and the context g1ves no clue to the identity of the persons or places mentioned, it may be necessary to wait until add1t1onal messages become available, or, lacking such a poss1b1hty, there ts usually sufficient JUstificat1on, under the 0X1gencies of war, to compel the correspondents to reveal the meanmg of these code names e Although transposition ciphers, as a general rule, are much less complex m thc:tr mechamcs than a.re subst1tut1on ciphers, the cryptanalyst usually expenences a feel mg of distaste and dlSmay when confronted with unknown ciphers of this category There are several reasons for his d1Shke for them In the first place, although transpos1t1on ciphers are admittedly less mtncate than subst1tut1on ciphers, as a general rwe there are not nearly so many cryptanalytw tools and "tncks" to be used m the solution of the former as there are m the latter, and therefore the mental strmwus and satisfaction which the cryptanalyst usually denves and regards as part of the reward for his hard labor m solvmg a cipher is often rmssmg m the case of transpoSition ciphers In the second place, despite therr lack of complexity, the solution of transpos1t10n ciphers often mvolves a tremendous amount of time and labor most of which commonly turns out to be frwtless expenmentat1on Thirdly, m modern military commumcation, transpos1t1onmethods are usually not employed alone but m conJunction with substitution methods-and then the problems may become difficult mdeed, for usually before the subst1tut1on can be attacked it is necessary first to uncover the transposition Fmally, m workmg with transposition ciphers a much higher degree of accuracy m mere mechaD.Ical operations is requrred than m workmg with substitution ciphers, because the accidental omission or addition of a smgle letter will usually necesSltate rewntlng the work sheets applymg to entrre messages and starting afresh Thus, this sort of work calls for a constant state of concentrated attention, with its resulting state of psycholog1cal tenSlon, which takes its toll m mental wear and tear 2 Basic mechamsm of transposition ciphers-a Basically,all transposition ciphers mvolve at least two processes (1) Wnting the plain-text umts (usually smgle letters) w1thm a specmc reglliar or irrPgular two-drmensional design called a "matnx," "cage," "frame," "rectangle," ef.c , m such a prearranged manner that the said umts are dIStnbuted regularly or irreglliarly throughout the vanous cells or subsections of that design, (2) removmg the plam-text umts from the design m such a prearranged manner as to change the ongmal sequence m which they followed one another m the plam text, thus producmg cipher text Smee the first process consists of mscnbmg the text withm the design, it IS techmcally referred to as the process of inscription, and Slllce the second process collSlsts of transcr1bmg the text from the design, it is techmcally referred to as that of transcription Either or both processes may be repet1t1ve, by prearrangement of course, m which case the mtermed1ate steps may be referred to as processes of rescription, or rescriptwe processes b It is hardly necessary at this pomt to g1ve the student any md1cations as to how to differentiate a transpo81t1on from a substitution cipher If a review is necessary, however, he is referred to Section IV of Military Cryptanalysis, Part I 3. Ko:p.ophase and polyphase transposition -a As may be mferred from the foregomg defimtions, when a transpos1t1on system mvolves but a smgle process of mscnpt1on, followed by a smgle process of transcnption, the system may be referred to as monopkase transposition, commonly called single transposition When one or more rescnptive processes mtervene between the ongmal lllScnption and the final tre.nscnpt1on the system may be referred to as polyphase transposition As a general rule, the solution of the latter type is much more difficult than the former, especially when the succesSlve transpo81tlons are theoretically correct m p1mc1ple b Any system which is swted for monophase transpo81t1on is also usually swted for polyphase transposition, the processes of lll8cnpt1on, rescnption and transcnpt1on bemg accomph~hed with the same or with different keys SECTION II SOLUTION OF SIMPLE TRANSPOSITION CIPHERS Paragraph Simple types of transpo'l1tion__ The prmciple~ of solution of umhteral route-tranopo-1t1011 c1pheri:. ----- -- -------- -- -- -- -------- - ------ -Keyed columnar tran'lpO'l1t1on ~1th completelv-fi.lled rectangles -- - - - - ---- ----- ----- - Example of solution _ ------ _ _ ---- -- ------ -- _ ------- -- -- ----- ------------ ---------------- --------- - ------ ---· The probable-word method of solution _ ___ ------------------- ----- ------------------------------------ ----- ----General remarks on bOlution -------- ------------ --- ---------------------- ----------------------------- - - ---- - ---- --Reconstruction of literal key --- ____ ----------- -- _ ----------- ---- ----- ------------- ------ ------ ---Column and row transposition - --- -- ------ --- -- ------- _ --- ----- -- - ----- -------- - -- -- -- ------ --- 4 5 6 7 8 9 10 11 4 Simple types of transposition -a The sunple cases of reversed wntmg, vertical wntmg, or rail fence wntmg hardly reqmre senous attention, smce they may be solved ahnost by mspect1on These methods are mcluded here only because they may be encountered m censorship operations b The low degree of cryptographic secunty afforded by these methods may be mcreased to a shght degree by addmg nulls or by disgmsmg the ongmal word lengths, and regroupmg mto false words or mto groups of regular length c Some examples of these simplest types of transposition follow Let the message be BRIDGE DESTROYED AT ELEVEN PM (1) Reversmg only the words and retammg ongmal word lengths Cipher___ E G D I R B D E Y 0 R T S E D T A N E V E L E M P (2) Reversmg only the words end regroupmg mto false word lengths Cipher__ E G D I R B D E Y 0 R T S E D T A N E V E L E M P (3) Reversmg the whole text and regroupmg mto fives Cipher ___ M P N E V E L E T A D E Y 0 R T S E D E G D I R B (4) Reversmg the whole text, regroupmg mto fives, and msertmg a null m every fifth position Cipher___ T R I M M P N E V P E L E T A A D E Y R 0 R T S L E DE GU DI R BM (5) Wntmg the text vertically m two columns and takmg the reswtmg digraphs for the cipher text, as shown at the side The cipher message becomes EEDDE , or B S R T I RDOGY B I GDS R YDR D E E T 0 E BS G y BR ID GE DE ST EE DD R 0 y E E D RT I R D 0 These srmple types can be solved merely by mspect1on 5. The pnnciples of solution of unihtera.l route-transposition ciphers-a The so-called umhteral route-transpos1t1on methods are next to be exammed The solution of cryptograms enciphered by these methods lS a matter of expenmentmg with geometnc figures, usually rec(3) 4 5 angles, of various drmensions suggested by the total number of letters in the message, then nspectmg these rectangles, searching for whole word~ or the fragments of words by readmg honzontally, diagonally, vertically, spirally, and so on 1 (See Special Text No 165, Elementary Mil'/Jary Cryptography, 1935, pars 20, 21) b The amount of experrmentation that must be performed m the solution of ciphers of this type may be matenally shortened by means of formulae and tables constructed for the purpose But because ciphers of thIS type are of mfrequent occurrence today, these formulae and tables are only occasionally useful and hence they have not been mcluded m this text 2 6 Keyed columnar transposition with completely-filled rectangles -a In practical cryptography, the drmens1ons of the transpos1t1on rectangle, as a general rule, cannot vary between large lrmits, that IS, it can be assumed m practice that rectangles based upon Imes of wntmg contammg less than 5 letters or more than 25 letters will not commonly be encountered If the width, that is, the number of columns, is determmed by a key, then the number of rows becomes a function of the length of the message to be enciphered If the latter is very long, longer than can be convemently handled without too many errors, it is a common practice to break up a message mto two or more parts and treat each part as though it were a separate commumcabon Such parts are commonly termed sections b When the last row of a transposition rectangle IS completely filled, the solution of the resultmg cryptogram IS considerably more srmple than when this is not the case 8 Consequently, thIS wtll the constitute first case to be studied c In solvmg a cryptogram of this type the first step taken by the cryptanalyst is to ascerlam the drmens1ons of the rectangle Clues for this are usually afforded by findmg the factors of the total number of letters m the cryptogram Suppose the cryptogram contams 152 letters The drmens10ns of the transpos1t1on rectangle may be 4X38 or 8X19, by wlnch is meant that four hypotheses may be made with respect to its drmens1ons The rectangle may consist of (1) 4 columns with 38 rows, or (2) 38 columns with 4 rows, nr (3) 8 columns with 19 10wq 1 01 t4) 19 columns with 8 rows In practical work it is rather unlikely to encounter a rectangle that conforms to hypothesIS (1) or (2), and f01 the present these may be discarded As to choosmg between hypotheses (3) and (4), a rather simple test to be described presently will di.,clm.e which is the more probable d It is obvious that if the cryptogram is transcribed w1thm a rectangleofthecorrectdimens1ons , the letters m each row will be the ones which actually were m those rows m the origmal , transpos1t10n rectangle and formed good plam text therem In fact, the rows of letters in the correctly-dimennoned rect,angle would read p'lain text were 1t not for the transposition which they have undergone within the rows Therefore, the rows of a correctly-dimens10ned rectangle are more hkely to manifest the expected vowel-consonant proportions of normal plam text than are the rows of an mr01rectly-d1mensioned rectangle, because m the latter case there are brought mto some of the 10ws letters which belong to other rows and which are hkely to dISturb the normal vowel-consonant proport10ns of plam text That is, m an mcorrectly-dimensioned rectangle some of the rows will have too many consonants and not enough vowels, m other rows this relationslup will be reversed, whereas ma correctly-dimensioned rectangle each row will have the proper number of vowels and consonants Hence m solvmg an unknown cryptogram of this type, If a count i<1 made of the vowels and consonants m the rows of rectangles of various probable drmens10ns, that rectangle m. which the rows show the best proportions of vowels and consonants 18 most likely to be correct, and the one that should be tried first e Havmg ascertamed the correct drmens10ns of the rectangle by the foregomg procedure, the next step is to expenment with the columns of the rectangle, trymg to brmg together several columns which wtll then show "good" digraphs, tngre.phs, or polygraphs m the rows formed by Juxtaposmg the columns This process of combmmg or matchmg columns m order to bmld up these fragments of plam text will heiem be referred to as anagramming' f The procedure is to select a column which has a good assortment of high-frequency letters and find another column which may be placed before or after the selected column to bmld up high-frequency digraphs m the rows, when such a pair of columns has been found, attempt is made to add another column before or after th1~ pair to bmld up high-frequency tngraphs, and so on, gradually butldmg up longer and longer polygraphs until entire words begm to appear m the respective rows of the rectangle In this process of anagrammmg, advantage may be taken of simple mathematical considerations such as adding the normal plam-textfrequency values of the digraphs m the rows to assist m discardmg combmat10ns whlCh are on the borderline of choice However, it must be noted that the totals obtamed by srmple addit10n of the frequency values of 1 It is mterecitmg to observe that Damel, of Biblical fame, wao; apparently the first cryptanalyst m history (as well as one of the earhe'!t mterpreters of dreams), for he solved the cryptogram m the "handwr1tmg on the wall," obtammg as his decipherment words which he mterpreted as predictmg the downfall of Belshazzar and his dynastv (Damel V 1-28) The followmg partial account of the episode is not as enhghtemng as one might wish, but it is probably the best explanation available It is taken from Dr Max Sehgsohn's article on the sub· Ject m The Jewish Encyclopedia, vol fl, pp 490-491 (1925) "MENE, MENE, TEKEL, UPHARSIN crci1n i,pn Km IOD) Words written by a mystenous hand on the walls of Bel<Jhaz:rar's palace, and mterpreted by Dame] as predictmg the doom of the Kmg and his dynasty The mcident is described as follows Once when Kmg Bel'lhazzar was banquetmg with his lords and dnnkmg wme from the golden vessel'! of the temple of YB WH, a man's hand was seen wntmg on the wall certain mvstenous words Frightened bv the apparition, the Kmg ordered his astrologers to explam the mscnption, but they were unable to read it Damel was then summoned to the Royal Palace, and the Kmg promISed hrm costly presents if he could decipher the mscription Damel read it "Mene, mene, tekel, upharsm," and explamed it to mean that God had "numbered" the Kmgdom of Bel'lhazzar and brought it to an end, that the Kmg had been weighed and found wantmg, and that his Kmgdom was divided and given to the Medes and Persians The first question which presents itself to the cntic, namely, why <'ould the mo;cription be deciphered by Damel onlv--engaged the attention of the TalmudISts, who advanced vanou'! an'!wers Certam of them concluded that the Hebrew writmg had been changed m the time of Ezra, so that even the Jews that were found m the royal court could not read an mscnpt10n wntten m archaic characters But those who follo\'1-ed R Simeon m mamtammg that thP wntmg had not changed found other solutions for the problem, e q 1t wa'! written m the crvptograph10 combmation 111:1 nic, eaoh letter of each pair bemg substituted bv its compamon e g tlDn 2i1 1,K ntl' ntl', or the words were written thu'I yii,n 'DPD l:IVlDD, one abovP the other, havmg to b~ read vertically, or 'lll"la'2 npi, Cl:llC cmc, each word backward, or agam, 1'1:1"1111 i,np acm ICDJ the first two letters of each word bemg transpo&ed {Sanh 22a) It 1s evident that the author of the Book of Damel meant that the mscnpt10n was written m characters fam1har to the Kmg and wise men of Babylon, but that, as often happens with ancient mscr1ptions, the transpos1t1on of certam letters baffled every attempt to decipher them " 1 See Lohr, Lenox R and Fnedman, Wiiham F, Formulae for the solutwn of transposition ciphers Riverbank Pubbcat1on No 19, Geneva, lllmo1s, 1918 1 See Special Text No 165, Elementary Military Cryptography, 1935, Sec V In this text the term "transpos1t1on rectangle" will be used to designate the matnx, frame, cage, or design regardless of whether the latter is completely filled or not I I I i 1 t L 'The Standard D1ct1onary defines the \\Ord anagram as follows "(noun) 1 The letters of a V'tord or phrase so transposed a<;; to make a different \\Ord or phra-;e, as, 'time' and 'mite' are anagrams of 'emit' 2 <\ tran<;;pos1t1on, mterchange" As a verb, 1t 11> defined as "to anagrammat1ze, to make an anagram of, make anagrams" (The construction of anagrams was a very \'l-1despread pastime m prev1ou<1 centunes See Wheatley's Of Anagrams, London, 1862) A strict mterpretation of the \\Ord would therefore confine 1t to cases wherem the letters to be rearranged already form bonafide words or mtelhgible phrases However, this \\ould hardlv be broad enough for crvptanalytic purposes As used m cryptanalysis the word 1s commonly employed as a verb to refertotheprocess of rearrangmg the disordered letters of cipher text so as to reconstruct the original plam te'\t 6 7 the digraphs should be considered only as rough approximations or gmdes in weighing probabilities m favor of one hypothesis as agamst another, for theoretically the probability of the srmultaneous ocrurrenre of two or more independent E>vents 1s the product, and not the sum, of their respective probabilities In most rases the calculat10n of products involves an amount of labor unwarranted by the results to be expected, so that simple addition of probabiht1es i~ usually ~ufficient However, if tables of the logarithms of the probabilities are readily available, the addition of these loganthms becomes a srmple matter and affords a more acrurate gmde m select10n of combmations produced m the anagrammmg proces~ 5 Once a ~et of four or five column~ has been correctly assembled 1t 1~ u~ually the case that the process may be rompleted very qmrkly, for with the placement of earh rolumn the number of remainmg columns possible for selection drm1mshes, toward the close of the p1ocess, when only two or three columns remain, their plarement is almost automatic g It is desirable, as a final step, to try to reconstruct, if possible, the literal key from which the numencal transposition key was denved 7 Example of solution -a Given the followmg cryptogram, the steps m solution will be set forth m detml CRYPTOGMM (126 letteii:.) B m figure 1 is studied, it is not so easy to say at once that it is rmprobable For in 18 letters there should be about 7 vowels and none of the rows of th.is arrangement shows too great a departure from this expected number Th.is poss1bil1ty will have to be explored further and it If it be assumed that the message was mscnbed vertically m the 1s for the moment put aside rectangle 18X7 and the rows subJected to transposition, there should be (7X40 percent=2 8) 2 or 3 vowels 10 each column But smce several of the columns show rather considerable departures from this expected number, it may be concluded that a vertical inscnphon and honzontal transcription 1s not probable and till& assumpt10n may be elrmmated Then the arrangement& at C and D m figure 1 are studied m the same manner, with the result that at the encl of the study the s1tuat1on as regards the vu.nous assumptions is summ8nzed as follows T I E 0 E UDHT S 0 N S 0 0 E E E E I TN NV U T L B F A E D F 0 Y C A P D T RIV NL RNRWE T U T C U V RAU 0 0 0 F D A UP 0 LR S 0 M T N FRAN F MN D MA S A F A T IL H HD RHNEA R T GE T 0 EF TR RR I I A 0 NAJ I YE CF X A b The cryptogram contains 126 letters (factors of 126 2, 3, 6, 7, 9, 14, 18, 21), suggestmg rectangles of 7X 18 or 9X 14 If the former dimensions are taken, the rectangle may have 7 rolumns and l810ws or 18 rolumns and 7 rows, if the latter dimensions are taken, it may have 9 rolumns and 14 iows or 14 columns and 9 rows The fartors of 126 do not, of course, preclude the possibility that the 1ectangle may be 6X21, that is, with 21 columns and 6 rows or 6 column., and 21 rows If no good results were obtained by testmg rectangles of the dimensions mdicated (7X18 or 9X14), then one would proceed to test rectangles 6X21 In the event that all tests on the basis of a completely-filled rectangle failed, then it would be assumed that the rectangle mav be incompletely filled In making the vowel-consonant test described m paragraph 6d, it is advisable to base the count on the columns as well as on the rows of a rectangle, smce it is possible that the cryptogram was prepared by mscnbmg the plam text m rows and transcl'l.bIDg the text from the columns, or vice oersa After exammmg a rectangle both honzontally and vertically, it is often possible to discard vanous arrangements without further tests For example, at A m figure 1 there is shown a rectangle of 7 columns a.nd 18 rows Now m a row of 7 letters there should be (7X40 percent=2 8) either 2 or 3 vowels, but rows 12 and 15 contam no vowels at all and rows 8 and 9 contam 5 vowels, row 16, 6 vowels It 1s concluded a.t once that this arrangement 18 highly improbable If the plam text had been mscnbed vertically m this same rectangle, and then the rows had been transposed m forming the mpher text, then m each column (18 letters) there should be (18X40 percent=7 2) a.bout 7 vowels, but column 2 contams 11 vowels and column 6 only 4 This likewise md1cates that it is highly improbable that the message was mscnbed vertically wd the crvptogram formed by transposmg the rows But when the arrangement at 1 A suggestion for which the author is indebted to Mr .\ W Small, Jumor crvptanah -.t m this office The pnnc1ple makes practtcahle the use of tabulatmg machmery for the purpose of <ipeedmg up and fac1htatmg tl>e matching of columns m the anagramrmng process 8 9 Rectangle 7 X 18 0 z 7 x 18 7 columns and 18 rows {l) Horizontal mscription, columnar transcription _______________________ Very improbable (2) Vertical mscription, horizontal transcription__ _ _________________ Very improbable 18 columns and 7 rows (3) Horizontal mscription, columnar transcription _____________________ Possible (4) Vertical mscription, horizontal transcription__ ___ __ __ ------ _ Improbable ~ I 0 NT T UM 1 1 2 3 2 3 4 L 0 NR C P A H E V R U 0 S 4 5 6 UT DL F F F 12 D R F R D R X 13 H R 0 N A A R 14 T H Y R 0 N T 15 S N C W N F G 16 0 E A E A M E 17 N A P T J N T 18 S T D U I D A 11 Number of} 7 11 vowels -- 6 6 10 4 I E S E T T B Y R N T A A P T MF X L 0 0 E R NF C I L UU0 0 NNAR HE NE R NAAI R T 0 NL F DT T H U S I H V E P A N C 0 A R R MY G DDOONUDDRRUOJSAAEE T H 0 E E T F T I WV F I 0 N S C T I T E F A L 0 R V E R D U MF A F A 2 3 0 E A V 0 T E E F E N 0 N C 9 10 x7 18 HEUIVLA 5 DETIRRF 6 TELAASA 7 I I BRU0 T 8 E 0 F I 0 MY 4 7 Number of} vowels --- 2 4 4 6 2 1 3 2 4 2 1 5 5 2 1 2 3 2 B 7 1 9 x 14 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 J 4 5 6 I S T BRTAT F L 0 R F I U0 NA HNR AI T NF T HS HE ACARY D0 NDR UJ AE T 0 E F I VI NC I E A0 VRUF F E E T Y N A P MX 0 E NC L U0 NR E E NAR 0 L DT U I V P N 0 R MG D0 UDR 0 S AE H E T T WF 0 S T T F L R E D MA A Number of} 6 vowels - 10 c Discardmg all assumptions except (3) and (5), the latter are subjected to further scrutmy Suppose the average amount of deviation from the expected number of vowels m each row is calculated by findmg the difference between the actual and expected numbers m each row, addmg these differences (neglectmg signs), and dividmg by the total number of rows For assumptions (3) and (5) the results are as follows ., ~ '"il 18 A 1 Rectangle 9 X 14 9 columns and 14 rows (5) Horizontal mscuption, columnar transcuption_ ____ _ ______ Possible (6) Vertical mscription, horizontal transcription__ _____________ --- Improbable 14 columns and 9 rows (7) Horizontal mscription, columnar transcription __________ __ ------ Improbable (8) Vertical mscription, horizontal transcription____ __________________ Very rmprobable J 0 5 7 7 3 2 5 2 4 4 4 5 4 4 4 3 5 2 3 14 1 1 2 3 4 5 6 7 8 9 Number of} vowels 2 3 4 5 6 x9 7 5 FIGURB l 9 10 11 12 13 14 I E 0 F N E T N T 0 U N MC 6 L U0 T NDR L CF P F AF 3 HDE R VF R R UD0 R S X 3 HHE RU0 I NVAL AAR 7 DT E HT YI RR 0 R NF T 4 T S E N L C A WA N S F A G 4 I 0 I E B A R E U A 0 M T E 10 E N 0 A F P I T 0 J MN Y T 6 0 S E T ADVU0 I T DE A 8 4 3 9 2 2 4 4 D c 8 2 553152 2 3 4 5 6 7 8 9 x7 10 11 ~ c; .. ~ U 14 M W " R I E S E T T B Y R N T A A P T MF X L 0 0 E R NF C I L UU0 0 NNAR HE NE R NAAI R T 0 NL F DT T H U S I H V E P A N C 0 A R R MY G DD0 0 NUDDRR U0 J S AAE E T H 0 E E T F T I WV F I 0 N S C T I T E F A L 0 R V E R D U MF A F A i 6 9 6 7 9 6 8 .. all ,g § == .8'i l!l<cl .."p,., A 1 2 1 8 1. 2 .2 1 8 1. 2 8 Total deviation=8 2 Average deviation=l 2 FIGURE le 10 11 I 2 3 4 5 6 7 8 J 1 I S T BR T AT F 2 2 L 0 R F I U0 NA 5 3 H NR A I T NF T 2 4 HS HE ACAR Y 4 5 D0 NDRUJ AE 4 6 T 0 E F I V I NC4 7 I E A0 V RUF F 5 8 E E T Y N A P MX 4 9 0 E NCL U0 NR 4 10 E E N A R 0 L D T 4 11 U I VP N 0 RM G 3 12 D 0 U D R 0 S A E 5 13 H E T T W F 0 S T 2 14 T F L R E D M A A 3 1 6 1 4 1 6 4 4 4 1 4 4 4 4 6 1 4 1 6 6 Total dev1ation=12 6 9 Average deviation= 2 A s -- -----0 Q__________ o_______ -- 41 6 8 41 2 41 u E__________ 11 N N__________ '' "'~ ii; i1 A s ___ ----J 0 --------I p E__________ 0 E __________ L E__________ R ! __________ s 0 --------- 0 E__________ M F---------- 7 6 "" A T__________ 47 u __________ 0 37 N T_-- ----- 82 A c__________ 14 J u__________ I 2 25 31 14 37 13 28 15 25 1 v_____ ---- u R__________ p A__________ 23 3 37 30 15 3 0 u__________ L o__________ R o__________ s o__________ 0 F---------M D__________ 1 lil"' ::;.El 7 8 ~~ g~ 7 "" A T_____ ---- 47 0 N_ - N F ___ - - A R_______ J A____ I N 9 A F__________ 0 A__________ N T__________ 77 9 44 A y __________ J E__________ I c__________ 75 u F_- --- 1 u F__________ p M -- - ---- 4 p 0 N_ -- L D -- - -R M_ _________ s A_____ ---0 s ___ ------ M A__________ Total_ _____ 371 TotaL __ 262 t'<l<D " C'" ..."~ ~~ §.Ol 7 p, t' t' ~~ g ... (4) (3) (2) (1) "O 9X14 1 (The frequencies shown are as given m table 6, appendix to Military Cryptanaly8i8, Part I) x__________ 0 R__________ 77 9 9 24 14 36 L T__________ R G__________ s E__________ 0 T_________ M A_ -------- ... "" 4 7 82 12 2 22 1 0 64 8 7 49 19 36 Total_ ___ 313 Total_ ___ 427 FIGURE 2 FIGURE If The average amount of deviation for assumpt10n (5) is only O 9 as agamst 1 2 for assumption (3), therefore the former assumpt10n 1s considered to be somewhat better than the latter and it will be tried first d The columns of the rectangle shown m figure If are now to be cut apart and the procedure of anagrammmg apphed (For this it is best to have the cryptogram written on cross-section paper preferably with ~'-mch squares for ease m handlmg) Consider column 7, with the letter J m row 5, this letter, if it is a part of a word, must be followed by a vowel, which ehmmates columns 1, 3, 4, and 5 as possibilities for placement on the right of column 7 Here are the digraphs formed by combmmg column 7 with columns 2, 6, 8, and 9, respectively, and the totals obtamed by addmg the frequency values of the digraphs formed m the rows Combmat10n (3) gives the lnghest frequency value for the digraphs and an attempt is made to add a column to it Here are some of the combmat10ns tried 7 8 I 7 8 2 7 8 3 7 8 9 A T I A T S A T T A T F 0 NL NF H ARH J AD I NT UF I P ME 0 N0 L DE RMU S AD 0 S H MA T 0 N0 NF N AR S J A0 I N0 UF E P ME 0 NE L DE RM I S AO 0 S E MA F 0 NR NF R ARH J AN I NE UF A P MT 0 NN L DN RMV S AU 0 S T MAL 0 NA NF T ARY J A E I NC UF F PM X 0 NR LDT RMG S AE 0 S T MA A FIGURE3 e Each of these combmations shows at least one "impossible" trigraph and several "poor" ones 6 After more or less work along these Imes, the crypta,nalyst begms to get the feehng that "somethmg is wrong," for, as a rule, once a correct start has been made m cases of this kmd, solution comes rather qmckly Hence, the cryptanalyst decides here that possibly his first • Followmg the steps taken m subpar d, frequency weights may be given the various trigraphs m fig 3 and the sums obtamed taken as mdicat10ns of the relative probability of each of the four trials These steps are here omitted, for they are obvious 13 12 choice of combmation (3) was a bad one, even though it gave the grC'atest total when frequency values for the digraphs were summed The second greatest total was fo1 combmation (2) m which columns 7 and 6 were put together The mfrequent digraph J U suggests a word such as JUST or JUNCTION Ifi t wei e the former there should be a column conta.mllig an S m the 5th row, and there is no such column If the word is JUNCTION, there should be a column contammg an N m the 5th row, and there is only one such column, the 3d Placmg column 3 after columns 7-6 gives the trigraphs shown m figure 4-A All of these tngraphs are excellent except the last, and that one may be either an abbreviation of a signature, or possibly nulls added to complete the rectangle If the word JUNCTION is correct then there should be a column with a Cm the 5th row, but none is found However, column 9 has a C in the 6th row, and if it happened that the last column on the nght is No 3, then column 9 would be the 1st column Thus, as shown m figure 4-B, the arrangement of columns becomes 9 763 3 9 A T T 0 UR N TR A C H J U N I VE UR A PAT 0 UN L 0 N R 0 V F A 7 6 s 0 u 0 F T MDL FIGUBll: 4-A T ? ' ? ? 7 6 3 AT T OUR NT R AC H J U N I VE UR A P A T 0 UN L 0 N R 0 V T y E c F x R T G E T A s 0 u 0 F T MDL FlGVl!.11: 4-B 9 1 6 2 8 ' 7 6 3 F I R S T B A T T A L I 0 N F 0 U R THINFANTR YHASREACH EDROADJUN C T I 0 N F I V E FIVEFOURA XENEMYPAT ROLENCOUN TEREDALON G U N I MP R 0 V E DR 0 A D S 0 U THWESTOFT ATEFARMDL FlGVBll: 5 f It is beheved that the procedure has been set forth with sufficient detail so as to make further demonstration unnecessary The rectangle can be completed very qwckly and is found to be as shown m figure 5 g It will be mterestmg to see if a calculation based upon the sum of the loganthms of the probab1ht1es given m figure 2 would have given the correct combination as the first choice Note the results shown m figure 6 Tlus calculation gives the correct combmation as first choice, viz, 7-6, with a logarithmically-weighted value of 17 35 as agamst a value of 16 51 for combmation 7-8, which was the first one tned on the basis of merely the sums of the frequency values of the digraphs ( 1) (2) a t' Ii!§ 7 2 J ~-: p., (3) .,"' l ~§ 7 6 ~-: p., 1 61 78 90 1 61 30 1 61 1 04 1 36 48 1 57 48 1 18 48 00 Total ___ 262 13 40 Total ___ 371 != A T_____ _ 7 ..:i A T _____ _ A Sr----- 41 0 Q____ _ 6 N N___ _ 8 A s ____ _ 41 J Q____ 2 I Q___ - 41 U E __ _ 11 p E_____ _ 23 0 E____ _ 3 37 L E ---R r_ ____ _ 30 s o_____ _ 15 0 E ___ _ 3 M F _____ _ 1 t' i!j 47 37 N T____ _ 82 A C______ 14 J u_ -2 I V ____ _ 25 u R_ ____ _ 31 p A ---- 14 0 u___ _ 37 L 0 __ _ 13 R 0 ___ _ 28 s o____ _ 15 0 F _____ _ 25 M D ___ _ 1 1 67 o u____ _ 8 47 O N_____ 77 N F_____ _ 9 A R_ __ 44 J A___ _ 1 I N___ _ 75 U F_____ _ 1 p M_ ____ _ 4 O N____ _ 77 L D ___ _ 9 R M__ _ 9 S A __ _ 24 o s_____ _ 14 M A __ _ 36 1 57 1 91 1 15 30 1 40 1 49 1 15 1 57 1 11 1 45 1 18 1 40 00 17 35 Total ___ 427 j 7 A F_____ _ 0 A_____ _ 95 N T_____ _ 1 64 A y _____ _ 00 J E_ --1 88 I C____ _ 00 U F____ _ 1 67 1 89 60 p x.. ---1 89 95 95 1 38 1 15 1 56 j II 0 R _. L T____ _ R G_____ _ S E____ _ 0 T____ _ M A_____ _ 4 7 82 12 2 22 1 0 64 8 7 49 19 36 16 51 Total ___ 313 0 60 85 I 91 1 08 30 1 34 00 -1 00 1 81 90 85 1 69 1 28 1 56 13 17 FlGUBll: 6 As a mattet of interest, it may be observed that the combination 7-6 is 7 times more probable than combmat10n 7-8, smce the drlfeience between 17 35 and 16 51 is 84, which is the logarithm of 7 Likewise, combmat10n 7-6 is roughly 15,000 times more probable than combmation 7-9 smce 17 35-13 17=4 18 ' 8 The probable-word method of solution -a The probable-word method of attack is as important m the solution of transpoSit1on ciphers as 1t 1s m the solut10n of substitution ciphers and if the cryptanalyst is able to assume the presence of such probable words as a.re usuan;. encountered m military commumcat1ons, the solution, as a rule, comes very qwckly b As an illustration, lookmg at the first row of letters m the rectangle shown m figure lj the letters I S TB RT AT F almost at once suggest FIRST BATTALION as the imtial words of th~ message A rearrangement of the columns of the cryptogram to bnng the necessary letters mto Juxtaposition at once discloses the key Thus 9 1 5 2 8 ' 7 6 3 FIRSTBATT AL I 0 N It will be noted that this assumption reqwres that there be a column headed by F A, another headed by I L, another headed by R I, and so on Had such columns not been found, then the word BATTALION would not be possible In that case the word FIRST would still remam as a pomt of departure for further expenmentation c In the foregomg illustration, the probable word was assumed to appear m the first hne of text m the rectangle If the probable word bC'mg sought ism the mtenor of the message the steps must be modified somewhat but the basic prmciple remains unchanged The modifications a.re of course obv10us 9 General remarks on solution.-a In solvmg transposition ciphers advantage should be taken of all the characteristics and id1osyncras1es which are applicable to the language of the 324155--41-2 14 15 enemy, because they often afford clues of considerable assistance to the cryptanalyst In all languages there are certain letters, usually of medmm or low frequency, which combine with other letters to form digraphs of high frequency For instance, in English the letter H is of medmm frequency, but it combmes with T to form the digraph TH, which is of highest frequency m literary text, it also combmes with C, a letter of medmm frequency, to form the fw.rly frequent digraph C H The letter V is almost in the low-frequency category yet it combines with E to form the digraph VE, which in military text is the 14th m frequency The low-frequency letter K often combmes with C to form the digraph C K Consequently, in workmg with transposition ciphers m English, when there is an H, attempts should be made to combine it first with a Tor with a C, a V should be combined first with an E, a K should be combined first with a C, and so on b There is usually m every language at least one letter which can be followed by only a certam other letter, formmg what may be termed an obligatory sequence, 01 an invariable digraph In all languages havmg the letter Q, the combmation Q U constitutes suc,h an mvariable digraph 7 In bonafide words of the German language the letter C is never used by itself, when present the lette1 C lb mvariably followed by an H, except on rare occasiom. when the digraph C K is employed In English, the letter J can be followed only by a vowel, the letter X can only be preceded by a. vowel and, except at tho end of a