I am trying to break a special substitution cipher (where the text is divided into several columns and each column has its own substitution table). Currently I am trying hill-climbing.
For the score, I am using Sinkov, which I found at the M4 project.
The algorithm for the Sinkov score is like this (My implementation in PHP):
S = ln(f / u * e), u=MIN(f) u is lowest non-zero frequency f is frequency of that substring in sample text e is base of natural logarithm.
I have created a lookup table for the Sinkov score for bigrams, trigrams and quadgrams, and I tested it with some good and bad text samples:
- Score of good text: 113648
- Score of bad text: 65496
- Score of good text: 94478
- Score of bad text: 23528
Now my problem: I see that trigrams and quadgrams are very good to find out if a text is valid English or not. However, during the hill-climb process, both will show bad results, because it is unlikely that 'good' trigram/quadgrams are found on the first try.
So I am looking for a Sinkov score algorithm, which combines bigram, trigram and quadgram together, kinda like this:
Do a hill-climb to find 'good' bigrams. Give 'bonus-points', if there are 'good' trigrams in it. Give 'super-bonus-points' if there are 'good' quadgrams in it.
How can I achive this? And can I achieve this in a single score-function, or do I need to modify the hill-climb process (how?)