I am working on teaching myself basic cryptography. In the process I created a simple substitution cipher based on a single alphabet, and a statically defined offset (no key for now). Now that everything is working, I want to start on another application to "crack" the offset. The key here is my cipher removes all spaces, so I can't judge the length of the individual words.

To solve this issue I would like to use regular expressions. I would then take parts of the (possibly) deciphered message and query a word list to determine where the words start and end.

Is this a good way to do this?

I know there are only 26 possibilities for the offset in my simple cipher. However, I would like to find the answer programmatically.

  • 2
    $\begingroup$ On most UNIX systems, there is a standard word list at /usr/share/dict/words. It's newline-delimited with one word per line. Is that what you need? I admit I am somewhat confused about what exactly you're looking for. $\endgroup$
    – Reid
    Dec 5, 2013 at 4:57
  • 1
    $\begingroup$ Wait, are you trying to recover the plaintext and replace the original spaces? $\endgroup$ Dec 5, 2013 at 11:43
  • 2
    $\begingroup$ You know, regexps are pretty useful for many things, but not too often for cryptanalysis. I'm somewhat reminded of that silly Jamie Zawinski quote here... $\endgroup$ Dec 5, 2013 at 12:58
  • $\begingroup$ This question appears to be off-topic because it is about finding resources for document processing, with no relation to cryptography. $\endgroup$ Dec 5, 2013 at 15:34
  • $\begingroup$ @Ilmari Karonen You may be on to something, maybe a machine learning algorithm for word prediction will work better. But additional ideas were asked for as well. So if you have a better way to score possibilities feel free to add it as an answer $\endgroup$
    – Jackie
    Dec 6, 2013 at 16:15

2 Answers 2


The simple shift sounds like a Ceasar Cipher.

The simplest crack for this is probably frequency analysis. The most common letter in the English language is E. Count your letters, and guess your shift based on that.

If you want to make it better, you could get the X most common letters in your cipher, calculate what you think the shift is, and compare that to known letter frequencies in English, like ETAOIN SHDRLU. The frequency guess that differs the least (with the lowest edit distance) is probably your candidate.

You can also judge how good the resulting text is by using bigram and trigram frequency tests.

You may also find some of the methods described in these books helpful: http://www.nsa.gov/public_info/declass/military_cryptanalysis.shtml

UPDATE: It sounds like what you're actually trying to do is detect when you've decoded your ciphertext. You don't necessarily need to match the words in a dictionary to do that.

The above mentioned methods should work quite well, especially if you start using bigram and trigram frequency.

If you get to the point where you need a more sophisticated method to detect when your text is decrypted, I suggest asking on Stack Overflow, and also telling them what your current approach is, and why it's not working for you.

Note that regular expressions are not useful for what you have in mind. A Markov chain would be a much better tool, especially since it can be used to predict where a word has ended and a new word has started.

  • $\begingroup$ True, but if I am doing it through programming without human review I need to interface with a dictionary somewhere. I know it is extremely easy to decode it manually. Also it does not have spaces so that makes it a tad more confusing which is why I was thinking regex $\endgroup$
    – Jackie
    Dec 6, 2013 at 16:17
  • 1
    $\begingroup$ Ah, so you are programmatically trying to detect when you've decrypted some ciphertext. You don't necessarily need to check words in the plaintext against words in a dictionary to do that. Even if you did, regular expressions would not be the way to do it. This is more a programming question than a cryptography question, I think you should ask this question on Stack Overflow, but include what programming language you're using, and show what you've already tried and why it wasn't good enough. $\endgroup$ Dec 6, 2013 at 17:07

Certainly you could turn your wordlist into a regexp that matches any string of concatenated words, something like:


There even exist tools to optimize such regexps, such as the Regexp::Assemble module for Perl.

However, I would not generally recommend this approach for identifying correctly decrypted plaintext.

For one thing, even a single misspelling or unrecognized word in the plaintext can cause the match to fail. For another, as you increase the size of the dictionary to reduce the chance of such mismatches, it becomes more and more likely that an incorrectly decrypted text will nonetheless match just because it happens to equal a meaningless string of obscure words.

Basically, the problem is that the regexp cannot distinguish common words like "the" from obscure but valid ones like "adz", not can it distinguish reasonable word combinations like "a quick brown fox" from nonsensical ones like "bulks fey hoof re". As an extreme example, if your wordlist happens to include all single letters as valid words (as some commonly used ones do), then the resulting regexp will match any string of letters!

Instead, what I'd recommend you to use is frequency analysis. To decrypt a simple Caesar cipher, it's usually enough to compare the single letter frequencies of the candidate decryption to those in typical English text, but for more complex ciphers, it's usually better to look at the frequencies of bigrams (i.e. pairs of adjacent letters) or longer n-grams.

The advantage of n-gram frequency analysis is that it provides a measure of statistical and context awareness, such that a substring like "thenext" is rated as more likely than either "irkteal" or "xheettn", while still remaining fairly robust against things like jargon or minor spelling variations. That said, there are a few issues to keep in mind when applying it:

  • The choice of source corpus does matter somewhat, since different words are common in different kinds of text. For example, I once tried to compile an n-gram list from a Wikipedia database dump and found some rather unexpected peaks for stuff like the 5-gram "ation", presumably due to the large number of formulaic tables listing the "location" and/or "population" of things. Properly applied frequency analysis is fairly robust against such variations, but it's still work keeping in mind.

  • In particular, never use a word list as your (sole) source of n-gram data. A word list lists each word once, no matter how common or rare it is in typical English text, and it also doesn't give any useful information about the frequencies of n-grams spanning word boundaries. (That said, using a dictionary as part of your source data, along with a large corpus of normal English text, may be useful to ensure that even rare n-grams are included.)

  • Especially for longer n-grams, there's a risk of overfitting: if the plaintext includes an n-gram that never appears in your source corpus, a naïve n-gram analysis would assign it a zero likelihood of being correct. There are statistical techniques that can help reduce this effect, such as additive smoothing, but applying them effectively is something of an art.

Ps. All that said, your regexp approach might be useful in some cases, e.g. for very short messages, for which frequency analysis can perform poorly. Even in those cases, however, I'd suggest using the regexp only as a first step to break the message into words, and then scoring the results based on their frequency and/or likelihood of co-occurrence. (For example, while "the" is a very common word, "the the" is much less common, at least unless the message is about British post-punk bands.)

It would also be a good idea to keep in mind that there might be more than one way to split single string into words; if you don't want to consider all possible matches (which could be slow), you should at least order the words in your regexp in descending order of frequency (which, under most regexp engines, will ensure that the more common words will be considered first).

  • $\begingroup$ Wow I gotta look over this a little bit more but very detailed explanation thanks. $\endgroup$
    – Jackie
    Dec 7, 2013 at 20:23

Your Answer

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

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