Friday, March 14, 2014

Encryption 101: Columnar Transposition Cipher

Jack Hammond
Junior Developer
Egress Software Technologies Ltd.
As part of the Encryption 101 series, we’ve previously looked at the Caesar cipher – a simple transposition cipher that sees every letter in the plaintext shifted by a set number (otherwise known as the key). So, for example, using a key of ‘4’, the following encryption occurs:

Plaintext: We can only see a short distance ahead, but we can see plenty there that needs to be done

Ciphertext: Ai ger srpc wii e wlsvx hmwxergi elieh, fyx ai ger wii tpirxc xlivi xlex riihw xs fi hsri

Columnar transposition

This post will focus on a columnar transposition cipher – a slightly more advanced transposition cipher that produces very different results. If we take the same phrase as above and run it through a columnar transposition cipher, the ciphertext would read:

OETNAEEYTEEX ASOTHTSNRNOE NERAEWETEEBX CYHSAUNEETTN WNADCDCPTHDD ELSIEBALHASO

Right away, we can see that this looks vastly different to the previous result: if you saw these two pieces of ciphertext next to each other, you’d initially have no way of knowing that they contained an identical message.

Working with columns

As with every cipher, you first need to define a key. For this example, we’ll be using the keyword of ‘Turing’, which will define how many columns we’ll use to encrypt the message: since the keyword has six letters in it, we’ll be using six columns.

To encrypt the text, we write each letter of the keyword at the top of a column. In the next row, each letter is given a number that dictates its alphabetical position in the keyword: since ‘G’ is the first letter of the alphabet that is present in the keyword, it gets designated ‘1’; ‘I’ is given ‘2’ as it appears next; and so on. Then we simply write the text we wish to encrypt out under it, moving to a new line once we reach the end of each row. (As we are using Regular Case transposition in this example, any empty cells at the end have been padded with the letter ‘X’.)

T
U
R
I
N
G
5
6
4
2
3
1
W
E
C
A
N
O
N
L
Y
S
E
E
A
S
H
O
R
T
D
I
S
T
A
N
C
E
A
H
E
A
D
B
U
T
W
E
C
A
N
S
E
E
P
L
E
N
T
Y
T
H
E
R
E
T
H
A
T
N
E
E
D
S
T
O
B
E
D
O
N
E
X
X

Using this table, we can now create our ciphertext. Starting with the column ‘1’ (‘G’ in this case), we now read down the whole column, writing out each letter in turn, which results in:

OETNAEEYTEEX ASOTHTSNRNOE NERAEWETEEBX CYHSAUNEETTN WNADCDCPTHDD ELSIEBALHASO.

Decrypting

Now that we have an encrypted piece of text, we need to know how to recover the actual message. If you know the keyword, this process is fairly straight forward. All you do is start with the letter in the keyword that appears first in the alphabet, in this case G, and put this at the top of the first column. Then put the letter that appears next in the alphabet at the top of the second column, etc.

With that done, start writing out the ciphertext – however, whereas before we wrote across the rows, this time we write down the columns.


G
I
N
R
T
U
1
2
3
4
5
6
O
A
N
C
W
E
E
S
E
Y
N
L
T
O
R
H
A
S
N
T
A
S
D
I
A
H
E
A
C
E
E
T
W
U
D
B
E
S
E
N
C
A
Y
N
T
E
P
L
T
R
E
E
T
H
E
N
E
T
H
A
E
O
B
T
D
S
X
E
X
N
D
O

Once the columns have been written out, rearrange them so the keyword makes sense and then read the resulting text off row-by-row.

Increased complexity = Increased security?

This initially seems to be a more complex method of encryption compared to the simple transposition cipher – and therefore it surely must provide more security? The answer is both ‘yes’ and ‘no’.

When this cipher was first created, it would have of course provided more security than those that came before it. However, it still possesses one weakness that was present in earlier ciphers: namely, the letter frequency will still closely resemble that of the original plaintext, thus making the ciphertext potentially vulnerable to a frequency analysis attack.

Your turn to crack the code (try these at your desk!)

Try the following examples at your desk and see if you get the correct results. Since these might take a while to crack, there are only two this time.
  1. Using the ‘encryption’ as a keyword, encrypt the following phrase (with ‘x’ as padding if needed):
    • “The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers” (Bill Gates)
    • Answer: etbgeoyautmaoenwreottlpacrshaludtalnscrbeyomxuihdmstixvmaolnfeeohrhvftrmiakuoeaprbeeweaogb
  2. Using ‘cryptography’ as a keyword, decrypt the following ciphertext:
    • oafntplnpyimrsexyedlccbegsixhhidtwfarkyleithapax
    • Answer: The cryptographic key was split by Diffie and Hellman

No comments:

Post a Comment