分組密碼

分組密碼概述

1. 基本定義
   分組密碼是將明文消息編碼后的數字序列劃分為長度為$n$的組（$n$維矢量），在密鑰控制下變換為等長的輸出數字序列（$m$維矢量），加密函數為$E:V_n\times K\to V_m$，其中$V_n$、$V_m$為$n$維、$m$維矢量空間，$K$為密鑰空間。
2. 核心概念
   • 代換：明文分組到密文分組的可逆變換。對于$n$比特分組，有$2^n$個可能取值，可逆變換的總數為$(2^n)!$（所有可能置換）。例如$n=4$時，4 比特輸入（16 種狀態）通過代換表映射為 4 比特輸出，加密與解密可通過代換表定義。
   • 擴散與混淆（Shannon 提出，抗統計分析的核心）：
     • 擴散：將明文的統計特性（如字母頻率）散布到密文，使密文統計特性更均勻（例如通過多輪置換 + 函數變換實現）。
     • 混淆：使密文與密鑰的統計關系復雜化，避免敵手通過密文統計特性推導密鑰（通過復雜非線性代換實現）。

Feistel 密碼結構

1. 基本原理
   • 采用 “乘積密碼” 思想，將分組分為左右兩半（$L_0,R_0$），經多輪迭代變換：
     • 第$i$輪：$L_i=R_{i?1}$，$R_i=L_{i?1}\oplus F(R_{i?1},K_i)$，其中$F$為輪函數，$K_i$為子密鑰。
     • 解密：與加密算法相同，但子密鑰使用順序相反（第 1 輪用$K_n$，最后一輪用$K_1$）。
2. 關鍵參數
   • 分組大小：越大安全性越高，但速度越慢；
   • 密鑰大小：越長安全性越高，但速度越慢；
   • 輪數：多輪可提升安全性（單輪不足以抗攻擊）；
   • 子密鑰產生算法：復雜度越高，密碼分析越難；
   • 輪函數：復雜度越高，安全性越強。

數據加密標準（DES）

1. 基本參數
   • 分組長度：64 比特；密鑰長度：56 比特（含 8 位奇偶校驗位）；輪數：16 輪。
   • 結構：Feistel 網絡，包含初始置換、16 輪迭代、逆初始置換。
2. 加密流程
   • 初始置換（IP）：重排 64 比特明文，輸出 32 比特左半（$L_0$）和 32 比特右半（$R_0$）。
   • 輪變換：
     1. 擴展置換（E）：將 32 比特$R_{i?1}$擴展為 48 比特（重復 16 個比特）；
     2. 與 48 位子密鑰$K_i$異或；
     3. S 盒代換：8 個 S 盒（每個 6 輸入 4 輸出），將 48 比特壓縮為 32 比特；
     4. 置換（P）：重排 32 比特輸出，作為輪函數$F$的結果；
     5. 迭代：$L_i=R_{i?1}$，$R_i=L_{i?1}\oplus F(R_{i?1},K_i)$。
   • 逆初始置換（IP?1）：16 輪后交換左右兩半，經 IP?1 輸出 64 比特密文。
3. 密鑰產生
   • 56 比特密鑰經置換選擇 1（PC1）分為 28 比特$C_0$和 28 比特$D_0$；
   • 每輪左移（1 或 2 位，依輪數而定），經置換選擇 2（PC2）產生 48 位子密鑰$K_i$。
4. 變種
   • 二重 DES：用兩個 56 比特密鑰（總 112 比特），易受 “中途相遇攻擊”（需$2^{56}$存儲和計算）；
   • 三重 DES：
     • 兩個密鑰（EDE 模式）：$C=E_{K1}(D_{K2}(E_{K1}(P)))$，密鑰長 112 比特；
     • 三個密鑰：$C=E_{K3}(D_{K2}(E_{K1}(P)))$，密鑰長 168 比特，安全性更高。

差分密碼分析與線性密碼分析

1. 差分密碼分析
   • 原理：通過分析明文對的差值（$\Delta X=X_1\oplus X_2$）對密文對差值（$\Delta Y=Y_1\oplus Y_2$）的影響，恢復密鑰。
   • 核心概念：
     • $r$輪特征：差分序列$({\alpha }_0,{\alpha }_1,...,{\alpha }_r)$，其中${\alpha }_0$為明文差分，${\alpha }_i$為第$i$輪輸出差分；
     • 概率：$r$輪特征的概率為各輪函數差分概率的乘積。
2. 線性密碼分析
   • 原理：利用 “不平衡線性逼近”，尋找明文（$P$）、密文（$C$）、密鑰（$K$）的線性方程$P[i_1,...,i_a]\oplus C[j_1,...,j_b]=K[k_1,...,k_c]$，通過已知明文對的統計偏差（概率≠1/2）確定密鑰。
3. 改進方法
   • 包括高階差分分析、不可能差分分析、多重線性分析、能量分析（針對硬件）等。

分組密碼的運行模式

1. 電碼本模式（ECB）
   • 特點：每個 64 比特明文分組獨立用同一密鑰加密，密文與明文一一對應（類似 “電碼本”）。
   • 優缺點：簡單快速，但重復明文產生重復密文，易暴露統計特性，適合短數據（如密鑰傳輸）。
2. 密碼分組鏈接模式（CBC）
   • 特點：當前明文分組與前一密文分組異或后加密，即$C_i=E_K(P_i\oplus C_{i?1})$，首組需初始向量（IV）：$C_0=E_K(P_0\oplus IV)$。
   • 優缺點：隱藏重復明文，安全性高于 ECB；IV 需保密（防止首組被篡改）。
3. 密碼反饋模式（CFB）
   • 特點：將分組密碼轉為流密碼，64 比特移位寄存器初始為 IV，加密輸出的前$j$比特與明文單元異或得密文，密文單元移入移位寄存器。
   • 優缺點：實時加密（無需填充），密文與明文等長；錯誤會傳播（影響后續解密）。
4. 輸出反饋模式（OFB）
   • 特點：移位寄存器反饋加密算法的輸出（而非密文），即$S_i=E_K(S_{i?1})$，密文$C_i=P_i\oplus S_i$。
   • 優缺點：錯誤不傳播（僅影響當前單元），但易受篡改（密文比特翻轉會導致明文對應比特翻轉）。

國際數據加密算法（IDEA）

1. 基本參數
   • 分組長度：64 比特；密鑰長度：128 比特；輪數：8 輪迭代 + 1 輪輸出變換。
2. 核心運算
   • 三種非線性運算（確保混淆與擴散）：
     • 逐比特異或（$\oplus$）；
     • 模$2^{16}$加法（$+$）；
     • 模$2^{16}+1$乘法（$\odot$，0 視為$2^{16}$）。
3. 加密流程
   • 明文分為 4 個 16 比特子段$(X_1,X_2,X_3,X_4)$；
   • 每輪用 6 個子密鑰，通過 “乘加（MA）結構” 處理，輸出 4 個子段；
   • 輸出變換：用 4 個子密鑰，調整子段順序以抵消最后一輪的交換。
4. 解密
   • 子密鑰為加密子密鑰的逆元（模$2^{16}+1$乘法逆元、模$2^{16}$加法逆元），輪密鑰順序相反。

高級加密標準（AES，Rijndael）

1. 基本參數
   • 分組長度（$N_b$）：128/192/256 比特（對應列數 4/6/8）；
   • 密鑰長度（$N_k$）：128/192/256 比特（對應列數 4/6/8）；
   • 輪數（$N_r$）：10/12/14 輪（依分組和密鑰長度而定）。
2. 數學基礎
   • 基于有限域$GF(2^8)$，元素表示為 8 次多項式（系數為 0/1），加法為異或，乘法模不可約多項式$m(x)=x^8+x^4+x^3+x+1$（十六進制 “11B”）。
3. 輪函數
   • 字節代換（SubBytes）：通過 S 盒（非線性變換，先求$GF(2^8)$逆元，再仿射變換）替換每個字節；
   • 行移位（ShiftRow）：第 0 行不動，第 1 行左移 1 位，第 2 行左移 2 位，第 3 行左移 3 位（依$N_b$調整）；
   • 列混合（MixColumn）：每列視為$GF(2^8)$上多項式，與固定多項式$c(x)=03x^3+01x^2+01x+02$模$x^4+1$相乘；
   • 密鑰加（AddRoundKey）：狀態與輪密鑰逐比特異或。
   • 最后一輪無 “列混合”。
4. 密鑰擴展
   • 種子密鑰擴展為$N_b\times (N_r+1)$個字（4 字節），通過循環移位、S 盒代換、輪常量異或生成子密鑰。
5. 解密
   • 用逆變換（逆字節代換、逆行移位、逆列混合），輪密鑰為加密輪密鑰的逆序（最后一輪密鑰不變，其余經逆列混合處理）。

中國商用密碼 SM4

1. 基本參數
   • 分組長度：128 比特；密鑰長度：128 比特；輪數：32 輪。
2. 核心部件
   • S 盒：8 輸入 8 輸出非線性替換，基于固定表；
   • 非線性變換（$\tau$）：4 個 S 盒并行處理 4 字節；
   • 線性變換（$L$）：$L(B)=B\oplus (B?2)\oplus (B?10)\oplus (B?18)\oplus (B?24)$，實現擴散；
   • 合成變換（$T$）：$T(X)=L(\tau (X))$，結合混淆與擴散。
3. 加密流程
   • 明文分為 4 個 32 比特子段$(X_0,X_1,X_2,X_3)$；
   • 32 輪迭代：$X_{i+4}=X_i\oplus T(X_{i+1}\oplus X_{i+2}\oplus X_{i+3}\oplus r{k}_i)$，$r{k}_i$為輪密鑰；
   • 反序處理：$(Y_0,Y_1,Y_2,Y_3)=(X_{35},X_{34},X_{33},X_{32})$。
4. 密鑰擴展
   • 由 128 比特密鑰生成 32 個輪密鑰，使用固定常數$FK$和參數$CK$，通過$T^{\prime }$變換（線性變換$L^{\prime }$替代$L$）生成。

祖沖之密碼（ZUC）

1. 結構
   • 三層邏輯：16 級線性反饋移位寄存器（LFSR）、比特重組（BR）、非線性函數（F）。
   • LFSR：16 個 31 比特寄存器，特征多項式為$GF(2^{31}?1)$上的本原多項式，支持初始化（引入非線性函數輸出）和工作模式。
   • 比特重組：從 LFSR 抽取 128 比特，組成 4 個 32 比特字$(X_0,X_1,X_2,X_3)$。
   • 非線性函數：壓縮 96 比特（$X_0,X_1,X_2$）為 32 比特，含 S 盒（4 個 8×8 S 盒并行）和線性變換。
2. 應用
   • 用于 4G 移動通信加密（128-EEA3 算法），基于初始密鑰和向量生成密鑰流，與消息異或實現加解密。