4 ms·
Simulated annealing works very well for this problem (and is both reliable and "debuggable" in that if it doesn't work you have good options for tweaking it unt
by jjoonathan 13y ago
Simulated annealing works very well for this problem (and is both reliable and "debuggable" in that if it doesn't work you have good options for tweaking it until it does). Instead of using a dictionary of complete words you can score text by computing the log-likelihood of the ciphertext's sequence of n-tuples given a proposed key.
For n=1 this reduces to "e is most common, t is second most common..." except with the caveat that the simulated annealing algorithm is stochastic and will explore 'almost-perfect' decode tables as opposed to just the 'perfect' decode table (which might not actually be correct).
At n=2 or n=3 this strategy will chew up any substitution-cipher'd block you feed it (assuming a reasonably well-behaved plaintext).
EDIT: this was stochastically generated by a n=4 model, in case it helps you form a picture of how good they are at determining how "english-like" something is.
% GAHLUABLEST ME BUCK NIGH GROUBLE ANY OLD A
% WORRIES BEAUTIFFEEL AND AND WHY COME FOR SOON
% I SEE IT DOWHEN WE PAY YEAR AT WHAH AND PULL YOU
% COMING ALLOW NECTLY SCOW DOWN AFTS DUKE TOWARNT AND
% SIXTEEN WA
It's good enough to be creepy, at least...