How to "score" partially decoded ciphertext?

Question

I am attempting to write a basic codebreaking program to break simple ciphers (think caesar cipher & railfence) such as these here https://en.wikipedia.org/wiki/Classical_cipher.

The program will make semi random attempts at decoding the ciphertext, and I need a way to "score" these attempts on how close they are to fully decoded plaintext. For example "hello world" would score higher than "Kello woHld" or "aellp wprld" which would both score higher than "KRYYP ZPHYI", thus the program can use a hill-climbing or similar method to converge on decoded text.

I am unsure how to score text, perhaps using a dictionary (+regex?) to check for decoded words, or counting occurences of common letters and common groups of 2,3 & 4 letters, then perhaps comparing to known frequencies.

I am not asking for a finished algorithm, just some pointers of how to score text on its "decodedness" / closeness to plaintext.

Edit: I am working with ciphertext 500 to 1000 characters long, would like the system to work with or without word boundaries preserved.

Answer 1

You are looking for a way to measure the similarity between strings, which is usually refered to as string metric. Now in your case one of the strings is the original plaintext and the other is a (more or less) similar string generated by encrypting and decrypting only partially correct. But actually, it doesn't really matter where the other string comes from, you just need to measure how similar they are.

However, there are many string metrics, and it's possible to adapt them to your specific needs. Here are a few common ones:

• Hamming distance: Number of mismatching characters
• Levenshtein distance: Number of insert/delete/substitute operations

There are countless other ways to measure the similarity between strings, and it has to be determined what is considered similar and what isn't.

Answer 2

When scoring a possible decoding if the message we are asking giw likely is it to be the actual message. For this we need some sort if statistical model for the language or source message(doesn't have to be natural language ).

A trivial model would be character frequencies, modeled independently essentially naive-bayes to use the machine learning term. You have a frequency of how common each character is in the language and you can multiply probabilities of the characters in the suggested decoding to get a score. For numerical reasons we prefer to sum the logarithms rather than multiply directly.

Obviously a charchter level model us a bit too simple. So usually you would prefer a model of pairs or triplet character frequencies. Such simple models are actuality very useful and usually sufficient.

You can obviously use an even more complicated model using markov chains or recurrent neural networks. If you want something really sophisticated you can use GANs to make a descriminator between generated text and text from a corpus. Such a model will not only learn character frequencies but also dictionary words and grammar. For most ciphers this is redundant but if for instance the cipher does word level suffeling obviously your language model must know something about word order and char-gram frequencies won't be sufficient.

Answer 3

What can help is:-

• Retain the first letter of the candidate word and drop all other occurrences of a, e, i, o, u, y, h, w.
• Replace consonants with digits as follows (after the first letter): b, f, p, v → 1. c, g, j, k, q, s, x, z → 2. d, t → 3. l → 4. m, n → 5. r → 6.
• If two or more letters with the same number are adjacent in the original name (before step 1), only retain the first letter; also two letters with the same number separated by 'h' or 'w' are coded as a single number, whereas such letters separated by a vowel are coded twice. This rule also applies to the first letter.
• If you have too few letters in your word that you can't assign three numbers, append with zeros until there are three numbers. If you have more than 3 letters, just retain the first 3 numbers.
• Final step would be to compare the values against those computed from a dictionary. Similar scores would be similar words even if slightly misspelled due to insufficient decryption.

I'd love to say that this textual scoring technique is my own clever invention, but it's actually an extant algorithm called Soundex. The above is a blatant extract of wiki's article to illustrate that it can (is) done very effectively for people's names. It's also used for general text as the letter weightings aren't that different. And as you hope for, your decryption can therefore use hill climbing as the algorithm's output is numerical. I think that you'll still need some human input as computers can't read properly. The algorithm would at least reduce the number of possible candidate decryptions.

Look to Metaphone 3 for an algorithm more appropriate to general words rather than names. You realise of course that this won't work for some messages that feature a lot of numerical or non verbal information. So stealing computer cookies or missile launch codes might be problematic.