1
$\begingroup$

So the other day, I was piqued by a ciphertext that was trivially encoded through substitution. Solvable only because we can use our eyes to determine word boundary word detection, etc. Trawling the net, there didn't seem to be any automated way of doing this, other than of course to generate a key the size of the alphabets.

How would one go about programmatically decrypting a substitution cipher given that all spaces have been removed?

It seems like there would be multiple runs of frequency analysis on single letters, then double letters, then finding out word boundaries. How would one go about solving this without resorting to a 26-factorial brute-force method?

Improve this question
$\endgroup$
3
  • $\begingroup$ Just thinking out loud, and I bow before the wisdom of others, there should exist a fitness function which uses the plaintext of the applied key as a basis for a search against a corpus of words. Of which, if the entire plaintext is a valid word salad, then it is the sentinel that stops the search algorithm. $\endgroup$
    – user13472
    May 9, 2014 at 10:14
  • $\begingroup$ As a side note, how would one use a markov chain to figure out the word boundaries? $\endgroup$
    – user13472
    May 9, 2014 at 10:22
  • $\begingroup$ Is this homework? If so, it should be tagged as such. Otherwise, you're on the right track: Frequency analysis reveals a lot, but there are other tools. E.g. if you suspect it to be a Vigenere cipher, calculating the autocorrelation also helps (which reveals the keylength, and then it's just a couple of Caesar ciphers) $\endgroup$
    – tylo
    May 9, 2014 at 10:39

3 Answers 3

Reset to default
2
$\begingroup$

I think frequency analysis is the preferred approach for breaking substitution ciphers. The more ciphertext you have, the better it is. My suggestion would be to do the following:

First, you compute two probability distributions:

  • a distribution that contains the probability of the symbols in a reference text of the same language and technical area than then expected message.
  • a distribution that contains the probability of the symbols in your ciphertext.

Once you have these distributions you have a significant knowledge. Instead of trying all possible permutations in brute force, you can now try the most probable ones first. For each permutation, you can check if the probabilities of the symbols in the ciphertext correspond to the probabilities of the symbols in the reference text.

The Kullbach-Leibler (KL) distance is often used to measure the similarity of two probability distributions. You will ideally start your search with the permutation that minimizes the KL distance and then proceed to permutations with a higher KL distance.

For each permutation you then substitute the symbols accordingly and you check if words that frequently appear in your reference text are also found in the decoded text. You keep the best solution which has the most matches, and you continue the search.

The probability to find a better decryption will decrease the longer you search. So you can just stop after some time. You have to decide when exactly the algorithm will stop, but here again you have the probabilites and the KL distance to help you make this decision.

Improve this answer
$\endgroup$
0
$\begingroup$

Eventually though, unless you're doing it through human intervention, there will be instances where a non fully formed word occurs and the program needs to decide on the relevancy of that word. It seems like you'd have to run the plaintext, after a sufficiently far enough iteration of determining the key, through a lexer/parser of some sort and attribute a probability that it is a word or part word. I'm unsure as to whether KL is relevant in a short ciphertext where the distribution isn't representative.

Improve this answer
$\endgroup$
0
$\begingroup$

BTIYLSSH LUK type of substitution cipher in each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet position:0111

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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