Columnar Transposition Cipher
Given a plain-text message and a numeric key, cipher/de-cipher the given text using Columnar Transposition Cipher The Columnar Transposition Cipher is a form of transposition cipher just like Rail Fence Cipher. Columnar Transposition involves writing the plaintext out in rows, and then reading the ciphertext off in columns one by one.
Examples:
Encryption Input : Beginner for Beginner Key = HACK Output : e kefGsGsrekoe_ Decryption Input : e kefGsGsrekoe_ Key = HACK Output : Beginner for Beginner Encryption Input : Beginner on work Key = HACK Output : e w_eoo_Gs kknr_ Decryption Input : e w_eoo_Gs kknr_ Key = HACK Output : Beginner on work
Encryption
In a transposition cipher, the order of the alphabets is re-arranged to obtain the cipher-text.
- The message is written out in rows of a fixed length, and then read out again column by column, and the columns are chosen in some scrambled order.
- Width of the rows and the permutation of the columns are usually defined by a keyword.
- For example, the word HACK is of length 4 (so the rows are of length 4), and the permutation is defined by the alphabetical order of the letters in the keyword. In this case, the order would be “3 1 2 4”.
- Any spare spaces are filled with nulls or left blank or placed by a character (Example: _).
- Finally, the message is read off in columns, in the order specified by the keyword.
Decryption
- To decipher it, the recipient has to work out the column lengths by dividing the message length by the key length.
- Then, write the message out in columns again, then re-order the columns by reforming the key word.
// CPP program for illustrating
// Columnar Transposition Cipher
#include <bits/stdc++.h>
using namespace std;
// Encription function
string Encryption(int no_rows, int len_key, int len_msg,
string msg, int col_val[])
{
int x = 0;
char enc_mat[no_rows + 1][len_key];
// creating the matrix
for (int i = 0; i < no_rows + 1; i++) {
for (int j = 0; j < len_key; j++) {
// initializes the positions with '_' after the
// end of message
if (x >= len_msg) {
enc_mat[i][j] = '_';
}
else {
enc_mat[i][j] = msg[x];
}
x++;
}
}
int t = 1;
string cipher = "";
// finding the cipher text according to the value of
// col_val matrix
while (t <= len_key) {
for (int i = 0; i < len_key; i++) {
int k = col_val[i];
if (k == t) {
for (int j = 0; j < no_rows + 1; j++) {
cipher += enc_mat[j][i];
}
t++;
}
}
}
return cipher;
}
// decryption function
string Decryption(int no_rows, int len_key, string cipher,
int col_val[])
{
char dec_mat[no_rows + 1][len_key];
int x = 0, t = 1;
// rearrange the matrix according to the col_val
while (t <= len_key) {
for (int i = 0; i < len_key; i++) {
int k = col_val[i];
if (k == t) {
for (int j = 0; j < no_rows + 1; j++) {
dec_mat[j][i] = cipher[x];
x++;
}
t++;
}
}
}
string message = "";
for (int i = 0; i < no_rows + 1; i++) {
for (int j = 0; j < len_key; j++) {
// replacing the '_' with space
if (dec_mat[i][j] == '_') {
dec_mat[i][j] = ' ';
}
message += dec_mat[i][j];
}
}
return message;
}
int main()
{
// message
string msg = "Beginner for Beginner";
// key
string key = "HACK";
int len_key = key.length();
int len_msg = msg.length();
int val = 1, count = 0, ind;
int col_val[len_key];
// intializing col_val matrix with 0
memset(col_val, 0, sizeof(col_val));
// numbering the key alphabets according to its ACII
// value
while (count < len_key) {
int min = 999;
for (int i = 0; i < len_key; i++) {
if ((min > int(key[i])) && (col_val[i] == 0)) {
min = int(key[i]);
ind = i;
}
}
col_val[ind] = val;
count++;
val++;
}
int no_rows = len_msg / len_key;
// encrypted text
string cipher_text = " ";
cipher_text = Encryption(no_rows, len_key, len_msg, msg,
col_val);
cout << "Encrypted Message : " << cipher_text << endl;
// decrypted text
string original_msg = " ";
original_msg = Decryption(no_rows, len_key, cipher_text,
col_val);
cout << "Decrypted Message : " << original_msg << endl;
}
// This code is contributed by Suchita Gond
import java.util.*;
public class ColumnarTranspositionCipher {
// Key for Columnar Transposition
static final String key = "HACK";
static Map<Character, Integer> keyMap = new HashMap<>();
static void setPermutationOrder() {
// Add the permutation order into the map
for (int i = 0; i < key.length(); i++) {
keyMap.put(key.charAt(i), i);
}
}
// Encryption
static String encryptMessage(String msg) {
int row, col;
StringBuilder cipher = new StringBuilder();
/* Calculate the number of columns in the matrix */
col = key.length();
/* Calculate the maximum number of rows in the matrix */
row = (int) Math.ceil((double) msg.length() / col);
char[][] matrix = new char[row][col];
for (int i = 0, k = 0; i < row; i++) {
for (int j = 0; j < col; ) {
if (k < msg.length()) {
char ch = msg.charAt(k);
if (Character.isLetter(ch) || ch == ' ') {
matrix[i][j] = ch;
j++;
}
k++;
} else {
/* Add padding character '_' */
matrix[i][j] = '_';
j++;
}
}
}
for (Map.Entry<Character, Integer> entry : keyMap.entrySet()) {
int columnIndex = entry.getValue();
// Get the cipher text from the matrix column-wise using the permuted key
for (int i = 0; i < row; i++) {
if (Character.isLetter(matrix[i][columnIndex]) || matrix[i][columnIndex] == ' ' || matrix[i][columnIndex] == '_') {
cipher.append(matrix[i][columnIndex]);
}
}
}
return cipher.toString();
}
// Decryption
static String decryptMessage(String cipher) {
/* Calculate the number of columns for the cipher matrix */
int col = key.length();
int row = (int) Math.ceil((double) cipher.length() / col);
char[][] cipherMat = new char[row][col];
/* Add characters into the matrix column-wise */
int k = 0;
for (int j = 0; j < col; j++) {
for (int i = 0; i < row; i++) {
cipherMat[i][j] = cipher.charAt(k);
k++;
}
}
/* Update the order of the key for decryption */
int index = 0;
for (Map.Entry<Character, Integer> entry : keyMap.entrySet()) {
entry.setValue(index++);
}
/* Arrange the matrix column-wise according to the permutation order */
char[][] decCipher = new char[row][col];
for (int l = 0; l < key.length(); l++) {
int columnIndex = keyMap.get(key.charAt(l));
for (int i = 0; i < row; i++) {
decCipher[i][l] = cipherMat[i][columnIndex];
}
}
/* Get the message using the matrix */
StringBuilder msg = new StringBuilder();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (decCipher[i][j] != '_') {
msg.append(decCipher[i][j]);
}
}
}
return msg.toString();
}
public static void main(String[] args) {
/* Message */
String msg = "Beginner for Beginner";
setPermutationOrder();
// Calling encryption function
String cipher = encryptMessage(msg);
System.out.println("Encrypted Message: " + cipher);
// Calling Decryption function
System.out.println("Decrypted Message: " + decryptMessage(cipher));
}
}
# Python3 implementation of
# Columnar Transposition
import math
key = "HACK"
# Encryption
def encryptMessage(msg):
cipher = ""
# track key indices
k_indx = 0
msg_len = float(len(msg))
msg_lst = list(msg)
key_lst = sorted(list(key))
# calculate column of the matrix
col = len(key)
# calculate maximum row of the matrix
row = int(math.ceil(msg_len / col))
# add the padding character '_' in empty
# the empty cell of the matix
fill_null = int((row * col) - msg_len)
msg_lst.extend('_' * fill_null)
# create Matrix and insert message and
# padding characters row-wise
matrix = [msg_lst[i: i + col]
for i in range(0, len(msg_lst), col)]
# read matrix column-wise using key
for _ in range(col):
curr_idx = key.index(key_lst[k_indx])
cipher += ''.join([row[curr_idx]
for row in matrix])
k_indx += 1
return cipher
# Decryption
def decryptMessage(cipher):
msg = ""
# track key indices
k_indx = 0
# track msg indices
msg_indx = 0
msg_len = float(len(cipher))
msg_lst = list(cipher)
# calculate column of the matrix
col = len(key)
# calculate maximum row of the matrix
row = int(math.ceil(msg_len / col))
# convert key into list and sort
# alphabetically so we can access
# each character by its alphabetical position.
key_lst = sorted(list(key))
# create an empty matrix to
# store deciphered message
dec_cipher = []
for _ in range(row):
dec_cipher += [[None] * col]
# Arrange the matrix column wise according
# to permutation order by adding into new matrix
for _ in range(col):
curr_idx = key.index(key_lst[k_indx])
for j in range(row):
dec_cipher[j][curr_idx] = msg_lst[msg_indx]
msg_indx += 1
k_indx += 1
# convert decrypted msg matrix into a string
try:
msg = ''.join(sum(dec_cipher, []))
except TypeError:
raise TypeError("This program cannot",
"handle repeating words.")
null_count = msg.count('_')
if null_count > 0:
return msg[: -null_count]
return msg
# Driver Code
msg = "Beginner for Beginner"
cipher = encryptMessage(msg)
print("Encrypted Message: {}".
format(cipher))
print("Decryped Message: {}".
format(decryptMessage(cipher)))
# This code is contributed by Aditya K
using System;
using System.Collections.Generic;
public class ColumnarTranspositionCipher {
// Key for Columnar Transposition
static readonly string key = "HACK";
static Dictionary<char, int> keyMap
= new Dictionary<char, int>();
static void SetPermutationOrder()
{
// Add the permutation order into the dictionary
for (int i = 0; i < key.Length; i++) {
keyMap[key[i]] = i;
}
}
// Encryption
static string EncryptMessage(string msg)
{
int row, col;
System.Text.StringBuilder cipher
= new System.Text.StringBuilder();
/* Calculate the number of columns in the matrix */
col = key.Length;
/* Calculate the maximum number of rows in the
* matrix */
row = (int)Math.Ceiling((double)msg.Length / col);
char[, ] matrix = new char[row, col];
for (int i = 0, k = 0; i < row; i++) {
for (int j = 0; j < col;) {
if (k < msg.Length) {
char ch = msg[k];
if (char.IsLetter(ch) || ch == ' ') {
matrix[i, j] = ch;
j++;
}
k++;
}
else {
/* Add padding character '_' */
matrix[i, j] = '_';
j++;
}
}
}
foreach(
var entry in new Dictionary<char, int>(keyMap))
{
int columnIndex = entry.Value;
// Get the cipher text from the matrix
// column-wise using the permuted key
for (int i = 0; i < row; i++) {
if (char.IsLetter(matrix[i, columnIndex])
|| matrix[i, columnIndex] == ' '
|| matrix[i, columnIndex] == '_') {
cipher.Append(matrix[i, columnIndex]);
}
}
}
return cipher.ToString();
}
// Decryption
static string DecryptMessage(string cipher)
{
/* Calculate the number of columns for the cipher
* matrix */
int col = key.Length;
int row = (int)Math.Ceiling((double)cipher.Length
/ col);
char[, ] cipherMat = new char[row, col];
/* Add characters into the matrix column-wise */
int k = 0;
for (int j = 0; j < col; j++) {
for (int i = 0; i < row; i++) {
cipherMat[i, j] = cipher[k];
k++;
}
}
/* Update the order of the key for decryption */
int index = 0;
foreach(
var entry in new Dictionary<char, int>(keyMap))
{
keyMap[entry.Key] = index++;
}
/* Arrange the matrix column-wise according to the
* permutation order */
char[, ] decCipher = new char[row, col];
foreach(var entry in keyMap)
{
int columnIndex = entry.Value;
for (int i = 0; i < row; i++) {
decCipher[i, columnIndex]
= cipherMat[i, columnIndex];
}
}
/* Get the message using the matrix */
System.Text.StringBuilder msg
= new System.Text.StringBuilder();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (decCipher[i, j] != '_') {
msg.Append(decCipher[i, j]);
}
}
}
return msg.ToString();
}
public static void Main(string[] args)
{
/* Message */
string msg = "Beginner for Beginner";
SetPermutationOrder();
// Calling encryption function
string cipher = EncryptMessage(msg);
Console.WriteLine("Encrypted Message: " + cipher);
// Calling Decryption function
Console.WriteLine("Decrypted Message: "
+ DecryptMessage(cipher));
}
}
// JavaScript implementation of
// Columnar Transposition
const key = "HACK";
// Encryption
function encryptMessage(msg) {
let cipher = "";
// track key indices
let k_indx = 0;
const msg_len = msg.length;
const msg_lst = Array.from(msg);
const key_lst = Array.from(key).sort();
// calculate column of the matrix
const col = key.length;
// calculate maximum row of the matrix
const row = Math.ceil(msg_len / col);
// add the padding character '_' in empty
// the empty cell of the matrix
const fill_null = (row * col) - msg_len;
for (let i = 0; i < fill_null; i++) {
msg_lst.push('_');
}
// create Matrix and insert message and
// padding characters row-wise
const matrix = [];
for (let i = 0; i < msg_lst.length; i += col) {
matrix.push(msg_lst.slice(i, i + col));
}
// read matrix column-wise using key
for (let _ = 0; _ < col; _++) {
const curr_idx = key.indexOf(key_lst[k_indx]);
for (const row of matrix) {
cipher += row[curr_idx];
}
k_indx++;
}
return cipher;
}
// Decryption
function decryptMessage(cipher) {
let msg = "";
// track key indices
let k_indx = 0;
// track msg indices
let msg_indx = 0;
const msg_len = cipher.length;
const msg_lst = Array.from(cipher);
// calculate column of the matrix
const col = key.length;
// calculate maximum row of the matrix
const row = Math.ceil(msg_len / col);
// convert key into list and sort
// alphabetically so we can access
// each character by its alphabetical position.
const key_lst = Array.from(key).sort();
// create an empty matrix to
// store deciphered message
const dec_cipher = [];
for (let i = 0; i < row; i++) {
dec_cipher.push(Array(col).fill(null));
}
// Arrange the matrix column wise according
// to permutation order by adding into a new matrix
for (let _ = 0; _ < col; _++) {
const curr_idx = key.indexOf(key_lst[k_indx]);
for (let j = 0; j < row; j++) {
dec_cipher[j][curr_idx] = msg_lst[msg_indx];
msg_indx++;
}
k_indx++;
}
// convert decrypted msg matrix into a string
try {
msg = dec_cipher.flat().join('');
} catch (err) {
throw new Error("This program cannot handle repeating words.");
}
const null_count = (msg.match(/_/g) || []).length;
if (null_count > 0) {
return msg.slice(0, -null_count);
}
return msg;
}
// Driver Code
const msg = "Beginner for Beginner";
const cipher = encryptMessage(msg);
console.log("Encrypted Message: " + cipher);
console.log("Decrypted Message: " + decryptMessage(cipher));
// This code is contributed by phasing17
Output
Encrypted Message : e kefGsGsrekoe_ Decrypted Message : Beginner for Beginner
Contact Us