Dado un mensaje de texto sin formato y una clave numérica, cifre/descifre el texto dado usando el algoritmo Rail Fence.
El cifrado de cerca de riel (también llamado cifrado en zigzag) es una forma de cifrado de transposición. Deriva su nombre de la forma en que está codificado.
Ejemplos:
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
Cifrado
En un cifrado por transposición, el orden de los alfabetos se reorganiza para obtener el texto cifrado.
- En el cifrado de la cerca de rieles, el texto sin formato se escribe hacia abajo y en diagonal en los rieles sucesivos de una cerca imaginaria.
- Cuando llegamos al riel inferior, atravesamos hacia arriba moviéndose en diagonal, luego de llegar al riel superior, la dirección cambia nuevamente. Así, los alfabetos del mensaje se escriben en zig-zag.
- Después de escribir cada alfabeto, las filas individuales se combinan para obtener el texto cifrado.
Por ejemplo, si el mensaje es «GeeksforGeeks» y el número de rieles = 3, el cifrado se prepara como:
.’.Su cifrado se realizará por filas, es decir, GSGSEKFREKEOE
Descifrado
Como hemos visto anteriormente, el número de columnas en el cifrado de valla de ferrocarril sigue siendo igual a la longitud del mensaje de texto sin formato. Y la clave corresponde al número de rieles.
- Por lo tanto, la array de rieles se puede construir en consecuencia. Una vez que tenemos la array, podemos averiguar los lugares donde se deben colocar los textos (utilizando la misma forma de movernos en diagonal hacia arriba y hacia abajo alternativamente).
- Luego, llenamos la fila de texto cifrado sabiamente. Luego de llenarlo, recorremos la array en forma de zig-zag para obtener el texto original.
Implementación:
Let cipher-text = “GsGsekfrek eoe” y Key = 3
- Número de columnas en array = len (texto cifrado) = 13
- Número de filas = clave = 3
Por lo tanto, la array original será de 3*13, ahora marcando lugares con texto como ‘*’ obtenemos
* _ _ _ * _ _ _ * _ _ _ * _ * _ * _ * _ * _ * _ * _ _ * _ _ _ * _ _ _ * _
A continuación se muestra un programa para cifrar/descifrar el mensaje utilizando el algoritmo anterior.
C++
// C++ program to illustrate Rail Fence Cipher
// Encryption and Decryption
#include <bits/stdc++.h>
using 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
# 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
Producción:
atc toctaka ne GsGsekfrek eoe dnhaweedtees alf tl GeeksforGeeks attack at once delendfthe east wal
Complejidad de tiempo: O(fila * columna)
Espacio auxiliar: O(fila * columna)
Referencias:
https://en.wikipedia.org/wiki/Rail_fence_cipher Ashutosh Kumar
contribuye con este artículo . Si te gusta GeeksforGeeks y te gustaría contribuir, también puede escribir un artículo usando write.geeksforgeeks.org o enviar su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA