Breaking the rotate-then-substitute alphabetic cipher

Question

My question is not typical for MathOverflow, and arises in my teaching rather than research, but I think there will be readers who can give interesting answers.

Identify $\{\mathrm{A}, \ldots, \mathrm{Z}\}$ with $\mathbb{Z}/26\mathbb{Z}$. Define a bijection $R$ on the set of words over $\{\mathrm{A}, \ldots, \mathrm{Z}\}$ by $R(w)_i = w_i + i$ for each $i \in \mathbb{N}$. Thus $R$ shifts the letter in position $i$ forwards in the alphabet by $i$ steps, so $R(\mathrm{TAXIS}) = \mathrm{UCAMX}$, and so on.

Let $\pi : \{\mathrm{A}, \ldots, \mathrm{Z}\} \rightarrow \{\mathrm{A}, \ldots, \mathrm{Z}\}$ be a permutation. Let $S_\pi$ denote the substitution cipher on words over $\{A,\ldots, Z\}$ defined by $S_\pi(w)_i = \pi(w_i)$. A not-too-short ciphertext $S_\pi(w)$ can easily be deciphered using frequency analysis.

The cipher $ R^j S_\pi$ (with unknown $\pi$ and $j$) can be broken in at most $26$ times the work required to break $S_\pi$, by trying each value for $j$. My question, raised in T. Körner's 'The pleasures of counting', is on the other possible composition. Even when $j=1$ this seems harder to break.

How, using any modern mathematical or computational techniques, can one decipher a single ciphertext $S_\pi R(w)$, given that $w$ is a message in English? How long a ciphertext is required?

One obvious strategy is to take every $26$th position of the ciphertext. These have all been enciphered using the same permutation, so frequency analysis will be effective. But while the probability distribution on letters agrees with English, no English words are enciphered: how does this affect the required length of ciphertext?

Answer 1

As you point out, frequency analysis will yield (for cipher texts long enough, say longer than Shannon's unicity distance) a non-English text which has been transformed from English via the position dependent transformation $R$.

But I think a differential analysis can break this with not too much extra effort. If you see letter $Z_t$ at position $t$ and letter $Z_{t+1}$ at position $t+1$ etc. of the ciphertext, for unknown $t$ they must be consistent so $$P_{t+k}=R_{i+k}^{-1}(Z_{t+k})\equiv Z_{t+k}-i-k~(\mathrm{mod}~26)\quad k=0,1,\ldots$$ must hold for some fixed unknown $i$. Thus inconsistencies with the posited $i$ can be discovered quickly with high likelihood.

A shortcut might be to encode a list of high probability English trigrams (THE, THI, AND,...) under the different possible $i$ and look for those trigrams in the text and check for the consistency of estimated $\hat{i}$ for the occurring trigrams with respect to the positions they occur at.

How much more overhead these methods will incur has to be more carefully analysed.

Answer 2

Guess this is not too helpful, but hope it is ok to make a remark. Suppose instead of an alphabet of $N=26$ letters, we consider general $N$, and $N$ is very large. Suppose we are dealing with the ciphertext $S_{\pi}R(w)$. Since $R$ is known we may do $R^{-1}$ on the ciphertext and we get $R^{-1}S_{\pi}R$ of the plaintext. In the unlikely event that a low (relative to $N$) power of $\rho=(12\dots N)$ commutes with $\pi$, that is, $\rho^{-m}\pi\rho^{m}=\pi$ for some $m$ that is small relative to $N$, then we only need to do frequency analysis with every $m$-th position instead of every $N$-th position. But admittedly we don't know a priori what $m$ is.