mathschallenge.net logo

In The Beginning

Problem

One of the methods used to encrypt a message is to use the message itself. We begin by providing a secret number that is used for the offset of the first letter and is known only to sender and receiver. This starting value is called a seed. For example, if we encode the word, CAT, we begin by finding the alphabetic value of each letter: 3, 1 and 20; and then use the value of the previous letter as an offset, with the first letter using the seed value.

Suppose the seed is 5:

C (3) maps (3 + 5[seed] = 8) H
A (1) maps (1 + 3[1st letter] = 4) D
T (20) maps (20 + 1[2nd letter] = 21) U

So the encoded message is HDU. It should be clear how, using the seed 5, it is possible to decode it easily.

However, your task is to decode the following message without being told the seed:

X B M W W N B G C U A O O M W N W H C V R Y L S W A Q

Good luck!


Solution

It should have been clear that there can be no more than 25 possible seeds to try. Despite the apparent polyalphabetic nature, it is, in fact, a monoalphabetic cipher with a clever twist and is similar in principle to cracking a Caesar-shift cipher. In addition, it seems that there is no easy method of decoding other than trying each combination.

It helps to write the alphabetic values for each of the encoded letters:

X  B  M  W  W  N  B  G  C  U  A  O  O  M
24 02 13 23 23 14 02 07 03 21 01 15 15 13
W  N  W  H  C  V  R  Y  L  S  W  A  Q
23 14 23 08 03 22 18 25 12 19 23 01 17

By starting with a seed of 1 and working upwards, we can analyse the first, say 5, letters to look for anything promising.

Seed 1:
X (24) maps (24 – 1 = 23) W
B (2) maps (2 – 23 = 5) E [Note that it was necessary to wrap around the alphabet]
M (13) maps (13 – 5 = 8) H
W (23) maps (23 – 8 = 15) O
W (23) maps (23 – 15 = 8) H
Doesn't look very promising.

Seed 2:
X (24) maps (24 – 2 = 22) V
B (2) maps (2 – 22 = 6) F
No need to proceed with this one!

Seed 3:
X (24) maps (24 – 3 = 21) U
B (2) maps (2 – 21 = 7) G
M (13) maps (13 – 7 = 6) F
No need to continue with this one either!

Seed 4:
X (24) maps (24 – 4 = 20) T
B (2) maps (2 – 20 = 8) H
M (13) maps (13 – 8 = 5) E
W (23) maps (23 – 5 = 18) R
W (23) maps (23 – 18 = 5) E
This looks very encouraging and fortunately for us the seed turns out to be 4; revealing the message:

THERE IS NO FUTURE IN TIME TRAVEL

Obviously this trial and improvement method is a little tedious, so once you"ve tried a seed of 1, can you find a more efficient way of decoding with subsequent seeds?

By adapting the method, can you find a more secure system?

Problem ID: 5 (Aug 2000)     Difficulty: 1 Star

Only Show Problem