Transposition cipher
Problem
A transposition cipher is one which rearranges the order of the letters in the ciphertext (encoded text), according to some predetermined method, without making any substitutions.
Suppose we want to encrypt the following message, a quote from 'Peter Rabbit' by Beatrix Potter: "Now run along and don't get into mischief, I'm going out." Let's remove the punctuation and the spaces between the words to get: "nowrunalonganddontgetintomischiefimgoingout".
This is 44 letters long. For reasons we'll soon discover, let's add 4 extra padding characters, "x", at the end to now get: "nowrunalonganddontgetintomischiefimgoingoutxxxx".
We can now write this message in 4 rows, each 12 letters long.
n o w r u n a l o n g a n d d o n t g e t i n t o m i s c h i e f i a m g o i n g o u t x x x x
By reading the letters in order down the columns, instead of along the rows, we get:
"nnog odmo wdii rosh uncg ntho agiu leet otfx niix gnax atmx"
We can now send this message to our friend with the spaces removed, and the message is "hidden".
Suppose the enemy intercepts and wants to decipher our message. What might they do?
Once you have thought about how to decipher a message encoded in this way, read on below:
48 characters can be encoded using grids of one of these dimensions:
$1\times48, 2\times24, 3\times16, 4\times 12, 6 \times 8, 8 \times 6, 12 \times 4...$
The first of these doesn't rearrange the message at all.
The second size gives:
n n o g o d m o w d i i r o s n u n c g n t h o a g i u l e e t o t f x n i I x g n a x a t m x
Reading down the columns gives "nangoigu....". Definitely not English!
The next arrangement is a 3 by 16 grid:
n n o g o d m o w d i i r o s n u n c g n t h o a g i u l e e t o t f x n i I x g n a x a t m x
"nuonntocf", let's try again!
A 4 by 12 grid gives:
n n o g o d m o w d i i r o s n u n c g n t h o a g i u l e e t o t f x "nrannogi..." n i I x g n a x a t m x
and a 6 by 8 grid gives:
n n o g o d m o w d i i r o s n u n c g n t h o "nwuaog.."
a g i u l e e t o t f x n i I x g n a x a t m x
Hmm, let's keep trying! An 8 by 6 arrangement gives:
n n o g o d
m o w d i i r o s n u n "nmrcaena...." c g n t h o a g i u l e e t o t f x n i I x g n a x a t m x
A 12 by 4 sized grid gives:
n n o g o d m o w d i i r o s n u n c g n t h o
a g i u "nowrunalongand....", the start of our original message!
l e e t o t f x n i I x g n a x a t m x
Can you see why we chose a 48-character message rather than a 44-character message?
Imagine you have intercepted the message below, and you know it has been encrypted using a transposition cipher.
Can you decrypt the message?
ttanopnshonstpdeendoaiherltsmnemaihuogrebkedmhsdbendeeetiadenrlottin tsfbhupltefeonpyolaalnettflveedhhblewlsaieirefutnfnynodakogdtrdlarde sseibeoetoncoswprmleuhnwaeyhteweiwdasfhlgaodtoalhywnoutx
You might find it useful to work on squared paper.
If you want to work on a computer to solve the problem, you can download the message as a text file which doesn't contain any line breaks.
There is a transposition solver as part of our Cipher Challenge Toolkit.
If you are interested in code breaking you might enjoy the Secondary Cipher Challenge.
Many codebreakers use frequency analysis as their first 'tool'. If the distribution of letters in the cipher text does not reflect the usual distribution (with E, T, A and so on as the most common letters) it is likely that a substitution or more complex encryption has been used. If the distribution reflects what you would expect for standard text, it could be that the text has simply been transposed, as it has in this problem.
Of course, with very short cipher texts, it is difficult to get any meaningful data from a frequency analysis.
For more on frequency analysis and substitution ciphers, see this problem.
Getting Started
Remember you'll be able to tell quite quickly whether the sequence of letters you get from reading down the columns is English or not, so you don't need to decrypt the whole message if you don't think you've found the right sized grid.
Don't forget you can use the toolkit to help you decrypt this message.
Student Solutions
Thanks to everyone for all the great answers! The original message was:
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 what seemed to be a very deep well.
We removed all punctuation and capital letters from this message, so before it was encoded, it looked like this:
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 what seemed to be a very deep well x
What's going on? Grace, from Saint Cecilia's, has an idea:
The message is 192 letters long. The factors of 192 are 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96 and 192. I believe the original text had 191 letters and an x was used for padding to make it 192.
Yes, that's right - 192 has lots of factors, so it's harder to decode! Jack, from the Beacon School, had a quick way of spotting where to start:
I knew that the T at the start of the passage was most probably going to be followed with an H. So, on my piece of paper, I took the first H in the passage and moved it down a line so that the top of my passage was 8 letters across. Then I carried on to get an 8x24 block.
He later remarked:
I thought this must be a quote from a book, so I searched "The rabbit hole went straight on like a tunnel for some way and then dipped suddenly down" on Google. In a description of a website it had the quote and it also mentioned "Alice in Wonderland", so I went onto www.gutenberg.org (a website I knew from a previous challenge) and searched "Alice in Wonderland" in the Book Search. This text was in the 5th paragraph.
Martha, from Kings Norton Girls' School, tried a lot of blocks, and after finding the 24 by 8 arrangement made the rather sharp comment:
I chose not to continue with the grids as the chance that this was in fact not the intended message is so minute and the idea that this quote has in fact turned up by chance sounds verging on crazy!
Here is the secret message written in a 24 by 8 grid:
t t a n o p n s h o n s t p d e e n d o a i h e r l t s m n e m a i h u o g r e b k e d m h s d b e n d e e e t i a d e n r l o t t i n t s f b h u p l t e f e o n p y o l a a l n e t t f l v e e d h h b l e w l s a i e i r e f u t n f n y n o d a k o g d t r d l a r d e s s e i b e o e t o n c o s w p r m l e u h n w a e y h t e w e i w d a s f h l g a o d t o a l h y w n o u t x
and then transposing (i.e. reading down the columns) gives:
therabbitholewentstraigh
tonlikeatunnelforsomeway andthendippedsuddenlydow nsosuddenlythatalicehadn otamomenttothinkaboutsto ppingherselfbeforeshefou ndherselffallingdownwhat seemedtobeaverydeepwellx
Teachers' Resources
Why do this problem?
This problem makes use of students' knowledge about factors and multiples, presented in an intriguing context using the 'hook' of codebreaking.
Possible approach
This problem could follow on from Substitution Cipher where students are introduced to frequency analysis.
Start by performing a frequency analysis on this text:
ttanopnshonstpdeendoaiherltsmnemaihuogrebkedmhsdbendeeetiadenrlottin tsfbhupltefeonpyolaalnettflveedhhblewlsaieirefutnfnynodakogdtrdlarde sseibeoetoncoswprmleuhnwaeyhteweiwdasfhlgaodtoalhywnoutx
It is available here as a text file.
Invite the class to comment on what they notice. As they realise that the distribution of letters matches that of ordinary English, invite suggestions as to how the text might have been encoded if not by substitution.
Show the "Peter Rabbit" example from the problem, showing how to encode text using a transposition cipher. This set of PowerPoint slides describes each step of the encryption and decryption process.
Then hand out this worksheet with the text above, and invite students to decode it.
Students could then create their own transposition ciphers and challenge the rest of the class to decipher them.
If computers are available, students might want to use our Cipher Challenge Toolkit which contains a transposition solver.
Key questions
Why might you choose a 48 character message rather than a 44 character one?
Possible extension
The Secondary Cipher Challenge and Substitution Transposed offer challenging extensions for students who have worked on this problem and the problem Substitution Cipher.
Possible support
Encourage students to work collaboratively. Working on squared paper is really helpful.