1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ Thanks for the suggestion/hint. I'm not sure I understand fully, but I'm going to give it a shot. $\endgroup$ – silentAitch Dec 8 '17 at 14:07
  • $\begingroup$ Thanks again. A question about the second part of your suggestion. It appears that I have 3 cycles in play. (Length 1, Length 11, and Length 14). (It is possible that there are 2 cycles of 7 rather than 1 cycle of 14, but I'm not sure). Anyway, you say to review the n+1 positions to find the next letter transform (and I suppose I could extend that to the n-1 positions to find the preceding transform), but how would that work when there are 11 possible (likely) values at pos n? I'm a bit confused would you mind elaborating? I'm not looking to be spoonfed, just seeking to understand. Thanks. $\endgroup$ – silentAitch Dec 11 '17 at 18:28
  • $\begingroup$ @silentAitch: I will assume that 'e' is a part of the cycle 11. Then, look at the statistics at locations 1, 12, 23, 34, ..., 11n+1; in each of those locations, an 'e' in the plaintext will transform into the next letter in the cycle (so if the transform is e -> w, then 'w's will be quite prominent. Then, look at the statistics in locations 2, 13, 24, 35, ..., 11n+2. In those locations, an 'e' in the plaintext will transform down two letters in the cycle (so if the transform is 'e -> w -> g', then 'g's will be quite prominent. Continue until you're recovered the entire cycle $\endgroup$ – poncho Dec 11 '17 at 19:02
  • $\begingroup$ Thanks for the clarification. I was mentally stuck on looking for characters in the N+1, N+2.... positions that matched expected English frequency, when in fact I needed to be looking for consistent outliers. After wrapping my head around that I was able to decrypt enough to get probably plain text, and used that to complete the key. Thanks again. $\endgroup$ – silentAitch Dec 12 '17 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.