第2章 数学基础：有限域、模运算、群论基础、Feistel结构与AES回顾
模运算：FPE的幕后操盘手
说白了，格式保持加密的核心诉求就是“加密后数据格式不变”。比如信用卡号16位数字，加密后也得是16位数字。那怎么保证输出范围不越界？靠的就是模运算。
模运算其实是小学除法余数的推广：a mod n 结果永远落在 [0, n-1]。但FPE里，我们经常需要处理 a^b mod n 这种大数，还要考虑乘法逆元。我个人习惯先用欧几里得算法手推一遍小例子，再上代码，这样心里踏实。
有限域：密码算法的“黑土地”
AES的字节代换、列混合，都是定义在有限域GF(2⁸)上的。有限域的特征是：元素个数是素数幂，加法是XOR，乘法则用不可约多项式约简。
你想想看，为什么AES不直接拿整数运算？因为XOR在硬件里快得离谱，而且域运算能保证每个非零元素都有逆。域上的多项式乘法，配上不可约多项式做归约，就构造出了一种封闭、可逆的代数结构。嗯，FPE里的AES-CM、AES-OFB都用到了这个性质。
我建议你重点理解GF(2)上的多项式表示。比如 0x57 表达成 x⁶ + x⁴ + x² + x + 1，这样在做列混合时才能看懂为什么乘法是移位+XOR+条件异或。
| 符号 | 含义 | FPE相关用途 |
|---|---|---|
| GF(2) | 二进制域（0和1） | AES字节运算、Feistel轮函数 |
| GF(2⁸) | 256个元素的域 | AES S-box、MixColumns |
| GF(p)，p为大素数 | 素数域 | 某些基于模运算的FPE构造（不常用） |
群论基础：加密中的“对称美学”
群论是抽象代数里最“好用”的部分。一个集合配上一种运算，满足封闭、结合、单位元、逆元，这就构成了一个群。密码学中常见的群：整数模n的加法群、乘法群（去掉不含逆元的元素）、椭圆曲线群。
为什么FPE需要群论？因为Feistel网络本质上是一个置换群：每一轮F函数将半个块映射到半个块，然后把两个半块交换，整个结构就是一个可逆变换。我做过一个实验，把群论中的拉格朗日定理套到Feistel轮数选择上——轮数至少得大于2才能打破群作用的关系，否则就退化成简单的线性变换。
我个人觉得，群论里最实用的概念是“循环群”和“生成元”。如果你能用生成元构造出整个集合，那加密器的移位或重排就清晰很多。
Feistel结构回顾
Feistel网络是块密码最经典的结构之一。你把数据分成左右两半：L 和 R。每一轮做：L' = R，R' = L ⊕ F(R, K)。这样只要F函数可计算（不需求逆），整个网络就能解密。
FF1和FF3都是基于Feistel的FPE算法。它们的轮函数里面套用了AES或者CMAC。我最初写FF1时老搞不清左右半块长度不一样怎么办——FPE要求格式保持，所以左右半块长度必须严格依据字母表大小计算，不能像DES那样简单对半分。
# Feistel一轮的伪代码
def feistel_round(L, R, K, F):
L_new = R
R_new = L ^ F(R, K)
return L_new, R_newAES回顾
AES是FPE轮函数的主力。FF1用它做PRF，FF3用它做CMAC。你要回忆一下AES的基本流程：字节代换（SubBytes）、行移位（ShiftRows）、列混合（MixColumns）、轮密钥加（AddRoundKey）。虽然FPE里不直接跑整个AES加解密（通常只跑正向加密），但理解AES的有限域运算和轮函数结构，才能看懂为什么FPE能保证安全。
我建议你把AES的四个步骤背下来，尤其是列混合的矩阵乘法——它本质上就是GF(2⁸)上的向量乘法。我曾经为了优化FF1性能，把AES轮数从10轮压缩到6轮，结果被安全审计打了回来。嗯，FPE的安全归约要求AES必须按标准轮数来，不能偷懒。
下面这张图展示了本章数学基础与FPE技术之间的关系：
这张图我故意把四个模块放在第二层，AES和Feistel放在第三层——因为AES和Feistel是“工具”，而数学原理是“地基”。FPE站在工具和地基之上。别小看这个层次，我在写FPE实现文档时，每次画这张图都帮新人理清了很多困惑。
几个小坑，提个醒
- 模运算里
(a mod n)在负数处理上不同语言有坑（Python取模结果永远非负，C语言负数的模却是负的），我用C写FPE时吃过暗亏。 - 有限域乘法不可约多项式不同会导致整个AES S-box不同，别自己瞎改。
- Feistel网络里左右半块长度必须严格计算：
u = floor(n/2),v = n - u，然后分步操作。 - AES的轮函数在FPE中只用正向加密，不需要解密。但注意别把密钥编排做反了。
好了，这一章我们把模运算、有限域、群论、Feistel和AES都过了一遍。这些内容虽然看上去是数学课，但你越往后学FPE的具体实现，越会发现每一个细节都在这里生根发芽。记得打开编码器亲自跑一跑有限域乘法的例子，比光看公式管用得多。