Wednesday, June 01, 2011

How to break the New Scientist cipher puzzle (part 3)

New Scientist had a little cipher challenge with four ciphers that needed breaking. The hardest of which (at least for me) was part 3. It's a form of transposition cipher where the letters are simply juggled around.

Here's the cipher text:
```EUINRECSTNCIHRLYYEORYNDPUPTAIPTSNIONOUEIODMNTHIBTN
THETESSREECWOEECLFOHNRPFRESRLIQDIHCYONOUEFCUOFLICS
ERPDTHNLYVOPEOEKTSTLVOTBEYEHGEDRERTHEMASLPOQISUSHO
WYTIPRRIWLYHMEINDPEOVNOTCIORAERTTBPLEATTHHNSEIETEE
CEPCSJRRNENDIEUSTNOTUFCBTAUITRIHPTSRTLEESNEHELESIA
UNTSEVTAEGUTTRANEEESTEDNTTGTNEKTHTODHAHERCTSAYHTEC
KNHOASUETHOUMLITDERFFYTIWANHHSREOSSTTDPEVUOEHEAFBO
LLEDN
```
There are exactly 355 characters there, and 5 is a divisor of 355 so write out the characters in blocks of 5:
```E U I N R
E C S T N
C I H R L
Y Y E O R
Y N D P U
P T A I P
T S N I O
N O U E I
O D M N T
H I B T N
T H E T E
S S R E E
C W O E E
C L F O H
N R P F R
E S R L I
Q D I H C
Y O N O U
E F C U O
F L I C S
E R P D T
H N L Y V
O P E O E
K T S T L
V O T B E
Y E H G E
D R E R T
H E M A S
L P O Q I
S U S H O
W Y T I P
R R I W L
Y H M E I
N D P E O
V N O T C
I O R A E
R T T B P
L E A T T
H H N S E
I E T E E
C E P C S
J R R N E
N D I E U
S T N O T
U F C B T
A U I T R
I H P T S
R T L E E
S N E H E
L E S I A
U N T S E
V T A E G
U T T R A
N E E E S
T E D N T
T G T N E
K T H T O
D H A H E
R C T S A
Y H T E C
K N H O A
S U E T H
O U M L I
T D E R F
F Y T I W
A N H H S
R E O S S
T T D P E
V U O E H
E A F B O
L L E D N
```
If you stare that this you'll see some words appear. In fact, the third column reads (downwards) ISHEDANUMBEROFPRINCIPLESTHEMOSTIMPORTANTPRINCIPLES
TATEDTHATTHEMETHODOFE
or ISHED A NUMBER OF PRINCIPLES THE MOST IMPORTANT PRINCIPLE STATED THAT THE METHOD OF E. So, switch the columns around into rows for easier readability.
```EECYYPTNOHTSCCNEQYEFEHOKVYDHLSWRYNVIRLHICJNSUAIRSLUVUNTTKDRYKSOTFARTVEL
UCIYNTSODIHSWLRSDOFLRNPTOEREPUYRHDNOTEHEERDTFUHTNENTTEEGTHCHNUUDYNETUAL
ISHEDANUMBEROFPRINCIPLESTHEMOSTIMPORTANTPRINCIPLESTATEDTHATTHEMETHODOFE
NTROPIIENTTEEOFLHOUCDYOTBGRAQHIWEETABTSECNEOBTTEHISERENNTHSEOTLRIHSPEBD
RNLRUPOITNEEEHRICUOSTVELEETSIOPLIOCEPTEESEUTTRSEEAEGASTEOEACAHIFWSSEHON
```
Now for a guess. Guess that that final E on line three is the start of the word ENCRYPTION and that the N on the next line is the next letter. Is it possible to find the complete word? Yes, by following a zig zag pattern. To make this easier rearrange the rows.
```EECYYPTNOHTSCCNEQYEFEHOKVYDHLSWRYNVIRLHICJNSUAIRSLUVUNTTKDRYKSOTFARTVEL
ISHEDANUMBEROFPRINCIPLESTHEMOSTIMPORTANTPRINCIPLESTATEDTHATTHEMETHODOFE
NTROPIIENTTEEOFLHOUCDYOTBGRAQHIWEETABTSECNEOBTTEHISERENNTHSEOTLRIHSPEBD
UCIYNTSODIHSWLRSDOFLRNPTOEREPUYRHDNOTEHEERDTFUHTNENTTEEGTHCHNUUDYNETUAL
RNLRUPOITNEEEHRICUOSTVELEETSIOPLIOCEPTEESEUTTRSEEAEGASTEOEACAHIFWSSEHON
```
The bolded characters form the sentence NCRYPTION ITSELF SHOULD NOT BE REQUIRED TO BE SECRET BUT THE STRENGTH SHOULD INSTEAD and the non-bolded zig zag characters read UTIONISED THE WORLD OF CRYPTOGRAPHY WHEN AT THE END OF THE NINETEENTH CENTURY HE PUBL.

That just leaves two lines of cipher:
```EECYYPTNOHTSCCNEQYEFEHOKVYDHLSWRYNVIRLHICJNSUAIRSLUVUNTTKDRYKSOTFARTVEL
RNLRUPOITNEEEHRICUOSTVELEETSIOPLIOCEPTEESEUTTRSEEAEGASTEOEACAHIFWSSEHON
```
Again the zig zag pattern applies and it's possible to read RELY UP ON THE SECRECY OF THE KEY THIS PRINCIPLE IS JUST AS RELEVANT TODAY AS IT WAS THEN and ENCRYPTION TECHNIQUES EVOLVED SLOWLY OVER THE CENTURIES AUGUSTE KERCKHOFFS REVOL

Put it all together and you have: ENCRYPTION TECHNIQUES EVOLVED SLOWLY OVER THE CENTURIES AUGUSTE KERCKHOFFS REVOLUTIONISED THE WORLD OF CRYPTOGRAPHY WHEN AT THE END OF THE NINETEENTH CENTURY HE PUBLISHED A NUMBER OF PRINCIPLES THE MOST IMPORTANT PRINCIPLE STATED THAT THE METHOD OF ENCRYPTION ITSELF SHOULD NOT BE REQUIRED TO BE SECRET BUT THE STRENGTH SHOULD INSTEAD RELY UPON THE SECRECY OF THE KEY THIS PRINCIPLE IS JUST AS RELEVANT TODAY AS IT WAS THEN.

PS Hot on the heels of this post is the official answer from New Scientist which also revealed that I was one of the winners. They also explain the actual technique used for part 3. I broke it without spotting the simple pattern that makes it work and by making a 'lucky' guess.