Break the subsitution cipher with a twist

Question

Breaking news: the NSA can break letter substitution ciphers. (Letter frequency, guessing the word "the", et cetera...) So, let's make our secret code more secure. Let's apply the secret substitution $n$ times to the $n^{\text{th}}$ letter of the message.

Here's an example. Suppose that the secret substitution was "move forward 1 in the alphabet". Then the naive substitution would encode "aaa! aa!" by "bbb! bb!". But our new method encodes it to "bcd! ef!" The same letter gets encoded differently every time. And the substitution needn't be this simple. It could be any permutation of the 26 English letters. Take that, NSA!

Anyway, break this cipher. The plaintext is a poem (not written by me) in plain English. The substitution was chosen uniformly at random from all 26! permutations. The algorithm is exactly as described above. I will give upvotes to partial answers, especially theoretical suggestions for attacking the cipher.

TZTC NQW WEXJLBUE KLTMXFAA TYQQOB COI RAR
SNXPBW QJXJ NRVURDVV UXVS WKKVJNYMMYR XMP XRHNYAKE
MUZX OHI TPHUX BYQSOSRR. URS IRTSRE DYSSICLFD OO FVQXVF
ZAD VATIMDINN MWKKHZS QP JLI AQDE,
JZI GZK IBYUDKWIE TAV RPD NN T MHUU EVU.
FU TXE GDBNQQ KBQPB ZXW ITXZXNVBC DU JLP ZOMHDQFS VDTK FDVEAV
"BTOSZWP," BGZ FY SGP KULGG: EUCNXS
YRI WSAQ ZWYY, LRUDAA TQ VXWM CC URP LFXC
BQFYP MS CIHUFD J GHHFK TCD ADTKIF OHE VCNKIM.


"QJXJ TFAI JR. XIOFK" VYK LFIOUWLTE LMTRDI,
MIUWM DLDQJPVV XVUV ZAI LMNN, UDKIIUXLBXD KZPJ
QMHJDAUIF LVRB QJXJ LVP JUNRXHRHFD AZLB SDHHS
NTX XVUV ZAQIS WVF, EFFPMXBW KOFS MGI MHJW
CTLSSHXKE YMP IJH. QGE XMS VS VVNE ACPQ
LTIY IRRRB QTLK XOSFDOBW BSXV U IYZNSWP,
JHJUMKXWVEJBFLL EMVUP.
GO, XI OXXXS CQA WDPLCTK RGIDV JERY DMJRL ZYRBK;
MIN OGN JWK FMCBD IVIFWNKE QJXJ MUPE IAS M NXVZDDVE VWKLQSW:
KGCG POF AW PAKRR QXDVV IY U KNEZJS?
QVH URI NWQIXI VS YMW LEUL DAUO
XX NQD XEWFYBHH ITJHRNF NE QJB VKLFMQ TJOIYNFD?


RLI OPTOUCY WUCNXP EYQKSW UDP KOOZI
LAF ERIZX FR ODP KTXFKZNW, GZJJNFHF MAHEEHHXO FAXWT,
YCXFTHTOGI KHRVZ KIRRK YNF HGIPI ZZ BZX
MM LTS LPVNGIJJ DECJALE LG TXI OWBXKCC:
SGDAD ENDHJ XDTF TCB MGMKP TIMISTB INQ QAHFTT.
OW RAS HNXXAYQ JKVKBJI Y HEXH, VUW TGYES LSULDCJOTC,
UJW FAFGZC CS RDP WCRH, VYI YJGOKA DYLU RW GZD YBAY;
DAC HLP RPFWD RNHXZAKC CUQWNW,


FKNJEB ZL OGCSCCB CTLUDNVEPI,
XOW BSDRPI GB VUE PYQEOBW.

-- DJYROI, WC IFIRAS PFBJF

Answer 1

Scroll to the end if you just want the answer. I give a detailed explanation of how I reached it.

---

First, I hypothesized that the permutation has two cycles: one of length 9, and one length 17. The length-17 one contains T and R, and the length-9 one contains E. How did I get there?

Look at the string JR. at the start of the second paragraph. That's a peculiar two-letter abbreviation. It could be "Mr." or "Ms." or "Dr.". It tempting to thing that the R maps to itself. If so, it must be in a cycle whose length is a factor of 340, its position. That's 340=2*2*5*17.

I was also struck by the three-letter words TXE and OHE. Wouldn't it be cool if they were THE? The positions are T: 187=11*17, H:323=17*19, and E:324=2*2*3*3*3*3, 189=3*3*7. Isn't the number 17 showing up a lot? It's not a common prime factor.

To check the theory, I took every 17th letter of the ciphertext

LADRHSONEATIHOGYPDHREPIANNFCEYWMOKRIAWDIATTYOKATNLTDMAHCDLRNCPR

Those sure are nicer letters than usual. Which makes sense, since if there were a cycle of 17, then all 17 letters in that cycle would map to themselves in every 17th position, and so take on their natural frequencies.

And taking every 9th letter,

ETQSJUNXUUREDZISEYVUEQZLSABUSWTRYDDEXIITDVNBHRJDSAFSTMMCRSVJEUXCEYNIJSEGAIQIENHNMDCYOITJEWOIIMIEXETIQAJEEOGCOGCRUECERYRA

13.3% of the letters are E, which is totally consistent with the 12.7% in English

In fact, this suggests a general method to find the cycle sizes. To test a cycle-length n, take every n'th letter, and see how well those letters correspond to the English distribution. Here, I measured this by taking the average English-letter frequency of each letter appearing.

As you can see there's peaks at 9 and 17. There are other "overtones" of 9 in its factors or multiples. 18 has the same peak because those letters are a subset of every ninth letter. Every multiple of 3 (shown as vertical gridlines) has 1/3 the peak because 1/3 of those letters are multiples of 9.

Next, I determined approximately what the nine-cycle is. I'm lucky to know the nine-cycle to contain the letter E, the most common letter in the English alphabet. This means that in positions that are 1 mod 9, E is mapped to the next letter in the cycle, and that letter is likely to be the most common letter. It turns out that letter is P. Likewise, the most common letter in positions 2 mod 9 is likely to be two after E in the cycle, and so on.

The gives the claimed cycle EPDKBIDWF. They're similar to the letters in richardb's analysis But they can't be totally right: D appears twice. Though E is the most common letter in English, that might fail to be the case in a random sample of letters, so some of these will be wrong. I guessed that the second D is wrong and replaced it with the filler character *.

Knowing the nine-cycle let me decrypt all the letters that are part of it. This gave:

---- --E FE---E-K I----I-- -----D --E --- 
---WED ---- -----I-- ---- KW*-------- --D ------*D 
---- --E -K--- D-------. --- P----E P---E--ED -- I----E 
--E ---F-KI-- -KW*--- -F --E --KE, 
--D --* WI--EEKEK --- -FF -- - ---- W--. 
K- --E -EP--- II-ED --D F------E- I- --E ----I-E- -E-F KI-P-- 
"D----ED," B-- I- --K B----: I----- 
--D K--- -W--, ---I-- -- --K- -- --E -I-- 
W-E-E -- -E--ED - ---K* --D -E-FED --E ---FE-. 


"---- -I-E --. -I-*E" --* -EI--B--K ----ED, 
-E-E- D-E--I-- ---- --E ----, -EEPE---B-E E-I- 
----E--ED ---K ---- --D --------ED ---E -I--- 
--- ---- ---K- K-D, DEFE--ED *-E- --D ---E 
-------*D --E K--. --D --- -- ---D --E- 
--E- W---D ---* ---WE-ED W--- - K----ED, 
-----W-E-E-DI-- K---E. 
--, -E ----- --- DIK---P --EI- -E-- F---- ---DE; 
-E- --- -IE B--*K I-KIK-*D ---- --IK W-- - ----IB-E -IE---E: 
B--- W-K -E D-D-- --I-- I- - E-B---? 
--- --E -E-I-K -- --E -E-- F--- 
-- --E -IDD-I-- K-----E -F --E -*-E-- ---E--ED? 


--D -I----- I----K P--P-K -IK B---D 
--D D-I-- I- -IK B--*E--P, -----I-K ---EF---- D--W-, 
---K-----K E---- BI--E --D --IEK -- F-- 
-- --- -I---I-- FI----E -- --E -EI-D--: 
--I-K E-E-- -I-E --D ---*K -I-K--F F-- ---I--. 
-E --- ------- -D-EE-F - -E--, --D ---E- ----I-----, 
--D D-E--- -- -IK F---, --E ----D- F--- -F --E -E--; 
B-- --W -IDEK ------*- ---I-K, 


K*--EK -- ------K ----I--EEK, 
--D W-K-EK -E --D D--W-ED. 

-- I----K, B- EDW--- FIE-D

So, there's clearly many things wrong; the K's look off in particular. But, there's segments of recognizable text. Particular useful is the last line, which contains "B- EDW--- FIE-D", which I guessed was "By Edward Field." Perfect, that's the name of a poet! It also means the letters EDWFI are right.

I looked for a word that had lots of those. There was the third word "FE---E-K". The K is surely wrong, and plugging the pattern into a regexp matcher gave the very plausible word "FEATHERS".

Finally, Googling "edward field feathers" was enough to take be to the poem Icarus whose text clearly matched.

Only the feathers floating around the hat
Showed that anything more spectacular had occurred
Than the usual drowning. The police preferred to ignore
The confusing aspects of the case,
And the witnesses ran off to a gang war.
So the report filed and forgotten in the archives read simply
“Drowned,” but it was wrong: Icarus
Had swum away, coming at last to the city
Where he rented a house and tended the garden.

“That nice Mr. Hicks” the neighbors called,
Never dreaming that the gray, respectable suit
Concealed arms that had controlled huge wings
Nor that those sad, defeated eyes had once
Compelled the sun. And had he told them
They would have answered with a shocked,
uncomprehending stare.
No, he could not disturb their neat front yards;
Yet all his books insisted that this was a horrible mistake:
What was he doing aging in a suburb?
Can the genius of the hero fall
To the middling stature of the merely talented?

And nightly Icarus probes his wound
And daily in his workshop, curtains carefully drawn,
Constructs small wings and tries to fly
To the lighting fixture on the ceiling:
Fails every time and hates himself for trying.

He had thought himself a hero, had acted heroically,
And dreamt of his fall, the tragic fall of the hero;
But now rides commuter trains,
Serves on various committees,
And wishes he had drowned.

Icarus, by Edward Field

Answer 2

I'm taking it as given per xnor's analysis that the substitution forms two cycles, of length 9 and length 17.

Suppose W is substituted by a common letter like E; then the first letter is more likely to be W than by chance. Also the 10th, 19th letter... is more likely to be W, and in general wherever the index mod 9 is 1. Unless that is, it is in the 17 long cycle, when the pattern would be locally pretty much random.

For each letter I've calculated the frequency at each position mod 9 and mod 17, and summed the squares to give a crude autocorrelation figure of merit.

Gratifyingly, there are 9 bars that have a good fit, from which I tentatively conclude that the cycles are: ACGHJLMNOQRTUVXYZ and BDEFIKPSW.

The next step could be to try to assign an order to BDEFIKPSW which maximises the overall autocorrelation. With such a large ciphertext, you can get a long way with just maths without bringing in English frequency tables.

Answer 3

Let's assume the frequency analysis done by xnor and richardb is correct, so that the permutation of the alphabet that we are using has a 9-cycle consisting of the list of letters B, D, E, F, I, K, P, S, W (we won't need to assume the existence of a 17-cycle). This means every ciphertext letter on this list corresponds to a plaintext letter on this list, and vice-versa.

For some of the longer ciphertext words, this alone is enough to recover the plaintext, which I determined with a regex dictionary search. For example, the ciphertext JHJUMKXWVEJBFLL can only come from the plaintext uncomprehending. Similarly, UDKIIUXLBXD must come from respectable, and WKKVJNYMMYR comes from spectacular (or spectrogram, but I considered this unlikely).

A Google search for 'poem uncomprehending respectable spectacular' turns up Edward Fields' poem Icarus, which is seen to be a match.

Answer 4

Some mixed minor observations:

• QJXJ appears 4 times, for a 4 letter sequence, that's quite unlikely. So this might be the same word every time.

  Positions are 24, 331, 416 and 620. Distances to the previous occurence are 307, 85 and 204. That might fit to the hypothesis of xnor because 85 = 5 * 17 and 204 = 12 * 17. On the other hand, 307 is a prime, which puzzles me, but it could just imply that the first and the second QJXJ are different words.

• There are 6 one-letter words (T, J, U, M, U, Y) which most likely map to the set (A, I, O) - O is quite unlikely, it's often used in poems, but doesn't appear at the beginning of a sentence here.