Rail Fence Cipher - шифрование и дешифрование

Опубликовано: 20 Января, 2022

Учитывая текстовое сообщение и числовой ключ, зашифруйте / расшифруйте данный текст с помощью алгоритма Rail Fence.
Шифр ограждения рельсов (также называемый зигзагообразным шифром) - это форма транспозиционного шифра. Он получил свое название от способа, которым он закодирован.
Примеры:

Шифрование
Ввод: "GeeksforGeeks"
Ключ = 3
Выход: GsGsekfrek eoe
Расшифровка
Сырьё: GsGsekfrek eoe.
Ключ = 3
Выход: "GeeksforGeeks"

Шифрование
Вход: «Защити восточную стену».
Ключ = 3
Выход: dnhaweedtees alf tl
Расшифровка
Сырьё: dnhaweedtees alf tl.
Ключ = 3
Выход: защитить восточную стену.

Шифрование
Ввод: "атаковать сразу"
Ключ = 2 
Выход: atc toctaka ne 
Расшифровка
Ввод: "atc toctaka ne"
Ключ = 2
Выход: атаковать сразу

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Шифрование

В транспозиционном шифре порядок алфавитов переупорядочивается для получения зашифрованного текста.

  • В шифре рельсового ограждения обычный текст записывается вниз и по диагонали на последовательных рельсах воображаемого забора.
  • Когда мы достигаем нижнего рельса, мы движемся вверх по диагонали, после достижения верхнего рельса направление снова меняется. Таким образом, алфавиты сообщения написаны зигзагообразно.
  • После того, как каждый алфавит был написан, отдельные строки объединяются для получения зашифрованного текста.

Например, если сообщение - «GeeksforGeeks» и количество рельсов = 3, тогда шифр готовится как:

Расшифровка

Как мы видели ранее, количество столбцов в шифре ограждения рельсов остается равным длине обычного текстового сообщения. И ключ соответствует количеству рельсов.

  • Следовательно, рельсовая матрица может быть сконструирована соответствующим образом. После того, как у нас есть матрица, мы можем определить места, где следует разместить текст (используя тот же способ перемещения по диагонали вверх и вниз поочередно).
  • Затем мы заполняем строку зашифрованного текста по мере необходимости. После его заполнения мы проходим по матрице зигзагообразно, чтобы получить исходный текст.

Реализация:
Пусть cipher-text = «GsGsekfrek eoe», а ключ = 3.

  • Количество столбцов в матрице = len (зашифрованный текст) = 12
  • Количество строк = ключ = 3

Следовательно, исходная матрица будет 3 * 12, теперь помечая места с текстом как '*', мы получаем

* _ _ _ * _ _ _ * _ _ _ *
_ * _ * _ * _ * _ * _ * 
_ _ * _ _ _ * _ _ _ * _

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 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] = " ";
  
    // 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]!=" ")
                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] = " ";
  
    // 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 = [[" " 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] != " ":
                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 = [[" " 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

Выход:

 atc toctaka ne
GsGsekfrek eoe
dnhaweedtees alf tl
GeeksforGeeks 
атаковать сразу
Делендф восточный вал


Использованная литература:
https://en.wikipedia.org/wiki/Rail_fence_cipher

Автором этой статьи является Ашутош Кумар. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью с помощью сайта deposit.geeksforgeeks.org или отправить ее по электронной почте на адрес deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022
Amazon SDE Sheet: вопросы и ответы на собеседовании
12 Декабря, 2022