Poe Puzzle Patiently Pondered 56
_J_ writes: "It looks like a solution has been found for this Edgar Allan Poe Coded Message as posted on Slashdot last March in Please Patiently Ponder Purported Poe Puzzle. To paraphrase Qwerty4 from last March - someone did have a lot of time on there hands. "Let's just say I didn't give up early enough" said Gil Broza - puzzle solver."
Congratulations from beyond the grave! (Score:5)
--Poe
is that really encryption? (Score:3)
Since there were around 140 different cypher-letters
140 encoding characters? From what I can see of the encrypted message, there are roughly 600 characters in the entire message. Once you get to the point where the number of encoding characters reaches the number of message characters, isn't the entire information content transferred to the encryption key, and you the message itself becomes garbage?
I mean, I can come up with an indecipherable code: replace the first letter with '1', the second letter with '2', etc. etc. Then my encoded message becomes "12345...", and my key says
1=H
2=E
3=L
4=L
5=O
Yeah, it's a cipher, but only because I've removed all the information from my message and put it in the key. Isn't actual cryptography the art of retaining information, but making it really hard to read? Frankly, I'm amazed Gil Broza was able to solve something with so little information left!
-D
I had posted this a while back (Score:1)
-----------------------------------------
Re:It's a crock! (Score:2)
And once you have the symbols transformed, you solve it like a cryptoquote. Using letter frequencies, word frequencies, etc. it is possible to solve any transliterated cipher. It may take time, but it can be done.
If you want much more difficult, translate an English document into a dead language phonetically, then encrypt it. Or use a queue-transformation on the document.
Just my 2 shekels.
Kierthos
security through obscurity works! (Score:1)
sc
Re:"- Puzzle Solver"? (Score:2)
Re:How do we know it's the solution? (Score:3)
The most unbreakable cryptography scheme involves xor-ing your message with purely random data. This creates purely random data.
In this scheme, you could always create a key eqaul to the xor of the cyphtertext and any message you wanted it to be.
I'm assuming the author had the intention of making the cyphertext decodeable, and so made sure there was some pattern to it.
Take a look at it and see.
Chaffe and Winnow (Score:1)
Cryptography (Score:1)
Re:This is what's wrong with the slashdot crowd. (Score:1)
Re:How do we know it's the solution? (Score:1)
- Stanislaw Lem, The Cyberiad
It's probably not correct. (Score:1)
If you put a bunch of Monkeys in a room with some typewriters for an infinite amount of time, They will eventually type out the correct method to decrypt this puzzle.
Chances are, they just happened to have stumbled upon a solution that only looks correct.
Re:How do we know it's the solution? (Score:2)
Although that is statistically possible, I find it doubtful given the circumstances.
One time pad encryption (sometimes called a vernam cipher) is the only form of encryption that is considered to be theoretically uncrackable (assuming, of course, that the pad is not compromised). The reason it is considered uncrackable is that all possible plaintexts are equally likely. For example, given a section of ciphertext n bytes in length, you could stumble upon a key of n bytes which, when xor'ed with the ciphertext in question, yielded english-language plaintext (this is somewhat akin to the "infinite monkeys on infinite typewriters" thing). It might be right, it might be wrong, it would certainly be a remarkable coincidence.
The reason I don't believe it to be likely in this case is because there is not enough entropy in the ciphertext. Just look at the puzzle, you can see repeated character sequences. If this were the output of a one time pad, it wouldn't have that kind of repetition.
Of course, there is still a valid possibility that the decryption was just a coincidence, which could explain the numerous small errors. Hey, stranger things have happened.
--
a picture of a man and his tool (Score:1)
The caption states, "Shawn Rosenheim, professor of English at Williams College, holds a wheel cipher, a tool for deciphering codes, in his office at the college in Williamstown, Mass., Tuesday, Nov 28, 2000. Rosenheim helped create a contest to solve an 1841 cipher published by Edgar Allan Poe. (AP Photo/Matthew Cavanaugh)"
http://dailynews.yahoo.com/h/p/ap/20001130/us/p
not_anne
Palimpsest riddle? (Score:1)
Re:is that really encryption? (Score:2)
Other "Great Puzzles" (Score:1)
We had Fermat's Last Theorm, and Poe's Cypher....is there anything else for us to bang our heads against?
-Harry
Re:Other "Great Puzzles" (Score:1)
Pick a wall and go to it.
---
Re:"Mistakes"? (Score:1)
Kewl subject title, but inaccurate :-) (Score:2)
At first Whalen believed he had uncovered an original Poe text, even though a number of features, such as the heavy use of alliteration, were unlike Poe.
Heh, given that information, the title of this article isn't really accurate ;-) Still, nice title, though!
It's... It's...
Re:Just a wee bit late again :) (Score:1)
j/k
--
Early Knockout (Score:2)
Of course... (Score:1)
Literary porn. A story of a couple in a secluded place engaged in a 'nooner' must have been some hard-core stuff back then.
In all seriousness, I am constantly amazed by the power of people's curiosity!
Congrats! (although a month late)
Re:This is what's wrong with the slashdot crowd. (Score:1)
karmawhoring-dont /. their servers here is the... (Score:1)
Cipher Solved, But Mystery Remains
Williams College Professor Shawn Rosenheim announced yesterday that the Edgar Allan Poe Cryptographic Challenge contest has a winner. After over 150 years, Gil Broza of Toronto has solved the second of two mysterious ciphers left by Poe for future readers.
Poe was fascinated by cryptography, which he often treated in his journalism and fiction. His most famous story - ?The Gold-Bug? - centers on the solution to a cipher, which turns out to be a map to hidden pirate treasure, and he concealed anagrams and hidden messages in many of his poems. In 1839 Poe even conducted his own cryptographic challenge. Writing in Alexander's Weekly Messenger, Poe challenged his readers to submit their cryptographs to him, asserting that he would solve them all. A year later Poe wrote an article for Graham's Magazine entitled ?A Few Words on Secret Writing?. In it, he offered to give a free subscription to the magazine to anyone who would send him a cipher he could not crack.
Poe ended the contest six months later, claiming to have solved all of the 100 legitimate ciphers sent to him, and complaining that cracking ciphers consumed time he should have spent writing fiction - a luxury Poe could ill afford. He concluded by publishing two ciphers ostensibly sent in by ?Mr. W. B. Tyler,? praising their author as ?a gentleman whose abilities we highly respect? and challenging readers to solve them.
There the ciphers remained, apparently forgotten, until 1985, when Professor Louis Renza of Dartmouth College suggested that Tyler was actually a double for Poe himself. Renza sees Poe's fiction ?as containing not readily apparent anagrams as well as thinly disguised allegories of his process of composing his tales -- often the very tale one is reading.? He felt Poe's cryptography articles shared this approach. In addition, a search of the major city directories of the time failed to locate a W. B. Tyler. That absence was, Renza admits, ?thin evidence, to be sure, but enough for me to venture my guess.?
Renza?s theory was later elaborated by Rosenheim in his book The Cryptographic Imagination: Secret Writing from Edgar Poe to the Internet (Johns Hopkins, 1997). In it, Rosenheim musters considerable circumstantial evidence which points to the likelihood that the ciphers were placed in the magazine by Poe as a final challenge to his readers. Tyler?s letter to Poe, Rosenheim notes, sounds exactly like Poe?s prose, and it praises Poe extravagantly. Tyler also claims that cryptography gives him ?a history of my mental existence, to which I may turn, and in imagination, retrace former pleasures, and again live through by-gone scenes-secure in the conviction that the magic scroll has a tale for my eyes alone. Who has not longed for such a confidante?? (Secret Writing, December, 1841)
The appeal of the ?magic scroll? has to do with the preservation of the past, fixed by its encoding. Cryptography provides Tyler and Poe with a way to preserve the self (as writing) from the destructions of time.Tyler?s ?who has not longed for such a confidante?? also echoes ?The Murders in the Rue Morgue,? where the narrator ?confides? to Dupin that his company seems ?a treasure beyond price.? And Tyler?s claim that the cryptograph will not ?betray its mission, even if intercepted?or if stolen from its violated depository? (SW, 141), directly recalls the violated crypts and tombs of ?Ligeia,? ?Ulalume,? ?The Fall of the House of Usher,? and other Poe texts. Poe is even known to have written to himself, publishing several anonymous reviews of his own writing, and acknowledging in Graham?s Magazine that some readers harbored a suspicion that his amazing decryptions were the result of ?our writing ciphers to ourselves.?
Spurred to action by Rosenheim?s work, in 1992 Professor Terence Whalen solved the first of Tyler's cryptographs -- a monoalphabetic substitution cipher. Decrypted, it read:
At first Whalen believed he had uncovered an original Poe text, even though a number of features, such as the heavy use of alliteration, were unlike Poe. As it turns out, the lines come from the 1713 play Cato, by the English essayist Joseph Addison. But that does not rule out Poe as the originator of the cryptograph, who may have selected Addison?s text because its themes of apocalyptic collapse and the soul?s immortality were also central to his own poetry and prose, which often treat ciphers as a kind of vault or crypt protected from time
Whalen?s solution did not answer the question of who created the cipher. Hoping to discover the answer, Rosenheim established a $2500 prize, supported by Williams College, for the solution of the second cipher. As he explains, ?The contest was an avenue of last resort. Because the second cipher uses six separate alphabets to encode its text, it?s several orders of magnitude harder than the first. I tried to solve it myself and failed. I also sent it to various cryptographers, from the editor of The Cryptogram magazine to professionals at Bell Labs, but no one was able to help me.?
So things would probably have remained, except that in 1998, Jim Moore, a software designer specializing in encryption, heard of the contest and offered to build a website to promote it (a site hosted through Bokler Software Corporation -- www.bokler.com [bokler.com]). In the next two years, Rosenheim and Moore fielded hundreds of inquiries from would-be sleuths in America, Europe, and South America. Most wrote once and were never heard of again. Then, in July, Gil Broza, a software engineer living in Toronto, submitted what turned out to be the correct decryption. Tyler's cryptograph proved to be a polyalphabetic substitution cipher using several different symbols for each English letter. The number of different symbols is greater as the plaintext letter is more frequent in English text, for instance 'z' is encrypted by two symbols and 'e' by 14. Given the brevity of the cipher, this meant that there was almost no information about letter frequencies, which cryptographers count as their most potent tool for decryption.In addition, Broza?s solution revealed that the original cipher had over two dozen mistakes introduced by the typesetters or the encipherer. Many of these were trivial(such as ?warb? for ?warm,? ?shaye? for ?share,? ?langomr? for ?langour?), but even after Broza corrected obvious errors, the final plaintext is sometimes garbled:
So who composed the ciphers? Rosenheim believes it was still probably Poe. ?The text is clearly not by Poe, but from some unidentified novel or story of the period. But like the first cipher text, its themes (enclosure, the dangers of exposure, immortality) are absolutely typical of Poe's writing. Plus there?s the case of Poe?s misleading comments about the ciphers.? In 1842 Poe wrote to a Mr. Bolton, who was attempting to solve Tyler?s ciphers ?It is unnecessary to trouble yourself with the cipher printed in our Dec. number - it is insoluble for the reason that it is merely type in pi or something near it. Being absent from the office for a short time, I did not see a proof, and the compositors have made a complete medley. It has not even a remote resemblance to the MS.? (http://www.eapoe.org/works/essays/gm41sw03.htm [eapoe.org]).& nbsp;
But as Broza?s solutions shows, the cipher is not hash, but English prose. The second cipher?s many errors, the judges agreed, stem from the difficulties of distinguishing between the different typestyles and their inversions and reversals. William Lenhart, Professor of Computer Science and Mathematics at Williams College, tested a range of alternative solutions, hoping to improve on the spelling and grammar of the plaintext, but found only trivial misidentifications by Broza.
In the end, as Jeffery Kurz writes, ?If the text turns out to be by Poe, it would fit into his grand scheme of speaking from the dead and be the final message from one of the greatest authors in American literature, a writer obsessed with the macabre and the transcendent power of words? (March 8, 2000, Salon.com).
And if not? That, Rosenheim suggests, may be an equally interesting prospect. ?One of the central themes of The Cryptographic Imagination is the difficulty of knowing who speaks in a written text. However much we like to fancy ourselves unique individuals, writing is a slippery, transpersonal medium. Think about the continuing arguments about whether Shakespeare was a middle-class boy from Stratford, or Francis Bacon. Better yet, think about the difficulty even serious scholars have in identifying the provenance of newly discovered poems - often, they simply can?t tell if they?re by Shakespeare - arguably the greatest and most distinctive English dramatist - or not.?
Thus, Rosenheim insists, there is something mysterious even in the decrypted cipher - not only because we do not know who enciphered it, but because it reminds us of the uncanny and limited immortality writing sometimes affords. As Poe wrote in his obituary for Margaret Fuller, ?The soul is a cypher, in the sense of a cryptograph; and the shorter a cryptograph is, the more difficult there is in its comprehension.? Or as Poe put it, in ?Shadow -- A Parable?:
Ye who read are still among the living; but I who write shall have long since gone my way into the region of shadows. For indeed strange things shall happen, and secret things be known, and many centuries shall pass away, ere these memorials be seen of men. And, when seen, there will be some to disbelieve, and some to doubt, and yet a few who will find much to ponder upon in the characters here graven with a stylus of iron.
How the cypher was brokenNote: see the pdf file for additional details [bokler.com]
The first task at hand was to determine the language and encryption method. The cypher solved by Whalen being in English, and either presumed author (Poe or Tyler) being an English speaker provided good grounds for assuming the cypher was in English. Further corroboration for that was provided by the distribution of word lengths, which quite resembles modern English but is even more likely older English. Assuming that the running text was indeed broken down at word boundaries - that is, its separation to letter sequences was not intended to mislead cryptanalysis- the repetition of several words, even with minor modifications, led me to believe the method was that of simple polyalphabetic substitution. Repetitions may also occur when using methods such as Vigenère, but the fact that the distances between repetitions had no common denominator ruled these methods out. Letter frequencies, the almost total absence of patterns, and Tyler?s bragging about the cypher?s resilience (which was obviously to be taken with a grain of salt, judging from the already solved cypher) all contributed to the impression that he simply tried to obliterate letter frequency by using numerous substitutions for frequent letters. This indeed turned out to be the case: he used more than 14 different letters for ?e? but only two for ?z?.
The fact that several cypher-words were repeated with changes in their characters? orientation or size (e.g. ?DNB?, ?JCP?) made me think that character inversion was just a smokescreen, but pursuing this direction proved futile. The same happened when I tried breaking the cypher with its words reversed, following the Whalen cypher precedent. The more I worked on it, the more my belief grew stronger that even though the cypher may well be simple polyalphabetic substitution, its author obviously took pains to do a good job on it, taking care to spread the use of each cypher-letter uniformly throughout the text. In fact, I am sure that had Tyler not used character inversion ?to make assurance doubly sure? - thus employing only half as many cypher-letters - the cypher would have been broken by now. Substituting some repetitive short cypher-words for likely English words (such as ?the?, ?and?, ?not?) yielded nothing, as the low letter frequency and lack of patterns would not allow me to validate these substitutions.
At this point I began to believe that I should try to use the computer to break the cypher. Since there were around 140 different cypher-letters, half of which were obviously difficult to manipulate in ASCII, I employed a transcription of two characters for every cypher-letter, the first indicating its orientation and the second its identity and case. There were some multi-word patterns: groups of non-consecutive cypher-words that shared several characters. I wrote a program, ?Matches?, that tried to match these patterns against wordlists. The output for a multi-word pattern typically amounted to hundreds or thousands of word groups that matched the patterns. These lists were mostly useless due to their sheer size, but they did help in some cases, such as identifying broken repetitions and ruling out certain substitutions. I also wrote a second program, ?Patterns?, to help me identify those multi-word patterns that shared the most letters, and as such provided enough constraints against the wordlists. But the more I used the program the more it became clear that solution did not lie in these programs because the outputs I got were, for the most part, meaningless. The wordlists I found on the Internet were either too comprehensive, providing too many far-fetched words, or too small to reflect common use of the English language (e.g. missing conjugations). Any good yields turned out to be incorrect substitutions. Much of this work I had to revisit once I found that not only I had several mistakes when transcribing the cypher to a file, the cypher I had downloaded from the contest?s website differed in at least nine cypher-letters from the one actually published by Poe, a blurred scan of which was provided on the website of the Poe Society of Baltimore. Apparently, the contest?s website used a tome from the turn of the century that contained a manually copied version of the cypher.
Not wanting to believe that the cypher was a hoax, my only conclusion from the above results was that the cypher simply contained too many errors to allow successful pattern-matching against lists of correctly spelt words. I tried another approach with the computer?s aid: looking for on-line texts containing word sequences that had the same lengths of words as some sequences in the cypher. My primary focus was on the sequence ?XQCMKUYWEKa gs B?, or word lengths 11-2-1, which has a rather low probability of appearing in English texts. I searched the Internet for texts by Joseph Addison - the author of Whalen?s plaintext - and other poets and writers predating Poe, but found nothing. Fortunately, I abandoned this search early, since it would have yielded nothing, as the text I finally deciphered was nowhere to be found on the Internet.
By now, almost seven weeks after first tackling the cypher, I was on the brink of giving up. But I decided to give it a final chance before saving it aside for next year. I determined to try substituting ALL repeating three-letter words with ?the?, ?and?, ?not? and follow each direction, letting my imagination roam freely. As I was certain there were many errors, I decided not to back down on any approach. I was almost certain that ?AmL? stood for ?the?, since it appears once after a long word, and once after a long word and a two-letter word, which must be a preposition. With these three plaintext letters I now had the following three patterns: ?1?2e???, ?e?3? and ?132?, which seemed promising enough. ?Matches? provided over 3500 word groups, many of which were likely, but when correlating them with other occurrences of these characters a specific one caught my attention: ?ardent?, ?eye?, ?and? (one character in ?132? had to be in error because they contradict, but I tried both.) This was the crux of the solution: I now had a word that looked like ???ter???n?, which had to be ?afternoon?. I also had two words, ?th??? and ???re?, which seemed plausible parts of words in English. Substituting the remaining letters in ?afternoon? provided the word ?of? before the second appearance of ?the?, and I was quite certain now that I was on the right track. Other patterns that now had at least one plaintext letter could be re-scrutinized; thus I had a sure substitution with ?KJ? ?JERK? = ?no? ?open?. The five-letter word starting with ?ea? had to be ?early? or ?earth?. The penultimate plaintext letter ?n? in some words indicated ?ing?. All this time I was trying likely guesses as well as wild ones, since most substitutions had at least one occurrence that didn?t look promising, due to errors. At several points during the deciphering procedure I was stymied by grave errors in the cypher, as well as by bad substitutions on my part, the most amazing of which was that the ?ardent eye? turned out to be an ?ardent sun?, with the latter word also misspelt ?zun??
The Winner: Gil Broza was born in 1973 in Israel. He has been interested in languages and mathematics since early age, and has been solving cryptograms in crossword magazines since age 13. He holds a B.Sc. in mathematics and computer sciences and an M.Sc. in computational linguistics from the Hebrew University in Jerusalem. He has been working as a software engineer in the last seven years. In 1999 he moved with his wife Ronit to Toronto, Canada. His personal interest in Poe?s writing was first sparked in high school while studying ?Annabel Lee? and ?The Raven?. It wasn?t until finishing David Kahn?s The Codebreakers and looking for cryptographic challenges on the Internet that he discovered the Poe contest, which had already been running for two years. This provided the perfect opportunity to engage in a real, historically valuable cryptanalytic challenge. The Judges: William Lenhart is chair of the Computer Science Department, and Professor of Computer Science and Mathematics at Williams College. The recipient of both Sloan and NSF grants, he has authored or coauthored numerous papers in Graph Theory, Graph Drawing, Computational Geometry, and Combinatorial Algorithms. Webmaster:For Further Information:
How do we know it's the solution? (Score:4)
Re:Just a wee bit late again :) (Score:1)
"Mistakes"? (Score:5)
Re:YAAAAAAAAAAAAAAAWWWWWWWWWWWWWWWWWWWWWWWWWWN (Score:1)
Often the really subtle ones go straight over peoples' heads. 'Not perfect' trolls catch people because the typical slashdotter thinks he/she is 'better' than 'ordinary' people on account of how they can install Slackware. They cannot resist a chance to point out the perceived flaws in someone's post.
Ha Ha (Score:1)
Already Posted to Slashdot! (Score:2)
This Slashback [slashdot.org] announced it on September 26 (albeit without confirmation).
And this Kuro5hin story [kuro5hin.org] featured it on October 19th, after the solution was confirmed, complete with a link to the solution details (PDF) !! [bokler.com]
Tounge twister. (Score:1)
I bet you can't say that three times fast.
- KA
// begin code
#include <iostream.h>
int main ()
{
cout << "Linux is the answer to all problems" << endl;
return 0;
}
// end code
Re:Ick (Score:1)
Re:Ha Ha (Score:2)
log(TIME) (Score:3)
I = 9
M = 13
E = 5
T * I * M * E = (20) * (9) * (13) * (5) = 7020
log(7020) = 3.8463371121298052763053277624322
Therefore,
------------
CitizenC
My name is not 'nospam,' but 'citizenc'.
here's the message -- what about the key (Score:1)
poecipher egroup which did not come up with
the solution first, but where the exact
reading of the solved cryptogram was discussed
thoroughly:
http://www.egroups.com/message/PoeCipher/140
here is what I believe it should read:
it was early spring warm and sultry
glowed the afternoon the very breezes
seemed to share the delicious languor of
universal nature and laden of various
and mingled perfumes of the rose and the
jessamine, the woodbine and the wildflower
they slowly wafted their fragrant offering
to the open window where sat the lovers
the ardent sun shone full upon her blushing
face and its gentle beauty was more like the
pyrexia of some wild romance or the fairy
inspiration of a dream than the actual
reality of earth tenderly her lover gazed
upon her as her clustering ringlets
were eased by amorous and sportive
zephyrs and when he perceived the rude
intrusion of the sunlight he sprang to
draw the curtain but she gently stayed
him no no dear charles she softly said
much rather would i have a little sun than
no air at all
which yields a key, depending on how exactly you transcribe the cryptogram, something like
dehiliaXnCnEtHesUuTorsyrop
XDaLXXenXoIsuwXhrTDvzEXgea
FwauadLdAeFyiOrXmTFUXXXgne
TasHpoRXctmwortenOlaXehime
hXeAilmXXnOrpsXtYhXeoXXXAX
NXeurPOrshSXhXXXXeXeXTtXge
now I'm a bit obsessed with a) tracing the
source of the text (because it sounds tantalizingly familiar to me) and b): why is that
key not plaintext! the "beauty" of this method of encryption would be that if you pick a plaintext key, automatically the more frequent letters get more aliases, yielding the desired flat lettercount of the encrypted message...
Verification... (Score:1)
It's a correct translation..
I held a seance to channel the spirit of Poe, and he told me so himself..
Re:is that really encryption? (Score:1)
As long as the key can produce every letter (or most letters), then this doesn't happen.
For example, this encryption could have easily used a key that had 600+ symbols, which mapped to all letters of the alphabet. This key can still produce *any* message you want, and therefore the "information content" has not transferred to the key. And yet you could still encode a message where no symbol is repeated at all in the cyphertext.
As an even more extreme example, I could encode my message as a series of numbers which are indexes to characters in a novel, say, War and Peace. Wouldn't that suck.
In the case you're citing (ie HELLO...), the only "information content" in the key is which letters *can't* be in the plaintext. Information on sequencing and length is still in the cyphertext, and that's what's important.
-------------
The following sentence is true.
Re:"Mistakes" probably just such (Score:1)
assisted solving, nor is it a real-life
(secret service etc.) cryptography situation
but a challange for readers of a cryptography
column.
also compare the background article at
http://www.eapoe.org/works/essays/gm41sw03.htm
quoting Poe:
"It is unnecessary to trouble yourself with the cipher printed in our Dec. number -- it is insoluble for the
reason that it is merely type in pi or something near it. Being absent from the office for a short time, I did not see a
proof and the compositors have made a complete medley. It has not even a remote resemblance to the MS."
which I think sounds credible enough (poor
printers)
Thinking Machine (Score:1)
If NSA et al have all these super-duper computers at Fort Meade, Digby etc., and all the people (well OK, at least a shitload of them) are CS and maths people, you'd have thought one of them would have come across this (hell, I bet some of them read /.) and run it through a few spare cycles on their Thinking Machine / Quantum Computers?
Mind you, I'm betting that posting the answer would have got them fired. But anyway, my point is I bet this was solved years ago, just outside the public domain.
Unless of course Osama Bin Laden's chinese satellite encryption and Saddam's russian one-time cipher pads are nothing next to EAPoe's whimsy.
Ben^3 (popping up on echelon as we speak)Re:"- Puzzle Solver"? (Score:1)
Move out of your parents basement. (Score:2)
Just a wee bit late again :) (Score:3)
I do remember seeing the first solution when it was first posted in March, I believe. I tried my hand, but I don't know enough cryptography!
"- Puzzle Solver"? (Score:2)
Here's the announcement... (Score:5)
Cipher Solved, But Mystery Remains
Williams College Professor Shawn Rosenheim announced yesterday that the Edgar Allan Poe Cryptographic Challenge contest has a winner. After over 150 years, Gil Broza of Toronto has solved the second of two mysterious ciphers left by Poe for future readers.
Poe was fascinated by cryptography, which he often treated in his journalism and fiction. His most famous story - "The Gold-Bug" - centers on the solution to a cipher, which turns out to be a map to hidden pirate treasure, and he concealed anagrams and hidden messages in many of his poems. In 1839 Poe even conducted his own cryptographic challenge. Writing in Alexander's Weekly Messenger, Poe challenged his readers to submit their cryptographs to him, asserting that he would solve them all. A year later Poe wrote an article for Graham's Magazine entitled "A Few Words on Secret Writing". In it, he offered to give a free subscription to the magazine to anyone who would send him a cipher he could not crack.
Poe ended the contest six months later, claiming to have solved all of the 100 legitimate ciphers sent to him, and complaining that cracking ciphers consumed time he should have spent writing fiction - a luxury Poe could ill afford. He concluded by publishing two ciphers ostensibly sent in by "Mr. W. B. Tyler," praising their author as "a gentleman whose abilities we highly respect" and challenging readers to solve them.
There the ciphers remained, apparently forgotten, until 1985, when Professor Louis Renza of Dartmouth College suggested that Tyler was actually a double for Poe himself. Renza sees Poe's fiction "as containing not readily apparent anagrams as well as thinly disguised allegories of his process of composing his tales -- often the very tale one is reading." He felt Poe's cryptography articles shared this approach. In addition, a search of the major city directories of the time failed to locate a W. B. Tyler. That absence was, Renza admits, "thin evidence, to be sure, but enough for me to venture my guess."
Renza's theory was later elaborated by Rosenheim in his book The Cryptographic Imagination: Secret Writing from Edgar Poe to the Internet (Johns Hopkins, 1997). In it, Rosenheim musters considerable circumstantial evidence which points to the likelihood that the ciphers were placed in the magazine by Poe as a final challenge to his readers. Tyler's letter to Poe, Rosenheim notes, sounds exactly like Poe's prose, and it praises Poe extravagantly. Tyler also claims that cryptography gives him "a history of my mental existence, to which I may turn, and in imagination, retrace former pleasures, and again live through by-gone scenes--secure in the conviction that the magic scroll has a tale for my eyes alone. Who has not longed for such a confidante?" (Secret Writing, December, 1841)
The appeal of the "magic scroll" has to do with the preservation of the past, fixed by its encoding. Cryptography provides Tyler and Poe with a way to preserve the self (as writing) from the destructions of time.Tyler's "who has not longed for such a confidante?" also echoes "The Murders in the Rue Morgue," where the narrator "confides" to Dupin that his company seems "a treasure beyond price." And Tyler's claim that the cryptograph will not "betray its mission, even if intercepted...or if stolen from its violated depository" (SW, 141), directly recalls the violated crypts and tombs of "Ligeia," "Ulalume," "The Fall of the House of Usher," and other Poe texts. Poe is even known to have written to himself, publishing several anonymous reviews of his own writing, and acknowledging in Graham's Magazine that some readers harbored a suspicion that his amazing decryptions were the result of "our writing ciphers to ourselves."
Spurred to action by Rosenheim's work, in 1992 Professor Terence Whalen solved the first of Tyler's cryptographs -- a monoalphabetic substitution cipher. Decrypted, it read:
At first Whalen believed he had uncovered an original Poe text, even though a number of features, such as the heavy use of alliteration, were unlike Poe. As it turns out, the lines come from the 1713 play Cato, by the English essayist Joseph Addison. But that does not rule out Poe as the originator of the cryptograph, who may have selected Addison's text because its themes of apocalyptic collapse and the soul's immortality were also central to his own poetry and prose, which often treat ciphers as a kind of vault or crypt protected from time
Whalen's solution did not answer the question of who created the cipher. Hoping to discover the answer, Rosenheim established a $2500 prize, supported by Williams College, for the solution of the second cipher. As he explains, "The contest was an avenue of last resort. Because the second cipher uses six separate alphabets to encode its text, it's several orders of magnitude harder than the first. I tried to solve it myself and failed. I also sent it to various cryptographers, from the editor of The Cryptogram magazine to professionals at Bell Labs, but no one was able to help me."
So things would probably have remained, except that in 1998, Jim Moore, a software designer specializing in encryption, heard of the contest and offered to build a website to promote it (a site hosted through Bokler Software Corporation -- www.bokler.com [bokler.com]). In the next two years, Rosenheim and Moore fielded hundreds of inquiries from would-be sleuths in America, Europe, and South America. Most wrote once and were never heard of again. Then, in July, Gil Broza, a software engineer living in Toronto, submitted what turned out to be the correct decryption. Tyler's cryptograph proved to be a polyalphabetic substitution cipher using several different symbols for each English letter. The number of different symbols is greater as the plaintext letter is more frequent in English text, for instance 'z' is encrypted by two symbols and 'e' by 14. Given the brevity of the cipher, this meant that there was almost no information about letter frequencies, which cryptographers count as their most potent tool for decryption.In addition, Broza's solution revealed that the original cipher had over two dozen mistakes introduced by the typesetters or the encipherer. Many of these were trivial(such as "warb" for "warm," "shaye" for "share," "langomr" for "langour"), but even after Broza corrected obvious errors, the final plaintext is sometimes garbled:
So who composed the ciphers? Rosenheim believes it was still probably Poe. "The text is clearly not by Poe, but from some unidentified novel or story of the period. But like the first cipher text, its themes (enclosure, the dangers of exposure, immortality) are absolutely typical of Poe's writing. Plus there's the case of Poe's misleading comments about the ciphers." In 1842 Poe wrote to a Mr. Bolton, who was attempting to solve Tyler's ciphers "It is unnecessary to trouble yourself with the cipher printed in our Dec. number - it is insoluble for the reason that it is merely type in pi or something near it. Being absent from the office for a short time, I did not see a proof, and the compositors have made a complete medley. It has not even a remote resemblance to the MS." (http://www.eapoe.org/works/essays/gm41sw03.htm [eapoe.org]).& nbsp;
But as Broza's solutions shows, the cipher is not hash, but English prose. The second cipher's many errors, the judges agreed, stem from the difficulties of distinguishing between the different typestyles and their inversions and reversals. William Lenhart, Professor of Computer Science and Mathematics at Williams College, tested a range of alternative solutions, hoping to improve on the spelling and grammar of the plaintext, but found only trivial misidentifications by Broza.
In the end, as Jeffery Kurz writes, "If the text turns out to be by Poe, it would fit into his grand scheme of speaking from the dead and be the final message from one of the greatest authors in American literature, a writer obsessed with the macabre and the transcendent power of words" (March 8, 2000, Salon.com).
And if not? That, Rosenheim suggests, may be an equally interesting prospect. "One of the central themes of The Cryptographic Imagination is the difficulty of knowing who speaks in a written text. However much we like to fancy ourselves unique individuals, writing is a slippery, transpersonal medium. Think about the continuing arguments about whether Shakespeare was a middle-class boy from Stratford, or Francis Bacon. Better yet, think about the difficulty even serious scholars have in identifying the provenance of newly discovered poems - often, they simply can't tell if they're by Shakespeare - arguably the greatest and most distinctive English dramatist - or not."
Thus, Rosenheim insists, there is something mysterious even in the decrypted cipher - not only because we do not know who enciphered it, but because it reminds us of the uncanny and limited immortality writing sometimes affords. As Poe wrote in his obituary for Margaret Fuller, "The soul is a cypher, in the sense of a cryptograph; and the shorter a cryptograph is, the more difficult there is in its comprehension." Or as Poe put it, in "Shadow -- A Parable":
Ye who read are still among the living; but I who write shall have long since gone my way into the region of shadows. For indeed strange things shall happen, and secret things be known, and many centuries shall pass away, ere these memorials be seen of men. And, when seen, there will be some to disbelieve, and some to doubt, and yet a few who will find much to ponder upon in the characters here graven with a stylus of iron.
How the cypher was brokenNote: see the pdf file for additional details [bokler.com]
The first task at hand was to determine the language and encryption method. The cypher solved by Whalen being in English, and either presumed author (Poe or Tyler) being an English speaker provided good grounds for assuming the cypher was in English. Further corroboration for that was provided by the distribution of word lengths, which quite resembles modern English but is even more likely older English. Assuming that the running text was indeed broken down at word boundaries - that is, its separation to letter sequences was not intended to mislead cryptanalysis- the repetition of several words, even with minor modifications, led me to believe the method was that of simple polyalphabetic substitution. Repetitions may also occur when using methods such as Vigenère, but the fact that the distances between repetitions had no common denominator ruled these methods out. Letter frequencies, the almost total absence of patterns, and Tyler's bragging about the cypher's resilience (which was obviously to be taken with a grain of salt, judging from the already solved cypher) all contributed to the impression that he simply tried to obliterate letter frequency by using numerous substitutions for frequent letters. This indeed turned out to be the case: he used more than 14 different letters for 'e' but only two for 'z'.
The fact that several cypher-words were repeated with changes in their characters' orientation or size (e.g. 'DNB', 'JCP') made me think that character inversion was just a smokescreen, but pursuing this direction proved futile. The same happened when I tried breaking the cypher with its words reversed, following the Whalen cypher precedent. The more I worked on it, the more my belief grew stronger that even though the cypher may well be simple polyalphabetic substitution, its author obviously took pains to do a good job on it, taking care to spread the use of each cypher-letter uniformly throughout the text. In fact, I am sure that had Tyler not used character inversion "to make assurance doubly sure" - thus employing only half as many cypher-letters - the cypher would have been broken by now. Substituting some repetitive short cypher-words for likely English words (such as 'the', 'and', 'not') yielded nothing, as the low letter frequency and lack of patterns would not allow me to validate these substitutions.
At this point I began to believe that I should try to use the computer to break the cypher. Since there were around 140 different cypher-letters, half of which were obviously difficult to manipulate in ASCII, I employed a transcription of two characters for every cypher-letter, the first indicating its orientation and the second its identity and case. There were some multi-word patterns: groups of non-consecutive cypher-words that shared several characters. I wrote a program, "Matches", that tried to match these patterns against wordlists. The output for a multi-word pattern typically amounted to hundreds or thousands of word groups that matched the patterns. These lists were mostly useless due to their sheer size, but they did help in some cases, such as identifying broken repetitions and ruling out certain substitutions. I also wrote a second program, "Patterns", to help me identify those multi-word patterns that shared the most letters, and as such provided enough constraints against the wordlists. But the more I used the program the more it became clear that solution did not lie in these programs because the outputs I got were, for the most part, meaningless. The wordlists I found on the Internet were either too comprehensive, providing too many far-fetched words, or too small to reflect common use of the English language (e.g. missing conjugations). Any good yields turned out to be incorrect substitutions. Much of this work I had to revisit once I found that not only I had several mistakes when transcribing the cypher to a file, the cypher I had downloaded from the contest's website differed in at least nine cypher-letters from the one actually published by Poe, a blurred scan of which was provided on the website of the Poe Society of Baltimore. Apparently, the contest's website used a tome from the turn of the century that contained a manually copied version of the cypher.
Not wanting to believe that the cypher was a hoax, my only conclusion from the above results was that the cypher simply contained too many errors to allow successful pattern-matching against lists of correctly spelt words. I tried another approach with the computer's aid: looking for on-line texts containing word sequences that had the same lengths of words as some sequences in the cypher. My primary focus was on the sequence 'XQCMKUYWEKa gs B', or word lengths 11-2-1, which has a rather low probability of appearing in English texts. I searched the Internet for texts by Joseph Addison - the author of Whalen's plaintext - and other poets and writers predating Poe, but found nothing. Fortunately, I abandoned this search early, since it would have yielded nothing, as the text I finally deciphered was nowhere to be found on the Internet.
By now, almost seven weeks after first tackling the cypher, I was on the brink of giving up. But I decided to give it a final chance before saving it aside for next year. I determined to try substituting ALL repeating three-letter words with 'the', 'and', 'not' and follow each direction, letting my imagination roam freely. As I was certain there were many errors, I decided not to back down on any approach. I was almost certain that 'AmL' stood for 'the', since it appears once after a long word, and once after a long word and a two-letter word, which must be a preposition. With these three plaintext letters I now had the following three patterns: '1?2e??', 'e?3' and '132', which seemed promising enough. "Matches" provided over 3500 word groups, many of which were likely, but when correlating them with other occurrences of these characters a specific one caught my attention: 'ardent', 'eye', 'and' (one character in '132' had to be in error because they contradict, but I tried both.) This was the crux of the solution: I now had a word that looked like '??ter???n', which had to be 'afternoon'. I also had two words, 'th??' and '??re', which seemed plausible parts of words in English. Substituting the remaining letters in 'afternoon' provided the word 'of' before the second appearance of 'the', and I was quite certain now that I was on the right track. Other patterns that now had at least one plaintext letter could be re-scrutinized; thus I had a sure substitution with 'KJ' 'JERK' = 'no' 'open'. The five-letter word starting with 'ea' had to be 'early' or 'earth'. The penultimate plaintext letter 'n' in some words indicated 'ing'. All this time I was trying likely guesses as well as wild ones, since most substitutions had at least one occurrence that didn't look promising, due to errors. At several points during the deciphering procedure I was stymied by grave errors in the cypher, as well as by bad substitutions on my part, the most amazing of which was that the 'ardent eye' turned out to be an 'ardent sun', with the latter word also misspelt 'zun'...
The Winner: Gil Broza was born in 1973 in Israel. He has been interested in languages and mathematics since early age, and has been solving cryptograms in crossword magazines since age 13. He holds a B.Sc. in mathematics and computer sciences and an M.Sc. in computational linguistics from the Hebrew University in Jerusalem. He has been working as a software engineer in the last seven years. In 1999 he moved with his wife Ronit to Toronto, Canada. His personal interest in Poe's writing was first sparked in high school while studying "Annabel Lee" and "The Raven". It wasn't until finishing David Kahn's The Codebreakers and looking for cryptographic challenges on the Internet that he discovered the Poe contest, which had already been running for two years. This provided the perfect opportunity to engage in a real, historically valuable cryptanalytic challenge. The Judges: William Lenhart is chair of the Computer Science Department, and Professor of Computer Science and Mathematics at Williams College. The recipient of both Sloan and NSF grants, he has authored or coauthored numerous papers in Graph Theory, Graph Drawing, Computational Geometry, and Combinatorial Algorithms. Webmaster:For Further Information:
Re:Just a wee bit late again :) (Score:1)
Announced October 13th? (Score:2)
And it just now makes the
The guy came up with the solution on the 26th of June 2000 it says too.
--
Ick (Score:3)
And that's why we always wash our hands after...
Salon story (not Slashdotted) (Score:5)
-B
Oh where oh where is the Grammar Nazi? (Score:1)
Come on, that's not English, that's barely even American. You probably meant, "Someone did have a lot of time on their hands," but even that's not quite correct, since "someone" is singular, but "their" isn't, and "a lot" isn't really correct, since time doesn't come bundled in "lots."
Re:This is what's wrong with the slashdot crowd. (Score:2)
Why should YOU be the arbiter of what is valuable to other humans?
<Insert Microsoft Joke Here>
-thomas
"Extraordinary claims require extraordinary evidence."
Log time? Really? (Score:2)
Wow! You mean they actually solved it in logarithmic time? This marks a major breathrough in cryptography. I thought these things took a long time to solve, like exponential or worse.
Oh, wait, it was a typo, nevermind.
--
It's a crock! (Score:1)
Well hats off to him (Score:5)
I am thoroughly impressed
Re:How do we know it's the solution? (Score:1)
If the cyphertext was completely random I would agree with you.
Re:How do we know it's the solution? (Score:1)
Isn't it true that the cyphertext from RSA can decrypt to any message of equal length if you just have the right key for that decryption?
I.e. "csh" can decrypt to "dog" or "cat" or "pop" depending on what key you used. (It would also decrypt to a bunch of giberish three letter combos as well). Isn't that one of it's strengths? It's hard to know what the "right" plaintext is without some context.
Someone please correct me if I'm wrong.
Is it possible that this encryption scheme has the same property?
--Ty