IPSC Logo

Internet Problem Solving Contest

IPSC 2005

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
      n adsfv-frnfq gbron ob zyeqk dub wbbrevr li qrqwsad xz nkg zvznsad wrr
      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
      ymad.

      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:

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: