How to determine which type of transposition cipher I have?

Question

I have some ciphertext that I have determined using frequency analysis to be most likely encrypted using a transposition cipher, as the letter frequencies are similar to plain English language text. I believe the next step should be to determine which transposition cipher it is, but I don't know how to do that.

Am I right to assume that what I have is definitely a transposition cipher? And if so, how do I determine which transposition cipher it is?

For what it's worth, here is the ciphertext I have. But (as asking for decryption of a specific ciphertext would be off-topic here) I'm interested in general techniques that could be applied to any ciphertext.

CTCRAL TYNIH ORFLN NLONH LTOWH SLINI IIEER NOENT AHRNE NWAAM CTEAK ERDHH
DMIOD AEINA YTFEI IEINM FSTGI UOVED GLMEI YINEE EYNGS BSCRA TUVGU UEIEV
OHIDA TISRO IEEEA TETMG RSFHD DHARA ICSEU EVHNS WIYII YIRND TFVCX GSMVL
IUELH RETRG NNREC ONEYI OTLUN SBRSH AIIEE TTOOI ESCLS KWSLE ETGHN EOTNU
STGIM EEACR TAEEN LAPEH RHNHE GWIEH EWRNN UETHT EPREN SDNFW YUFGI TUEAY
ETLMR TBIPW UPANI OEFUS RSEAT NRTDP RENOA EETIL HNNAD HECWD TTILI UECDT
DTLAM RQERS MVVTR HYTYO UFOAM ONCNS NFSST EEVHA YHERE OEONM RE- GAO HCVLO
COIYT HSENZ FAHHL LYRII USBAS IEHEO IOSOT TILAI EOGOT ETEHL DEENP AEISP
IDDMT RHNBI EEEMO NTIOE ISGZE SEAEE IDLNI TRTTD RIDUT PTNIY NIYNQ MMMIR
BDAOI AYDOT DTELG HAIHO BDESA RSYLN HNWCN TRLRE NTAMN AESEI EHAEY NHGMO
REFOT TFTUP AEREE HTONG OISHT TVEHO MSEFO OLINE TOLET SOATR AERTC TGEGT
STTNA ONNTG OHAIA TYUOT IIARN TENCO TKGAU TSEHH EIBWO SDTUW INDTR UECHC
RSEAT DEOEW ENWFA ELGKM

Answer 1

However how do I determine which transposition cipher I would need to use? Am I right to assume this is definitely a transposition cipher also?

As you found out that the ciphertext has a similar frequency to the English letter frequency. This can lead to lots of possibilities

1. It can be a shift cipher, that is the generalization of the Caesar cipher $$c = m + k \bmod 26.$$ In the Caesar cipher, the $k=3$ is fixed. There are at most 26 candidates to test, not so far.

2. It can be a permutation cipher, that is there is a permutation $\pi$ on the alphabet that permutes the letters. The 1000 years old frequency attack work on this. You need to swap the top three letters and try to reveal some other. Since you have a long message this should be working very well. Actually, the substitution cipher is also a permutation cipher.

3. It can be any of the transposition ciphers since they are keeping the letter frequency, too.

   1. Rail fence cipher

      Try some possible rail lengths. It is a very weak cipher. The below is the Rail Fence histogram with rail size 3. This is exactly the same as Moby Dick's frequency since the letters are not permuted, just the positions changed. The same applies other transposition ciphers since they just transpose.

2. Scytale

   The cylinder size cannot be too long. try some possible sizes.

3. Route cipher

   Row size and route to read the letters are required. Don't expect the road to be too complex. Set a row size and test for well-known routes. spiral inwards.outwards, clockwise/anticlockwise, starting from the top right/top left, bottom right/ bottom left, etc.

4. Columnar transposition

 Guess the column size and look for digrams to determines the permutation on the columns.

5. Double transposition

   This is hard to attack, it takes the result of the column transposition and applies another transposition. Still, we have computers, and once can test all values up to some limit and check for the string in the decrypted text. Linux's strings command can be helpful to distinguish those.

6. Myszkowski transposition

   Just a modification of the Columnar transposition that deals with the reoccurrence of a letter in the key. Increases the key space a little bit.

7. Disrupted transposition

8. Grilles

   This is one of the hardest ones in this series since the attacker needs to form the grille. Gaines book's chapter is advised. It has some variants.

We don't expect combinations since the combinations can hide the frequency.

4. Vigenère cipher

   It is not expected to be Vigenère cipher, however, the Kasiski test can be used to test.

Online Tools

• Crypto Tools 2
• dCode.xyz
• boxentriq

---

I also did;

The light gray is from the Moby Dick text, the medium grey is your text. In a bar, a light grey on the top means that moby dick has a higher frequency, a medium grey on the top means that your text higher frequency, a sample Python code, and Moby Dick is here.

From here we can simply say that it cannot be Caesar or Shift Cipher since the frequency is very close to the real English frequency!.

Answer 2

If the single character frequencies in your ciphertext indeed approximately match typical English letter frequencies — i.e. if the mix of letters is about 13% E, 9% T, 8% A, 7.5% O, 7% I, etc. — then you can indeed be fairly sure that you're dealing with a pure transposition cipher.

(If the frequencies are a bit off, but still look plausible for natural text — with lots of vowels and a few common consonants — then you might be dealing with plaintext written in some other language, or with specific recurring words — such as spelled-out numbers — that are throwing off the letter counts. Similarly, if one normally rare letter like X or Q appears unusually often, but the letter frequencies look right if you exclude that letter, the plaintext might be using that letter as a word or sentence separator. In general, don't get too hung up on small mismatches or a few outliers; if common English letters like E, T, A, O, I, N, etc. appear anywhere near the top of the sorted frequency list, it's worth at least suspecting a pure transposition.)

Now for the good news and the bad news:

• The bad news is that there's no general way to solve a transposition cipher other than by trying different ways of shuffling the ciphertext and seeing if the results look like plausible plaintext.

• The good news is that 1) you can automate the testing for "plausible plaintext", and 2) it's not necessary to get your initial shuffling order exactly right — even a partial match is often a useful starting point.

For automating the plaintext recognition, we can make use of the fact that adjacent letters in English (and any other natural language) plaintext tend to be highly correlated: certain pairs of adjacent letters, like "TH", appear far more often than one would expect if the letters were randomly shuffled.

A useful statistical tool for finding and measuring such deviations from randomness is Pearson's chi-squared test. In particular, if we just want to compare a bunch of different reading orders of the same ciphertext and see which one looks most plausible, we can compute the $\chi^2$ test statistic for each order and list the ones with the highest result.

For example, here's a fairly generic Python routine I just wrote to calculate the $\chi^2$ statistic for a list of letter pairs:

def pair_chi2(pairs):
    """
    Calculate the chi-squared statistic for a sequence of pairs, under the null
    hypothesis that the elements in each pair are independent. The higher the
    result, the better one element of a pair is as a predictor of the other. The
    input sequence is only iterated once, so it may be a generator.
    """
    from collections import defaultdict

    count = defaultdict(int)
    left_margin = defaultdict(int)
    right_margin = defaultdict(int)
    total = 0

    for a, b in pairs:
        count[a, b] += 1
        left_margin[a] += 1
        right_margin[b] += 1
        total += 1

    scale = 1.0 / total
    chi2 = 0.0

    for a, n_a in left_margin.items():
        for b, n_b in right_margin.items():
            observed = count[a, b]
            expected = n_a * n_b * scale
            chi2 += (observed - expected)**2 / expected

    return chi2

Now, an often useful starting point can be to try taking pairs of letters $n$ positions apart in the ciphertext, for different values of $n$, and using something like the routine above to calculate the $\chi^2$ test statistic for each sequence of such pairs, something like this:

length = len(ciphertext)
results = []
for offset in range(1, length):
    pairs = ((ciphertext[i], ciphertext[(i + offset) % length]) for i in range(length))
    chi2 = pair_chi2(pairs)
    results.append((chi2, offset))

The reason why this is a useful is that, while the exact procedure of taking every $n$-th letter of the ciphertext (and wrapping around at the end) isn't a very common decryption method as such, quite many common transposition ciphers do end up placing at least a large fraction of consecutive plaintext letter pairs the same distance apart in the ciphertext.

Depending on the type of cipher you're dealing with, this may work very well or basically not at all. If it doesn't work, you'll just have to try other kinds of permutations of the ciphertext. However (spoiler!) for your sample ciphertext it turns out to work exceptionally well.

---

For example, if we apply the code above to your sample ciphertext (after removing any spaces and punctuation) and list the 10 offsets with the highest $\chi^2$ values, we'll see something like this:

Offset 667: X^2 = 1224.005399
Offset  74: X^2 = 1224.005399
Offset 549: X^2 =  942.194191
Offset 192: X^2 =  942.194191
Offset 255: X^2 =  908.591098
Offset 486: X^2 =  908.591098
Offset 604: X^2 =  871.545349
Offset 137: X^2 =  871.545349
Offset 360: X^2 =  845.234315
Offset 381: X^2 =  845.234315

There's two things to note here:

• First, note how the offsets appear in pairs that have the same $\chi^2$ value and which each sum to 741 — i.e. to the number of letters in the ciphertext. That makes sense, since negating the offset modulo the length of the ciphertext is equivalent to reversing the ciphertext, and just results in reversing the letters in each pair. And since the statistical test we're using doesn't care about what the most common letter pairs in its input are, but just about how much their frequencies differ from what would be expected in randomly shuffled text, reversing the pairs doesn't affect the calculated test statistic at all.

• Second, note how the top two offsets stand out, with a $\chi^2$ value 30% higher than the next pair of offsets. This suggests that we may, in fact, be on to something.

The next step is to try to naïvely decrypt the ciphertext, just by starting with the first letter and taking every $n$-th letter modulo the length of the ciphertext, for each of the highest ranked offsets $n$. This isn't likely to give us the correct plaintext, but it might give us fragments of it.

So let's do that:

Offset 667: X^2 = 1224.005399   "CNATSMUCRITNEDIVELAICTYREVASIERGNIHTYKCIAOHDEREWSNLHGUOHTSEMTAMTIYLLUFYIOPOTMEESNARTSYREVTITENOOTTHGHYFITUBGNIOUOYTFIHSU..."
Offset  74: X^2 = 1224.005399   "CEASTSATHOMFHEIRBREAKTDIGESTINGYDOFQUIETLAHOURINSTENFTYMILESAISTWARDATFEREFLYINGWAGENTLEMENDMIDDLEAGEOTISTHATTWIEANDHENC..."
Offset 549: X^2 =  942.194191   "COEITIPTEOLTTEUGEUCRTASIRNCRTTRETNROITGTDHOOAAHUCSETSETGLTCNEHGIPEONPDNENIEOSNNSOIIRCENIHTZPVTENMOOPAEIENSEURBRSDNNAHEII..."
Offset 192: X^2 =  942.194191   "CNATLORFAEROFRTGCYERARTIILAGRUWWTOOCGLVIHOTSUBIEATTNTAARTNLIEHAUAHIWAAYGRURRLOECRNERSOHHEEONOTHTAEYDATFEISDMELVSNBHEHHHO..."
Offset 255: X^2 =  908.591098   "CNEWHNALITRTYTTVROHHTRIUNEITDDUOIHTENARPSFEESTERANSOTSAEOTISPACZORNHUTARTDDOGRHTSAICHRUTHTCHBRPLLPMCTBIPNELUITEHHGTHICOO..."
Offset 486: X^2 =  908.591098   "CREEOBGRETANTSAORTHNOWFIOGNTHNIENESTSERNCTEAOUTEEYSNISPARNITRTEOEEIHARAOIAERVVEFCMRANGYENULEAGDSTAUOLLOREONEOLCEIGNIHAYN..."
Offset 604: X^2 =  871.545349   "COTPRETDOCUURSRRIOIDLOTLCTFTPEEYMOIFNISNHUCOTZQEMSOISRRHSNNIHQVRDOEOELROEVEEBRNUUOITCAEUBRWOFHIERARTYTSUNLEWWEELTMRYMRTM..."
Offset 137: X^2 =  871.545349   "CENRDNFOIEHHIALWWBGORTMEAEGAIIEDOIIWRSNEFZSWEOTIANIFTHEAHHMANSNPTFADYBEEEEEOEXPEAEELSYNIIENAYHEVGKVSTOOINTBEEVRNUSRERETT..."
Offset 360: X^2 =  845.234315   "CTCIHFUUGUONEHEIWNTTNAERBCEOEAHEEWARLENIRIYTHNPOOHTTCGCNSLEETDDONNAOLNTRDDOARLTPOROUOOREISMETAOGNMSTACRISIRECTRETONTHHGF..."
Offset 381: X^2 =  845.234315   "CULHHIIAGTSRTEHNRORNHEEEAERTGAITEEEGTOHNOHUFOYDIZHTIARSBSSUCOHAYHPGNTLARNENCRRIAEPVIRIIAESUNSTEVWANTPOPITNVRSEAALITYEEIT..."

Now, most of those outputs are pretty much just gibberish, but take a closer look at the output for offset 74, with some spaces added by hand to highlight recognizable English words (or fragments of them):

"C EAST SAT HOM F HEIR BREAK T DIGESTING YDOF QUIET LA HOUR IN S TEN FTY MILES AISTWARD AT FERE FLYING W AGENT LEM END MIDDLE AGE OT IS THAT TWIE AND HENC..."

Clearly that's still scrambled a bit, but it's not completely scrambled any more. We can definitely make out pieces of the plaintext — honestly even more than I expected.

This suggests that, whatever the actual encryption method is, it's something that tends to leave consecutive plaintext letters 74 letters apart in the ciphertext. At this point, it might be useful to just try breaking the ciphertext into 74-letter chunks and print them out:

CTCRALTYNIHORFLNNLONHLTOWHSLINIIIEERNOENTAHRNENWAAMCTEAKERDHHDMIODAEINAYTF
EIIEINMFSTGIUOVEDGLMEIYINEEEYNGSBSCRATUVGUUEIEVOHIDATISROIEEEATETMGRSFHDDH
ARAICSEUEVHNSWIYIIYIRNDTFVCXGSMVLIUELHRETRGNNRECONEYIOTLUNSBRSHAIIEETTOOIE
SCLSKWSLEETGHNEOTNUSTGIMEEACRTAEENLAPEHRHNHEGWIEHEWRNNUETHTEPRENSDNFWYUFGI
TUEAYETLMRTBIPWUPANIOEFUSRSEATNRTDPRENOAEETILHNNADHECWDTTILIUECDTDTLAMRQER
SMVVTRHYTYOUFOAMONCNSNFSSTEEVHAYHEREOEONMREGAOHCVLOCOIYTHSENZFAHHLLYRIIUSB
ASIEHEOIOSOTTILAIEOGOTETEHLDEENPAEISPIDDMTRHNBIEEEMONTIOEISGZESEAEEIDLNITR
TTDRIDUTPTNIYNIYNQMMMIRBDAOIAYDOTDTELGHAIHOBDESARSYLNHNWCNTRLRENTAMNAESEIE
HAEYNHGMOREFOTTFTUPAEREEHTONGOISHTTVEHOMSEFOOLINETOLETSOATRAERTCTGEGTSTTNA
ONNTGOHAIATYUOTIIARNTENCOTKGAUTSEHHEIBWOSDTUWINDTRUECHCRSEATDEOEWENWFAELGK
M

Still doesn't look too readable, does it? That's because we're supposed to be reading it vertically, column by column. To make that easier, let's try transposing it to swap the rows and columns:

CEASTSATHOM
TIRCUMSTAN
CIALEVIDEN
REISAVERYT
AICKYTHING
LNSWEREDHO
TMESTHOUGH
YFULLYITMA
NSEEMTOPOI
ITVERYSTRA
...

That looks almost readable, exact that the leftmost column (i.e. the first 74-letter line of ciphertext before transposition) seems to be misaligned when compared to the rest. Can you see why, and how to fix it?

This appears to be a 10-column ragged columnar transposition cipher (with no key — the columns are just written out from left to right in order!). But since the plaintext length of 741 letters is not a multiple of 10, the first column ends up being one letter longer than the rest. Adjusting the splitting so that the first column comprises the first 75 letters of ciphertext, rather than 74, gives the following plaintext (middle portion omitted for brevity):

 CIRCUMSTAN
 TIALEVIDEN
 CEISAVERYT
 RICKYTHING
 ANSWEREDHO
 LMESTHOUGH
 ...
 IFTYMILESA
 NHOURINSTE
 ADOFQUIETL
 YDIGESTING
 THEIRBREAK
 FASTSATHOM
 E