Re:Quippiuq – cryptoquip and cryptogram solver
by bmm6o on Wednesday May 07, 2014 @02:28PM
(#7711866)
Is the source available? I'd be curious what his technique is. I wrote something similar a few years ago, based on pattern matching against a dictionary (which has obvious drawbacks but is very fast when it works).
[ Parent
| on HN ]
Re:Quippiuq – cryptoquip and cryptogram solver
by jjoonathan on Wednesday May 07, 2014 @03:32PM
(#7712198)
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...
Re:Quippiuq – cryptoquip and cryptogram solver
by Allagash on Wednesday May 07, 2014 @03:03PM
(#7712061)
Olson wrote up his algorithm in a paper: http://april.eecs.umich.edu/papers/details.php?name=olson200...