Columnar Transposition - Cryptanalysis

Cryptology

Cryptanalysis of a Columnar Transposition

Example

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Ciphertext

AEIMC TLITN SAAAV TNANO UHISA LPLII LWPTX OONMH WHNFU DUERE
WMRSE ACATA OHSTO MSTAS ESAAD TNART TEOEN SIAAS POVTE EEEMC
SALRI TNSET ROKMA LMAET GEUTS TRORN FHTVO EAAWT GAARN ELLES
TNLGE HSHOC EHSTA AFIHT NNEYL OSRAH SLONI IAFOS EYHTS U

We follow the hypothesis that the ciphertext originates from a transposition of an English plaintext. The frequencies of the single letters support this hypothesis.

Examining Possible Columnar Schemes

The length of the ciphertext is 196. The integer division by assumed key lengths 2, 3, 4, … are

196 = 98 × 2
196 = 65 × 3 + 1
196 = 49 × 4
196 = 39 × 5 + 1
196 = 32 × 6 + 4
196 = 28 × 7
196 = 24 × 8 + 4

and so on.

Key length 2?

Because 196 = 98 × 2 we have to consider two columns of length 98:

   AEIMCTLITNSAAAVTNANOUHISALPLIILWPTXOONMHWHNFUDUEREWMRSEACATAOHSTOMSTASESAADTNARTTEOENSIAASPOVTEEEE
   MCSALRITNSETROKMALMAETGEUTSTRORNFHTVOEAAWTGAARNELLESTNLGEHSHOCEHSTAAFIHTNNEYLOSRAHSLONIIAFOSEYHTSU

Even the first 30 bigrams give cBLW rates of 1.58 and (in reverse order) 1.63 that immediately let us reject the key length 2.

Key length 3?

Because 196 = 65 × 3 + 1 we have to consider one column of length 66 and two columns of length 65. We pick the first and the last 65 letters from the ciphertext:

   AEIMCTLITNSAAAVTNANOUHISALPLIILWPTXOONMHWHNFUDUEREWMRSEACATAOHSTO
   HTVOEAAWTGAARNELLESTNLGEHSHOCEHSTAAFIHTNNEYLOSRAHSLONIIAFOSEYHTSU

Moving the first of these along the ciphertext we get one good cBLW rate:

   ATAOHSTOMSTASESAADTNARTTEOENSIAASPOVTEEEEMCSALRITNSETROKMALMAETGE, cBLW rate: 1.48

This is at position 58, absolutely incompatible with the column lengths of 66 or 65. Therefore we reject this possibility. (In fact if we had started with position 66 as the general method suggests, we hadn't encountered this »solution« at all!)

If we do the same for the last 65 letters we find no cBLW rate greater than 1.72. Thus we may reject 3 as the key length.

Key length 4?

Because 196 = 49 × 4 we have to consider four columns of length 49:

   AEIMCTLITNSAAAVTNANOUHISALPLIILWPTXOONMHWHNFUDUER
   EWMRSEACATAOHSTOMSTASESAADTNARTTEOENSIAASPOVTEEEE
   MCSALRITNSETROKMALMAETGEUTSTRORNFHTVOEAAWTGAARNEL
   LESTNLGEHSHOCEHSTAAFIHTNNEYLOSRAHSLONIIAFOSEYHTSU

We could compare these columns pairwise. But let's consistently follow the general method and pick the first and the last 49 letters. Moving these along the ciphertext we get one good cBLW rate for each, and both of them at impossible positions.

Therefore we also reject 4 as possible key length.

Key length 5?

Integer division yields 196 = 39 × 5 + 1. We have to consider one column of length 40 and four columns of length 39. The first and the last 39 letters from the ciphertext are:

   AEIMCTLITNSAAAVTNANOUHISALPLIILWPTXOONM
   HOCEHSTAAFIHTNNEYLOSRAHSLONIIAFOSEYHTSU

Moving the first of these along the ciphertext we get one good cBLW rate:

   CATAOHSTOMSTASESAADTNARTTEOENSIAASPOVTE, cBLW rate: 1.92

This is at position 57, incompatible with the column lengths of 40 or 39. Therefore we reject this finding.

If we do the same for the last 39 letters we find no cBLW rate greater than 1.77. Thus we may also reject 5 as the key length.

Key length 6?

Integer division yields 196 = 32 × 6 + 4. We have to consider four columns of length 33 and two columns of length 32. The first and the last 32 letters from the ciphertext are:

   AEIMCTLITNSAAAVTNANOUHISALPLIILW
   AAFIHTNNEYLOSRAHSLONIIAFOSEYHTSU

Moving the first of these along the ciphertext we get one good cBLW rate:

   CATAOHSTOMSTASESAADTNARTTEOENSIA, cBLW rate: 1.93

again at position 57, incompatible with the column lengths of 33 or 32. Therefore we reject this finding.

If we do the same for the last 32 letters we find no cBLW rate greater than 1.77. Thus we may also reject 6 as the key length.

Key length 7?

Integer division yields 196 = 28 × 7. We have to consider seven columns of length 28. The first and the last 28 letters from the ciphertext are:

   AEIMCTLITNSAAAVTNANOUHISALPL
   HTNNEYLOSRAHSLONIIAFOSEYHTSU

Moving the first of these along the ciphertext we get two good results:

   CATAOHSTOMSTASESAADTNARTTEOE, cBLW rate: 1.89
   TASESAADTNARTTEOENSIAASPOVTE, cBLW rate: 1.81

The first one is at position 57, perfectly compatible with the column length 28. The second one is at the incompatible position 68.

If we do the same for the last 28 letters we even find two good results:

   AEIMCTLITNSAAAVTNANOUHISALPL, Pos =   1, cBLW rate: 1.84
   AADTNARTTEOENSIAASPOVTEEEEMC, Pos =  73, cBLW rate: 1.80

The first of these occurs at the perfectly compatible position 1, the second one at the incompatible position 73.

Therefore we have a promising finding that is worth of pursuit.

Completing the Solution

The columns we identified as our favorites together yield the constellation:

(7) HTNNEYLOSRAHSLONIIAFOSEYHTSU
(1) AEIMCTLITNSAAAVTNANOUHISALPL
(3) CATAOHSTOMSTASESAADTNARTTEOE

and the remaining columns are:

(2) IILWPTXOONMHWHNFUDUEREWMRSEA
(4) NSIAASPOVTEEEEMCSALRITNSETRO
(5) KMALMAETGEUTSTRORNFHTVOEAAWT
(6) GAARNELLESTNLGEHSHOCEHSTAAFI

We try the possible neighbors of (3):

    (3) with (2) has cBLW rate 1.35 ---> NO
    (3) with (4) has cBLW rate 1.45 ---> NO
    (3) with (5) has cBLW rate 1.87 ---> YES
    (3) with (6) has cBLW rate 1.43 ---> NO

This suggests the extended constellation:

(7) HTNNEYLOSRAHSLONIIAFOSEYHTSU
(1) AEIMCTLITNSAAAVTNANOUHISALPL
(3) CATAOHSTOMSTASESAADTNARTTEOE
(5) KMALMAETGEUTSTRORNFHTVOEAAWT

We try possible neighbors of (5):

    (5) with (2) has cBLW rate 1.91 ---> YES
    (5) with (4) has cBLW rate 1.59 ---> NO
    (5) with (6) has cBLW rate 1.17 ---> NO

Again we have a good continuation:

(7) HTNNEYLOSRAHSLONIIAFOSEYHTSU
(1) AEIMCTLITNSAAAVTNANOUHISALPL
(3) CATAOHSTOMSTASESAADTNARTTEOE
(5) KMALMAETGEUTSTRORNFHTVOEAAWT
(2) IILWPTXOONMHWHNFUDUEREWMRSEA

Finally we try possible neighbors of (2):

    (2) with (4) has cBLW rate 1.95 ---> YES
    (2) with (6) has cBLW rate 1.28 ---> NO

This gives the constellation:

(7) HTNNEYLOSRAHSLONIIAFOSEYHTSU
(1) AEIMCTLITNSAAAVTNANOUHISALPL
(3) CATAOHSTOMSTASESAADTNARTTEOE
(5) KMALMAETGEUTSTRORNFHTVOEAAWT
(2) IILWPTXOONMHWHNFUDUEREWMRSEA
(4) NSIAASPOVTEEEEMCSALRITNSETRO

The remaining column (6) fits at the end only.

Thus we have a solution:

(7) HTNNEYLOSRAHSLONIIAFOSEYHTSU
(1) AEIMCTLITNSAAAVTNANOUHISALPL
(3) CATAOHSTOMSTASESAADTNARTTEOE
(5) KMALMAETGEUTSTRORNFHTVOEAAWT
(2) IILWPTXOONMHWHNFUDUEREWMRSEA
(4) NSIAASPOVTEEEEMCSALRITNSETRO
(6) GAARNELLESTNLGEHSHOCEHSTAAFI

or, written in row form,

  HACKING TEAMISA NITALIA NMALWAR ECOMPAN YTHATSE LLSEXPL OITTOOL
  STOGOVE RNMENTS ASSUMET HATTHEN SAASWEL LASTHEG OVERNME NTSOFCH
  INARUSS IAANDAH ANDFULO FOTHERC OUNTRIE SHAVETH EIROWNS YSTEMST
  HATAREA TLEASTA SPOWERF ILETAOI

Split into words this reads:

HACKING TEAM IS AN ITALIAN MALWARE COMPANY THAT SELLS EXPLOIT TOOLS TO GOVERNMENTS ASSUME THAT THE NSA AS WELL AS THE GOVERNMENTS OF CHINA RUSSIA AND A HANDFUL OF OTHER COUNTRIES HAVE THEIR OWN SYSTEMS THAT ARE AT LEAST AS POWERFUL [ETAOI]

with a padding of 5 letters at the end.

The plaintext is from Bruce Schneier's Cryptogram, July 15, 2014.

Author: Klaus Pommerening, 2014-Jul-24; last change: 2014-Jul-24.