레일펜스 암호 - 암호화 및 복호화
일반 텍스트 메시지와 숫자 키가 주어지면 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인 경우 암호는 다음과 같이 준비됩니다.
.'.암호화는 행 방식으로 수행됩니다(예: GSGSEKFREKEOE).
암호 해독
앞서 살펴본 것처럼 레일 펜스 암호의 열 수는 일반 텍스트 메시지의 길이와 동일하게 유지됩니다. 그리고 키는 레일 수에 해당합니다.
- 따라서 레일 매트릭스는 이에 따라 구성될 수 있습니다. 행렬을 얻은 후에는 텍스트를 배치해야 하는 지점을 알아낼 수 있습니다(대각선 위아래로 번갈아 이동하는 동일한 방법을 사용).
- 그런 다음 암호문 행을 순서대로 채웁니다. 그것을 채운 후 지그재그 방식으로 행렬을 탐색하여 원본 텍스트를 얻습니다.
구현:
암호문 = 'GsGsekfrek eoe' 및 키 = 3이라고 가정합니다.
- 행렬의 열 수 = len(cipher-text) = 13
- 행 수 = 키 = 3
따라서 원래 행렬은 3*13이 되며 이제 텍스트가 있는 장소를 '*'로 표시합니다.
* _ _ _ * _ _ _ * _ _ _ *
_ * _ * _ * _ * _ * _ *
_ _ * _ _ _ * _ _ _ * _
C++
다음은 위의 알고리즘을 사용하여 메시지를 암호화/복호화하는 프로그램입니다.
Java// C++ program to illustrate Rail Fence Cipher // Encryption and Decryption #includeusing namespace std ; // function to encrypt a message string 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 decryption string 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 functions int main () { cout < < encryptRailFence ( 'attack at once' 2 ) < < endl ; cout < < encryptRailFence ( 'GeeksforGeeks ' 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 ; } Python3// 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 JayC## 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 SomwanshiJavaScriptusing 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 )); } }
산출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
이 기사는 기고자: 아슈토시 쿠마르
