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:

Sinkov bigram:

Sinkov trigram:

  • Score of good text: 113648
  • Score of bad text: 65496

Sinkov quadgram:

  • 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?)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.