FF1 算法数学基础：Feistel 网络与平衡归纳总结
说实话，刚开始研究 FF1 的时候，我总觉得它绕不开 Feistel 网络这个老骨架。这个结构最早在 DES 里就用了，到现在还在 Format-Preserving Encryption 里发光发热。你想想看，一个几十年的设计，凭啥还能成为新标准的基础？
我个人习惯把 Feistel 网络理解成一个“左右互搏”的接力赛。每一轮只改一半数据，另一半直接传递。这样既保证了可逆性，又降低了实现复杂度。FF1 正是基于这种思想，只是它要求左右两半必须严格对称——也就是所谓“平衡 Feistel”。
什么是 Feistel 网络？
Feistel 网络把一个固定长度的分组切成两半：左半 L、右半 R。然后重复多轮，每轮只用一个密钥控制的函数 F 去改造右半，再与左半异或，最后左右交换。核心公式很简单：
对于第 i 轮：
L_i = R_{i-1}
R_i = L_{i-1} ⊕ F(R_{i-1}, K_i)我在学 DES 那会儿，总觉得这个设计很聪明——解密时只要把密钥顺序反过来就行，不用单独写逆运算。嗯，后来做 FF1 测试时，又重温了一遍这个感觉。
但 FF1 有个特殊要求：它要保留明文的格式，比如纯数字、电话号码或信用卡号。这就意味着分组长度不能是传统 64 或 128 位的 2 次幂，而是任意偶数长度的字符串。Feistel 网络天然支持这种变长输入，只要左右等长就行。
平衡 vs 非平衡：为什么 FF1 必须走平衡路线？
非平衡 Feistel 在很多场景下也有用，比如一些轻量级密码。但 FF1 的标准规定死了——每轮的左右两部分长度必须完全相等。我把差异列个表，方便对比：
| 特性 | 平衡 Feistel | 非平衡 Feistel |
|---|---|---|
| 左右半长度 | 相等（len(L) = len(R)） | 可以不等 |
| 轮函数输入输出 | 输出长度等于右半长度 | 输出长度可能不等于右半 |
| 可逆性 | 严格对称，解密简单 | 需额外处理左右拼接 |
| FF1 适用性 | 必须，否则格式保留失败 | 不适用 |
| 典型应用 | DES、FF1、FF3 | 部分轻量级算法 |
平衡要求到底有多重要？我举个例子：如果一个 10 位数字的分组（比如 1234567890），按平衡 Feistel 分割，左 5 位右 5 位。每轮只修改右边 5 位，左边直接传过去。如果左右不等，比如左 6 右 4，处理输出时会破坏数字长度约束，密文就可能出现非数字字符。这就是格式保留倒塌的直接原因。
平衡归纳：从数论到工程
平衡 Feistel 的数学本质是什么？说白了就是“可逆置换的分治策略”。把一个 n 位的置换，拆成两个 n/2 位的置换，然后用密钥控制的函数 F 来连接它们。这个 F 不一定要可逆，但必须能把 n/2 位映射到 n/2 位。
我在第一次实现 FF1 时，踩过一个坑：轮数的选择。标准推荐最少 10 轮，我贪快只设了 8 轮，结果测试向量死活对不上。后来才意识到，平衡 Feistel 的轮数直接决定安全性。10 轮是 NIST 给出的安全下界。
另一个容易忽略的点是“平衡分割”。对于奇数长度分组，FF1 加了个小技巧：在加密前先对分组长度做“保持长度”的 padding？不对，FF1 要求分组长度必须为偶数，否则不能直接用平衡 Feistel。实际处理中，小于 2 的分组根本不允许单独加密。
⚠ 我曾经犯过的错：测试时输入了一个 7 位数字，系统没有报错，但输出总是稀疏的字母混合结果。排查两天才发现是分组长度检查没做，代码自动把 7 位拆成了左 4 右 3 的非平衡结构，格式完全丢失。记住：FF1 的分组长度必须是大于或等于 2 的偶数。
Feistel 网络结构图
下面这张 SVG 图把一轮平衡 Feistel 的过程画清楚了。注意左右半等长，轮函数只作用在右半，异或结果直接取代左半。下一轮再交换。
⋆ 核心归纳：平衡 Feistel 的本质是“各改一半，再交换”。FF1 通过强制左右等长，确保了任意偶数长度分组的格式保留。轮函数 F 不需要可逆，但必须能接受 n/2 位输入并输出 n/2 位，通常用 AES 或 CMAC 实现。
轮函数与平衡的互动：我的一点实战体会
做 FF1 参数配置时，我最怕的是轮函数设计。标准里推荐用 AES 作为底层的 F，但 AES 的输入是 128 位，如果 n/2 小于 128 位怎么办？它内部会做 padding？其实 FF1 规范规定了一种叫“PRF”的构造方式：先用 CSPRNG 把小块数据扩展到 AES 需要的长度，再把输出截断回 n/2 位。这个过程中，平衡性不能断，否则一截就丢了半个字节的语义。
我记得第一次按照 NIST SP 800-38G 写代码时，在“Ciphertext Stealing”那部分卡了两天。后来发现是自己把 Feistel 左右边界算反了——左半应该是输入明文的前一半，右半是后一半，但字符串切分时索引搞混了，导致密文总是差一个字符。说白了，平衡 Feistel 的工程实现里，程序员最容易犯的错就是“左右不分”。
💡 我的测试小技巧：写一个已知向量的单元测试，比如输入 0x00 00 00 00 00 00（6 字节，平衡后左 3 右 3），用标准库的值比对比对。如果第一轮后的左右两个半块输出与标准一致，那么 Feistel 结构基本就对了。
平衡性的数学保护：一种散列思维
可能有同学问：Feistel 网络里，左右等长到底保护了什么？我用一个最直白的比喻：你有一个 10 位的数字串，加密后必须还是 10 位的数字串。Feistel 每轮只改其中 5 位，那 5 位改完后怎么保证仍然全是数字？这就要靠轮函数 F 的输出必须是“格式保真”的——比如输出也被限制在数字字符的编码空间内。FF1 的做法是：先把这 5 位当成一个整数，用 AES 加密后再取模保留在 10^5 范围内。这个过程天然依赖平衡分割，因为左右等长才能用同一个模数。
所以，平衡 Feistel 不仅仅是一个结构选择，它直接决定了实现方案：左半和右半可以共用同一套格式映射逻辑。我用 FF1 加密信用卡号时，16 位卡号拆成两个 8 位的子串，每轮只改右 8 位，前 8 位直接传递，下一轮交换后再改另一半。8 轮之后，整个字符串就彻底混淆了，但每个字符仍然是数字。
总结性的个人念叨
如果你看过 DES，再看 FF1 的 Feistel 网络，会觉得很亲切。但真正的坑往往藏在平衡性这个细节里。我现在做安全审计，拿到一个新算法，第一件事就是看它的 Feistel 网络是平衡还是非平衡。如果是平衡的，再检查左右半长度是否严格相等。如果不是，十有八九会出格式保留的兼容性 bug。
嗯，平衡归纳很重要，但别忘了实际编码时的边界检查。我曾经在线上环境遇到过一个问题：输入分组长度恰好为 128 位（偶数），但内部把 128 位按字节拆成左 8 字节右 8 字节，结果因为字节序问题，左右半搞反了，输出乱了一串。后来加了个端序检测才修复。所以啊，理论讲起来清爽，做起来总得绕几个弯。