singingbanana code challenge 2012: solution

In February 2012 I set a code breaking challenge. This was part of 'Code Month' on the nrich website (http://nrich.maths.org/thismonth/all/2012/02). Here was the cipher:

VA BT LS EG OT XK PB BH CI FV GA YC QG BP UW IH QD OE DI HL CQ YC QG BP EI LZ GA GB IZ PS AZ DQ NI CY UY EA AI UA BF BV OVQA ZS DP QD PG QM PS WL QY DH BD TL VZ PL LW AH GZ BP IM NI KP DZ QU DH FP CI FV RT SB BP BV XO BE BQ PG KO GE IK KO NA OSDG DG DA OX PO GE LZ GA OP FL WU PU UT WF BV IC HF EQ SP NA UX DC BV

I also gave the clue that the message contained the phrase 'EXTRA LARGE FRENCH FRIES' (known as a 'crib'):

See the video of me setting the challenge here: http://youtu.be/laCupCrZNx8
And here is my solution video, including the winners: http://youtu.be/iQhkoV_-8WI

Below is a more detailed explantion.

How the code works:

This time I used a 'Playfair cipher'. http://en.wikipedia.org/wiki/Playfair_cipher

You need to use a 5 x 5 square containing a mixed up alphabet. The letters I and J are combined:

A

W

E

S

O

M

T

I

C

B

D

F

G

H

K

L

N

P

Q

R

U

V

X

Y

Z

An easy way to create such a square is to start it using a keyword, without repeated letters, this time I used I used the word AWESOMETASTIC . Fill in the remaining boxes with the rest of the alphabet, in order.

Let's send the message 'HELLO WORLD'. First split the message into pairs 'HE LL OW OR LD' . There are now three rules:

If a pair are in the same column, move each letter down one place. So the pair OR becomes BZ .
If a pair asre in the same row, move each letter one place to the right. So the pair OW becomes AE. (Notice the letter O wraps back to the start of the row, to A ).
Otherwise, the two letters form two opposing corners of a box. Each letter becomes the other corner of the box in the same row. For example. HE becomes GS .

If you have a double letter, change the second letter to an X. So the pair LL above, becomes LX . Nows apply the same rules.
If you have an odd number of letters in your message, add an X to the end to make it an even numer of letters.

Altogether we get:

 HE

 LX

 OW

 OR

 LD

 GS

 PU

 AE

 BZ

 UL


When sending the message, letters may wrap around within the rows or columns of the square. The means all letters in the square may be shifted to the right, or shifted down, without changing the result. For example, the following is an equivalent square that may be used for the above message.

H

K

D

F

G

L

N

P

Q

R

U

V

X

Y

Z

S

O

A

W

E

C

B

M

T

I


How I broke the code:

Here is the cipher again:

VA BT LS EG OT XK PB BH CI FV GA YC QG BP UW IH QD OE DI HL CQ YC QG BP EI LZ GA GB IZ PS AZ DQ NI CY UY EA AI UA BF BV OVQA ZS DP QD PG QM PS WL QY DH BD TL VZ PL LW AH GZ BP IM NI KP DZ QU DH FP CI FV RT SB BP BV XO BE BQ PG KO GE IK KO NA OSDG DG DA OX PO GE LZ GA OP FL WU PU UT WF BV IC HF EQ SP NA UX DC BV


Remember, I gave you the clue that the message contained the phrase 'EXTRA LARGE FRENCH FRIES'.

There are two ways to break up the crib into pairs:

EX TR AL AR GE FR EN CH FR IE S*

or,

*E XT RA LA RG EF RE NC HF RI ES

It is the first option that is the most interesting. Since FR appears twice, there is only one place where this can fit into the code above, namely:

 EX

 TR

 AL

 AR

 GE

 FR

 EN

 CH

 FR

 IE

 S*

 BV

 XO

 BE

 BQ

 PG

 KO

 GE

 IK

 KO

 NA

 OS

s
I will try to use this crib to deduce the square that made this cipher.


First of all, let's look at the pair GE. GE becomes PG. Since G is repeated from the crib to the cipher, this means they are in the same row or column. Let's try column.s

 

 

E

 

G

P


Similary, EN=GE means N is in the same column as E and G .

N

 

E

 

G

P


IE not in the same column otherwise E is G .
IE=NA not in the same row because E and N are in the same column.
So IE are diagonal.

N

I

E

A

 

G

P


We now know EX are not in the same column. So EX= BV means

EB  XV  or  E  B
                    V  X

B is definitely in the same row and to the right of E. V and X are in the same row, but we don't know which way round.

N

I

 

E

A

B

G

P

or

N

 

I

 

E

B

A

G

P


Since AL=BE, and A, B, E are in the same row, then L must be in the same row.

N

I

L

E

A

B

G

P

 

 

If VX were in the same row as EB the row would have six letters. So VX is in a row below EB

N

I

L

E

A

B

G

P

 

 

V

X

We have filled a column! Exciting!


Since AB are next to each other in the same row, then AR=BQ means we might have AB RQ in the same row, but that would give us six letters in that row. So instead we must have QR next to each other on some row below AB .

AB

QR

 

A guess of PQR is very tempting since they are consecutive letters - assuming none of these letters are in the keyword.

N

I

L

E

A

B

G

 

P

Q

R

 

V

X



Using TR=XO we can see T and R are not next to each other in the same row or column. So we must have T diagonal of R :

O  R   or  RO
T  X         XT


Using FR=KO, since R and O are in the same row, FK must be in the same row. RO cannot be next to each other, otherwise FK  would be next to each other in the same row, giving six letters in the row. So using the first option above we have,

N

I

 

L

E

A

B

 

G

 

 

O

P

Q

R

T

V

X

and most likely

N

I

 

L

E

A

B

F

G

 

K

O

P

Q

R

T

V

X


Using CH=IK we get

N

I

C

L

E

A

B

 

F

G

H

K

 

O

P

Q

R

 

T

V

 

X


This fills in every letter from the crib.


We seem to be one column short! Let's start at AB and try to fill in consecutive letters, or near consecutive letters:

 

N

I

C

 

L

E

A

B

D

F

G

H

K

M

O

P

Q

R

S

T

V

W

X

 


 Is the keyword UNICYCLE ?

U

N

I

C

Y

L

E

A

B

D

F

G

H

K

M

O

P

Q

R

S

T

V

W

X

Z



And there we have it. We have completely deduced the square used to send the cipher.

If we use it to decode the message, we get:

"Well done for breaking the cipher! It was a playfair cipher, and the key word was unicycle. I will keep this message short as I am about to eat. I am very hungry, so I am going to order extra large french fries. Remember to send the solution to the enigma project. Bye."

 

 

 

 

 

This Web Page Created with PageBreeze Free HTML Editor