Given a plain-text message and a numeric key, cipher/de-cipher the given text using Rail Fence algorithm.
The rail fence cipher (also called a zigzag cipher) is a form of transposition cipher. It derives its name from the way in which it is encoded.
Examples:
Encryption Input : "neveropen " Key = 3 Output : GsGsekfrek eoe Decryption Input : GsGsekfrek eoe Key = 3 Output : "neveropen " Encryption Input : "defend the east wall" Key = 3 Output : dnhaweedtees alf tl Decryption Input : dnhaweedtees alf tl Key = 3 Output : defend the east wall Encryption Input : "attack at once" Key = 2 Output : atc toctaka ne Decryption Input : "atc toctaka ne" Key = 2 Output : attack at once
Encryption
In a transposition cipher, the order of the alphabets is re-arranged to obtain the cipher-text.
- In the rail fence cipher, the plain-text is written downwards and diagonally on successive rails of an imaginary fence.
- When we reach the bottom rail, we traverse upwards moving diagonally, after reaching the top rail, the direction is changed again. Thus the alphabets of the message are written in a zig-zag manner.
- After each alphabet has been written, the individual rows are combined to obtain the cipher-text.
For example, if the message is “neveropen” and the number of rails = 3 then cipher is prepared as:
.’.Its encryption will be done row wise i.e. GSGSEKFREKEOE
Decryption
As we’ve seen earlier, the number of columns in rail fence cipher remains equal to the length of plain-text message. And the key corresponds to the number of rails.
- Hence, rail matrix can be constructed accordingly. Once we’ve got the matrix we can figure-out the spots where texts should be placed (using the same way of moving diagonally up and down alternatively ).
- Then, we fill the cipher-text row wise. After filling it, we traverse the matrix in zig-zag manner to obtain the original text.
Implementation:
Let cipher-text = “GsGsekfrek eoe” , and Key = 3
- Number of columns in matrix = len(cipher-text) = 13
- Number of rows = key = 3
Hence original matrix will be of 3*13 , now marking places with text as ‘*’ we get
* _ _ _ * _ _ _ * _ _ _ * _ * _ * _ * _ * _ * _ * _ _ * _ _ _ * _ _ _ * _
Below is a program to encrypt/decrypt the message using the above algorithm.
C++
// C++ program to illustrate Rail Fence Cipher// Encryption and Decryption#include <bits/stdc++.h>using namespace std;// function to encrypt a messagestring encryptRailFence(string text, int key){ // create the matrix to cipher plain text // key = rows , length(text) = columns char rail[key][(text.length())]; // filling the rail matrix to distinguish filled // spaces from blank ones for (int i=0; i < key; i++) for (int j = 0; j < text.length(); j++) rail[i][j] = '\n'; // to find the direction bool dir_down = false; int row = 0, col = 0; for (int i=0; i < text.length(); i++) { // check the direction of flow // reverse the direction if we've just // filled the top or bottom rail if (row == 0 || row == key-1) dir_down = !dir_down; // fill the corresponding alphabet rail[row][col++] = text[i]; // find the next row using direction flag dir_down?row++ : row--; } //now we can construct the cipher using the rail matrix string result; for (int i=0; i < key; i++) for (int j=0; j < text.length(); j++) if (rail[i][j]!='\n') result.push_back(rail[i][j]); return result;}// This function receives cipher-text and key// and returns the original text after decryptionstring decryptRailFence(string cipher, int key){ // create the matrix to cipher plain text // key = rows , length(text) = columns char rail[key][cipher.length()]; // filling the rail matrix to distinguish filled // spaces from blank ones for (int i=0; i < key; i++) for (int j=0; j < cipher.length(); j++) rail[i][j] = '\n'; // to find the direction bool dir_down; int row = 0, col = 0; // mark the places with '*' for (int i=0; i < cipher.length(); i++) { // check the direction of flow if (row == 0) dir_down = true; if (row == key-1) dir_down = false; // place the marker rail[row][col++] = '*'; // find the next row using direction flag dir_down?row++ : row--; } // now we can construct the fill the rail matrix int index = 0; for (int i=0; i<key; i++) for (int j=0; j<cipher.length(); j++) if (rail[i][j] == '*' && index<cipher.length()) rail[i][j] = cipher[index++]; // now read the matrix in zig-zag manner to construct // the resultant text string result; row = 0, col = 0; for (int i=0; i< cipher.length(); i++) { // check the direction of flow if (row == 0) dir_down = true; if (row == key-1) dir_down = false; // place the marker if (rail[row][col] != '*') result.push_back(rail[row][col++]); // find the next row using direction flag dir_down?row++: row--; } return result;}//driver program to check the above functionsint main(){ cout << encryptRailFence("attack at once", 2) << endl; cout << encryptRailFence("neveropen ", 3) << endl; cout << encryptRailFence("defend the east wall", 3) << endl; //Now decryption of the same cipher-text cout << decryptRailFence("GsGsekfrek eoe",3) << endl; cout << decryptRailFence("atc toctaka ne",2) << endl; cout << decryptRailFence("dnhaweedtees alf tl",3) << endl; return 0;} |
Java
// C++ program to illustrate Rail Fence Cipher// Encryption and Decryptionimport java.util.Arrays;class RailFence { // function to encrypt a message public static String encryptRailFence(String text, int key) { // create the matrix to cipher plain text // key = rows , length(text) = columns char[][] rail = new char[key][text.length()]; // filling the rail matrix to distinguish filled // spaces from blank ones for (int i = 0; i < key; i++) Arrays.fill(rail[i], '\n'); boolean dirDown = false; int row = 0, col = 0; for (int i = 0; i < text.length(); i++) { // check the direction of flow // reverse the direction if we've just // filled the top or bottom rail if (row == 0 || row == key - 1) dirDown = !dirDown; // fill the corresponding alphabet rail[row][col++] = text.charAt(i); // find the next row using direction flag if (dirDown) row++; else row--; } // now we can construct the cipher using the rail // matrix StringBuilder result = new StringBuilder(); for (int i = 0; i < key; i++) for (int j = 0; j < text.length(); j++) if (rail[i][j] != '\n') result.append(rail[i][j]); return result.toString(); } // This function receives cipher-text and key // and returns the original text after decryption public static String decryptRailFence(String cipher, int key) { // create the matrix to cipher plain text // key = rows , length(text) = columns char[][] rail = new char[key][cipher.length()]; // filling the rail matrix to distinguish filled // spaces from blank ones for (int i = 0; i < key; i++) Arrays.fill(rail[i], '\n'); // to find the direction boolean dirDown = true; int row = 0, col = 0; // mark the places with '*' for (int i = 0; i < cipher.length(); i++) { // check the direction of flow if (row == 0) dirDown = true; if (row == key - 1) dirDown = false; // place the marker rail[row][col++] = '*'; // find the next row using direction flag if (dirDown) row++; else row--; } // now we can construct the fill the rail matrix int index = 0; for (int i = 0; i < key; i++) for (int j = 0; j < cipher.length(); j++) if (rail[i][j] == '*' && index < cipher.length()) rail[i][j] = cipher.charAt(index++); StringBuilder result = new StringBuilder(); row = 0; col = 0; for (int i = 0; i < cipher.length(); i++) { // check the direction of flow if (row == 0) dirDown = true; if (row == key - 1) dirDown = false; // place the marker if (rail[row][col] != '*') result.append(rail[row][col++]); // find the next row using direction flag if (dirDown) row++; else row--; } return result.toString(); } // driver program to check the above functions public static void main(String[] args) { // Encryption System.out.println("Encrypted Message: "); System.out.println( encryptRailFence("attack at once", 2)); System.out.println( encryptRailFence("neveropen ", 3)); System.out.println( encryptRailFence("defend the east wall", 3)); // Now decryption of the same cipher-text System.out.println("\nDecrypted Message: "); System.out.println( decryptRailFence("atc toctaka ne", 2)); System.out.println( decryptRailFence("GsGsekfrek eoe", 3)); System.out.println( decryptRailFence("dnhaweedtees alf tl", 3)); }}// This code is contributed by Jay |
Python3
# Python3 program to illustrate# Rail Fence Cipher Encryption# and Decryption# function to encrypt a messagedef encryptRailFence(text, key): # create the matrix to cipher # plain text key = rows , # length(text) = columns # filling the rail matrix # to distinguish filled # spaces from blank ones rail = [['\n' for i in range(len(text))] for j in range(key)] # to find the direction dir_down = False row, col = 0, 0 for i in range(len(text)): # check the direction of flow # reverse the direction if we've just # filled the top or bottom rail if (row == 0) or (row == key - 1): dir_down = not dir_down # fill the corresponding alphabet rail[row][col] = text[i] col += 1 # find the next row using # direction flag if dir_down: row += 1 else: row -= 1 # now we can construct the cipher # using the rail matrix result = [] for i in range(key): for j in range(len(text)): if rail[i][j] != '\n': result.append(rail[i][j]) return("" . join(result)) # This function receives cipher-text# and key and returns the original# text after decryptiondef decryptRailFence(cipher, key): # create the matrix to cipher # plain text key = rows , # length(text) = columns # filling the rail matrix to # distinguish filled spaces # from blank ones rail = [['\n' for i in range(len(cipher))] for j in range(key)] # to find the direction dir_down = None row, col = 0, 0 # mark the places with '*' for i in range(len(cipher)): if row == 0: dir_down = True if row == key - 1: dir_down = False # place the marker rail[row][col] = '*' col += 1 # find the next row # using direction flag if dir_down: row += 1 else: row -= 1 # now we can construct the # fill the rail matrix index = 0 for i in range(key): for j in range(len(cipher)): if ((rail[i][j] == '*') and (index < len(cipher))): rail[i][j] = cipher[index] index += 1 # now read the matrix in # zig-zag manner to construct # the resultant text result = [] row, col = 0, 0 for i in range(len(cipher)): # check the direction of flow if row == 0: dir_down = True if row == key-1: dir_down = False # place the marker if (rail[row][col] != '*'): result.append(rail[row][col]) col += 1 # find the next row using # direction flag if dir_down: row += 1 else: row -= 1 return("".join(result))# Driver codeif __name__ == "__main__": print(encryptRailFence("attack at once", 2)) print(encryptRailFence("neveropen ", 3)) print(encryptRailFence("defend the east wall", 3)) # Now decryption of the # same cipher-text print(decryptRailFence("GsGsekfrek eoe", 3)) print(decryptRailFence("atc toctaka ne", 2)) print(decryptRailFence("dnhaweedtees alf tl", 3))# This code is contributed# by Pratik Somwanshi |
C#
using System;class GFG_RailFence { // function to encrypt a message public static string EncryptRailFence(string text, int key) { // create the matrix to cipher plain text // key = rows, length(text) = columns char[,] rail = new char[key, text.Length]; // filling the rail matrix to distinguish filled // spaces from blank ones for (int i = 0; i < key; i++) for (int j = 0; j < text.Length; j++) rail[i, j] = '\n'; bool dirDown = false; int row = 0, col = 0; for (int i = 0; i < text.Length; i++) { // check the direction of flow // reverse the direction if we've just // filled the top or bottom rail if (row == 0 || row == key - 1) dirDown = !dirDown; // fill the corresponding alphabet rail[row, col++] = text[i]; // find the next row using direction flag if (dirDown) row++; else row--; } // now we can construct the cipher using the rail // matrix string result = ""; for (int i = 0; i < key; i++) for (int j = 0; j < text.Length; j++) if (rail[i, j] != '\n') result += rail[i, j]; return result; } // This function receives cipher-text and key // and returns the original text after decryption public static string DecryptRailFence(string cipher, int key) { // create the matrix to cipher plain text // key = rows, length(text) = columns // create the matrix to cipher plain text // key = rows , length(text) = columns char[,] rail = new char[key, cipher.Length]; // filling the rail matrix to distinguish filled // spaces from blank ones for (int i = 0; i < key; i++) for (int j = 0; j < cipher.Length; j++) rail[i, j] = '\n'; // to find the direction bool dirDown = true; int row = 0, col = 0; // mark the places with '*' for (int i = 0; i < cipher.Length; i++) { // check the direction of flow if (row == 0) dirDown = true; if (row == key - 1) dirDown = false; // place the marker rail[row, col++] = '*'; // find the next row using direction flag if (dirDown) row++; else row--; } // now we can construct the fill the rail matrix int index = 0; for (int i = 0; i < key; i++) for (int j = 0; j < cipher.Length; j++) if (rail[i, j] == '*' && index < cipher.Length) rail[i, j] = cipher[index++]; // create the result string string result = ""; row = 0; col = 0; // iterate through the rail matrix for (int i = 0; i < cipher.Length; i++) { // check the direction of flow if (row == 0) dirDown = true; if (row == key - 1) dirDown = false; // place the marker if (rail[row, col] != '*') result += rail[row, col++]; // find the next row using direction flag if (dirDown) row++; else row--; } return result; } // driver program to check the above functions public static void Main() { // Encryption Console.WriteLine("Encrypted Message: "); Console.WriteLine(EncryptRailFence("attack at once", 2)); Console.WriteLine( EncryptRailFence("neveropen ", 3)); Console.WriteLine( EncryptRailFence("defend the east wall", 3)); // Now decryption of the same cipher-text Console.WriteLine("\nDecrypted Message: "); Console.WriteLine( DecryptRailFence("atc toctaka ne", 2)); Console.WriteLine( DecryptRailFence("GsGsekfrek eoe", 3)); Console.WriteLine( DecryptRailFence("dnhaweedtees alf tl", 3)); }} |
Javascript
// function to encrypt a messagefunction encryptRailFence(text, key) { // create the matrix to cipher plain text // key = rows , text.length = columns let rail = new Array(key).fill().map(() => new Array(text.length).fill('\n')); // filling the rail matrix to distinguish filled // spaces from blank ones let dir_down = false; let row = 0, col = 0; for (let i = 0; i < text.length; i++) { // check the direction of flow // reverse the direction if we've just // filled the top or bottom rail if (row == 0 || row == key - 1) dir_down = !dir_down; // fill the corresponding alphabet rail[row][col++] = text[i]; // find the next row using direction flag dir_down ? row++ : row--; } // now we can construct the cipher using the rail matrix let result = ''; for (let i = 0; i < key; i++) for (let j = 0; j < text.length; j++) if (rail[i][j] != '\n') result += rail[i][j]; return result;}// function to decrypt a messagefunction decryptRailFence(cipher, key) { // create the matrix to cipher plain text // key = rows , text.length = columns let rail = new Array(key).fill().map(() => new Array(cipher.length).fill('\n')); // filling the rail matrix to mark the places with '*' let dir_down = false; let row = 0, col = 0; for (let i = 0; i < cipher.length; i++) { // check the direction of flow if (row == 0) dir_down = true; if (row == key - 1) dir_down = false; // place the marker rail[row][col++] = '*'; // find the next row using direction flag dir_down ? row++ : row--; } // now we can construct the rail matrix by filling the marked places with cipher text let index = 0; for (let i = 0; i < key; i++) for (let j = 0; j < cipher.length; j++) if (rail[i][j] == '*' && index < cipher.length) rail[i][j] = cipher[index++]; // now read the matrix in zig-zag manner to construct the resultant text let result = ''; row = 0, col = 0; for (let i = 0; i < cipher.length; i++) { // check the direction of flow if (row == 0) dir_down = true; if (row == key - 1) dir_down = false; // place the marker if (rail[row][col] != '*') result += rail[row][col++]; // find the next row using direction flag dir_down ? row++ : row--; } return result;}// driver program to check the above functions // Encryptionconsole.log(encryptRailFence('attack at once', 2)); console.log(encryptRailFence('neveropen', 3)); console.log(encryptRailFence('defend the east wall', 3));// Now decryption of the same cipher-textconsole.log(decryptRailFence('GsGsekfrek eoe', 3));console.log(decryptRailFence('atc toctaka ne', 2));console.log(decryptRailFence('dnhaweedtees alf tl', 3)); |
Output:
atc toctaka ne GsGsekfrek eoe dnhaweedtees alf tl neveropen attack at once defend the east wall
Time Complexity: O(row * col)
Auxiliary Space: O(row * col)
References:
https://en.wikipedia.org/wiki/Rail_fence_cipher
This article is contributed by Ashutosh Kumar If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
