密码学中的概率论与统计学：从频率分析到现代密码攻击

在密码学的攻防博弈中，概率论与统计学始终是破解密码的“利器”。从古典密码时期通过字母频率推测凯撒密码的密钥，到现代利用线性偏差破解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 ⁻²¹
通过约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）