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?



Breaking the rotate-then-substitute alphabetic cipher
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.


