密碼學 - 希爾密碼

上一頁
下一頁

在經典密碼學的語境下，希爾密碼使用多字母替換密碼，這意味著在多個塊級別上進行同質替換。這種多字母替換密碼允許希爾密碼輕鬆地使用二字母組（兩字母塊）、三字母組（三字母塊）或任何其他多尺寸塊來建立統一的密碼。

希爾密碼基於線性代數、高階矩陣（矩陣乘法和矩陣逆）和模算術原理。顯然，它比其他密碼更具有數學性。

希爾密碼也是一種分組密碼。分組密碼使用確定性演算法和對稱金鑰來加密一段文字。與流密碼不同，它不需要一次加密一位。希爾密碼是一種分組密碼，這意味著它可以處理任何大小的塊。

雖然希爾密碼本質上是二字母組的，但它可以擴充套件到任何字母大小的乘法，增加了複雜性和可靠性，從而提高了使用效率。因為希爾密碼的大部分問題和解決方案本質上都是數學性的，所以很容易精確地隱藏字母。

Hill Cipher

由於希爾密碼相當複雜，讓我們加密文字“CODE”，然後解密生成的密文來學習它的工作原理。為了使示例保持簡單，我們將使用一種簡單的替換方法，其中字母 A 對映到 0，B 對映到 1，依此類推，以符合 2x2 金鑰矩陣。隨著金鑰矩陣大小的增加，希爾密碼變得更加複雜。

歷史

透過使用獨特的方法和技術，密碼學——安全通訊的研究和實踐——防止未經授權的人員或團隊獲取機密資料。保密性、資料完整性、身份驗證等概念在現代密碼學中非常重要。

著名的美國數學家萊斯特·S·希爾於 1929 年開發和改進了希爾密碼技術。希爾密碼使用多種數學技術，這些技術與傳統密碼學中的許多關鍵技術相關。

加密

使用希爾密碼加密取決於以下操作：

E(K, P) = (K*P) mod 26

這裡 K 是我們的金鑰矩陣，P 是向量化的明文。將這兩個項進行矩陣乘法得到加密的密文。讓我們一步一步地開始吧：

  • 選擇一個關鍵字來加密您的明文訊息。讓我們使用隨機關鍵字“DCDF”。使用替換技術，將此項更改為數值 2x2 金鑰矩陣。

Hill Cipher Encryption

  • 然後我們將明文訊息轉換為向量格式。因為我們的金鑰矩陣是 2x2，矩陣乘法需要一個大小為 2x1 的向量。在我們的示例中，我們的訊息有四個字母長，所以我們可以將其分成兩個字母的塊，然後進行替換以獲得我們的明文向量。

Hill Cipher example

  • 最終的密文“WWVA”可以透過將金鑰矩陣與每個 2x1 明文向量進行矩陣相乘，取結果 2x1 向量的模 26，並將結果連線起來生成。所以對於 22 22 21 0 將是 WWVA。

Final Cipher

解密

希爾密碼解密過程基於以下操作：

D(K, C) = (K-1 *C) mod 26

這裡 C 是向量化的密文，K 是我們的金鑰矩陣。透過將金鑰矩陣的逆與密文進行矩陣相乘可以得到解密的明文。讓我們使用“WWVA”作為我們的密文一步一步地進行：

  • 我們首先計算金鑰矩陣的逆。為此，我們必須使用模 26 來保持結果在 0 和 25 之間。因此，使用擴充套件歐幾里得方法找到金鑰矩陣行列式的模乘法逆。

  • 之後，我們將密文的 2x1 塊乘以金鑰矩陣的逆，以恢復我們原始的明文訊息“CODE”。

使用 Python 實現

這段 Python 程式碼藉助 NumPy 進行矩陣運算，構建了希爾密碼加密演算法。它建立函式來根據給定的金鑰定義金鑰矩陣，使用生成的金鑰矩陣加密訊息，並進行希爾密碼加密。hill_cipher 函式接受訊息和金鑰作為輸入，建立金鑰矩陣，也使用金鑰矩陣加密訊息，並將輸出列印為密文。

示例

以下是使用 Python 的 numpy 庫實現的希爾密碼的 Python 實現：

import numpy as np

key_matrix = np.zeros((3, 3), dtype=int)
message_vector = np.zeros((3, 1), dtype=int)
cipher_matrix = np.zeros((3, 1), dtype=int)

def get_key_matrix(key):
   k = 0
   for i in range(3):
      for j in range(3):
         key_matrix[i][j] = ord(key[k]) % 65
         k += 1

def encrypt(message_vector):
   for i in range(3):
      cipher_matrix[i][0] = 0
      for x in range(3):
         cipher_matrix[i][0] += (key_matrix[i][x] * message_vector[x][0])
      cipher_matrix[i][0] = cipher_matrix[i][0] % 26

def hill_cipher(message, key):
   get_key_matrix(key)
   for i in range(3):
      message_vector[i][0] = ord(message[i]) % 65
   encrypt(message_vector)
   ciphertext = [chr(cipher_matrix[i][0] + 65) for i in range(3)]
   print("The Ciphertext:", "".join(ciphertext))

message = "DOG"
key = "YHGINUKER"
hill_cipher(message, key)

以下是上述示例的輸出：

輸入/輸出

The Ciphertext: YOG

使用 Java 實現

這段 Java 程式碼使用希爾密碼演算法執行加密和解密。加密函式採用明文和金鑰矩陣。返回加密的密文。解密函式採用密文和金鑰矩陣。返回原始明文。行列式計算矩陣的行列式。並計算矩陣的伴隨矩陣（餘因子矩陣）。沿對角線轉換矩陣以轉置矩陣。

示例

請參見以下希爾密碼的 Java 實現程式碼：

import java.util.Arrays;

public class HillCipher {
   private static final int MOD = 26;

   public static String encryptText(String plaintext, int[][] key) {
      plaintext = plaintext.toUpperCase().replaceAll(" ", "");
      int n = key.length;
      int padding = n - plaintext.length() % n;
      if (padding != n) {
         plaintext += "X".repeat(padding);
      }

      StringBuilder ciphertext = new StringBuilder();
      for (int i = 0; i < plaintext.length(); i += n) {
         int[] block = new int[n];
         for (int j = 0; j < n; j++) {
            block[j] = plaintext.charAt(i + j) - 'A';
         }
         int[] encryptedBlock = multiplyMatrix(key, block);
         for (int value : encryptedBlock) {
            ciphertext.append((char) (value + 'A'));
         }
      }
      return ciphertext.toString();
   }

   public static String decryptText(String ciphertext, int[][] key) {
      int determinant = determinant(key);
      int adjoint[][] = adjoint(key);
      int n = key.length;
      int[][] inverseKey = new int[n][n];

      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            inverseKey[i][j] = (adjoint[i][j] * determinant) % MOD;
            if (inverseKey[i][j] < 0) {
               inverseKey[i][j] += MOD;
            }
         }
      }
      return encryptText(ciphertext, inverseKey);
   }

   private static int[] multiplyMatrix(int[][] key, int[] block) {
      int n = key.length;
      int[] result = new int[n];
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            result[i] += key[i][j] * block[j];
         }
         result[i] %= MOD;
      }
      return result;
   }

   private static int determinant(int[][] matrix) {
      if (matrix.length == 1) {
         return matrix[0][0];
      }
      int det = 0;
      for (int i = 0; i < matrix.length; i++) {
         int[][] minor = new int[matrix.length - 1][matrix.length - 1];
         for (int j = 1; j < matrix.length; j++) {
            for (int k = 0, col = 0; k < matrix.length; k++) {
               if (k == i) continue;
               minor[j - 1][col++] = matrix[j][k];
            }
         }
         det += Math.pow(-1, i) * matrix[0][i] * determinant(minor);
      }
      return det;
   }

   private static int[][] adjoint(int[][] matrix) {
      int n = matrix.length;
      int[][] adjoint = new int[n][n];
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            int[][] minor = new int[n - 1][n - 1];
            for (int k = 0, row = 0; k < n; k++) {
               if (k == i) continue;
               for (int l = 0, col = 0; l < n; l++) {
                  if (l == j) continue;
                  minor[row][col++] = matrix[k][l];
               }
               row++;
            }
            adjoint[i][j] = (int) Math.pow(-1, i + j) * determinant(minor);
         }
      }
      return transpose(adjoint);
   }

   private static int[][] transpose(int[][] matrix) {
      int[][] result = new int[matrix.length][matrix.length];
      for (int i = 0; i < matrix.length; i++) {
         for (int j = 0; j < matrix.length; j++) {
            result[i][j] = matrix[j][i];
         }
      }
      return result;
   }

   public static void main(String[] args) {
      int[][] key = {{6, 24, 1}, {13, 16, 10}, {20, 17, 15}};
      String plaintext = "POINT";
      String ciphertext = encryptText(plaintext, key);
      System.out.println("The Encrypted Text: " + ciphertext);
      String decrypted = decryptText(ciphertext, key);
      System.out.println("The Decrypted Text: " + decrypted);
   }
}

以下是上述示例的輸出：

輸入/輸出

The Encrypted Text: SFILBS
The Decrypted Text: POINTX

使用 C++ 實現

這段 C++ 程式碼實現了希爾密碼的加密和解密演算法。multiplyMatrix 函式將執行矩陣乘法。之後，determinant 函式將計算矩陣的行列式。然後，adjoint 函式計算矩陣的伴隨矩陣。encrypt 函式使用金鑰矩陣加密明文。decrypt 函式使用金鑰矩陣解密密文。

示例

請參見下面的 Hill 密碼 C++ 實現程式碼：

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 26;

vector<vector<int>> multiplyMatrix(const vector<vector<int>>& key, const vector<int>& block) {
   int n = key.size();
   vector<vector<int>> result(n, vector<int>(1, 0));
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < 1; j++) {
         for (int k = 0; k < n; k++) {
            result[i][j] += key[i][k] * block[k];
         }
         result[i][j] %= MOD;
      }
   }
   return result;
}

   int determinant(const vector<vector<int>>& matrix) {
      if (matrix.size() == 1) {
         return matrix[0][0];
      }
      int det = 0;
      int sign = 1;
      for (int i = 0; i < matrix.size(); i++) {
         vector<vector<int>> minor(matrix.size() - 1, vector<int>(matrix.size() - 1, 0));
         for (int j = 1; j < matrix.size(); j++) {
            for (int k = 0, col = 0; k < matrix.size(); k++) {
               if (k == i) continue;
               minor[j - 1][col++] = matrix[j][k];
            }
         }
         det += sign * matrix[0][i] * determinant(minor);
         sign *= -1;
      }
      return det;
   }

vector<vector<int>> adjoint(const vector<vector<int>>& matrix) {
      int n = matrix.size();
      vector<vector<int>> adjoint(n, vector<int>(n, 0));
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            vector<vector<int>> minor(n - 1, vector<int>(n - 1, 0));
            for (int k = 0, row = 0; k < n; k++) {
               if (k == i) continue;
               for (int l = 0, col = 0; l < n; l++) {
                  if (l == j) continue;
                  minor[row][col++] = matrix[k][l];
               }
               row++;
            }
            adjoint[i][j] = determinant(minor) * ((i + j) % 2 == 0 ? 1 : -1);
         }
      }
      vector<vector<int>> result = adjoint;
      for (int i = 0; i < n; i++) {
         for (int j = i + 1; j < n; j++) {
            swap(result[i][j], result[j][i]);
         }
      }
      return result;
   }

   string encrypt(const string& plaintext, const vector<vector<int>>& key) {
      string modifiedPlaintext = plaintext;
      int n = key.size();
      int padding = n - modifiedPlaintext.size() % n;
      if (padding != n) {
         modifiedPlaintext += string(padding, 'X');
      }

      string ciphertext = "";
      for (int i = 0; i < modifiedPlaintext.size(); i += n) {
         vector<int> block(n, 0);
         for (int j = 0; j < n; j++) {
            block[j] = modifiedPlaintext[i + j] - 'A';
         }
         vector<vector<int>> encryptedBlock = multiplyMatrix(key, block);
         for (const auto& row : encryptedBlock) {
            for (int value : row) {
               ciphertext += (char) (value + 'A');
            }
         }
      }
      return ciphertext;
   }

   string decrypt(const string& ciphertext, const vector<vector<int>>& key) {
      int det = determinant(key);
      vector<vector<int>> adj = adjoint(key);
      vector<vector<int>> inverseKey = key;

      int n = key.size();
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < n; j++) {
            inverseKey[i][j] = (adj[i][j] * det) % MOD;
            if (inverseKey[i][j] < 0) {
               inverseKey[i][j] += MOD;
            }
         }
      }
      return encrypt(ciphertext, inverseKey);
   }

int main() {
   vector<vector<int>> key = {{6, 24, 1}, {13, 16, 10}, {20, 17, 15}};
   string plaintext = "HELLO";
   string ciphertext = encrypt(plaintext, key);
   cout << "The Encrypted Text: " << ciphertext << endl;
   string decrypted = decrypt(ciphertext, key);
   cout << "The Decrypted Text: " << decrypted << endl;
   return 0;
}

以下是上述示例的輸出：

輸入/輸出

The Encrypted Text: TFJJZX
The Decrypted Text: HELLOX

優勢

Hill 密碼加密演算法具有以下優勢：

  • 安全性 − Hill 密碼使用字母塊而不是單個字母進行運算，因此比其他傳統的替換密碼更安全。它不易受到使用頻率分析的攻擊。

  • 靈活性 − Hill 密碼可以加密和解密包含大寫字母、小寫字母、標點符號和空格的訊息。由於其適應性強，它可以用於加密各種文字檔案。

  • 數學背景 − Hill 密碼基於線性代數的思想，為理解和建立高階加密方法提供了框架。它提供了一個研究加密技術和矩陣之間關係的機會。

  • 金鑰強度 − 加密金鑰矩陣的大小和不可預測性直接影響 Hill 密碼的安全性。透過使用更大的金鑰矩陣可以提高加密強度，這將使未經授權的方更難以解密訊息。

  • 複雜性 − Hill 密碼在沒有加密金鑰的情況下更難理解，因為它在加密過程中使用了矩陣運算。這進一步提高了演算法的安全性。

Hill 密碼的安全性

當使用 2x2 矩陣時，Hill 密碼很容易破解。然而，對於提供 256 種可能數字的現代加密系統而言，Hill 密碼效率非常低。

先前已經證明，Hill 密碼的線性相關性在防禦已知明文攻擊方面存在已知的漏洞。由於 Hill 密碼僅使用常規的代數方法求解，因此任何具有線性密文對的系統都可以輕鬆破解 Hill 密碼矩陣。

然而，增加矩陣乘法的次數並不能顯著增強系統安全性。另一方面，它可以與非線性過程結合使用以支援擴散。像 AES 這樣的現代高階加密技術使用不同的擴散來更好地增強系統安全性。

Lester S. Hill 開發了一種用於 6x6 矩陣密碼的專用機器，該機器被證明安全性有所提高。但由於其主要設定不可調整，其實際應用受到限制。

列印頁面
上一頁
下一頁
廣告
© . All rights reserved.