Identifying and attacking a proposed cipher (multiple substitution)

Question

I'm just beginning to dip my toes into cryptography and a friend has proposed a cipher and challenged me to figure out how to attack it. I know the process used to encrypt, but am having a hard time wrapping my head around a way to go about attacking it.

The cipher is a simple substitution cipher (26 characters possible, each character directly mapping to one other character) and the text is evidently plain ole English. The complicating (at least to me) factor is that in his process he performs this substitution N times where N is the index of the character.

ex.
plain text = "test"
  alphabet = "abcdefghijklmnopqrstuvwxyz"
       key = "bdfhjlnprtvxzywusqomkigeca" (permutation of alphabet)

plain[0] = 't'                       (1st char subs 0 times, so remains 't')
plain[1] = 'e' -> 'j'                (2nd char subs 1 time, becomes 'j')
plain[2] = 's' -> 'o' -> 'w'         (3rd char subs 2 times, becomes 'w')
plain[3] = 't' -> 'm' -> 'z' -> 'a'  (4th char subs 3 times, becomes 'a')

encoded = "tjwa"

Does this cipher have a name? I'm having a hard time finding one online if it does.

As for attacking it, he has given me a large encoded string (100k+ chars). I wrote up a simple Java program to perform encode/decode given a known key, but 26! keys are too many to brute force. So I looked at the letter frequency and noted that a single letter (in my case 'x') appears a disproportionately low number of times (much closer to it's expected English frequency the the other characters), which leads me to believe that perhaps it maps to itself. But obviously that would still leave 25! keys.

I'm genuinely interested in figuring out other techniques to attack this, and am not asking for a single simple solution, but does anyone have any ideas of other ways to go about attacking it? I know the first letter of the plain text, and possibly the positions of a single other letter, but possible "cycles" or "loops" (sorry, I don't know if there's a better word for this) within the key (a->b->c->a) are thus far stumping me as to how to attack it. I at first thought I'd know every 26th character, but that would only be true if there were no "cycles" created by the key.

Any help/direction/pointers/suggestions would be appreciated. Thanks.

Answer 1

The obvious way to approach this would be to attempt to recover the cycle structure of the permutation, and the first place to start is to attempt to reconstruct the order of each letter.

The "order" of a letter is how many times the permutation needs to be applied to the letter before it turns back to that letter.

To start, you believe that you have the matting x -> x; that means that the order of the letter 'x' is 1.

Let us extend that idea, if we have the mapping e -> w -> g -> e, then the order of the letter 'e' (and 'w' and 'g') is 3.

So, how do we estimate the order of a letter? Well, we start be looking at every 'n'th letter of the ciphertext (that is, positions 0, n, 2n, 3n, etc); if the order of a letter is n (or a divisor of n), then in those positions, that letter will map to itself (and so the character frequency in those positions of the ciphertext will be exactly the character frequency in the plaintext); assuming that the plaintext is English text, it should be fairly straightforward to come up with plausible guesses.

Once you've tried that, and have come up with plausible guesses for the orders of all the letters, we then need to reconstruct the 'cycles' that make up the permutation. The first obvious place to start is to find the element that e maps to; if we have found that the order of e is 3, we can start by looking at every 3rd element offset by 1 (e.g. at locations 1, 4, 7, 10, 13, etc); in those locations, 'e' will encrypt to whatever letter it is permuted to, and so if in those locations, the letter w happens exceedingly often, we can deduce that e -> w is a likely mapping within the permutation.

Those hints should give you a good start...