Slashdot Mirror
Poe Puzzle Patiently Pondered
_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."
I did not anticipate the use of your "calculating machines". Nonetheless well done, you have shown fortitude and ingenuity.
--Poe
Thank you for not thinking.
From the solver's explanation:
...
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
Do you realize what you're saying? Okay, coming up with a line of poetry of equal length is so easy it's not even funny, but given the length of time to come up with an encryption scheme so that your line of poetry matches an already existing cipher would be pointless. At that level of complexity, it's much easier to solve the original cipher by transliteration into the Roman alphabet.
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
Mr. Hu is not a ninja.
Yea, but puzzle workers only work 23 days a year. Half that of a programmer.
RSA is asymetric or "public key". Since everyone in a public key cryptography system has the encrytpion key, you could just try re-encrypting the "cracked" code to see if you have the right one.
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.
-... ---
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.
--
www.scorbett.ca
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...
"We can confirm that Debian does *not* ship the version with the trojan horse. Our version predates it." [CA-2002-28]
Are these sites coming in pre-Slashdotted now? Damn, stories been up for like 10 minutes, and already I can't hit it. Anyone lucky enough to view it care to post some relevant information?
You have to admit, there's a miniscule chance that the translation is just a coincidence. Hell, it could be insoluble gibberish, but enough "analysis" produces a (somewhat) meaningful translation.
Has anyone here considered that the "mistakes" in the printed cryptograph might have been intentional? I know that I'd have a few "mistakes" in any message I'd encrypt (if I was doing it manually), with the REAL message available upon decrypting the decrypted message. I'd probably even eliminate all the vowels, and use homonyms, etc. Has anyone checked into this? If not, maybe someone should do so, to see if there is another message encrypted inside the decrypted message.
Not only is this old news, but its old news that was covered by Slashdot before!
This Slashback announced it on September 26 (albeit without confirmation).
And this Kuro5hin story featured it on October 19th, after the solution was confirmed, complete with a link to the solution details (PDF) !!
Using your sig line to advertise for friends is lame.
Didn't somebody make a padlock that took 70 years to finally pick?
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'.
You obviously thought about it too much. Get a life and don't worry about it.
This was solved over a month ago..the press release is dated October 13.
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!
Is that a real title? Can you actually get paid for that? That's like having business cards printed up that say "Bob User - Board Game Winner". It just is to mind boggling for me, maybe I should call up Gil Broza to solve it for me.
How Jaded Are You?
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). 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).& 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
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:
And it just now makes the
The guy came up with the solution on the 26th of June 2000 it says too.
--
Delphis
someone did have a log of time on there hands.
And that's why we always wash our hands after...
ich muß mehr Kuhglocke haben
Check out the Salon.com story about the decoding. I'm a big Poe fan and was excited to see that the cypher had been broken, but disappointed with the results.
-B
Why don't you go do something valuable for your fellow humans?
Why should YOU be the arbiter of what is valuable to other humans?
<Insert Microsoft Joke Here>
-thomas
"Extraordinary claims require extraordinary evidence."
"And like that
someone did have a log of time on there hands
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.
--
Friends don't let friends misuse the subjunctive.
I am thoroughly impressed
"It is a greater offense to steal men's labor, than their clothes"