密碼學 - MixColumns 變換

AES（高階加密標準）演算法使用 MixColumns 變換進行資料加密和解密。此數學過程應用於 AES 資料矩陣的每一列。

它是如何工作的？

為了使 AES 中的 MixColumns 變換正常工作，狀態矩陣的每一列都需要進行數學運算。此運算的基本組成部分是 GF(28) 中的多項式算術，GF(28) 是一種稱為伽羅瓦域 (GF) 的原始代數域。

以下是其工作原理的詳細說明 -

狀態矩陣表示 - 正在處理的資料儲存在一個稱為狀態矩陣的 4x4 網格中。
固定矩陣 - MixColumns 變換使用固定矩陣。此矩陣在整個加密和解密過程中保持不變。
逐列乘法 - 狀態矩陣的每一列都被視為 GF(2^8) 中的多項式。然後將該多項式乘以固定矩陣的對應列。
多項式乘法 - 在 GF(2^8) 中乘以多項式時，需要遵循一些規則。首先，必須使用稱為不可約多項式的固定多項式進行模運算。在 AES 的情況下，此多項式為 x⁸ + x⁴ + x³ + x + 1，用十六進位制表示為 0x11B。
XOR 運算 - 在乘法階段之後，將結果進行 XOR（異或）以生成每一列的最終結果。
結果狀態矩陣 - 透過對每一列執行乘法和 XOR 運算，生成轉換後的狀態矩陣，該矩陣顯示 MixColumns 變換。

此方法產生的資料擴散和混淆增強了加密過程的安全性。透過確保輸入資料中單個位元組的修改會影響輸出中的多個位元組，攻擊者更難訪問和解密加密資料。

使用 Python 實現

為了對狀態矩陣執行 MixColumns 變換，Python 程式碼實現了兩個輔助函式：mix_columns 和 gf_multiply。在 AES 加密過程中的 MixColumns 階段，透過將每一列中的位元組與固定矩陣相乘，從而轉換狀態矩陣的列。

示例

def mix_columns(state):
   fixed_matrix = [
      [0x02, 0x03, 0x01, 0x01],
      [0x01, 0x02, 0x03, 0x01],
      [0x01, 0x01, 0x02, 0x03],
      [0x03, 0x01, 0x01, 0x02]
   ]

   new_state = []
   for col in range(4):
      new_column = []
      for row in range(4):
         val = 0
         for i in range(4):
            val ^= gf_multiply(fixed_matrix[row][i], state[i][col])
         new_column.append(val)
      new_state.append(new_column)
   return new_state

def gf_multiply(a, b):
   p = 0
   for _ in range(8):
      if b & 1:
         p ^= a
      hi_bit_set = a & 0x80
      a <<= 1
      if hi_bit_set:
         a ^= 0x1B  # irreducible polynomial
      b >>= 1
   return p if p < 0x80 else p ^ 0x11B

# Example usage:
state_matrix = [
   [0x32, 0x88, 0x31, 0xe0],
   [0x43, 0x5a, 0x31, 0x37],
   [0xf6, 0x30, 0x98, 0x07],
   [0xa8, 0x8d, 0xa2, 0x34]
]
new_state = mix_columns(state_matrix)

# Displaying output in matrix form
for row in new_state:
   print(row)

以下是上述示例的輸出 -

輸入/輸出

[484, 6, 101, 424]
[67, 506, 318, 232]
[11, 322, 214, 421]
[170, 424, 414, 120]

使用 Java 實現

Java 實現的 mixColumns 函式接收一個 4x4 狀態矩陣作為輸入，並在應用 MixColumns 變換後輸出修改後的狀態矩陣。gfMultiply 函式用於在 GF(2^8) 中對每個矩陣元素執行多項式乘法。因此，使用 Java 的程式碼如下 -

示例

public class MixColumns {

   public static int[][] mixColumns(int[][] state) {
      int[][] fixedMatrix = {
         {0x02, 0x03, 0x01, 0x01},
         {0x01, 0x02, 0x03, 0x01},
         {0x01, 0x01, 0x02, 0x03},
         {0x03, 0x01, 0x01, 0x02}
      };

      int[][] newState = new int[4][4];
      for (int col = 0; col < 4; col++) {
         for (int row = 0; row < 4; row++) {
            int val = 0;
            for (int i = 0; i < 4; i++) {
               val ^= gfMultiply(fixedMatrix[row][i], state[i][col]);
            }
            newState[row][col] = val;
         }
      }
      return newState;
   }

   public static int gfMultiply(int a, int b) {
      int p = 0;
      for (int i = 0; i < 8; i++) {
         if ((b & 1) != 0) {
            p ^= a;
         }
         int hiBitSet = a & 0x80;
         a <<= 1;
         if (hiBitSet != 0) {
            a ^= 0x1B;  // irreducible polynomial
         }
         b >>= 1;
      }
      return p;
   }

   public static void main(String[] args) {
      int[][] stateMatrix = {
         {0x32, 0x88, 0x31, 0xe0},
         {0x43, 0x5a, 0x31, 0x37},
         {0xf6, 0x30, 0x98, 0x07},
         {0xa8, 0x8d, 0xa2, 0x34}
      };
      int[][] newState = mixColumns(stateMatrix);

      // Displaying output in matrix form
      for (int[] row : newState) {
         for (int val : row) {
            System.out.print(String.format("%02X ", val));
         }
         System.out.println();
      }
   }
}

以下是上述示例的輸出 -

輸入/輸出

FF 158 0B 1B1 
11D E1 142 B3
65 13E D6 85 
1A8 E8 1A5 163

使用 C++ 實現

在這些實現中，我們將使用 C++，並且我們將有一個名為 mixColumns 的函式，該函式接收一個 4x4 狀態矩陣作為輸入，並在使用 MixColumns 變換後返回轉換後的狀態矩陣。因此，程式碼如下 -

示例

#include <iostream>
#include <vector>

int gfMultiply(int a, int b);

std::vector<std::vector<int>> mixColumns(std::vector<std::vector<int>> state) {
   std::vector<std::vector<int>> fixedMatrix = {
      {0x02, 0x03, 0x01, 0x01},
      {0x01, 0x02, 0x03, 0x01},
      {0x01, 0x01, 0x02, 0x03},
      {0x03, 0x01, 0x01, 0x02}
   };

   std::vector<std::vector<int>> newState(4, std::vector<int>(4, 0));
   for (int col = 0; col < 4; col++) {
      for (int row = 0; row < 4; row++) {
         int val = 0;
         for (int i = 0; i < 4; i++) {
            val ^= gfMultiply(fixedMatrix[row][i], state[i][col]);
         }
         newState[row][col] = val;
      }
   }
   return newState;
}

int gfMultiply(int a, int b) {
   int p = 0;
   for (int i = 0; i < 8; i++) {
      if (b & 1) {
         p ^= a;
      }
      int hiBitSet = a & 0x80;
      a <<= 1;
      if (hiBitSet) {
         a ^= 0x1B;  // irreducible polynomial
      }
      b >>= 1;
   }
   return p;
}

int main() {
   std::vector<std::vector<int>> stateMatrix = {
      {0x32, 0x88, 0x31, 0xe0},
      {0x43, 0x5a, 0x31, 0x37},
      {0xf6, 0x30, 0x98, 0x07},
      {0xa8, 0x8d, 0xa2, 0x34}
   };
   auto newState = mixColumns(stateMatrix);

   // Displaying output in matrix form
   for (auto row : newState) {
      for (int val : row) {
         std::cout << std::hex << val << " ";
      }
      std::cout << std::endl;
   }
   return 0;
}

以下是上述示例的輸出 -

輸入/輸出

ff 158 b 1b1 
11d e1 142 b3 
65 13e d6 85 
1a8 e8 1a5 163

總結

MixColumns 變換是 AES 加密演算法的重要組成部分，它增強了資料加密和解密過程的安全性。此變換在 GF(2^8) 伽羅瓦域中使用多項式算術對狀態矩陣的列進行操作。Python、Java 和 C++ 中提供的實現展示瞭如何以程式設計方式實現 MixColumns 變換。

列印頁面