密碼學 - 列置換密碼

上一頁
下一頁

一種以矩陣形式表示明文的換位密碼稱為列置換密碼。將明文按行寫入，然後逐列讀取密文稱為列置換。在本教程中，我們描述了列置換密碼的加密和解密方法。列置換可能是研究最多的換位密碼。

Columnar Transposition

它是如何工作的？

訊息被構造為一個二維陣列。訊息的長度決定了將有多少行和列。如果訊息長 30 個字元（包括空格），則有 50% 的機率會有 15 行 2 列、10 行 3 列、5 行 6 列或 6 行 5 列。

請記住，如果訊息長度超過 29，我們必須在訊息末尾附加一個虛擬字母。

加密

請參閱下面列置換密碼的加密過程：

  • 首先，明文按預先定義的行寫入，金鑰確定長度。
  • 可以使用金鑰確定明文列的轉置順序。
  • 然後透過逐列讀取轉置後的明文來建立密文。

解密

因此，列置換密碼的解密過程如下：

  • 使用與加密相同的金鑰，首先按列轉置密文。
  • 可以透過逐行讀取轉置後的密文來檢索明文。

列置換示例

如果訊息為“The attack will start on Monday”，那麼我們可以看到它有 28 個字元。但是，如果我們在末尾新增虛擬字母“x”和“x”，則訊息將為 30 個字元。我們可以計算出 30 = 10 X 3，如果金鑰為 (2,3,1)，則列排列如下：

明文：“the attack will start on Monday”

Columnar Transposition Example

密文 - “HAA LSROMDXETCWLTTNOAXT TKI A NY” 是密文，它是根據表格按列讀取計算得出的。為了更容易記住金鑰，我們對關鍵字（如“TWO”）的字母進行重新排列，使其按字母順序排列。因此，陣列列將使用金鑰 (2,3,1) 進行重新排列。

主要特徵

列置換密碼的主要特徵如下：

  • 列置換密碼是一種換位密碼，它需要在加密之前將明文重新排列成列。
  • 由於金鑰是對稱的，因此它可以用於加密和解密。
  • 列置換密碼允許使用可變的金鑰大小。金鑰包含 1 到 N 的整數的排列，其中 N 是明文的長度。
  • 密碼分析可以破解列置換密碼，尤其是在明文具有重複模式或金鑰較短的情況下。

列置換密碼的用例

  • 列置換密碼的應用非常廣泛，例如資料保護、軍事通訊和間諜活動。
  • 它在明文包含長重複模式（如二進位制資料或 DNA 序列）的情況下特別有效。
  • 為了提高加密資料的安全性，列置換密碼還可以與其他加密技術（如替換密碼）結合使用。

實施

現在，我們將使用 Python、Java、C++ 和 Javascript 實現列置換密碼。

使用 Python 實現

該程式碼將演示如何使用 Python 程式語言中的列置換密碼加密明文訊息，然後將密文解密回明文。

示例

def columnar_encrypt(plaintext, keyword):
   matrix = create_encryption_matrix(len(keyword), plaintext)
   keyword_sequence = get_keyword_sequence(keyword)

   ciphertext = ""
   for num in range(len(keyword_sequence)):
      pos = keyword_sequence.index(num + 1)
      for row in range(len(matrix)):
         if len(matrix[row]) > pos:
            ciphertext += matrix[row][pos]
   return ciphertext

def create_encryption_matrix(width, plaintext):
   r = 0
   c = 0
   matrix = [[]]
   for pos, ch in enumerate(plaintext):
      matrix[r].append(ch)
      c += 1
      if c >= width:
         c = 0
         r += 1
         matrix.append([])

   return matrix

def get_keyword_sequence(keyword):
   sequence = []
   for pos, ch in enumerate(keyword):
      previous_letters = keyword[:pos]
      new_number = 1
      for previous_pos, previous_ch in enumerate(previous_letters):
         if previous_ch > ch:
            sequence[previous_pos] += 1
         else:
            new_number += 1
      sequence.append(new_number)
   return sequence

def columnar_decrypt(ciphertext, keyword):
   matrix = create_encryption_matrix(len(keyword), ciphertext)
   keyword_sequence = get_keyword_sequence(keyword)

   plaintext = ""
   index = 0
   for num in range(len(keyword_sequence)):
      pos = keyword_sequence.index(num + 1)
      for row in range(len(matrix)):
         if len(matrix[row]) > pos:
            matrix[row][pos] = ciphertext[index]
            index += 1

   for row in range(len(matrix)):
      for col in range(len(matrix[row])):
         plaintext += matrix[row][col]

   return plaintext

# Execution of the functions
plaintext = "Tutorialspoint is best"
keyword = "railfence"
ciphertext = columnar_encrypt(plaintext, keyword)
print("The Encrypted Text:", ciphertext)
decrypted_text = columnar_decrypt(ciphertext, keyword)
print("The Decrypted Text:", decrypted_text)

以下是上述示例的輸出：

輸入/輸出
The Encrypted Text: uoelsi s rttisontaiTpb
The Decrypted Text: Tutorialspoint is best

使用 Java 實現

現在，我們將使用 Java 程式語言實現列置換密碼。我們將使用 Java 的 util 包，該包用於匯入 Map 介面和 HashMap 類。程式碼如下：

示例

import java.util.*;

public class ColumnarCipher {
   // Define the Key 
   static final String encryptionKey = "BEST";
   static Map<Character, Integer> keyMap = new HashMap<>();

   static void setPermutationOrder() {
      // Add the permutation order into the map
      for (int i = 0; i < encryptionKey.length(); i++) {
         keyMap.put(encryptionKey.charAt(i), i);
      }
   }

   // Encryption Function
   static String encrypt(String plaintext) {
   int rows, columns;
   StringBuilder ciphertext = new StringBuilder();

   // Number of columns in the matrix
   columns = encryptionKey.length();

   // Maximum number of rows in the matrix 
   rows = (int) Math.ceil((double) plaintext.length() / columns);

   char[][] matrix = new char[rows][columns];

   for (int i = 0, k = 0; i < rows; i++) {
      for (int j = 0; j < columns; ) {
         if (k < plaintext.length()) {
            char ch = plaintext.charAt(k);
            if (Character.isLetter(ch) || ch == ' ') {
            matrix[i][j] = ch;
            j++;
            }
            k++;
         } else {
            /* Add padding character '_' */
            matrix[i][j] = '_';
            j++;
         }
      }
   }

      for (Map.Entry<Character, Integer> entry : keyMap.entrySet()) {
         int columnIndex = entry.getValue();

         // Get the cipher text 
         for (int i = 0; i < rows; i++) {
            if (Character.isLetter(matrix[i][columnIndex]) || matrix[i][columnIndex] == ' ' || matrix[i][columnIndex] == '_') {
               ciphertext.append(matrix[i][columnIndex]);
            }
         }
      }
      return ciphertext.toString();
   }

   // Decryption Function
   static String decrypt(String ciphertext) {
      int columns = encryptionKey.length();

      int rows = (int) Math.ceil((double) ciphertext.length() / columns);
      char[][] cipherMat = new char[rows][columns];

      // Add characters into the matrix column-wise 
      int k = 0;
      for (int j = 0; j < columns; j++) {
         for (int i = 0; i < rows; i++) {
            if (k < ciphertext.length()) {
               cipherMat[i][j] = ciphertext.charAt(k);
               k++;
            } else {
               cipherMat[i][j] = '_'; 
            }
         }
      }

      // Update the order of the key 
      int index = 0;
      for (Map.Entry<Character, Integer> entry : keyMap.entrySet()) {
         entry.setValue(index++);
      }

      char[][] decCipher = new char[rows][columns];
      for (int l = 0; l < encryptionKey.length(); l++) {
         int columnIndex = keyMap.get(encryptionKey.charAt(l));
         for (int i = 0; i < rows; i++) {
            decCipher[i][l] = cipherMat[i][columnIndex];
         }
      }

      // Get the message with the help of the matrix
      StringBuilder msg = new StringBuilder();
      for (int i = 0; i < rows; i++) {
         for (int j = 0; j < columns; j++) {
            if (decCipher[i][j] != '_') {
               msg.append(decCipher[i][j]);
            }
         }
      }
      return msg.toString();
   }


   public static void main(String[] args) {
      /* Plain text message */
      String plaintext = "This is a secret message.";

      setPermutationOrder();

      // Call the encryption function
      String ciphertext = encrypt(plaintext);
      System.out.println("The Encrypted Message: " + ciphertext);

      // Call the Decryption function
      System.out.println("The Decrypted Message: " + decrypt(ciphertext));
   }
}

以下是上述示例的輸出：

輸入/輸出
The Encrypted Message: T ac s_isseeg_s etse_hi rma_
The Decrypted Message: This is a secret message

使用 C++ 實現

現在，我們將使用相同的概念並在 C++ 中為列置換密碼實現程式碼。請檢視下面的程式碼：

示例

#include<bits/stdc++.h>
using namespace std;

// Encryption key
string const encryptionKey = "BEST"; 
map<int,int> keyMap;

// Set the permutation order 
void setPermutationOrder() {			 
	// Add the permutation order into map 
	for(int i=0; i < encryptionKey.length(); i++) {
		keyMap[encryptionKey[i]] = i;
	}
}

// Encryption function
string encrypt(string plaintext) {
	int numRows, numCols, j;
	string ciphertext = "";
	
    // Calculate the number of columns in the matrix
	numCols = encryptionKey.length(); 
	
	// Calculate the maximum number of rows in the matrix 
	numRows = plaintext.length() / numCols; 
	
	if (plaintext.length() % numCols)
		numRows += 1;

	char matrix[numRows][numCols];

	for (int i=0, k=0; i < numRows; i++){
		for (int j=0; j < numCols; ){
			if(plaintext[k] == '\0'){
				// Add the padding character
				matrix[i][j] = '_';	 
				j++;
			}
			
			if(isalpha(plaintext[k]) || plaintext[k] == ' '){ 
				// Add only spaces and alphabets
				matrix[i][j] = plaintext[k];
				j++;
			}
			k++;
		}
	}

	for (map<int,int>::iterator it = keyMap.begin(); it != keyMap.end(); ++it){
		j = it->second;
		
		for (int i = 0; i < numRows; i++){
         if(isalpha(matrix[i][j]) || matrix[i][j] == ' ' || matrix[i][j] == '_')
            ciphertext += matrix[i][j];
		}
	}
	return ciphertext;
}

// Decryption function
string decrypt(string ciphertext){
	// Calculate the row and column 
	int numCols = encryptionKey.length();

	int numRows = ciphertext.length() / numCols;
	char cipherMat[numRows][numCols];

    // Add characters into the matrix column-wise
	for (int j = 0, k = 0; j < numCols; j++)
		for (int i = 0; i < numRows; i++)
			cipherMat[i][j] = ciphertext[k++];

	// Update the order of the key 
	int index = 0;
	for(map<int,int>::iterator it = keyMap.begin(); it != keyMap.end(); ++it)
		it->second = index++;

	// Arrange the matrix column-wise 
	char decCipher[numRows][numCols];
	map<int,int>::iterator it = keyMap.begin();
	int k = 0;
	for(int l = 0, j; encryptionKey[l] != '\0'; k++){
		j = keyMap[encryptionKey[l++]];
		for(int i = 0; i < numRows; i++){
			decCipher[i][k] = cipherMat[i][j];
		}
	}

	// Get the plaintext message 
	string plaintext = "";
	for(int i = 0; i < numRows; i++){
		for(int j = 0; j < numCols; j++){
			if(decCipher[i][j] != '_')
				plaintext += decCipher[i][j];
		}
	}
	return plaintext;
}

// Driver program
int main(void){
   string plaintext = "I am using Tutorialspoint"; 

   setPermutationOrder();
   string ciphertext = encrypt(plaintext);
   cout << "The Encrypted Message: " << ciphertext << endl;
   cout << "The Decrypted Message: " << decrypt(ciphertext) << endl;

   return 0;
}

以下是上述示例的輸出：

輸入/輸出

The Encrypted Message: I nuipt ugtao_as oli_miTrsn_
The Decrypted Message: I am using Tutorialspoint

列置換的安全性

直到 20 世紀上半葉，列置換在全世界範圍內被廣泛使用。

為了破譯密文，攻擊者應該嘗試製作各種大小的表格，將加密的訊息輸入到列中，並在每個表格中搜索行中存在的字謎。

優點

與任何加密方法一樣，列置換密碼也有其自身的優點。

  • 列置換密碼透過重新排列給定明文中的字元順序提供基本的安全性。此屬性使未經授權的使用者難以在不知情金鑰的情況下破譯。
  • 列置換密碼演算法非常易於實現，因為它需要最少的資源。
  • 它支援多種金鑰長度，這意味著它允許使用者根據其特定需求自定義安全級別。
  • 與其他替換密碼不同，列置換密碼不會保留字元的頻率，這使得它對頻率分析攻擊具有很強的抵抗力。

缺點

儘管有優點，但列置換密碼也有一些缺點：

  • 列置換密碼提供基本的安全性，但容易受到暴力攻擊，尤其是在金鑰空間有限或選擇不佳的情況下。
  • 適當的管理對於該保護至關重要，但在大型系統中很難做到。
  • 已知明文攻擊可以透過揭示加密金鑰的詳細資訊來破壞密碼的安全性。

  • 儘管列置換密碼適用於基本的加密需求，但它無法抵禦意志堅定的對手或高階的密碼分析技術。
  • 此外，當使用明文文字量較大時，其效能會下降，尤其是在使用手動儲存方法時，因為矩陣的建立和轉換非常複雜。

結論

列置換密碼是一種置換密碼，在加密前會將明文按列重新排列。它是一種常用的加密技術，易於使用，並且可以有效地用於各種目的，例如資料保護和軍事通訊。它可以與其他加密技術結合使用，以提高加密資料的安全性，但同時也容易受到密碼分析的攻擊。因此，選擇性地使用列置換密碼並採取適當的預防措施以降低其漏洞至關重要。

列印頁面
上一頁
下一頁
廣告