The Code Book
Oct. 12th, 2000 11:52 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
alexpgpI got Simon Singh's The Code Book as a Christmas present last year. It's a good read and covers quite a bit of ground in the area of cryptography, starting with the earliest cryptanalytic efforts that eventually cost Mary, Queen of Scots her head, and finishing with a description of cryptographic techniques that could make use of quantum theory to assure the secrecy of underlying messages.
Besides the information in the text, the author includes a series of ten cryptographic challenges, starting with a monoalphabetic substitution cipher and progressing through more complex techniques (and through history, at the same time), arriving at messages encoded using state-of-the-art techniques. A sizeable cash prize was offered for the first solution to all ten puzzles. Back around the time I got the book, solutions to the first seven or eight puzzles had been found. Today, I learned that the tenth and hardest puzzle had been cracked by a group of Swedish programmers. You can find the details on Singh's Web site.
Not having a lot of time (and apparently, not a lot of patience, or talent, or what-have-you), my efforts to find solutions sort of tapered off just after solving the fourth challenge. But it was enough of an experience to let me know that it's one thing to read a description of how to slay a dragon (or solve a cryptogram), and quite another to actually deal with one "in the wild." It's also quite a bit of fun, if you're a puzzle-solving kind of person (the British, by the way, enlisted a number of puzzle-lovers in their effort to break the German Enigma cipher during WW II, including chess players and crossword puzzle whizzes). In tackling the fourth cryptogram, I experienced quite a rush after writing a Perl script that successfully analyzed the puzzle, which was encoded using a Vigenère cipher scheme, and then rewriting the script to actually solve for the underlying message.
Running the first script allowed me to determine, to a fair degree of certainty, that the "key" to the cipher was five letters long. Assuming that only the 26 letters of the alphabet were used and that case was not important, that meant there were "only" 26 x 26 x 26 x 26 x 26, or about 12 million possible keys to consider. Since computers are really good at doing things over and over, the solution, therefore, lay in trying them all.
But this raised a secondary problem, which was finding a way to avoid having to eyeball the output of the "brute-force" solution. (Assuming it takes one second to review the output from one "try," it'd take just over two solid months to review half the output. Yech!) I met the challenge by having the script analyze the output for the presence of common English digrams and trigrams (e.g., letter combinations such as th, the, an, ion, ed, etc.) and the absence of uncommon letter combinations (e.g. bx, qj, and so on). Each "try" was then assigned a numerical score, based on the result. The script ran overnight on my old 486 box and presented me with one solution whose analysis score far outstripped the scores for the remaining 12 million tries.
Upon viewing the solution, I realized I'd come close to missing the mark altogether, because one of my assumptions was dead wrong (but not so wrong as to prevent finding the solution). Can you guess what my slipup was?
Cheers...
Besides the information in the text, the author includes a series of ten cryptographic challenges, starting with a monoalphabetic substitution cipher and progressing through more complex techniques (and through history, at the same time), arriving at messages encoded using state-of-the-art techniques. A sizeable cash prize was offered for the first solution to all ten puzzles. Back around the time I got the book, solutions to the first seven or eight puzzles had been found. Today, I learned that the tenth and hardest puzzle had been cracked by a group of Swedish programmers. You can find the details on Singh's Web site.
Not having a lot of time (and apparently, not a lot of patience, or talent, or what-have-you), my efforts to find solutions sort of tapered off just after solving the fourth challenge. But it was enough of an experience to let me know that it's one thing to read a description of how to slay a dragon (or solve a cryptogram), and quite another to actually deal with one "in the wild." It's also quite a bit of fun, if you're a puzzle-solving kind of person (the British, by the way, enlisted a number of puzzle-lovers in their effort to break the German Enigma cipher during WW II, including chess players and crossword puzzle whizzes). In tackling the fourth cryptogram, I experienced quite a rush after writing a Perl script that successfully analyzed the puzzle, which was encoded using a Vigenère cipher scheme, and then rewriting the script to actually solve for the underlying message.
Running the first script allowed me to determine, to a fair degree of certainty, that the "key" to the cipher was five letters long. Assuming that only the 26 letters of the alphabet were used and that case was not important, that meant there were "only" 26 x 26 x 26 x 26 x 26, or about 12 million possible keys to consider. Since computers are really good at doing things over and over, the solution, therefore, lay in trying them all.
But this raised a secondary problem, which was finding a way to avoid having to eyeball the output of the "brute-force" solution. (Assuming it takes one second to review the output from one "try," it'd take just over two solid months to review half the output. Yech!) I met the challenge by having the script analyze the output for the presence of common English digrams and trigrams (e.g., letter combinations such as th, the, an, ion, ed, etc.) and the absence of uncommon letter combinations (e.g. bx, qj, and so on). Each "try" was then assigned a numerical score, based on the result. The script ran overnight on my old 486 box and presented me with one solution whose analysis score far outstripped the scores for the remaining 12 million tries.
Upon viewing the solution, I realized I'd come close to missing the mark altogether, because one of my assumptions was dead wrong (but not so wrong as to prevent finding the solution). Can you guess what my slipup was?
Cheers...
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Puzzled Puzzler
Date: 2000-10-13 12:10 am (UTC)Anyone recall the Kit Williams (http://www.bunnyears.net/kitwilliams/masq.html) visual book-puzzles of the 80's? That's my kind of recreational puzzle! Though I've been known to hunch over a chunk of code or script for hours, its not nearly as rewarding.
By the by, all the techs I've been meeting through LJ have inspired me to compose a "how I got into the tech industry at the dawn of supercomputing" entry, forthcoming. Consider this your fair warning that I'll want to know eventually, Alex. :-)