3 ms·
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 (whic
by bmm6o 12y ago
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).
- Allagash 12y agoOlson wrote up his algorithm in a paper: http://april.eecs.umich.edu/papers/details.php?name=olson2007crypt http://april.eecs.umich.edu/papers/details.php?name=olson200...
- jjoonathan 12y agoSimulated 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...