back to index

M4 Project

## Hill climbing algorithm performance:

How many restarts will the hill climbing algorithm need to decrypt a
message? Was a particular break lucky? Is there a correlation between the
flatness of character distribution in the ciphertext and the number of
restarts needed?

It is easy to test any theory: Generate a large number of random
encryptions of the same plaintext and count the restarts that are
required for a successful break.

Have a look at the
results for 1000 random encryptions
of the plaintext.

The first column contains the number of restarts needed for each
ciphertext, the second column contains the IC of the ciphertext.

You can see that 66.3% of random encryptions yield with zero restarts
and 81.3% with a single restart. This suggests that the *settings*
of the actual break were not particularly favourable.

It can be seen that zero-restart breaks occur with wildly varying ciphertext
ICs. I can see no correlation between the number of restarts and the IC of
the ciphertext.

These tests were performed on the plaintext of the Schroeder signal
*truncated to 100 letters*:

Results for 1000 random encryptions

The single column contains the number of restarts needed for each ciphertext.

#### Statistics:

`
Restarts: Success:
0 14,3%
1 23,6%
5 50,5%
10 66,4%
30 84,9%
100 97,0%
`

### Simulated worst case (100 letter Schroeder message):

I tested how many restarts it would take in practice to break the
most resistant encryption of the Schroeder message. The answer was 350.
Keep in mind that this particular encryption was *the* most resistant
one out of 1000.

### Conclusion:

*If* the plaintext of the unbroken signal has about the same characteristics as
the Schroeder signal, *if* the signal is not an Offizier message and *if* we are
not dealing with a particularly resistant encryption, hopefully less than 100
restarts are needed.

### Contact:

Stefan Krah <website @ bytereef.org>