Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

So to solve this issue I would like to use REGEX. I would then take parts of the (possibly) deciphered and query a word list to determine where the words start and end. I found a few sites like WordNet but none of these seem to support REGEX. Now I know I can create one myself, however, I would like to use existing services to minimize the amount of work I need to do.

Questions:

  1. Is this a good way to do this?
  2. Is there an existing service I can search like this?

I know there are only 26 possibilities, however, I would like to find the answer programmatically.

share|improve this question

closed as off-topic by e-sushi, Gilles, archie, D.W., B-Con Dec 13 '13 at 6:17

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

2  
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. –  Reid Dec 5 '13 at 4:57
1  
Wait, are you trying to recover the plaintext and replace the original spaces? –  Gustav Bertram Dec 5 '13 at 11:43
2  
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... –  Ilmari Karonen Dec 5 '13 at 12:58
    
This question appears to be off-topic because it is about finding resources for document processing, with no relation to cryptography. –  Gilles Dec 5 '13 at 15:34
    
@Reid that may help as well thanks –  Jackie Dec 6 '13 at 16:12

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.

share|improve this answer
    
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 –  Jackie Dec 6 '13 at 16:17
1  
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. –  Gustav Bertram Dec 6 '13 at 17:07

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

^(a|aardvark|aardvarks|abaci|aback|...|zucchinis|zygote|zygotes)*$

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

share|improve this answer
    
Wow I gotta look over this a little bit more but very detailed explanation thanks. –  Jackie Dec 7 '13 at 20:23

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