# Internet Problem Solving Contest

## Solution to Problem H – Hidden Messages

### Easy cipher

The cipher looked as follows:

```      Xjibmvopgvodjin ji njgqdib ocz admno kvmo ja ocdn xdkczm.
Jiz hjmz nozk vrvdon tjp. Tjp cvqz oj yzxdkczm ocz mzhvdidib kvmo ja ocdn
ozso jixz vbvdi, pndib v ydaazmzio hzocjy. Bjjy gpxf.

Dvvzh gnp eotfqxvkj db dhd ibui gfuoq li cvqwsad ei ubu cvpwoe lq dub
ekah, dxq li rnslxt krdufqq gl gy: bkfo bo wgvzh cub kkq mhocbg saqr dub
eybh koe plcgbu gnp uonalxt, yxd vq kkq kr zvzweebv ye zrxibucnqlyap lx
vq, `dxq tkkg fv dub xcr li k olru,' geretew Kyffo `jfwrbrw zvzweebv ye
zrxibucnqlya?'

Pr cub zkf zrxffgoefqq vk koe lzx zfqn (np zoyi dc feh mbron, slu dub kyg
adi zxgo ubu prbo frob cybhzl xqn fqxzva), zrrqkoe qko cihkfruo bc pkxfqq
adsffhc, jehx frgnrkoi n Tksgb Ukoyld jfwr cfqu rvhc exq mylvo ov koe.

Qkoeb zkf krdufqq fl YOEV uozxuunyoo vk wrnq; qye aln Nilmr qksah ld fl
YOEV pepe reg li dub zkl qr rrxu dub Ukoyld fxb db fwcrii, `Yu ahke! Lk
nrxu! S fedvy yh vnqh!' (gubq cub wrbrjrg fw yibu ksqhbjxunf, fw ypzxbebg
db ehb gedd feh yhdkd gl kkib zyaahbra dd gelc, orw kg qko gfpo vq dvy
phozbg ahfwo axweexo); lhq zrrk wrr Odlofw kpqxkyib DBLN K JXWMU LXD BC
LDF TDSFQFYNQ- SYPHHD, nkg vblnoq xw sg, xqn gehx urubvbg ya, Xospb
vdnowoq qr rro iorq, iye fw pyxvrra dmelvc ubu wvkg duxw cub kkq khfro
eosluo fbh k exelvq zsge hsgehb n tdsfqfynq-syphhd, bo d gnqfr gl wkxb reg
li sg, xqn oruxvkj gvqk mholyffwi, feh bnk dmelvc geh pvbon ncwoe fw, kaa
iyeqxxnqhvl tdc wrvd vk wszb wy fbh sg mrz qlzx n idbtb ukoyld-uloo hkgoe
qko ubgqr.

Fq kalwrro pyzbqd qlzx jbqd Nilmr xidro ld, abyoe lqmr zrxffgoefqq ulz sa
qko jluvq pko jxv db dhd brw ktxlx.

Geh bnyesg-ervr thxg pwbnfjrg lq vvhh k grqxri iye prwr tdi, nkg dubq
nvmsoq pxnqbqvl arga, pr chagoaib duxw Kyffo uxg xbq d wbjhxg qr dufqu
nyreg pwycmlxt ehbfbop obiyeb vrr creaa koephvs cdvyfqq qlzx n shbl ahoc
thvy.

Qko floegfrx llx rnsh db pxlzfw sf: "qrdni isnpfy".
```

Getting the first part of the easy cipher was pretty simple: If we try to rotate the alphabet (i.e. replace a by b, b by c, ..., y by z and z by a), after a few steps the first paragraph starts to make sense:

```      Congratulations on solving the first part of this cipher.
One more step awaits you. You have to decipher the remaining part of this
text once again, using a different method. Good luck.
```

This simple cipher is known as the Caesar cipher. Let's take a look at the currently remaining text:

```      Iaaem lsu jtykvcapo ig imi ngzn lkztv qn havbxfi jn zgz haubtj qv izg
jpfm, icv qn wsxqcy pwizkvv lq ld: gpkt gt blaem hzg ppv rmthgl xfvw izg
jdgm ptj uqhlgz lsu ztsfqcy, dci av ppv pw eaebjjga dj ewcngzhsvqdfu qc
av, `icv yppl ka izg chw qn p tqwz,' ljwjyjb Pdkkt `okbwgwb eaebjjga dj
ewcngzhsvqdf?'

Uw hzg epk ewckkltjkvv ap ptj qec ekvs (su etdn ih kjm rgwts, xqz izg pdl
fin eclt zgz uwgt kwtg hdgmeq cvs kvceaf), ewwvptj vpt hnmpkwzt gh upckvv
s fixka-kwskv lgwts tg edjvp izg bggwjaw qn vwvbxfi ce spl eaesxfi bww
fixkkmh, ojmc kwlswptn s Ypxlg Zptdqi okbw hkvz wamh jcv rdqat ta ptj.

Vptjg epk pwizkvv kq DTJA zteczzsdtt ap bwsv; vdj fqs Snqrw vpxfm qi kq
DTJA ujuj wjl qn izg epq vw wwcz izg Zptdqi kcg ig kbhwnn, `Dz fmpj! Qp
swcz! X kjiad dm asvm!' (lzgv hzg bwgwowl kb dngz pxvmgoczsk, kb duecgjgl
ig jmg ljii kjm dmipi lq ppng edffmgwf ii ljqh, twb pl vpt lkut av iad
umtegl fmkbt fcbjjct); qmv ewwp bww Tiqtkb puvcpdng IGQS P OCBRZ QCI GH
QIK YIXKVKDSV- XDUMMI, spl agqstv cb xl, cvs ljmc zwzgagl df, Ctxug
aistbtv vw wwt ntwv, ndj kb udcawwf irjqah zgz bapl izcb hzg ppv pmkwt
jtxqzt kgm p jcjqav exlj mxljmg s yixkvkdsv-xdummi, gt i lsvkw lq bpcg wjl
qn xl, cvs twzcapo lavp rmtqdkkbn, kjm gsp irjqah ljm uagts shbtj kb, pff
ndjvccsvmaq yih bwai ap bxeg bd kgm xl rwe vqec s nigyg zptdqi-zqtt mpltj
vpt zglvw.

Kv pfqbwwt udegvi vqec ogvi Snqrw cniwt qi, fgdtj qvrw ewckkltjkvv zqe xf
vpt oqzav upt oca ig imi gwb pycqc.

Ljm gsdjxl-jwaw ymcl ubgskowl qv aamm p lwvcwn ndj uwbw yin, spl izgv
sarxtv ucsvgvaq fwlf, uw hmfltfng izcb Pdkkt zcl cgv i bgomcl vw izkvz
sdwjl ubdhrqcy jmgkgtu tgndjg aww hwjff ptjumax hiadkvv vqec s xmgq fmth

Vpt kqtjlkwc qqc wsxm ig ucqekb xk: "vwisn nxsukd".
```

Note that several words in the ciphertext repeat. This suggests some periodic encryption scheme. The most simple is known under the name Vigenère cipher (or "periodic key", "periodic password").

The length of the key could be obtained as the greatest common divisor of distances of the repeating parts of the ciphertext. (Why?) Each of the letters of the key can then be determined by counting the frequencies of letters that were encrypted by a given letter of the key. In our cipher the key was IPSC (hey, this was the easy cipher ;) and this is the resulting plaintext:

```      Alice was beginning to get very tired of sitting by her sister on the
bank, and of having nothing to do: once or twice she had peeped into the
book her sister was reading, but it had no pictures or conversations in
it, `and what is the use of a book,' thought Alice `without pictures or
conversation?'

So she was considering in her own mind (as well as she could, for the hot
day made her feel very sleepy and stupid), whether the pleasure of making
a daisy-chain would be worth the trouble of getting up and picking the
daisies, when suddenly a White Rabbit with pink eyes ran close by her.

There was nothing so VERY remarkable in that; nor did Alice think it so
VERY much out of the way to hear the Rabbit say to itself, `Oh dear! Oh
dear! I shall be late!' (when she thought it over afterwards, it occurred
to her that she ought to have wondered at this, but at the time it all
seemed quite natural); but when the Rabbit actually TOOK A WATCH OUT OF
ITS WAISTCOAT- POCKET, and looked at it, and then hurried on, Alice
started to her feet, for it flashed across her mind that she had never
before see a rabbit with either a waistcoat-pocket, or a watch to take out
of it, and burning with curiosity, she ran across the field after it, and
fortunately was just in time to see it pop down a large rabbit-hole under
the hedge.

In another moment down went Alice after it, never once considering how in
the world she was to get out again.

The rabbit-hole went straight on like a tunnel for some way, and then
dipped suddenly down, so suddenly that Alice had not a moment to think
about stopping herself before she found herself falling down a very deep
well.

The solution you have to submit is: "total fiasco".
```

### Hard cipher

In part A probably the first step is to put the whole sentence into one row and to discover that its length matches the length of the rows in the table:

```      #############################_###############################
#_##_#################################################_######
######################################_######################
#####################_######################################_
#####################_######_################################
####################################################_########
########_############_########_########################_#####
#####################__#####################################_
#############################_###############################
##########_################################################_#
#########################################################_###
##_#####################_##################_###_#############
##########_##############_#_#####_###########################
####################################################_########
##############################################_#_############
######################################_################_#####
###########################################################_#
#######_#############_#################_#############_######_
################################################_############
####################################################_########
##############################################_##############
####################################################_########
####################__######_################################
##########_################################################_#
##############################_#################_############
#####_##__################_###_#######__########_############
#############################_###############################
do not submit this text you have to decode it first gjklpqrwz
```

Now it looks that the underscores simply select the letter we should take. Well, it was not that simple.

The table has 27 rows. There are 26 letters, 27 if we count the space. The number of rows is a hint that we should do so. The correct approach was to increase the selected letters in the i-th row by i (computing modulo 27, i.e. a letter could change to a space or vice versa).

We get the text: apple ball card five kitty letter line pizza scissors stamp

Part B was a plain substitution cipher. Counting frequencies of letters can be used to discover this. As long as you know the boundaries of words, the substitution cipher can be solved by hand. Solution:

```hello
as you can see this is just a plain substitution cipher we sure do hope that
all of you can easily solve this part of the problem
but more steps await you
to solve the last one you will need a set of words
here they come
shadow starlight tiger total towel vienna wave world pinky sea kiribati ketchup
fifteen gutenberg sound werewolf divide book desert virgin lightning bishop
needle recall phantom shell test silver ender express sun bunny worm postcard
brain page
```

STOP READING HERE. Before you proceed, try to solve the part C on your own!

To solve Part C we clearly needed the words from the first two parts. These words and some of their letters had to be added to the image in the problem statement. Now we may cut the image into 24 tiles and try to put the tiles in the correct positions. Of course, two tiles can share an edge if and only if the corresponding two words have something in common. There were some fake pairs, but these could be discovered when the other edges of the tile didn't match. The correct pairs were:

• achilles - tortoise: One of Zeno's paradoxes.
• ball - lightning: A natural phenomenon.
• bishop - knight: Chess pieces.
• book - flight: You can book a flight.
• brin - page: Google founders.
• bunny - egg: Easter.
• burundi - bujumbura: Country + its capital.
• card - ender: Orson Scott Card is the author, Ender is the main hero of a series of his books.
• coat - arms: A coat of arms is a (usually shield-shaped) picture identifying some noble family.
• command - line: The part of your terminal after the prompt.
• commander - keen: An oldie but goodie by Apogee Software.
• desert - fox: Operation Desert Fox.
• divide - conquer: A powerful technique in designing efficient algorithms.
• eve - apple: From the Bible.
• fat - rat: A task from IPSC 2004.
• ford - towel: Ford Prefect is the famous hitchhiker from the famous guide to the galaxy by Douglas Adams.
• ghost - shell: "Ghost in the Shell", a true classic in anime genre.
• gutenberg - bible: The first printed copy of the Bible.
• hatter - hare: Mad Hatter and the March Hare, from Lewis Carroll's "Alice in Wonderland"
• heal - world: "Heal the World", a famous song by Michael Jackson.
• hello - kitty: Google and see for yourself, if you don't know Hello Kitty.
• hockey - vienna: Ice Hockey World Championships 2005.
• kiribati - tarawa: Another country + capital.
• letter - stamp: You can find them in the nearest post office.
• love - fifteen: Score in a tennis game (see problem A :)
• moonlight - shadow: A song by Mike Oldfield.
• needle - haystack: "To look for a needle in a haystack." == a futile search. See also "man strstr".
• phantom - opera: "The Phantom of the Opera", a book, a musical and most recently a movie.
• pinky - brain: "Pinky and The Brain", a great cartoon about two mice that try to take over the world.
• postcard - quest: See our webpages to find out what this is about.
• pride - prejudice: A classic novel by Jane Austen.
• prime - time: In television the time around evening news when most people tune in.
• raphael - pizza: Who could ever forget our heroes, the Teenage Mutant Ninja Turtles?
• rock - scissors: And "paper" is missing.
• salt - sea: The sea is salty.
• santiago - cuba: A city and its country; also, Hemingway's old man Santiago
• scarecrow - lion: Characters in "The Wizard of Oz".
• starlight - express: A musical by Andrew Lloyd Webber.
• sun - java: Yep, THE Sun and THE Java.
• tea - five: A tea at five, an old English tradition.
• tiger - dragon: "Crouching Tiger, Hidden Dragon", a movie.
• tomato - ketchup: Still trying to "catch up" on this one? :)
• total - recall: The name of a movie.
• turing - test: The Turing Test is a famous test of how good an AI can mimic a human.
• virgin - unicorn: Legends say that only a pure virgin was allowed to touch a unicorn.
• wave - sound: Sound is propagated by sound waves.
• werewolf - silver: Supposedly werewolves can't stand the touch of silver.
• worm - spice: Frank Herbert's "Dune"

When assembling the result we find that the tiles actually form a 6 times 4 torus. The right way to place them is to form a rectangle with the same dimensions than the one we started with. Then we only had to try 24 rotations and select the one where the resulting text makes sense: