일반 텍스트 메시지와 숫자 키가 주어지면 Rail Fence 알고리즘을 사용하여 주어진 텍스트를 암호화/해독합니다.
레일펜스 암호(지그재그 암호라고도 함)는 전치 암호의 한 형태입니다. 인코딩되는 방식에서 이름이 파생됩니다.
예:
Encryption
Input : 'GeeksforGeeks '
Key = 3
Output : GsGsekfrek eoe
Decryption
Input : GsGsekfrek eoe
Key = 3
Output : 'GeeksforGeeks '
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
암호화
전치암호에서는 알파벳의 순서를 재배열하여 암호문을 얻는다.
- 레일 펜스 암호에서 일반 텍스트는 가상 펜스의 연속 레일에 아래쪽 대각선으로 기록됩니다.
- 하단 레일에 도달하면 상단 레일에 도달한 후 방향이 다시 바뀌어 대각선으로 위쪽으로 이동합니다. 따라서 메시지의 알파벳은 지그재그 방식으로 작성됩니다.
- 각 알파벳이 작성된 후 개별 행이 결합되어 암호문을 얻습니다.
예를 들어 메시지가 'GeeksforGeeks'이고 레일 수가 3인 경우 암호는 다음과 같이 준비됩니다.
암호 해독
앞서 살펴본 것처럼 레일 펜스 암호의 열 수는 일반 텍스트 메시지의 길이와 동일하게 유지됩니다. 그리고 키는 레일 수에 해당합니다.
- 따라서 레일 매트릭스는 이에 따라 구성될 수 있습니다. 행렬을 얻은 후에는 텍스트를 배치해야 하는 지점을 알아낼 수 있습니다(대각선 위아래로 번갈아 이동하는 동일한 방법을 사용).
- 그런 다음 암호문 행을 순서대로 채웁니다. 그것을 채운 후 지그재그 방식으로 행렬을 탐색하여 원본 텍스트를 얻습니다.
구현:
암호문 = 'GsGsekfrek eoe' 및 키 = 3이라고 가정합니다.
- 행렬의 열 수 = len(cipher-text) = 13
- 행 수 = 키 = 3
따라서 원래 행렬은 3*13이 되며 이제 텍스트가 있는 장소를 '*'로 표시합니다.
* _ _ _ * _ _ _ * _ _ _ *
_ * _ * _ * _ * _ * _ *
_ _ * _ _ _ * _ _ _ * _
다음은 위의 알고리즘을 사용하여 메시지를 암호화/복호화하는 프로그램입니다.
// C++ program to illustrate Rail Fence Cipher // Encryption and Decryption #include
// Java program to illustrate Rail Fence Cipher // Encryption and Decryption import 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('GeeksforGeeks ' 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 program to illustrate # Rail Fence Cipher Encryption # and Decryption # function to encrypt a message def 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 decryption def 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 code if __name__ == '__main__': print(encryptRailFence('attack at once' 2)) print(encryptRailFence('GeeksforGeeks ' 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
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('GeeksforGeeks ' 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)); } }
// function to encrypt a message function 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 message function 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 // Encryption console.log(encryptRailFence('attack at once' 2)); console.log(encryptRailFence('GeeksforGeeks' 3)); console.log(encryptRailFence('defend the east wall' 3)); // Now decryption of the same cipher-text console.log(decryptRailFence('GsGsekfrek eoe' 3)); console.log(decryptRailFence('atc toctaka ne' 2)); console.log(decryptRailFence('dnhaweedtees alf tl' 3));
산출
atc toctaka ne GsGsekfrek eoe dnhaweedtees alf tl GeeksforGeeks attack at once defend the east wall
시간 복잡도: O(행*열)
보조 공간: O(행*열)
참고자료:
https://en.wikipedia.org/wiki/Rail_fence_cipher
이 기사는 기고자: 아슈토시 쿠마르