You <i>can</i> break substitution ciphers pretty trivially, just using a simple hill climbing algorithm see <a href="http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-simple-substitution-cipher/" rel="nofollow">http://practicalcryptography.com/cryptanalysis/stochastic-se...</a><p>If your cipher is at least 100 characters this will solve it very quickly.
Many misunderstand the classical lesson as "substitution ciphers are trivially broken by symbol frequency analysis", which isn't the point.<p>The point is to illustrate a property of a cipher that leaks information, in this case the symbol frequencies because the cipher preserves them. This is information that we don't normally consider valuable when working with plaintexts, but for crypto it's enormously valuable (i.e. it leaks a lot of information).
<i>"I was expecting that this would yield an almost perfect result. In fact, the result still needs significant guesswork to decrypt."</i><p>I've never heard that substitution ciphers are simple to break using <i>only</i> letter frequencies. It does get you to a point where it makes the guessing a lot easier.
If you'd like to play with this yourself, it's #6 in the cryptopals challenges:<p><a href="http://cryptopals.com/sets/1/challenges/6" rel="nofollow">http://cryptopals.com/sets/1/challenges/6</a><p>I agree with the author: it's conceptually very simple, but a little tricky to code, even in the simplest case where you're relying on simple letter frequencies. You could probably do 10 good challenges on different ways to attack this problem, and towards the end you'd be getting into somewhat serious cryptanalysis: for instance, look at what Patterson and Al Fardan did with RC4.
><i>"In fact, the result still needs significant guesswork to decrypt."</i><p>I have never heard anyone other than the author of this piece suggest otherwise. Ironically, this result is trivial. That said, I have a pretty serious classical crypto habit, so my conception of what constitutes 'crypto folklore' may be poorly calibrated.
I used simulated annealing, which is a non-obvious but fairly easy algorithm: <a href="https://github.com/Smaug123/ClassicalCiphers.jl/blob/master/src/monoalphabetic.jl" rel="nofollow">https://github.com/Smaug123/ClassicalCiphers.jl/blob/master/...</a>
I know plenty of CS undergrads who have broken the substitution cipher a part of a assignment. Saying it isn't trivial just because you couldn't do it foolish.
Does anyone know the history of where the word "trivial" started being used to mean "easy" instead of as "unimportant", like the author does here?<p>It drives me crazy - but perhaps I'm the one that's wrong. Is it correct to use "trivial" to mean "easy"?<p>I keep thinking it comes from people misunderstanding the meaning of "non-trivial", as in complex