2
$\begingroup$

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

$\endgroup$

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.