"I was expecting that this would yield an almost perfect result. In fact, the result still needs significant guesswork to decrypt."
I've never heard that substitution ciphers are simple to break using only letter frequencies. It does get you to a point where it makes the guessing a lot easier.
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.
Did they break it using only single symbol frequency counts? Completely ignoring positional information? Because when a human breaks it by starting with frequency counts and then filling in blanks in words, that's a totally different ball game. Computers can definitely do it, but you need to put in more effort.
Seriously. With a simple genetic algorithm you can do significantly better. Considering 2-grams etc. It's nice that they decided to write up what they "learned" with this simple experiment, but they didn't try very hard. Or look at the literature.
No, he implemented exactly the algorithm, and correctly noticed that it doesn't perfectly reveal the plain text because the letter distribution isn't fixed; it varies around some average.
A human would put in the top few letters and work out the rest with knowledge of english _words_, not with the rest of the letter distribution.
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.
The problems in set 1 are a little different, though. You get the important hint (which the author was missing) to use letter frequencies for a fitness function. But the cryptopals set 1 ciphers have tiny keyspaces that are easily searched exhaustively - a substitution cipher in general doesn't. To solve the author's problem you need to re-invent something like stochastic hill climbing.
Many misunderstand the classical lesson as "substitution ciphers are trivially broken by symbol frequency analysis", which isn't the point.
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).
It literally means "of the trivium" (grammar, logic/dialectic and rhetoric) , or, more broadly, that which can be arrived at by straightforward argument, without further specialized knowledge (covered in the quadrivium). It can, but doesn't necessarily, mean either easy or unimportant. Is identity merely unimportant, or is it also easy? Is a long chain of logic either easy or unimportant merely because it's trivial?
In math, the word is used pretty much as a synonym for 'obvious'. But if you understand something well, it is obvious to you, which is why many results are called trivial by those who understand them.
A math professor I had once took a very, very long time to think about a question. After that, his first response was 'that is trivial', after which a quite long explanation followed.
Well, there are reasons why there are dictionaries and ethimology dictionaries:
http://www.thefreedictionary.com/trivialhttp://www.etymonline.com/index.php?term=trivial
it has usually two slightly different meanings, adopted more or less at the same time at the end of the 16th century in English.
The actual meaning is not (in this context) "unimportant" and not exactly "easy", but rather - as I see it slightly different - "simple" in the sense of "commonplace" or rather "at the reach of the ordinary people".
As well, non-trivial does not IMHO really mean "complex" but rather "beyond the reach of the ordinary people" or "needing some non-common reasoning or tools/methods to be reached", it is almost the same, but not exactly the same.
>"In fact, the result still needs significant guesswork to decrypt."
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.
19 comments
[ 3.0 ms ] story [ 49.3 ms ] threadI've never heard that substitution ciphers are simple to break using only letter frequencies. It does get you to a point where it makes the guessing a lot easier.
A human would put in the top few letters and work out the rest with knowledge of english _words_, not with the rest of the letter distribution.
http://cryptopals.com/sets/1/challenges/6
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.
If your cipher is at least 100 characters this will solve it very quickly.
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).
It drives me crazy - but perhaps I'm the one that's wrong. Is it correct to use "trivial" to mean "easy"?
I keep thinking it comes from people misunderstanding the meaning of "non-trivial", as in complex
Not being a native English speaker, that's where I got the impression that trivial meant easy/straightforward.
A math professor I had once took a very, very long time to think about a question. After that, his first response was 'that is trivial', after which a quite long explanation followed.
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.