Double Transposition Matrix

Problem

Decrypt the ciphertext
IAUTMOCSMNIMREBOTNELSTRHEREOAEVMWIHTSEEATMAEOHWHSYCEELTTEOHMUOUFEHTRFT
This message was encrypted with a double transposition using a matrix of 7 rows
and 10 columns. Hint: The first word is “there.”

Note: This is from Mark Stamp's Information Security: Principles and Practice book, chapter 2. Solution below was submitted as homework for CS265 Cryptography and Information Security class at San Jose State University.

Solution

Step 1: Spread the ciphertext across a  7x10 matrix

	0	1	2	3	4	5	6	7	8	9
0	I	A	U	T	M	O	C	S	M	N
1	I	M	R	E	B	O	T	N	E	L
2	S	T	R	H	E	R	E	O	A	E
3	V	M	W	I	H	T	S	E	E	A
4	T	M	A	E	O	H	W	H	S	Y
5	C	E	E	L	T	T	E	O	H	M
6	U	O	U	F	E	H	T	R	F	T

Step 2: Try to rearrange the columns in at least one row to form the words ‘THERE’. Here we spot ‘HERE’ and see a T in row #2, so we know we can form “THERE” on that row. And we also see that we can form the words “ARE”, “SO” from the remaining letters in that row, so we can form the phrase “THERE ARE SO” in row #2

	1	3	4	5	6	8	2	9	0	7
0	A	T	M	O	C	M	U	N	I	S
1	M	E	B	O	T	E	R	L	I	N
2	T	H	E	R	E	A	R	E	S	O
3	M	I	H	T	S	E	W	A	V	E
4	M	E	O	H	W	S	A	Y	T	H
5	E	L	T	T	E	H	E	M	C	O
6	O	F	E	H	T	F	U	T	U	R

Step 3: One of the remaining rows need to have the next word. We can guess the next word to be MANY or “SOME” (taking SO from row #2 and ME from one of the other rows. We can’t form MANY, but can form ME. So we think of the next word and guess it to be WHO. Then we see that we can form ME and WHO on row #4, but need to change the columns, where there were multiple Es  in column 6,4 when we arranged them for row #2. So we get the phrase: THERE ARE SOME WHO SAY TH

	1	3	6	5	4	8	2	9	0	7
0	A	T	C	O	M	M	U	N	I	S
1	M	E	T	O	B	E	R	L	I	N
2	T	H	E	R	E	A	R	E	S	O
3	M	I	S	T	H	E	W	A	V	E
4	M	E	W	H	O	S	A	Y	T	H
5	E	L	E	T	T	H	E	M	C	O
6	O	F	T	H	E	F	U	T	U	R

Step 4: The TH at the ending of our phrase can only be THAT. We see that row #1 has AT to complete the word THAT. So we rearrange the rows to form the phrase: THERE ARE SOME WHO SAY THAT COMMUNIS

	1	3	6	5	4	8	2	9	0	7
2	T	H	E	R	E	A	R	E	S	O
4	M	E	W	H	O	S	A	Y	T	H
0	A	T	C	O	M	M	U	N	I	S
1	M	E	T	O	B	E	R	L	I	N
3	M	I	S	T	H	E	W	A	V	E
5	E	L	E	T	T	H	E	M	C	O
6	O	F	T	H	E	F	U	T	U	R

Step 5: COMMUNIS can either be COMMUNISM or COMMUNIST. Row #1, 3 help to form COMMUNISM, but row #3 has IS THE WAVE as coherent English phrase. So we pick that as the next row to get: THERE ARE SOME WHO SAY THAT COMMUNISM IS THE WAVE

	1	3	6	5	4	8	2	9	0	7
2	T	H	E	R	E	A	R	E	S	O
4	M	E	W	H	O	S	A	Y	T	H
0	A	T	C	O	M	M	U	N	I	S
3	M	I	S	T	H	E	W	A	V	E
1	M	E	T	O	B	E	R	L	I	N
5	E	L	E	T	T	H	E	M	C	O
6	O	F	T	H	E	F	U	T	U	R

Step 6: Next possible word could be OF or TO. We can find OF in row #6, but can’t find TO. So using row #6, we now get: THERE ARE SOME WHO SAY THAT COMMUNISM IS THE WAVE OF THE FUTUR

	1	3	6	5	4	8	2	9	0	7
2	T	H	E	R	E	A	R	E	S	O
4	M	E	W	H	O	S	A	Y	T	H
0	A	T	C	O	M	M	U	N	I	S
3	M	I	S	T	H	E	W	A	V	E
6	O	F	T	H	E	F	U	T	U	R
1	M	E	T	O	B	E	R	L	I	N
5	E	L	E	T	T	H	E	M	C	O

Step 7: FUTUR can only be FUTURE and row #5 hence forms the next row and we get back the original matrix with the phrase: THERE ARE SOME WHO SAY THAT COMMUNISM IS THE WAVE OF THE FUTURE LET THEM COME TO BELIN

	1	3	6	5	4	8	2	9	0	7
2	T	H	E	R	E	A	R	E	S	O
4	M	E	W	H	O	S	A	Y	T	H
0	A	T	C	O	M	M	U	N	I	S
3	M	I	S	T	H	E	W	A	V	E
6	O	F	T	H	E	F	U	T	U	R
5	E	L	E	T	T	H	E	M	C	O
1	M	E	T	O	B	E	R	L	I	N

Step 8: Add punctuation marks to get lines from John F. Kennedy’s famous speech from 1963.

Plaintext:

THERE ARE SOME WHO SAY THAT COMMUNISM IS THE WAVE OF THE FUTURE. LET THEM COME TO BELIN.