Столбчатый шифр транспонирования

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

Учитывая текстовое сообщение и числовой ключ, зашифруйте / расшифруйте данный текст с помощью шифра транспонирования столбцов.

Столбчатый шифр транспозиции - это разновидность шифра транспонирования, подобная шифру Rail Fence. Транспонирование по столбцам включает запись открытого текста по строкам, а затем чтение зашифрованного текста по столбцам один за другим.

Примеры:

Шифрование
Сырьё: Вундеркинды для гиков
Ключ = HACK
Выход: e kefGsGsrekoe_
Расшифровка
Ввод: e kefGsGsrekoe_
Ключ = HACK
Продукт: Гики для гиков. 

Шифрование
Сырьё: Компьютерщики по работе
Ключ = HACK
Выход: e w_eoo_Gs kknr_
Расшифровка
Ввод: e w_eoo_Gs kknr_
Ключ = HACK
Вывод: Гики по работе

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

Шифрование

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

Сообщение записывается строками фиксированной длины, а затем снова считывается столбец за столбцом, и столбцы выбираются в некотором зашифрованном порядке.
Ширина строк и перестановка столбцов обычно определяются ключевым словом.
Например, слово HACK имеет длину 4 (так что строки имеют длину 4), а перестановка определяется алфавитным порядком букв в ключевом слове. В этом случае порядок будет «3 1 2 4».
Любые свободные места заполняются нулями, остаются пустыми или помещаются символом (пример: _).
Наконец, сообщение читается в столбцах в порядке, указанном ключевым словом.

Decryption

To decipher it, the recipient has to work out the column lengths by dividing the message length by the key length.

Then, write the message out in columns again, then re-order the columns by reforming the key word.

C++

// CPP program for illustrating
// Columnar Transposition Cipher
#include<bits/stdc++.h>
using namespace std;
  
// Key for Columnar Transposition
string const key = "HACK"; 
map<int,int> keyMap;
  
void setPermutationOrder()
{             
    // Add the permutation order into map 
    for(int i=0; i < key.length(); i++)
    {
        keyMap[key[i]] = i;
    }
}
  
// Encryption 
string encryptMessage(string msg)
{
    int row,col,j;
    string cipher = "";
      
    /* calculate column of the matrix*/
    col = key.length(); 
      
    /* calculate Maximum row of the matrix*/
    row = msg.length()/col; 
      
    if (msg.length() % col)
        row += 1;
  
    char matrix[row][col];
  
    for (int i=0,k=0; i < row; i++)
    {
        for (int j=0; j<col; )
        {
            if(msg[k] == "")
            {
                /* Adding the padding character "_" */
                matrix[i][j] = "_";     
                j++;
            }
              
            if( isalpha(msg[k]) || msg[k]==" ")
            { 
                /* Adding only space and alphabet into matrix*/
                matrix[i][j] = msg[k];
                j++;
            }
            k++;
        }
    }
  
    for (map<int,int>::iterator ii = keyMap.begin(); ii!=keyMap.end(); ++ii)
    {
        j=ii->second;
          
        // getting cipher text from matrix column wise using permuted key
        for (int i=0; i<row; i++)
        {
            if( isalpha(matrix[i][j]) || matrix[i][j]==" " || matrix[i][j]=="_")
                cipher += matrix[i][j];
        }
    }
  
    return cipher;
}
  
// Decryption 
string decryptMessage(string cipher)
{
    /* calculate row and column for cipher Matrix */
    int col = key.length();
  
    int row = cipher.length()/col;
    char cipherMat[row][col];
  
    /* add character into matrix column wise */
    for (int j=0,k=0; j<col; j++)
        for (int i=0; i<row; i++)
            cipherMat[i][j] = cipher[k++];
  
    /* update the order of key for decryption */
    int index = 0;
    for( map<int,int>::iterator ii=keyMap.begin(); ii!=keyMap.end(); ++ii)
        ii->second = index++;
  
    /* Arrange the matrix column wise according 
    to permutation order by adding into new matrix */
    char decCipher[row][col];
    map<int,int>::iterator ii=keyMap.begin();
    int k = 0;
    for (int l=0,j; key[l]!=""; k++)
    {
        j = keyMap[key[l++]];
        for (int i=0; i<row; i++)
        {
            decCipher[i][k]=cipherMat[i][j];
        }
    }
  
    /* getting Message using matrix */
    string msg = "";
    for (int i=0; i<row; i++)
    {
        for(int j=0; j<col; j++)
        {
            if(decCipher[i][j] != "_")
                msg += decCipher[i][j];
        }
    }
    return msg;
}
  
// Driver Program
int main(void)
{
    /* message */
    string msg = "Geeks for Geeks"; 
  
    setPermutationOrder();
      
    // Calling encryption function
    string cipher = encryptMessage(msg);
    cout << "Encrypted Message: " << cipher << endl;
      
    // Calling Decryption function
    cout << "Decrypted Message: " << decryptMessage(cipher) << endl;
  
    return 0;
}

Python3

# Python3 implementation of 
# Columnar Transposition
import math
  
key = "HACK"
  
# Encryption
def encryptMessage(msg):
    cipher = ""
  
    # track key indices
    k_indx = 0
  
    msg_len = float(len(msg))
    msg_lst = list(msg)
    key_lst = sorted(list(key))
  
    # calculate column of the matrix
    col = len(key)
      
    # calculate maximum row of the matrix
    row = int(math.ceil(msg_len / col))
  
    # add the padding character "_" in empty
    # the empty cell of the matix 
    fill_null = int((row * col) - msg_len)
    msg_lst.extend("_" * fill_null)
  
    # create Matrix and insert message and 
    # padding characters row-wise 
    matrix = [msg_lst[i: i + col] 
              for i in range(0, len(msg_lst), col)]
  
    # read matrix column-wise using key
    for _ in range(col):
        curr_idx = key.index(key_lst[k_indx])
        cipher += "".join([row[curr_idx] 
                          for row in matrix])
        k_indx += 1
  
    return cipher
  
# Decryption
def decryptMessage(cipher):
    msg = ""
  
    # track key indices
    k_indx = 0
  
    # track msg indices
    msg_indx = 0
    msg_len = float(len(cipher))
    msg_lst = list(cipher)
  
    # calculate column of the matrix
    col = len(key)
      
    # calculate maximum row of the matrix
    row = int(math.ceil(msg_len / col))
  
    # convert key into list and sort 
    # alphabetically so we can access 
    # each character by its alphabetical position.
    key_lst = sorted(list(key))
  
    # create an empty matrix to 
    # store deciphered message
    dec_cipher = []
    for _ in range(row):
        dec_cipher += [[None] * col]
  
    # Arrange the matrix column wise according 
    # to permutation order by adding into new matrix
    for _ in range(col):
        curr_idx = key.index(key_lst[k_indx])
  
        for j in range(row):
            dec_cipher[j][curr_idx] = msg_lst[msg_indx]
            msg_indx += 1
        k_indx += 1
  
    # convert decrypted msg matrix into a string
    try:
        msg = "".join(sum(dec_cipher, []))
    except TypeError:
        raise TypeError("This program cannot",
                        "handle repeating words.")
  
    null_count = msg.count("_")
  
    if null_count > 0:
        return msg[: -null_count]
  
    return msg
  
# Driver Code
msg = "Geeks for Geeks"
  
cipher = encryptMessage(msg)
print("Encrypted Message: {}".
               format(cipher))
  
print("Decryped Message: {}".
       format(decryptMessage(cipher)))
  
# This code is contributed by Aditya K

Output:

Encrypted Message: e  kefGsGsrekoe_
Decrypted Message: Geeks for Geeks

Try it yourself: A double columnar transposition( It was used by the U.S. Army in World War I, and it is just a columnar transposition followed by another columnar transposition).

This article is contributed by Yasin Zafar. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course.

In case you wish to attend live classes with industry experts, please refer Geeks Classes Live and Geeks Classes Live USA

Алгоритмы

Столбчатый шифр транспонирования

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

C++

Python3

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