January 29, 2005

Breaking the code

As a follow-up to my previous post, I'd like to describe how the I broke the GCHQ code. All it took was a bit of luck, some detective work and some programming.

The first time I saw the challenge, I skimped over the names to get a feel for it, without any intention of actually trying to solve it. It was pretty obvious to me, though, that the names had been encrypted with some kind of substitution cypher.

And then I saw the tip-off... BZGZD A'GAANZ. That had to be an irish-like name, so the A would be and encrypted O. Consequently, the last name would have to have the form O'xOOxx. Peter O'Toole immediately came to mind, although I didn't initially remember who he was. But the name sounded so familiar. I googled for it and it turned out he was an actor. Then I remembered :), and I was hooked.

I looked at the other names carefully, trying to spot easy ones, like KHP FNWHQBEV. With three distinct letters in the first name, I couldn't think of anything else than "Kim". Kim Basinger came to mind, and it fit nicely.

It was then that I decided to write a program to automate the discovery. I needed the program to take a name as input and match it to each name in the list. The question was how to do this efficiently. I realized that when dealing with substitution cyphers, an unencrypted string has the same form as the encrypted version. For example, PETER could be described as a sequence of characters [a, b, c, d, e] where a = P, b = d = E, c = T, e = R. It can be rewritten as [a, b, c, b, e], or "abcbe". In a sense, this sequence is a canonical form for the string. This (Ruby) code snippet will do the transformation:

def canonicalForm(chars)
     map = {}
     currentIndex = 64
     result = ""
     chars.each_byte { |char|
         if not Regexp.new("[' ]") =~ char.chr
             index = map[char] ||= (currentIndex += 1)
         else
             index = char
         end
         result << index
     }
     return result
end


A string and its encrypted version will both have the same canonical form. For instance, for PETER O'TOOLE and BZGZD A'GAANZ, the canonical form is ABCBD E'CEEFB.

The original version was quite primitive... if you fed it a name it would tell you which, if any, encrypted names matched. I discovered a few names with this approach. At first I thought the actors and actresses were Oscar winners, but I quickly dropped that hypothesis when I encountered "Kirsten Dunst". Given that she performed in Spiderman, I decided to try "Tobey Maguire". Direct hit! So my new theory was that an actor and actress that had performed in the same movie would be paired together. But I had to test it.

That's when I came up with the second version of the program, one that would build the cypher given a string and its encrypted version. For example, if I provided it with TOBEY MAGUIRE and DYFJN WCLEQPJ, it would produce

CF..J.L.Q...W.Y..P.DE...N.

The dots represent unknown substitutions. If I did the same with Kirsten Dunst, I'd get

...HJ...Q.U..X...PIDE.....

If you take a close look at the cyphers, you'll notice that they look awfully similar (the J, Q, P, D, and E are in the same positions). If you merge them, you get

CF.HJ.L.Q.U.WXY..PIDE...N.

Also, you'll note that the merged cypher is very regular and that the letters seem to be, up to a point, in alphabetical order. We can confidently fill in some of the missing spaces, for only one letter seems to fit:

CFGHJKL.Q.UVWXY..PIDE...N.

The last portion is suspiciously close to Spiderman, the name of the movie. That was one of the tell-tale signs that confirmed that the cyphers were unique to each pair, and that they were built from the name of the movie. Completing the cypher with the missing letters from Spiderman we get

CFGHJKL.Q.UVWXY.SPIDERMAN.

That leaves only a few letters left, which, again, we can detemine unequivocally:

CFGHJKLOQTUVWXYZSPIDERMANB


Some names were still missing their pair. I was able to infer a few by applying the cyphers of the still-unpaired names to the remaining encrypted names. For example, the cypher for Sean Connery produced .ONOR...AC..AN when decrypting one of the names. .ONOR could be nothing else than "Honor", so I queried www.imdb.com for all the people named that way. The first entry in the list was "Honor Blackman". Another direct hit!

At this point I was out of luck. I had no idea how to decrypt the remaining names and I had tried with all the actors and actresses I could remember. That's when I decided to investigate if IMDb had a programmatic interface. It did not, but it was possible to download the list of all known actors and actresses in a text file. Oh yeah, baby!

The third incarnation of the program would parse the text files and attempt to decrypt each of the remaining names with each of the names in the file. Surprisingly, some names produced unambiguous translations, but others resulted in dozens of alternatives. And I was not going to try one by one.

During the few minutes I spent thinking about how to best tackle the problem ahead I contemplated a couple of alternatives and I made an interesting discovery: if I picked any name (with Ae and Ad being the encrypted and decrypted versions, respectively) and another name B (with Be and Bd following the same rule as A), such that A and B are encrypted with the same cypher, the concatenation of Ae with Be has the same canonical form as the concatenation of Ad with Bd. If you stop to think about it for a second it, it makes perfect sense. Just consider what happens within a name. The encrypted and decrypted versions of the first name have the same canonical form. If we add the last name, which is written in terms of the standard alphabet in the decrypted version, and in a non-standard alphabet resulting applying the cypher on the standard alphabet, the strings are still isomorphic (i.e., they have the same canonical form). Thus, it follows that if we add a full name to each of the strings, each in their respective alphabet, the result will still be two isomorphic strings.

In the fourth incarnation, the program would pair up all the alternatives for the names that I hadn't been able to decrypt and make sure that their concatenation was isomorphic with the contatenation of the encrypted versions. Amazingly, the program produce one and only one pairing for each name! I was done with the first step.

Next, I had to figure out what were the names of the movies, since I had a hunch that the hidden quotation would be buried somewhere within the cyphers. I could've written a program to extract this information from the IMDb text files, but they are not well structured and I considered that it would take me longer to figure out how to parse them than to query IMDd. It did take some going back and forth in IMDb, but it wasn't that bad. Plus, I had already figured out most of the names, anyway.

Finding the hidden quotation took me a while, though. I tried everything I could possibly think of, to no avail. Then, it simply clicked. I looked at the release dates of the movies and noticed they were all different, and ranged from the 40's up to the present day. That could imply only one thing: they were meant to be sorted! And so I did. I sorted the cyphers based on the release date, in ascending order. And it didn't take me long to realize that the quote was in the diagonal of the matrix formed by the cyphers.

11 Comments:

Anonymous Anonymous said...

I'm impressed. And another lesson learned, never give up even if it looks undoable. Cool stuff, enjoyed the entry!

Veit (g o c u b s (a t) g m x . n e t)

January 31, 2005 11:48 AM  
Blogger nasha said...

Why was there no follow on bankruptcy then? The bailout of AIG FP went to (wow power leveling) hedge funds that bound credit swaps on Lehman failing or others betting on rating (wow power leveling) declines. AIG has drained over 100 billion from the government. Which had to go to (wow power leveling) those who bet on failures and downgrades. Many of whom (power leveling)were hedge funds. I-banks that had offsetting swaps needed the money from the AIG bailout or they would have been caught. Its an (wow powerleveling) insiders game and it takes just a little bit too much time for most people to think (wow gold) through where the AIG 100 billion bailout money went to, hedge funds and players, many of whom hire from the top ranks of DOJ, Fed, Treasury, etc. ZHANG XIAO CHEN

April 19, 2009 9:56 PM  
Blogger Adi said...

Thank you for sharing.
Oes Tsetnoc | Mengembalikan Jati Diri Bangsa | Kenali dan Kunjungi Objek Wisata di Pandeglang | Oes tsetnoc | Online Marketing | Electronics Gadgets | etips solution | Travel Guide

October 25, 2009 8:10 AM  
Blogger crazyloko said...

buy products wholesaleThis phenomenom is typified by China Wholesalersthe rise ofbusiness. Incredible range of products available with China Wholesale “Low Price and High Quality” not only reaches directly to their target clients worldwide but also ensures that wholesale from china from China means margins you cannot find elsewhere and China Wholesale will skyroket your profits.china wholesale productsbuy china wholesalewholesale chinawholesale productsbuy products

October 27, 2009 12:49 AM  
Blogger The Jack said...

Thanks ever so much, very useful article. If you do not mind, please visit my article related to pandeglang district in Banten, Indonesia at Kenali dan Kunjungi Objek Wisata di Pandeglang or Kenali dan Kunjungi Objek Wisata di Pandeglang second and also Kenali dan Kunjungi Objek Wisata di Pandeglang Objek Wisata Air Terjun Curug Gendang or related to a leadership at Mengembalikan Jati Diri Bangsa and Oes Tsetnoc or Oes Tsetnoc the second and our hard work at Kerja Keras Adalah Energi Kita that's right Kerja Keras Adalah Energi Kita, and Kenali dan Kunjungi Objek Wisata di Pandeglang Memasuki Babak Akhir also Objek Wisata Taman Wisata Alam Carita, Kenali dan Kunjungi Objek Wisata di Pandeglang, or Kenali dan Kunjungi Objek Wisata di Pandeglang, also Kenali dan Kunjungi Objek Wisata di Pandeglang, or Kenali dan Kunjungi Objek Wisata di Pandeglang, also Kenali dan Kunjungi Objek Wisata di Pandeglang, or Kenali dan Kunjungi Objek Wisata di Pandeglang, also Kenali dan Kunjungi Objek Wisata di Pandeglang, or Kenali dan Kunjungi Objek Wisata di Pandeglang, very smart thank you!

October 28, 2009 11:03 PM  
Blogger Apa Saja Dah said...

Find and download what you need at Rapidshare Search Engine.
Top Site List Free Proxy Site Internet Marketing Tools Internet Marketing Auto Insurance Quotes Home Mortgage Loan Newest Gadgets Review Free Download mp3

October 31, 2009 9:23 PM  
Blogger Daniela said...

Find your great Travel News and sing the songs at Free Song Lyric or you can watch the drama at Korea Drama Online one of great korea drama is A Love to Kill if you go to travel to Indonesia learn Learn Indonesia Language first! And find your home cari rumah or make a blog Belajar membuat Blog find your home again rumah dijual and again at jual rumah then if you want buy a new laptop see the Laptop Price List or you can buy a New Blackberry and then take care your Health & Jewerly.

November 14, 2009 7:49 PM  
Blogger James Taylor said...

Almeda University | accredited degree | online diploma

December 03, 2009 10:20 PM  
Blogger James Taylor said...

Online universities | Online education

December 03, 2009 10:20 PM  
Blogger nike said...

Nice work and thanks!
Running
Adidas currently manufactures several running shoesNike shoes, including the adiStar Control 5, the adiStar Ride
Cheap nike shoes
Discount nike shoes
the Supernova Sequence and the Supernova Cushion 7, among others.
Nike shox r4
nike shox torch
nike shox shoes
Adidas also uses kangaroo leather to make their more expensive shoes.
Association football
One of the main focuses of Adidas is football kit and associated equipment.
puma cat
cheap sport shoes
Adidas also provides apparel and equipment for all teams in Major League Soccer. Adidas remain a major company in the supply of team kits for international football teams.
cheap nike shox
cheap nike max
Adidas also makes referee kits that are used in international competition and by many countries and leagues in the world. In the United States, referees wear the Adidas kits in MLS matches even though the primary referee supplier is Official Sports.
nike tn dollar
nike running shoes
The company has been an innovator in the area of footwear for the sport with notable examples including development of the Copa Mondial moulded boot on firm dry pitches for forty years.
nike air max tn
puma shoes
Adidas became renowned for advancing the "Predator" boot design.This design featured a ribbed rubber structure for the upper leather of the shoe, used to accent the movement of the ball.
discount puma shoes
puma mens shoes
The Predator also features the Craig Johnston invented "Traxion" sole. As the development and popularity of Football continued Adidas played a leading role in shaping the style of the play itself.
puma running shoes
puma shoes
FIFA, the sports governing body, commissioned specially designed footballs for use in its own World Cup tournaments to favour more attacking play.
ghd hair straighteners mk4
hair straightners
ghd iv styler hair straightener
ghd hair straightners
cheap ghd hair straighteners

December 09, 2009 5:51 PM  
Blogger nike said...

Clothing has always been a thing that has been given a great importance by human beings. It displays the attitude that the people exhibit.
ed hardy clothes
ed hardy shirts
Lots of brands have been existent in the clothing industry and a famous one among them is the Ed hardy clothing brand.
ed hardy jackets
ed hardy hoodies
The brand got its name from the famous American tattoo artist Ed Hardy. He was a very famous tattoo artist and has published many books on tattooing techniques.
ed hardy boots
ed hardy polo shirts
But his tattooing turned into a brand by the efforts of a company called Christian Audiger. This company was a very famous and very powerful company in the field of clothing.
ed hardy shoes
ed hardy jeans
They felt that it would be appropriate to create a brand called Ed hardy and use Hardy's art as the main selling point for the brand. This venture had turned out to be a very successful one and Ed hardy clothing is one of the most famous brands in the clothing industry.
ed hardy outerwear
ed hardy long sleeve shirts
The brand became very famous because it was worn by many famous celebrities like Madonna, Britney spears and also Sylvester Stallone.
ed hardy bags
ed hardy winter boots
The brand has clothes for men, women, and kids. They have also diversified their business by having a lot of accessories to support their clothing business.
ed hardy love kills slowly shirts
ed hardy love kills slowly shoes
ed hardy love kills slowly boots
for men they have a variety of products such as active wear, denim, outwear, swim trucks, sweaters, t-shirts, tops etc.
ed hardy trousers
ed hardy mens
the accessories include things such as belts, caps, scarves, shoes, socks, jeweler, sunglasses, ties and even wallets.
The art works is a unique combination of American and Japanese cultures. The unique selling proposition of the brand is the way in which the company has used the art works of Ed hardy.
ed hardy womens
ed hardy t shirts
ed hardy sunglasses

December 09, 2009 5:52 PM  

Post a Comment

Links to this post:

Create a Link

<< Home