第3章 FPE核心原理：Feistel网络结构

说白了，Feistel网络就是那个让密码学变得更「实用」的设计。我刚开始研究FPE时，第一反应也是：怎么把AES那种大黑盒子，缩到能处理手机号、身份证这种短数据？答案就是Feistel。

你想想看，传统的分组密码像AES，输入128位输出128位。可我们的信用卡号只有16位十进制数，约53位二进制。硬套AES？数据长度不匹配，格式也乱了。Feistel网络刚好能解决这个痛点——它不对整个数据块做一次变换，而是把数据切成两半，来回折腾。

一个核心思想：Feistel网络能保证加密和解密是同一个结构，只是密钥顺序反过来。这意味着你只要写一套加解密逻辑，不需要为解密单独写逆向函数。

3.1 Feistel网络的基本结构

Feistel网络把输入数据分成左右两半：L0和R0。然后经过多轮迭代，每一轮做三件事：

  1. 把右半Ri送进一个轮函数F
  2. 把F的输出和左半Li做异或
  3. 左右交换，进入下一轮

公式很简洁：

L(i+1) = R(i)
R(i+1) = L(i) ⊕ F(R(i), K(i))

我记得刚开始实现FPE时，总在纠结要不要做最后一轮交换。后来发现，如果最后一轮不做交换，那加密和解密就完美对称了。很多开源库的FPE实现，最后一步是「不交换」的。

我的习惯：标准的Feistel网络最后一轮不做左右交换。这样解密时只需要把密钥顺序倒过来，逻辑一模一样。

3.2 为什么FPE选Feistel？

原因其实很简单：格式保持。Feistel网络输入和输出的位数完全一样，不膨胀，不缩小。AES那种SPN结构，一旦输出长度变了，格式就毁了。

举个例子，如果我的数据是8位数字，那经过Feistel后还是8位数字。不会偶尔冒出字母或符号来。这在金融系统里是刚需——你见过一个含大写字母的银行卡号吗？

特性 Feistel网络 AES (SPN)
输入输出长度 严格一致 固定128位
加解密结构 完全相同 需要逆向
适用于短数据 是（如8位数字） 否（数据太短不安全）
轮函数复杂度 可调（轻量到AES级） 固定高复杂度

「那我用AES做轮函数行不行？」当然行。实际上你在FPE的轮函数里塞一个AES，那安全性就直接对标AES了。FF1标准就是这么干的——它用AES或SM4来做轮函数。

3.3 轮函数设计——这才是灵魂

Feistel网络的安全性，80%靠轮函数。我在项目中见过不少人，套了个Feistel壳子就觉得安全了，结果轮函数写了个简单的XOR……

我当时帮一个支付公司做脱敏方案，他们自己写了个FPE，轮函数就是Ri XOR Ki。结果呢？加密后的数据还能看出明显的统计特征——开头几位数字频率分布跟原数据一模一样。这就是轮函数太弱，扩散性不够。

避坑指南：我曾经见过一个案例，轮函数只用了简单的哈希截断，导致至少3对不同的输入加密后产生了相同的密文。这就是分组长度太短+轮函数设计不当的典型后果。在FPE里，每轮必须把右半部分充分「搅乱」。

设计轮函数时，这几个点我建议你注意：

  • 足够的非线性：纯线性运算，比如只做XOR，很容易被差分攻击破解。最好用S-box或分组密码。
  • 良好的雪崩效应：输入的1位变化，应该让输出一半以上的位都翻转。AES做轮函数时这一点就特别好。
  • 轮函数输出长度 = 左半数据长度：这样才能和左半部分做XOR。比如数据是8字节，左右各4字节，那轮函数输出必须是4字节。
  • 每轮不同密钥：千万别所有轮用同一个K。FF1标准里是先用KDF（密钥派生函数）生成多轮密钥。
// FPE轮函数的伪代码思路（用AES做底层）
uint8_t* round_function(uint8_t* right_half, uint8_t* round_key) {
    // 1. 将右半部分扩展/补齐到16字节（AES的块大小）
    uint8_t padded[16] = {0};
    memcpy(padded, right_half, len(right_half));
    
    // 2. 用AES加密
    AES_encrypt(padded, round_key);
    
    // 3. 截断到左半部分的长度并返回
    return truncate(padded, left_length);
}

我的经验：在FPE中，轮函数使用的密钥要由主密钥通过KDF派生。我习惯用HKDF，每次生成64字节，然后按轮次切分。这样每轮密钥都是独立的，安全性更高。

3.4 加密与解密流程

加密和解密在Feistel里真的是「孪生兄弟」。解密就是把加密的密钥顺序倒过来，流程完全一样。这在实际工程里太香了——嵌入式设备、智能卡这种资源受限的场景，你可以复用同一套代码。

加密流程（以10轮为例）：

  1. 输入数据分成左右两半：L0, R0
  2. for i = 0 to 9:
    • 计算 F = round_function(Ri, Ki)
    • 新左 = Ri
    • 新右 = Li XOR F
  3. 输出：合并L10和R10（注意：最后一轮不交换）

解密流程：

  1. 输入密文分成L10, R10
  2. for i = 9 to 0:
    • 计算 F = round_function(Li+1, Ki)
    • 新右 = Li+1
    • 新左 = Ri+1 XOR F
  3. 输出：合并L0和R0

看明白了吗？加密和解密用的是同一个round_function，密钥也是同一套，只是遍历方向相反。这就是Feistel最优雅的地方。

我举个更直观的例子。假设我们要加密一个4位数字「3528」，左右各2位：

  • L0 = 35, R0 = 28
  • 第1轮：F(28, K0) = 62, 新L = 28, 新R = 35 XOR 62 = 85
  • 第2轮：F(85, K1) = 14, 新L = 85, 新R = 28 XOR 14 = 42
  • 最终密文：8542

解密时从8542开始，反向运行密钥，一步不差地回到3528。

Feistel网络加密与解密流程图 Feistel网络加密流程（一轮展开） 输入平文 (P) 左半 L₀ 右半 R₀ 轮函数 F 密钥K₀ ⊕ 新右半 R₁ 新左半 L₁ (=R₀) 密文 (C) = 合并L₁R₁ 解密时只需反向遍历密钥，保持轮函数和XOR结构完全不变

一句话总结：Feistel网络用左右分治+每轮异或，让加密和解密共用同一套轮函数。你只需正向设计，反向自然就解密了。这对FPE来说，简直是天作之合。

3.5 实际项目中的选择

我做过几个FPE项目，总结下来几点：

  • 数据长度8字节以内 → 用8轮Feistel+RFC 标准轮函数
  • 数据长度8-16字节 → 用10轮，轮函数内置AES加密
  • 超过16字节 → 考虑用FF3或直接拆分成多个块分别处理

另外，轮数不是越多越好。我记得有一次测试，从10轮加到14轮，安全性增益不到5%，但性能掉了30%。所以实际项目中，我一般卡在8-10轮。

注意：在FPE中，Feistel网络只能处理偶数长度的数据（因为要分左右两半）。如果数据是奇数位怎么办？比如11位手机号。我通常的做法是：先补1位到偶数位，加密完成后再去掉补位。这1位补什么？补「0」或特殊标记位，保证解密后能识别并移除。

Feistel网络其实不复杂。它的精髓在于「分而治之」——把一个大问题拆成两个小问题，每轮只处理一半，迭代足够多次后，整体就变得安全了。你如果之前用过分组密码，会发现Feistel的思路与之类似，但灵活得多。

← 上一章 📖 返回目录 下一章 →