FPE核心原理：Feistel网络、PRP与Round函数设计
学FPE，绕不开 Feistel 网络。这玩意儿是个老古董——70 年代从 Lucifer 密码里诞生的，但放到今天依然好用。我做过好几个 FPE 项目，底层用的全是 Feistel。为什么呢？因为它的可逆性太漂亮了，不管你的轮函数有多乱，加密和解密只在密钥编排上差一点，轮结构完全一样。
这章我带你拆解三个核心部件：Feistel 网络、伪随机置换 (PRP) 以及 Round 函数设计。说白了，它们就是 FPE 的三块积木，搭好了你的格式保留密码就稳了。
1. Feistel 网络结构——FPE 的脊梁
Feistel 网络的设计思路非常优雅：把明文分成两半，每轮只处理一半，另一半原封不动。具体来说——
- 分割：输入数据切成左 (L0) 和右 (R0)，长度相等，都是 n/2 位。
- 轮迭代：第 i 轮，用轮函数 F 处理 Ri 和轮密钥 Ki，结果与 Li 异或，得到 Li+1；而 Ri+1 直接等于 Li。
- 交换：每轮结束后左右互换，下一轮继续。
- 解密：完全一样的结构，只是轮密钥逆序。你不需要实现 F 的逆函数。
我最初学密码学时，觉得 Feistel 绕来绕去很麻烦。但真正写代码才发现——可逆性这个特性简直是天赐的。你想想，F 可以是一个复杂的哈希函数，可以有非线性、有截断，反正解密时根本不需要把它反过来。这就是为什么 FPE 几乎清一色选 Feistel。
工程要点：Feistel 的轮数直接影响安全性。对于 64 位块，至少需要 3 轮才能达到伪随机性，4 轮可达超伪随机。我建议至少用 8 轮，工程上一般 10-16 轮。
2. 伪随机置换 (PRP)——FPE 要扣的帽子
FPE 的本质，就是在特定字符集上构造一个伪随机置换。什么是伪随机置换？输入和输出长度相同，且没有人能区分它是真随机还是构造出来的。
拿银行卡 CVV 来说：3 位数字，共 1000 种可能。我们需要一个一一映射，把 000~999 映射到新的 000~999，而且映射关系看起来像随机的。这就是一个 PRP 在 {0..999} 上的应用。
为何非要叫"伪随机"？因为真正的随机置换需要存一个巨大的查找表，不现实。我们用 Feistel + 底层分组密码（如 AES）来模拟随机性。底层密码的伪随机性传递给 Feistel，最终整个结构在特定域上表现像个黑盒置换。
| 概念 | 说明 | 在 FPE 中的体现 |
|---|---|---|
| PRP | 确定性的可逆映射，长度不变 | 加密前后数据格式完全一致 |
| 强 PRP | 即使攻击者可以同时查询加密/解密，依然不可区分 | 需要至少 4 轮 Feistel |
| 安全参数 | 轮数、块大小、轮函数强度 | 工程上轮数 ≥ 8，块大小≥ 64 位 |
注意：如果你的域不是 2^n 形式（比如数字 0-9），直接套 Feistel 会出问题。我曾经在项目中直接拿 16 位数字做 64 位块处理，结果加密后的数字可能超出 16 位范围。必须用循环行走或保留进位等技术修正。
3. Round 函数设计——灵魂在哪？
Round 函数 F 是整个 Feistel 网络中最容易出岔子的地方。它的输入是右半部分（某轮）和该轮密钥，输出一个与左半部分等长的伪随机位串。
最常见的做法：
- 把右半部分和轮密钥拼起来，用 AES 或其他分组密码加密一个块。
- 如果输出长度大于左半部分，就截断；如果小于，就填充或多次迭代。
- 轮密钥一般通过主密钥派生（KDF）生成，每轮不同。
这里有个坑：截断时丢失的位数会影响安全边界。我踩过一次，由于截断太多，导致有效轮函数输出只有原计划的一半，安全性大打折扣。后来我的习惯是：保留至少左半部分长度 + 16 位的随机性。
# 简化示例：Feistel 加密数字字符串（16 位数字）
def feistel_encrypt(plain_text, keys):
# 假设 plain_text 已经转为 64 位整数
L = plain_text >> 32
R = plain_text & 0xFFFFFFFF
for i in range(8):
# Round 函数：用 AES 加密 (R || keys[i])，取低 32 位
f_input = (R << 32) | keys[i]
f_output = aes_block_encrypt(f_input) & 0xFFFFFFFF
new_L = R
new_R = L ^ f_output
L, R = new_L, new_R
return (L << 32) | R
def feistel_decrypt(cipher_text, keys):
L = cipher_text >> 32
R = cipher_text & 0xFFFFFFFF
for i in reversed(range(8)):
f_input = (L << 32) | keys[i] # 注意使用新的 L（原 R）
f_output = aes_block_encrypt(f_input) & 0xFFFFFFFF
new_R = L
new_L = R ^ f_output
L, R = new_L, new_R
return (L << 32) | R
我的技巧：如果域不是 2 的幂，加密后需要检测输出的值是否仍在域内。不在则重新加密（循环行走）。但循环行走次数有上限，我一般设置最大 100 次，超过则报错。实测 16 位数字下很少超过 3 次。
最后聊两句轮函数的安全性。底层 AES 足够安全，但 Feistel 的轮数太少会让密钥恢复攻击变容易。我记得有一篇指出，3 轮 Feistel 在已知明文攻击下只需要 2^32 的复杂度就能恢复密钥。所以别再问“3 轮够不够”了——至少 8 轮起步。