密碼學中的概率論與統計學：從頻率分析到現代密碼攻擊

在密碼學的攻防博弈中，概率論與統計學始終是破解密碼的“利器”。從古典密碼時期通過字母頻率推測凱撒密碼的密鑰，到現代利用線性偏差破解DES的線性密碼分析，再到側信道攻擊中通過功耗數據的統計特性還原密鑰，統計思維貫穿了密碼分析的整個發展史。本文將系統梳理概率論與統計學在密碼分析中的核心應用，從基礎概念到具體攻擊方法，結合實例與代碼實現，展示“隨機性檢測”與“概率偏差利用”如何成為密碼破譯者的核心手段。

一、密碼學與概率統計的天然聯系

密碼學的核心目標是在不可信環境中保障信息安全，而“隨機性”是密碼系統的基石——一個安全的加密算法應使密文呈現完全隨機的特征，無法通過統計分析推導出明文或密鑰信息。然而，絕對的隨機性在現實中難以實現，任何加密算法的設計缺陷或實現漏洞都會導致密文中引入可被統計分析的“偏差”，這正是密碼分析的突破口。

1.1 密碼分析的本質：尋找統計偏差

密碼系統的安全性依賴于“密文與明文、密鑰的統計獨立性”。若密文的統計特性（如字母頻率、比特分布、差分概率）與明文或密鑰存在可量化的關聯，則攻擊者可利用這種關聯（偏差）還原密鑰。例如：

古典密碼中，密文的字母頻率與英文文本高度一致（如“e”出現頻率最高），直接暴露密鑰；
現代分組密碼中，S盒設計缺陷可能導致“輸入差分→輸出差分”的概率偏離隨機值，成為差分分析的靶點；
側信道攻擊中，加密操作的功耗與密鑰比特存在線性相關性，通過統計分析可提取密鑰。

1.2 核心概率統計概念

在密碼分析中，以下概率統計概念是基礎工具：

概率分布：描述密文、明文、密鑰等隨機變量的取值規律（如均勻分布、二項分布）。理想密文應服從均勻分布（每個取值概率相等）。
期望值與方差：期望值描述隨機變量的平均取值，方差描述離散程度。例如，英文文本中字母“e”的出現概率約12.7%（期望值），遠高于均勻分布的3.8%（26字母）。
相關性與偏差：相關性衡量兩個變量的線性關聯程度（如密鑰比特與功耗的相關性）；偏差描述實際分布與理想分布的偏離（如線性密碼分析中的“線性偏差”）。
大數定律：大量樣本的統計特性趨近于理論期望，為密碼分析提供“需要足夠多密文/樣本”的理論依據。

二、古典密碼的“命門”：頻率分析

古典密碼（如凱撒密碼、維吉尼亞密碼）因未掩蓋明文的統計特性，極易被頻率分析破解。這種方法通過統計密文中字符的出現頻率，對比自然語言的頻率特征，推測密鑰。

2.1 英文文本的統計特性

英文文本的字母頻率具有穩定的統計規律（基于大量樣本統計），這是頻率分析的基礎。典型頻率分布如下（前6位）：

e: ~12.7%，t: ~9.1%，a: ~8.2%，o: ~7.5%，i: ~7.0%，n: ~6.7%

其他特征：

雙字母組合：“th”“he”“in”出現頻率最高；
單詞長度：平均單詞長度約5個字母，短單詞（如“a”“the”）出現頻繁。

2.2 凱撒密碼的頻率分析破解

凱撒密碼通過固定偏移量替換字母（如密鑰k=3時，a→d、b→e），其密文的字母頻率分布與明文完全一致，僅整體偏移k位。破解步驟：

統計密文中每個字母的出現頻率；
將密文頻率最高的字母對應明文的“e”（或其他高頻字母），計算偏移量k；
用k嘗試解密，驗證語法合理性。

實例：密文“dwwdfndwgdzq”的字母頻率中“w”出現3次（最高），假設對應明文“e”，則k=18（w - e = 18：實際凱撒密碼中a=0，e=4，w=22，22-4=18，此處簡化舉例，實際通過偏移量計算：若密文高頻字母是c，對應e，則k= c - e = 2 - 4 = -2 mod 26，即偏移24）。

Python實現頻率分析：

import string
from collections import Counterdef letter_frequency(ciphertext):"""統計密文中字母出現的頻率（忽略非字母字符）"""# 過濾非字母并轉為小寫filtered = [c.lower() for c in ciphertext if c.isalpha()]total = len(filtered)if total == 0:return {}# 統計頻率freq = Counter(filtered)# 轉換為百分比for c in freq:freq[c] = (freq[c] / total) * 100# 按字母表順序補充缺失字母（頻率0）for c in string.ascii_lowercase:if c not in freq:freq[c] = 0.0return dict(sorted(freq.items()))def caesar_crack(ciphertext):"""通過頻率分析破解凱撒密碼"""# 英文字母頻率表（參考值）english_freq = {'a': 8.167, 'b': 1.492, 'c': 2.782, 'd': 4.253, 'e': 12.702,'f': 2.228, 'g': 2.015, 'h': 6.966, 'i': 7.507, 'j': 0.153,'k': 1.037, 'l': 4.025, 'm': 2.406, 'n': 6.749, 'o': 7.507,'p': 1.929, 'q': 0.095, 'r': 5.987, 's': 6.327, 't': 9.056,'u': 2.758, 'v': 0.978, 'w': 2.360, 'x': 0.150, 'y': 1.974, 'z': 0.074}# 計算密文頻率cipher_freq = letter_frequency(ciphertext)# 嘗試所有可能偏移（0-25），計算與英文頻率的偏差（最小二乘）min_error = float('inf')best_shift = 0for shift in range(26):error = 0.0for c in string.ascii_lowercase:# 密文字母c對應明文字母 (c - shift) mod 26plain_char = chr((ord(c) - ord('a') - shift) % 26 + ord('a'))error += (cipher_freq[c] - english_freq[plain_char]) **2if error < min_error:min_error = errorbest_shift = shift# 用最佳偏移解密plaintext = []for c in ciphertext:if c.isalpha():is_upper = c.isupper()c_lower = c.lower()# 偏移計算shifted = (ord(c_lower) - ord('a') - best_shift) % 26plain_char = chr(shifted + ord('a'))plaintext.append(plain_char.upper() if is_upper else plain_char)else:plaintext.append(c)return ''.join(plaintext), best_shift# 測試：凱撒密碼密文（密鑰k=3）
ciphertext = "DWWDFNDWG DZQ WKH WRJDQ"
plaintext, shift = caesar_crack(ciphertext)
print(f"推測密鑰偏移: {shift}")
print(f"解密結果: {plaintext}")  # 應輸出"ATTACKAT THE GOAL"（忽略空格差異）

2.3 維吉尼亞密碼的統計破解

維吉尼亞密碼通過關鍵詞控制多表替換，破解難度高于單表密碼，但仍可通過“卡西斯基試驗”和“弗里德曼檢驗”利用統計特性：
1.確定密鑰長度：尋找密文中重復出現的字符串，其間距的最大公約數可能是密鑰長度。例如，密文“ABCABC”中“ABC”重復出現，間距3，推測密鑰長度3。
2.按密鑰長度分組：將密文按密鑰長度n分為n組，每組對應單表凱撒密碼。
3.單組頻率分析：對每組單獨進行頻率分析，破解對應凱撒密鑰，拼接得到維吉尼亞密鑰。

代碼思路：通過計算重合指數（Index of Coincidence, IC）確定密鑰長度。重合指數是密文中隨機選取兩個字符相同的概率，英文文本的IC約0.0667，而隨機文本約0.0385。對不同可能的密鑰長度n，計算每組的平均IC，接近0.0667的n即為候選長度。

三、現代對稱密碼的統計攻擊：線性與差分分析

古典密碼的統計分析依賴字符頻率，而現代分組密碼（如DES、AES）的設計引入了擴散與混淆，掩蓋了明文的直接統計特征。但統計攻擊并未失效，而是升級為利用“線性近似”和“差分概率”的高級方法。

3.1 線性密碼分析：利用線性近似的偏差

線性密碼分析由Matsui于1993年提出，核心思想是尋找明文、密文與密鑰之間的線性近似關系，通過大量明密文對統計該關系的“偏差”，還原密鑰。

3.1.1 核心原理

線性近似：對于分組密碼的S盒（非線性組件），尋找線性方程
x ₁⊕x ₂⊕…⊕x_n=y₁⊕y₂⊕…⊕y_m⊕k
x為輸入比特，y 為輸出比特，k 為密鑰比特），該方程成立的概率 p 偏離0.5（隨機期望）。
偏差：定義偏差 ? = |p - 0.5| ，偏差越大，線性近似越有效。
密鑰還原：收集大量明密文對，統計線性方程成立的次數，通過偏差符號推測密鑰比特。

3.1.2 DES的線性分析實例

DES的線性分析需找到16輪的線性近似路徑，例如：

輸入掩碼：α = 0x0000000000000001 （僅最后1位為1）
輸出掩碼：β = 0x8000000000000000 （僅第64位為1）
總偏差：?≈2 ^?21
通過約2⁴³個明密文對，可統計該路徑的偏差，逐步還原16個輪密鑰。

3.3 差分密碼分析：追蹤差分的傳播概率

差分密碼分析由Shamir和Biham于1990年提出，通過分析明文對的差分（XOR）在加密過程中的傳播規律，利用“高概率差分路徑”破解密鑰。

3.3.1 核心概念

差分：明文對 (P, P’) 的差分定義為ΔP=P⊕P ′，對應密文差分ΔC=C⊕C′。
差分概率：對于給定輸入差分ΔX，輸出差分ΔY的概率:
Pr(ΔY=f(X⊕ΔX)⊕f(X))
其中f為加密函數（如S盒）。
差分路徑：多輪加密中，差分從輸入到輸出的高概率傳播路徑。例如，DES的一個2輪差分路徑概率可達0.25。

3.3.2 攻擊步驟（以DES為例）

1.選擇明文對：構造大量具有固定輸入差分ΔP的明文對
(P,P⊕ΔP)。
2.加密與差分計算：獲取對應密文對 (C, C’) ，計算密文差分ΔC。
3.驗證差分路徑：若ΔC符合高概率路徑的輸出差分，則對應輪密鑰的候選值概率升高。
4.統計密鑰候選：通過大量樣本統計，出現頻率最高的候選值即為真實密鑰。

簡化實例：對4位S盒，輸入差分ΔX = 0011 ，輸出差分ΔY = 0101 的概率為0.5（即一半輸入對滿足該差分）。通過1000對樣本，可統計出S盒的密鑰信息。

Python實現S盒差分概率計算：

def sbox(x, key):"""簡化4位S盒（示例）：x為4位輸入，key為4位密鑰，輸出4位"""# 實際S盒是固定置換表，此處用簡單函數模擬return (x ^ key) * 3 % 16  # 僅為示例，非真實S盒def compute_difference_probability(sbox, delta_x, delta_y, key):"""計算輸入差分delta_x到輸出差分delta_y的概率"""count = 0total = 0for x in range(16):  # 4位輸入共16種可能x_prime = x ^ delta_xy = sbox(x, key)y_prime = sbox(x_prime, key)if (y ^ y_prime) == delta_y:count += 1total += 1return count / total# 測試：密鑰key=0010（二進制），輸入差分delta_x=0011（3）
delta_x = 3  # 0011
delta_y = 5  # 0101
key = 2      # 0010
prob = compute_difference_probability(sbox, delta_x, delta_y, key)
print(f"差分概率: {prob}")  # 輸出該差分路徑的概率

四、公鑰密碼的統計攻擊

公鑰密碼基于數學難題（如大整數分解、離散對數），但實現中的統計缺陷仍可能被利用，典型如“時序攻擊”和“錯誤注入攻擊”。

4.1 RSA的時序攻擊

RSA解密公式為 m = c^d mod n ，其中指數運算通過快速冪實現（平方-乘算法）。若密鑰d的比特為1時運算時間長于0時（因多一次乘法），攻擊者可通過統計解密時間推測d的比特值。

攻擊原理

時間差異：快速冪中，若當前密鑰比特為1，執行“平方+乘法”；為0時僅執行“平方”，兩者耗時不同。
統計分析：通過大量不同c的解密時間，關聯c的數值特征（如高比特位），推測d的比特序列。

防御措施：采用恒定時間算法（Constant-Time Algorithm），確保運算時間與密鑰比特無關（如強制每次迭代都執行乘法，忽略結果是否有效）。

4.2 橢圓曲線密碼（ECC）的側信道統計攻擊

ECC的點乘運算( kP )（k為私鑰，P為基點）是側信道攻擊的目標，攻擊者通過統計功耗、電磁輻射等物理信息的偏差還原k。

攻擊步驟

1.采集物理數據：記錄多次點乘運算的功耗曲線（每個時鐘周期的功耗值）。
2.對齊與分段：將功耗曲線按點乘步驟（加法、倍乘）分段。
3.相關性分析：計算每段功耗與假設密鑰比特的相關性（如漢明重量——1的個數，功耗與漢明重量正相關）。
4.還原密鑰：通過相關性峰值依次確定k的每個比特。

實例：若k的第i位為1時，某段功耗的平均值為5.2；為0時平均值為3.1，則通過統計該段功耗可判斷第i位取值。

五、隨機數發生器的統計檢測

密碼學依賴高質量隨機數（如密鑰、IV生成），若隨機數發生器（RNG）存在統計缺陷（如分布不均、相關性），則加密系統可被破解。NIST SP 800-22定義了15項統計檢測指標，用于評估RNG的質量。

5.1 核心檢測指標

頻率檢測：檢測0和1的出現頻率是否接近0.5（均勻性）。
序列檢測：檢測長序列（如100個連續0）的出現概率是否符合隨機期望。
線性復雜度檢測：檢測序列的線性反饋移位寄存器（LFSR）最小長度，過長則非隨機。
近似熵檢測：衡量序列的不確定性，與隨機序列的熵值對比。

5.2 實例：頻率檢測實現

頻率檢測通過計算序列中1的比例，用正態分布檢驗其是否偏離0.5：

統計1的個數S(n) ，計算統計量Z= ∣S(n)?n/2∣/(n/4)^-1。
若Z≤1.96（置信水平95%），則通過檢測。

Python實現：

import math
from scipy.stats import normdef frequency_test(bit_sequence):"""NIST頻率檢測：檢驗0和1的分布是否均勻"""n = len(bit_sequence)if n == 0:return False, 0.0# 統計1的個數s = sum(bit_sequence)# 計算統計量Zz = abs(s - n/2) / math.sqrt(n / 4)# 計算P值（正態分布尾部概率）p_value = 2 * (1 - norm.cdf(z))# 結論：P值>0.01則通過檢測return p_value > 0.01, p_value# 測試：良好隨機序列（應通過）
good_rng = [1,0,1,1,0,0,1,0,1,0] * 100  # 近似均勻
pass_test, p = frequency_test(good_rng)
print(f"良好隨機序列：{'通過' if pass_test else '失敗'}, P值：{p:.4f}")# 測試：缺陷序列（過多1，應失敗）
bad_rng = [1]*600 + [0]*400
pass_test, p = frequency_test(bad_rng)
print(f"缺陷序列：{'通過' if pass_test else '失敗'}, P值：{p:.4f}")

5.3 常見RNG缺陷與攻擊案例

線性同余發生器LCG： Xⁿ⁺¹ = (aX_n + c) mod m ，可通過已知輸出序列還原參數a、c、m，預測后續輸出。
種子泄露：若RNG的種子可預測（如用系統時間且精度低），則所有輸出可還原。例如，早期SSL協議用當前時間作為種子，攻擊者通過猜測時間破解會話密鑰。

六、統計攻擊的防御策略

統計攻擊的本質是利用“非隨機性”，防御需從算法設計到實現全方位消除統計偏差：

1.算法層面：

對稱密碼：增加輪數、使用非線性更強的S盒（如AES的S盒基于有限域逆元，差分和線性偏差極低）。
公鑰密碼：采用恒定時間實現，避免密鑰相關操作的時間/功耗差異。

2.實現層面：

隨機數：使用 cryptographically secure RNG（CSPRNG），如Linux的/dev/urandom，通過物理噪聲（如鍵盤輸入、磁盤延遲）增強隨機性。
側信道防護：加入噪聲（如隨機延遲）、采用掩碼技術（將密鑰與隨機值結合，消除與物理信息的相關性）。

3.評估層面：

定期用NIST SP 800-22、Dieharder等工具檢測隨機數質量。
進行側信道分析測試（如CPA、DPA），驗證實現安全性。

七、總結與展望

概率論與統計學在密碼分析中扮演著“矛”的角色——從古典密碼的頻率分析到現代的差分/線性分析，再到側信道的相關性分析，統計思維始終是破解密碼的核心方法論。同時，這些攻擊手段也推動了密碼設計的進步（如AES的抗差分/線性分析設計），形成“攻擊-防御”的良性循環。

未來，隨著量子計算和機器學習的發展，統計攻擊將呈現新形態：量子算法可加速統計分析中的樣本處理，機器學習可自動挖掘密碼系統的非線性統計偏差。但無論技術如何演進，“消除統計偏差、保持完美隨機性”始終是密碼學的永恒追求。

對于開發者，理解統計攻擊的原理是設計安全系統的前提：永遠不要低估統計分析的威力，也不要高估自己實現的隨機性——密碼學的安全性，往往崩塌于一個微小的統計偏差。

參考資料：

《密碼學原理與實踐》（Douglas Stinson）
NIST SP 800-22 《A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications》
《Differential Cryptanalysis of the Data Encryption Standard》（Eli Biham, Adi Shamir）
《Linear Cryptanalysis Method for DES Cipher》（Mitsuru Matsui）ui）