Cifratura del recinto ferroviario: crittografia e decrittografia
Dato un messaggio di testo normale e una chiave numerica cifra/decifra il testo dato utilizzando l'algoritmo Rail Fence.
Il cifrario ferroviario (chiamato anche cifrario a zigzag) è una forma di cifrario a trasposizione. Deriva il suo nome dal modo in cui è codificato.
Esempi:
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
Crittografia
In una cifratura a trasposizione l'ordine degli alfabeti viene riorganizzato per ottenere il testo cifrato.
- Nella cifratura del recinto ferroviario il testo in chiaro è scritto verso il basso e in diagonale sui binari successivi di un recinto immaginario.
- Quando raggiungiamo il binario inferiore procediamo verso l'alto muovendoci in diagonale. Dopo aver raggiunto il binario superiore la direzione viene nuovamente cambiata. Pertanto gli alfabeti del messaggio sono scritti a zig-zag.
- Dopo che ogni alfabeto è stato scritto, le singole righe vengono combinate per ottenere il testo cifrato.
Ad esempio, se il messaggio è "GeeksforGeeks" e il numero di binari = 3, la cifra viene preparata come:
.'.La sua crittografia verrà eseguita in base alle righe, ovvero GSGSEKFREKEOE
Decrittazione
Come abbiamo visto in precedenza, il numero di colonne nel codice del recinto ferroviario rimane uguale alla lunghezza del messaggio di testo semplice. E la chiave corrisponde al numero di binari.
- Quindi la matrice ferroviaria può essere costruita di conseguenza. Una volta ottenuta la matrice, possiamo determinare i punti in cui posizionare i testi (utilizzando lo stesso modo di spostarsi diagonalmente su e giù alternativamente).
- Quindi riempiamo la riga del testo cifrato. Dopo averlo riempito attraversiamo la matrice a zig-zag per ottenere il testo originale.
Attuazione:
Sia testo cifrato = 'GsGsekfrek eoe' e Chiave = 3
- Numero di colonne nella matrice = len(testo cifrato) = 13
- Numero di righe = chiave = 3
Quindi la matrice originale sarà di 3*13 e ora contrassegneremo i posti con il testo come '*' che otteniamo
* _ _ _ * _ _ _ * _ _ _ *
_ * _ * _ * _ * _ * _ *
_ _ * _ _ _ * _ _ _ * _
C++
Di seguito è riportato un programma per crittografare/decrittografare il messaggio utilizzando l'algoritmo di cui sopra.
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 )); } }
Produzioneatc toctaka ne GsGsekfrek eoe dnhaweedtees alf tl GeeksforGeeks attack at once defend the east wallComplessità temporale: O(riga * col)
Crea quiz
Spazio ausiliario: O(riga * col)
Riferimenti:
https://en.wikipedia.org/wiki/Rail_fence_cipher
Questo articolo è stato fornito da Ashutosh Kumar
