📚 课程目录第3章 FPE的数学基础

3. FPE 的数学基础：Feistel 结构与 NIST SP 800-38G

咱们做 FPE，说白了就是在加密后还能保持数据的原始格式。这个神奇能力怎么来的？靠的是 Feistel 网络和 NIST 给的标准化配方。

我刚接触 FPE 时，觉得这玩意儿挺玄乎。后来亲手搭了个 FF1 的实现，踩了些坑，才真正理解了它的巧妙。今天咱们就把这块硬骨头啃透。

3.1 为什么是 Feistel？

Feistel 结构最初是设计块密码的，比如 DES。但它有个天然优势：加密和解密用同样的电路结构——轮函数 f 的顺序反向就行，不用写两套代码。

FPE 借用了这个特性，但做了两处重大改造：

域不是 2ⁿ：传统块密码工作在二进制域，FPE 的输入可能是 10 位数字、8 位字母，没法直接用 AES 轮函数。
轮函数需要把整数映射到整数：Feistel 的 f 必须接受一个数值类型，输出也是该域内的值。

于是 NIST 在 SP 800-38G 里定了两种标准：FF1 和 FF3。我工作中用得最多的是 FF1，它通用性更强。

3.2 Feistel 结构在 FPE 里的具体工作

假设你要加密一个 16 位数字的信用卡号。Feistel 把它拆成左右两半：左 L₀，右 R₀。然后迭代 n 轮（FF1 默认 10 轮，FF3 默认 8 轮）。

每轮的计算是：

for i = 1 to n:
  L[i] = R[i-1]
  R[i] = L[i-1] ⊕ f(R[i-1], K[i])

这里面有个关键点：异或 ⊕ 要换成数字域的加法后取模。你想想看，数字 0-9 没法直接 XOR，所以得用「模 10^len 加法」来替代。

核心区别：传统 Feistel 用 XOR，FPE 用模加法。这个改动我一开始没注意，导致加密出来的结果范围越界，吃了大亏。

3.3 NIST SP 800-38G 里的两个范本

标准里给了 FF1 和 FF3-1（修偏版）。我用一个表格帮你快速对照：

特性	FF1	FF3-1
最小域长度	2（字符）	2（字符）
推荐轮数	10	8
内部使用密码	AES / CMAC	AES / CMAC
适用场景	通用（长域、短域）	短域（如两位数月份）
经典翻车点	最大消息长度限制大	偶数长度要求严格

我曾经在一个项目里用 FF3 加密三位数校验码，结果协议里必须补成偶数长度，折腾了好久。后来换了 FF1，省心很多。

3.4 轮函数 f 的设计——核心中的核心

Feistel 的 f 负责生成一个伪随机数，去遮蔽另一半。FPE 里的 f 是这样实现的：

把 R_i-1 转成字节串
用 AES-CMAC 计算一个 Hash 值
把 Hash 截断并按域取模

这个取模操作很考究。FF1 标准里有一段伪代码，专门处理「除法余数」的平衡问题。我直接贴我的简化版：

# Python 伪代码，模 10^len
def feistel_f(R_bytes, round_key, domain_size):
    mac = AES_CMAC(R_bytes, round_key)  # 输出 16 字节
    mac_int = int.from_bytes(mac, 'big')
    return mac_int % domain_size

你可能会问：直接取模会导致分布不均吗？NIST 在这个问题上做了大量的安全性分析，结论是一般安全场景足够。但如果你做高安全等级的应用，建议检查轮数。

注意：轮函数 f 里的 CMAC 是必选项，任何替换方案都必须经过 NIST 审核。我在一次评审中见过有人擅自改用 SHA-256，被当场打回。

3.5 一张图看清整体结构

下面这张 SVG 图总结了 Feistel 结构在 FPE 里的数据流。我习惯把它叫作「分-揉-合」三部曲：

个人习惯：我在实现时会把左右两半的长度调成一样（如果域长度是奇数，补一个最大可编码字符）。虽然标准里允许不等长，但等长实现起来代码更干净，测试也更容易覆盖。

3.6 哪些坑我已经替你踩过了

模加法溢出：Python 的 int 没上限，但 C 里要小心。我曾经在 C 代码里忘了用足 32 位，结果高位被截断，加密结果乱套。
轮密钥生成：FF1 的轮密钥不是直接喂 AES 密钥，而是先做一次 CMAC 派生。我一开始图省事直接复用密钥，导致分组相关性过高，被安全评审老师骂了一顿。
域大小类型：NIST 标准里规定域大小必须用整数表示。比如字母表 26 个字母，域大小就是 26。但如果你要做字母+数字混合，域大小要按独立字符集计算，不是简单把 Unicode 码点当数。

嗯，这一章的内容差不多讲完了。Feistel 结构是 FPE 的骨架，NIST 标准是血肉。你把它俩对齐了，后面的 Tokenization 对比篇就水到渠成。