4. Feistel网络：FPE算法的核心结构

聊到FPE，绕不开一个经典结构——Feistel网络。说实话，我刚开始接触FPE的时候，脑子里全是DES的影子。但实际用起来才发现，FPE里的Feistel已经被改造得面目全非了。今天咱们就把它拆开看看，到底哪些地方变了，哪些地方没变。

经典Feistel vs FPE中的Feistel

经典Feistel长什么样？你想想看，DES的每一步都是把数据切成左右两半，右半部分送进轮函数，输出和左半部分做XOR，然后交换左右位置。一轮完了再进下一轮。这个结构最妙的地方在于：加解密共用同一个轮函数，只是轮密钥顺序反过来。

但到了FPE里，情况变了。FPE处理的数据往往不是二进制位，而是数字、字母，甚至是一段电话号码。经典的DES块大小是64位，FPE的块可能只有16位，也可能大到128位。更关键的是，FPE必须保证输出的字符集和输入一致——你不能把数字变成了乱码字母。

我在做银行卡号令牌化项目时，就遇到了这个问题。卡号是纯数字，16位长度，如果直接套用DES，加密后变成二进制，再转成十进制，很可能出现前导零、首字母变成了字母。所以FPE的Feistel网络必须支持任意字符集，并且输出严格落在相同字符集内。

平衡与非平衡Feistel

经典Feistel是平衡的，左右两半长度相等。但在FPE里，有时候输入长度是奇数，就只能切成左半比右半长一位，或者相反。这就是非平衡Feistel（Unbalanced Feistel）。我建议你记住这个关键点：当字符集不是2的幂次时，几乎必然用到非平衡Feistel。

轮函数：FPE的灵魂

轮函数F是Feistel网络里唯一非线性的地方。经典DES的轮函数包含了S盒、扩展置换等，但FPE的轮函数通常基于分组密码（比如AES）或者哈希函数。

咱们拿FF1举个例子：每一轮，右半部分会和当前轮密钥一起，通过AES加密得到一个中间值，然后跟左半部分做某种形式的加法（在字符集范围内）。注意，这里不是二进制XOR，而是字符集内的模加。为什么？因为XOR只在二进制下是保结构的，对于十进制数字，你需要做“模10加法”。

说白了，就是把左右两半的数据当作整数，在模 radix 的运算下相加。这个radix就是字符集大小，比如数字是10，小写字母是26。

一个简单的Feistel实现（Python伪代码）

def feistel_round(L, R, K, radix):
    # 轮函数：用AES加密R和K，得到一个字节串
    temp = AES_encrypt(pad(R), K)
    # 将temp转换为整数，模radix
    f_output = bytes_to_int(temp) % radix
    # 左半部分和函数输出做模加
    new_L = (L + f_output) % radix
    # 交换左右
    return (R, new_L)

def feistel_encrypt(plaintext, rounds, radix, keys):
    # 假设plaintext已经分割为L和R
    L, R = plaintext
    for i in range(rounds):
        L, R = feistel_round(L, R, keys[i], radix)
    # 最后一轮通常不交换（或者交换，看标准）
    return L, R

注意：实际FF1/FF3还有额外的格式保留处理，比如对右半部分的长度调整、轮密钥生成等。上面这个代码只是为了展示Feistel的核心逻辑。

Feistel网络的一次迭代流程

下面这张SVG图展示了一次Feistel迭代的核心步骤。你可以看到左半L_i和右半R_i如何经过轮函数、模加、交换得到下一轮的L_i+1和R_i+1。