January 27, 2005

Solution to the GCHQ challenge

As promised, here's the solution to the challenge.

The names in the two lists are those of actors and actresses. They are encoded using a simple substitution cypher. There's one cypher for each pair of men and women, built from the name of the movie they performed in together. These are the translations:

Men
QJAMDU WWVDUMICKEY ROONEY
KCRVKXHL EUJDXZHUMPHREY BOGART
XCT GSXXJYUQREX HARRISON
JRFJWRI XFCSGREGORY PECK
NRIKUSL UIQORMDBCHARLES LAUGHTON
QFDX ORNQTPTONY CURTIS
UFIV WKXXZYJACK LEMMON
HYUE WREEYCSSEAN CONNERY
WKNJVWL GSWOXURICHARD BURTON
BZGZD A'GAANZPETER O'TOOLE
VTWMAC UEIIMLALBERT FINNEY
ZGRT BPDIIRNNALEC GUINNESS
XIVL VFBDJOHN HURT
GMTHYL IKUBGMFPTPSSPMARNOLD SCHWARZENEGGER
OFIIPTYX LYIJHARRISON FORD
RNBTCNP TCOSHNMANTHONY HOPKINS
KEZHQ WSNIECKEVIN SPACEY
LVZD CONKLNFKEWAN MCGREGOR
DYFJN WCLEQPJTOBEY MAGUIRE
PZSS TEBBMJBILL MURRAY


Women
LRNU FHZOHVNJUDY GARLAND
MTJXMG EHXJRDTINGRID BERGMAN
OSXFSXCZ XBZGCXDUXAMARGARET RUTHERFORD
YAERFI KFXBARVAUDREY HEPBURN
AIKUSBS EHSMKHNRMARLENE DIETRICH
CZNTBXD CFDNFEMARILYN MONROE
AQSEWKC XFIWFSYKSHIRLEY MACLAINE
ORERC VIUWFNUEHONOR BLACKMAN
BQKDVGBOJ OVIQXWELIZABETH TAYLOR
OUGEUDLRZ EZBVJDRKATHARINE HEPBURN
TVFAMI WVYVTTLAUREN BACALL
TZMMDR WDNCRMCARRIE FISHER
CWUIFBLSK HSOGSBSIGOURNEY WEAVER
YVTLG UGZVYNHTLINDA HAMILTON
RKUUC VHMPUUPTKELLY MCGILLIS
ECWHX YCMBXAJODIE FOSTER
KHP FNWHQBEVKIM BASINGER
DGOFBL AGUCZDNICOLE KIDMAN
UQPIDJX HEXIDKIRSTEN DUNST
CQMBSVDD LNYMICCNISCARLETT JOHANSSON


And here's how they relate to each other and the name of each movie:

STRIKE UP THE BANDMICKEY ROONEYJUDY GARLAND
CASABLANCAHUMPHREY BOGARTINGRID BERGMAN
BLITHE SPIRITREX HARRISONMARGARET RUTHERFORD
ROMAN HOLIDAYGREGORY PECKAUDREY HEPBURN
WITNESS FOR THE PROSECUTIONCHARLES LAUGHTONMARLENE DIETRICH
SOME LIKE IT HOTTONY CURTISMARILYN MONROE
THE APARTMENTJACK LEMMONSHIRLEY MACLAINE
GOLDFINGERSEAN CONNERYHONOR BLACKMAN
WHO'S AFRAID OF VIRGINIA WOOLFRICHARD BURTONELIZABETH TAYLOR
THE LION IN WINTERPETER O'TOOLEKATHARINE HEPBURN
MURDER ON THE ORIENT EXPRESSALBERT FINNEYLAUREN BACALL
STAR WARSALEC GUINNESSCARRIE FISHER
ALIENJOHN HURTSIGOURNEY WEAVER
THE TERMINATORARNOLD SCHWARZENEGGERLINDA HAMILTON
WITNESSHARRISON FORDKELLY MCGILLIS
THE SILENCE OF THE LAMBSANTHONY HOPKINSJODIE FOSTER
LA CONFIDENTIALKEVIN SPACEYKIM BASINGER
MOULIN ROUGEEWAN MCGREGORNICOLE KIDMAN
SPIDERMANTOBEY MAGUIREKIRSTEN DUNST
LOST IN TRANSLATIONBILL MURRAYSCARLETT JOHANSSON


The cyphers are created by taking the name of the movie, capitalizing it, removing duplicate letters and completing the string with the missing letters from the alphabet, in alphabetical order. The string is then shift-rotated by a certain number of positions.

For example, if the movie is "The silence of the lambs", we get "THESILNCOFAMB" after the first two steps. We then add the missing letters and obtain "THESILNCOFAMBDGJKPQRUVWXYZ". The cypher is then shift-rotated to produce "RUVWXYZTHESILNCOFAMBDGJKPQ".

You may be wondering how is that used to encrypt the actor name. Simple, replace each letter in the name with the letter that appears in the cypher in the position that corresponds to the original letter's position in the alphabet. For instance, to encrypt an F we look at the 6th position in the cypher (F is the 6th letter of the alphabet) and find a Y.

To find the hidden quotation we first listing all cyphers to form a matrix (26x20). They should be sorted according to the movie release date, in ascending order. The hidden quotation can be read from the diagonal of the matrix, starting top-left corner and going down and to the right. The phrase reads "Here's looking at you, kid", a quote from Casablanca.

HBANDCFGJLMOQVWXYZSTRIKEUP STRIKE UP THE BAND
DEFGHIJKMOPQRTUVWXYZCASBLN CASABLANCA
SPRACDFGJKMNOQUVWXYZBLITHE BLITHE SPIRIT
YBCEFGJKPQSTUVWXZROMANHLID ROMAN HOLIDAY
ITNESFORHPCUABDGJKLMQVXYZW WITNESS FOR THE PROSECUTION
ZSOMELIKTHABCDFGJNPQRUVWXY SOME LIKE IT HOT
FGIJKLOQSUVWXYZTHEAPRMNBCD THE APARTMENT
UVWXYZGOLDFINERABCHJKMPQST GOLDFINGER
VGNLBCEJKMPQTUXYZWHOSAFRID WHO'S AFRAID OF VIRGINIA WOOLF
UVXYZTHELIONWRABCDFGJKMPQS THE LION IN WINTER
VWYZMURDEONTHIXPSABCFGJKLQ MURDER ON THE ORIENT EXPRESS
ZSTARWBCDEFGHIJKLMNOPQUVXY STAR WARS
OPQRSTUVWXYZALIENBCDFGHJKM ALIEN
GJKLPQSUVWXYZTHERMINAOBCDF THE TERMINATOR
FGHJKLMOPQRUVXYZWITNESABCD WITNESS
RUVWXYZTHESILNCOFAMBDGJKPQ THE SILENCE OF THE LAMBS
NFIDETBGHJKMPQRSUVWXYZLACO LA CONFIDENTIAL
ZMOULINRGEABCDFHJKPQSTVWXY MOULIN ROUGE
CFGHJKLOQTUVWXYZSPIDERMANB SPIDERMAN
MPQUVWXYZLOSTINRABCDEFGHJK LOST IN TRANSLATION


Here's a Ruby script to automate the decryption process. You'll also need to get the list of movies and the actors.list and actresses.list files from IMDB's text database.

3 Comments:

Anonymous Anonymous said...

Interesting read! But it would be great if you could shed a little more light on the process than the actual solution. How did you start? How did you find the actual number by which you had to shift the movie titles? How did you know which movies you had to use? All brute force?
If you could shed a little light on that, it would be great.

sorry for posting anonymously, but I have no blogger account.

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

January 29, 2005 1:18 PM  
Blogger Martin said...

Don't worry, I'll get to it. That's the topic of my next post ;)

Martin

January 29, 2005 3:09 PM  
Anonymous Anonymous said...

I'm looking forward to it :)

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

January 29, 2005 4:36 PM  

<< Home