Today I thought we could talk a little bit about Columnar Transposition Ciphers (hereby called CTC for short), let’s start with discussing what a CTC is.
A CTC is a simple encryption method using a shared key between the participants, where the characters in a clear text message gets shifted around in a specific predetermined way in a matrix.
Let’s say that Alice wants to send Bob a message about a secret meeting place. They’ve previously decided on a shared key, QUIET. She then writes her message “meet me at the cafe on main street tomorrow at noon”. Next step is to create the matrix based on their key.
QUIET meetm eatth ecafe onmai nstre ettom orrow atnoo nspeq
The letters at the end are randomized to to pad the matrix. Next Alice write out the columns in lexicographical order based on the key. With this key would be in the order of E, I, Q, T, and U. The encrypted message would then look like this: ttfaroooe etamttrnp meeoneoan mheiemwoq eacnstrts
Alice then sends this encrypted message to Bob who reconstructs the matrix, using the same key, by filling in the columns in the key’s lexicographical order. After the columns have been filled in, the matrix will look like the example above and Bob can read the message in clear text line by line.
Code example
The following example is written in C# but should be pretty easy to rewrite into any other object oriented language.
The code consists of three classes, Encipher, Decipher, and an abstract class Cipher that they inherit common and helper methods from.
public class Encipher : Cipher
{
public Encipher(string clearText, string key) : base(key)
{
int rows = clearText.Length / Key.Length + (clearText.Length % Key.Length > 0 ? 1 : 0);
Grid = new char[rows, Key.Length];
FillGrid(clearText);
}
public string DoCipher()
{
string cipheredText = "";
string sortedKey = string.Concat(Key.OrderBy(c => c));
foreach (char ch in sortedKey)
{
int column = Key.IndexOf(ch);
cipheredText += GetColumnText(column);
}
return cipheredText;
}
private void FillGrid(string text)
{
int stringPosition = 0;
for (int i = 0; i < Grid.GetLength(Row); i++)
{
for (int j = 0; j < Grid.GetLength(Column); j++)
{
Grid[i, j] = GetChar(text.ToUpper(), stringPosition++);
}
}
}
}Let’s look at what the code in the Encipher class does.
public Encipher(string clearText, string key) : base(key)
{
int rows = clearText.Length / Key.Length + (clearText.Length % Key.Length > 0 ? 1 : 0);
Grid = new char[rows, Key.Length];
FillGrid(clearText);
}The constructor takes two arguments, the clear text message and the key we will use to encrypt. We calculate the number of rows the grid will have based on the key length. The modulus part is to make sure that we add an extra row if the characters can’t be divided equally.
private void FillGrid(string text)
{
int stringPosition = 0;
for (int i = 0; i < Grid.GetLength(Row); i++)
{
for (int j = 0; j < Grid.GetLength(Column); j++)
{
Grid[i, j] = GetChar(text.ToUpper(), stringPosition++);
}
}
}The FillGrid method loops over the rows and columns and places the characters into the matrix. We also want to make sure we only use upper or lowercase letters, in this case I chose to go with uppercase.
public string DoCipher()
{
string cipheredText = "";
string sortedKey = string.Concat(Key.OrderBy(c => c));
foreach (char ch in sortedKey)
{
int column = Key.IndexOf(ch);
cipheredText += GetColumnText(column);
}
return cipheredText;
}The DoCipher method sorts the key in lexicographical order and then goes through the sorted key and concatenates the characters in the corresponding column to our cipheredText variable.
public class Decipher : Cipher
{
public Decipher(string encryptedText, string key) : base(key)
{
if (encryptedText.Length % Key.Length > 0)
{
throw new ArgumentException($"The key '{Key}' has an unexpected length.");
}
int rows = encryptedText.Length / Key.Length;
Grid = new char[rows, Key.Length];
FillGrid(encryptedText);
}
private void FillGrid(string text)
{
int stringPosition = 0;
string sortedKey = string.Concat(Key.OrderBy(c => c));
foreach (char ch in sortedKey)
{
int column = Key.IndexOf(ch);
for (int i = 0; i < Grid.GetLength(Row); i++)
{
Grid[i, column] = GetChar(text.ToUpper(), stringPosition++);
}
}
}
public string DoDecipher()
{
string clearText = "";
for (int i = 0; i < Grid.GetLength(Row); i++)
{
for (int j = 0; j < Grid.GetLength(Column); j++)
{
clearText += Grid[i, j];
}
}
return clearText;
}
}Now let’s look at the Decipher class.
public Decipher(string encryptedText, string key) : base(key)
{
if (encryptedText.Length % Key.Length > 0)
{
throw new ArgumentException($"The key '{Key}' has an unexpected length.");
}
int rows = encryptedText.Length / Key.Length;
Grid = new char[rows, Key.Length];
FillGrid(encryptedText);
}The constructor in the Decipher class also takes two parameters, the encrypted string and the key. We start with checking if the message can be divided equally by the key, if not the key has the incorrect length.
private void FillGrid(string text)
{
int stringPosition = 0;
string sortedKey = string.Concat(Key.OrderBy(c => c));
foreach (char ch in sortedKey)
{
int column = Key.IndexOf(ch);
for (int i = 0; i < Grid.GetLength(Row); i++)
{
Grid[i, column] = GetChar(text.ToUpper(), stringPosition++);
}
}
}When we fill in the grid in the Decipher class we first sort the key in lexicographical order and then fill in the encrypted message into the matrix column by column in the sorted key’s order.
public string DoDecipher()
{
string clearText = "";
for (int i = 0; i < Grid.GetLength(Row); i++)
{
for (int j = 0; j < Grid.GetLength(Column); j++)
{
clearText += Grid[i, j];
}
}
return clearText;
}To decipher the message we then simply read the clear text message line by line.
public abstract class Cipher
{
private const string VALID_KEY_CHARACTERS = "^[A-Z0-9]{2,}$";
private const int CHAR_A = 65;
private const int CHAR_Z = 90;
protected const int Row = 0;
protected const int Column = 1;
protected char[,] Grid { get; set; }
protected string Key { get; }
protected Cipher(string key)
{
Key = key.Trim().ToUpper();
if (!IsKeyValid())
{
throw new ArgumentException(
$"{Key} is not a valid key. The key must be at least 2 characters, only use alphanumeric " +
"characters, and can't contain duplicate characters.");
}
}
private bool IsKeyValid()
{
return !(
from c in Key
group c by c
into grp
where grp.Count() > 1
select grp.Key
).Any() &&
Regex.IsMatch(Key, VALID_KEY_CHARACTERS);
}
internal char GetChar(string text, int stringPosition)
{
if (stringPosition >= text.Length)
{
return (char) new Random().Next(CHAR_A, CHAR_Z + 1);
}
return text[stringPosition];
}
internal string GetColumnText(int column)
{
string columnText = "";
for (int i = 0; i < Grid.GetLength(Row); i++)
{
columnText += Grid[i, column];
}
return columnText;
}
public void PrintGrid(bool printHeader = false)
{
if (printHeader)
{
PrintHeader();
}
PrintLine();
for (int i = 0; i < Grid.GetLength(Row); i++)
{
Console.Write("|");
for (int j = 0; j < Grid.GetLength(Column); j++)
{
Console.Write($"{Grid[i, j]}|");
}
Console.WriteLine();
}
PrintLine();
}
private void PrintHeader()
{
PrintLine();
Console.Write("|");
foreach (char ch in Key)
{
Console.Write($"{ch}|");
}
Console.WriteLine();
}
private void PrintLine()
{
Console.WriteLine("+".PadRight(Key.Length * 2, '-') + "+");
}
}The Cipher class is pretty straight forward but we’ll take a look at a few things.
private const string VALID_KEY_CHARACTERS = "^[A-Z0-9]{2,}$";
// ...
private bool IsKeyValid()
{
return !(
from c in Key
group c by c
into grp
where grp.Count() > 1
select grp.Key
).Any() &&
Regex.IsMatch(Key, VALID_KEY_CHARACTERS);
}The IsKeyValid method checks that each character in the key is unique, is alphanumerical and at least two characters long.
private const int CHAR_A = 65;
private const int CHAR_Z = 90;
// ...
internal char GetChar(string text, int stringPosition)
{
if (stringPosition >= text.Length)
{
return (char) new Random().Next(CHAR_A, CHAR_Z + 1);
}
return text[stringPosition];
}The GetChar method simply return a character at a specific position in the message, or if the position is outside the scope of the message (e.g. when we fill in a clear text message that can’t be divided equally with the key) we return a random letter instead.
Using the code
To use the code in this example you can simply call the code something like this.
Console.Write("Type the text to encode: ");
string clearText = Console.ReadLine();
Console.Write("Type the key to use: ");
string key = Console.ReadLine();
Encipher encipher = new Encipher(clearText, key);
encipher.PrintGrid(true);
string encipheredText = encipher.DoCipher();
Console.WriteLine(encipheredText);
Decipher decipher = new Decipher(encipheredText, key);
decipher.PrintGrid(true);
Console.WriteLine(decipher.DoDecipher());Using the example with Alice and Bob we get this output.
Type the text to encode: meetmeatthecafeonmainstreettomorrowatnoon Type the key to use: quiet +---------+ |Q|U|I|E|T| +---------+ |M|E|E|T|M| |E|A|T|T|H| |E|C|A|F|E| |O|N|M|A|I| |N|S|T|R|E| |E|T|T|O|M| |O|R|R|O|W| |A|T|N|O|O| |N|H|M|P|C| +---------+ TTFAROOOPETAMTTRNMMEEONEOANMHEIEMWOCEACNSTRTH +---------+ |Q|U|I|E|T| +---------+ |M|E|E|T|M| |E|A|T|T|H| |E|C|A|F|E| |O|N|M|A|I| |N|S|T|R|E| |E|T|T|O|M| |O|R|R|O|W| |A|T|N|O|O| |N|H|M|P|C| +---------+ MEETMEATTHECAFEONMAINSTREETTOMORROWATNOONHMPC
Conclusion
CTC is one of my favorite ciphers because it’s so simple to use even when using pen and paper. It should not however be considered secure by any stretch of the imagination. If you decide to use this cipher you should combine it with another kind of cipher, even combining with a simple substitution cipher makes this more difficult to decrypt.
There’s one flaw, or feature depending on how you look at it, with this method. Both people doesn’t have to use the same key, the important thing is that the columns are sorted the same. Let’s say Alice uses a simple three letter key like JOB. If we look at the order we will use the key it will be B=1, J=2, and O=3. If Bob uses another key with the same 231 pattern, e.g. SPA, he can decipher the message even though he doesn’t use the same key.
You can download the demo code from github.
Featured image by Pete Linforth from Pixabay
Jimmie is a full stack developer with over 13 years working experience in building web based solutions and over 25 years of programming experience over all.
Jimmie has worked with a slew programming languages over the years, but his main focus is usually on web frameworks such as Symfony, Angular, and Spring Boot.