kdb programming challenge – rotating substitution cipher

Blog kdb+ 4 Jul 2014

Matt Doherty

[image type=”thumbnail” src=”7110″ alt=”The Enigma Machine” link=”true” href=”http://en.wikipedia.org/wiki/Enigma_machine” target=”blank”]

Puzzle 3 – Rotating Substitution Cipher

In cryptography one of the simplest forms of encryption is the substitution cipher, where you take each letter and pick a replacement for it. Encryption is then as simple as substituting each letter in your message with the replacement letter from the cipher. This type of encryption is usually not difficult to break, since much of the structure in the underlying information remains.

A type of encryption which represents a big improvement on simple substitution is stateful encryption, the simplest form of which is the rotating cipher. In this form of encryption you have a substitution map the same as before, but each time a letter is encoded the cipher is shifted by one character. For example, if our cipher is the alphabet reversed:

`“ZYXWVUTSRQPONMLKJIHGFEDCBA”`

And our message is:

`“HELLO”`

The cipher takes the first letter “H” and maps that to “S”. The cipher is then shifted by one index and the next letter is encoded the same way, but with the new cipher:

`“YXWVUTSRQPONMLKJIHGFEDCBAZ”`

So “E” now maps to “U”. The full message will be encrypted as “SUMLH”.
This week’s challenge is to write two functions that takes a cipher and message as arguments; one will encrypt the message, and the other decrypts it. The functions should be of the form:

```e:{[c;m]} d:{[c;em]}```

Note that you can assume the only characters used in the message and cipher will be the 26 upper case letters.

[showhide type=”post” more_text=”Show Solution” less_text=”Solution” hidden=”yes”]

```e:{[c;m]c mod[til[count m]+.Q.A?m;26]} d:{[c;em].Q.A mod[neg[til[count em]]+c?em;26]}```

Lets break down the encryption function a little. First we find the index of each letter in our message in the alphabet:

```q).Q.A?m 7 4 11 11 14```

Then add the list 0 1 2 3… to these indices, effectively simulating the cipher rotation:

```q) til[count m]+.Q.A?m 7 5 13 14 18```

And finally apply a modulus and then index into our cipher to produce the encrypted message:

```q) c mod[til[count m]+.Q.A?m;26] “SUMLH”```

The decryption function works in a very similar manner.

[/showhide]

Extra challenge

You’ve intercepted an encrypted message from AquaA Analytics HQ, along with a partial cipher to decrypt it:

```Message: "TOZQLIRKRKQRMIHQXDTNEBEHNGBXUDUVWWSDOPQ" Partial cipher:"THEQUICKB “```

where the partial cipher is the first 9 characters of the full 26 character cipher. Good men and women died to bring you this information, can you decrypt the message? (hint: the message starts with AQUAQ and ends with CIPHER)