Decrypting Texts Encrypted With Irregular Columnar Transposition

What do you do when the text does not fill up the columns?

Decrypting Texts Encrypted With Irregular Columnar Transposition

You're presented with the following encrypted text and the key: Welchman.

LAOAE CEDOS EEOHN NAHRE FESSV EGEGA SCJMS WDPSD OTIAS

The only other thing you know is the encryption method, columnar transposition. How will you decrypt this message? If you count the number of letters in the encrypted text, you'll get 45. The key is an 8 lettered word, so we get 8 columns. I'm assuming you can decrypt this easily if the message's length is divisible by key's length; it means the letters will fill the required table without leaving an empty cell. But that is not the case here.

The original text must have been encrypted using a table like this (The columns are numbered according to the order of letters in the key):

Order of Letters in Key
W E L C H M A N
8 3 5 2 4 6 1 7
8 3 5 2 4 6 1 7
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - -

45 is not divisible by 8 (it will not result in an integer), this means the three empty cells were not filled. This can present significant trouble during decryption. When arranging the encrypted text in a table for decryption, it is impossible to know the length of each column.

L E O R V S W O
A D H E E C D T
O O N F G J P I
A S N E E M S A
E E A S G S D S
C E H S A

You may want to try this, but it just won't work. The trick is to use the key to map the columns from the original message to the encrypted message.

Again, let's consider the original table:

8 3 5 2 4 6 1 7
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - -

When we sort the columns, we get the following:

1 2 3 4 5 6 7 8
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - -

This is how the encrypted message should be arranged in a table. If we enter the encrypted text into the table column by column, we get this:

1 2 3 4 5 6 7 8
L C E H S A S D
A E O R V S W O
O D H E E C D T
A O N F G J P I
E S N E E M S A
E A S G S

Now, we're sure we've entered the encrypted text into the table in the correct order, and we can rearrange the columns, using the key, to get the original text:

8 3 5 2 4 6 1 7
D E S C H A L S
O O V E R S A W
T H E D E C O D
I N G O F J A P
A N E S E M E S
S A G E S

When we read out the text row after row, we get this:

DESCHALSOOVERSAWTHEDECODINGOFJAPANESEMESSAGES

A careful look will help us add spaces in required places.

DESCH ALSO OVERSAW THE DECODING OF JAPANESE MESSAGES

That is the original text.