保留格式加密（FPE）算法原理：从 Feistel 构造到 NIST SP 800-38G 标准

概述

在数据库密评合规改造中，一个让人头疼的问题是：传统分组密码（如 SM4-CBC）加密后密文长度膨胀，需要修改数据库字段类型或增加额外列来存储密文和初始化向量。对于信用卡号、身份证号、手机号等已经定长的字段，这种"格式破坏"意味着：数据库表结构要改、索引要重建、业务代码要适配、历史数据要迁移——成本巨大。

保留格式加密（Format-Preserving Encryption, FPE） 正是为了解决这个问题而生。FPE 是一类特殊的对称加密算法，其核心特征是：密文与明文具有相同的长度、字符类型和格式约束。加密一张 16 位信用卡号，输出仍然是 16 位数字；加密一个身份证号，输出仍然是 18 位数字（末位可作 X）。这种"格式透明"特性让 FPE 成为数据库字段级加密的最优解决方案，也是国密改造中数据保护的关键技术路径。

FPE 的研究始于 20 世纪 80 年代，经过约 40 年发展，已从基本算法探索演进到标准化应用阶段。2016 年美国 NIST 发布 SP 800-38G，定义了 FF1 和 FF3 两种 FPE 工作模式（后经修订为 FF3-1），FPE 从此进入标准化、工程化的成熟阶段。在中国，FPE 虽然没有独立的国家标准，但已在金融 IC 卡、政企数据脱敏、数据库字段加密等场景中得到广泛应用。

FPE 的形式化定义与安全性要求

基本定义

一个 FPE 算法定义在有限消息空间 $\mathcal{M}$ 上，加密和解密是一对置换（Permutation）：

$$E_K: \mathcal{M} \rightleftarrows \mathcal{M}: D_K$$

即对于同一密钥 $K$，$D_K(E_K(X)) = X$，且 $E_K$ 是 $\mathcal{M}$ 上的双射。

消息空间 $\mathcal{M}$ 可以是：

• 整数集：$\{0, 1, 2, \dots, n-1\}$，如 $\{0, \dots, 10^{16}-1\}$ 对应 16 位信用卡号
• 字符串集：长度为 $L$ 的字母数字串，如 [A-Za-z0-9]^10
• 结构化数据：符合 Luhn 校验的身份证号、符合特定日期格式的日期串等

安全性要求

多目标 CPA 安全（Multi-target CPA Security）：当允许攻击者选择明文时，FPE 的安全性直观假设是：对于不同消息 $m_1, m_2$，如果密文 $c_1 = E_K(m_1)$ 和 $c_2 = E_K(m_2)$ 看起来像是随机排列，那么攻击者无法从密文推断明文。

用伪形式化描述，考虑 PRP 优势（Pseudo-Random Permutation advantage）：

$$\text{Adv}_{FPE}^{PRP}(A) = \left| \Pr[A^{E_K(\cdot)}(1^n) = 1] - \Pr[A^{P(\cdot)}(1^n) = 1] \right| \leq \epsilon(n)$$

其中 $P$ 是真随机置换。

对于小的消息空间（如只有 $N = 10^6$ 个可能值），这种安全性非常有限——攻击者穷举所有明文并比对密文即可恢复密钥。因此 FPE 的安全使用通常需要满足 |M| > $2^{40}$。

三大基本构造方法

所有 FPE 算法都可以追溯到三种基本构造方法：

#### 1. Prefix 方法

对可能消息 $m \in \{0, \dots, n-1\}$，计算 $y_i = F_K(m \| i)$（$i = 0, 1, 2, \dots$），输出第一个落在目标范围的 $y_i$：

def prefix_encrypt(m, n, K):
    for i in range(2^32):
        y = F_K(int_to_bytes(m * 2^32 + i))
        if y < n:
            return y

该方法的优点是简单，但缺点是性能不可预测——当 $n$ 远小于分组密码域时需要大量迭代。

#### 2. Cycle-Walking 方法

先按分组密码加密，如果输出落在目标范围内则输出；否则对输出再次加密，直到输出落在目标范围内：

def cycle_walking_encrypt(m, n, K):
    c = block_encrypt(m, K)
    while c >= n:
        c = block_encrypt(c, K)
    return c

形象称为"绕圈行走"——当目标范围接近分组密码域时，期望迭代次数接近 1（效率最优）；当目标范围远小于分组密码域时，迭代次数可能非常多（效率极差）。

#### 3. Generalized-Feistel 方法

这是目前应用最广的构造方法，核心思想是将经典 Feistel 网络从 2 分支扩展到多分支，将目标空间划分成多个子域分别处理。

设消息空间大小为 $n$，分解 $n = n_1 \times n_2 \times \dots \times n_m$。对于输入 $(x_1, x_2, \dots, x_m)$，每轮：

$$y_{m} = F_K(i \| x_1 \| x_2 \| \dots \| x_{m-1}) \pmod{n_m}$$ $$x_m' = (x_m + y_m) \pmod{n_m}$$

通常使用 4-6 轮实现足够的安全性。Generalized-Feistel 是 FF1、FF3 等标准的基础。

NIST SP 800-38G 标准模式

FF1：Feistel-based FPE

FF1 由 NIST 在 SP 800-38G（2016 年）中发布，基于平衡 Feistel 网络，支持任意大小的消息空间 ($2 \leq |\mathcal{M}| \leq 2^{128}$)。

加密过程：设字符串长度为 $n$（十进制数字）、radix（数字表大小 $\leq 256$），分为左右两部分 $(A, B)$，执行 10 轮 Feistel 变换：

function FF1.Encrypt(K, T, X):
    n = length(X)
    u = floor(n/2); v = n - u
    A = X[0:u]; B = X[u:n]
    b = ceil(ceil(v * log_2(radix)) / 8)
    d = 4 * ceil(b/4) + 4
    for i in 0..7:
        P = [1] || [2] || [1] || 0^{96}[256] || 0^{radixbits} || 0^{48} || [n] || [t] || 0^{b*8}
        mod_radix_B = PRF(K, P || rev(B)) mod radix^u
        if i is even: C = (A + mod_radix_B) mod radix^u
        if i is odd:  C = (A + mod_radix_B) mod radix^v
        A = B; B = C
    return A || B

其中 $T$ 是 tweak（可选关联参数，使同一明文在不同 tweak 下获得不同密文）。

FF1 使用 AES-128/192/256 作为底层 PRF（伪随机函数），目前已扩展支持 SM4 的变体由多家厂商实现。

FF3-1：提高平衡 Feistel

FF3 原始版本（2016）被发现存在小域安全性问题——当域 $|X| \leq (\log_{|\mathcal{M}|} 2)^8$ 时，可能泄露密钥信息。NIST 在 SP 800-38G Rev.1（2019 年）中发布 FF3-1 修正：

• 保持 8 轮
• 调整 Feistel 左右分界点的选择逻辑（round num 决定左右偏移）
• 增加了对 tweak 长度的限制

function FF3-1.Encrypt(K, T, X):
    n = length(X); u = ceil(n/2); v = n - u
    A = X[0:u]; B = X[u:n]
    T_L = T[0:32]; T_R = T[32:56]
    for i in 0..7:
        m = (i is even) ? u : v
        P = T_(i mod 2) || 0^5 || [i] || rev(num_to_bytes(rev(B), b))
        W = T_(i+1 mod 2) XOR truncate(AES(K, P), 8)
        rev_C = (rev(A) + bytes_to_num(W)) mod 10^v
        A = B; B = rev(rev(C))
    return A || B

FF1 vs FF3-1 对比

FPE 在 SM4 国密场景中的适配

虽然 FF1 和 FF3-1 规定使用 AES 作为底层 PRF，但在国密合规场景下需要将 AES 替换为 SM4：

# SM4-FF1 概念示意
def sm4_ff1_encrypt(K, T, X):
    # 用 SM4 替代 AES 作为底层分组密码
    # 其余结构（Feistel、轮数、rebalancing）保持相同
    PRF = sm4_cbc_mac  # 使用 SM4 的 CBC-MAC 模式作为 PRF
    # ... 与 FF1 相同的 Feistel 结构

适配注意事项：

• 底层分组密码选择：SM4 是 128 位分组密码，频宽与 AES 相同，可以直接替换。但 NIST SP 800-38G 的测试向量基于 AES，SM4 需要重新生成测试向量以验证正确性。

• 密钥长度：SM4 固定 128 位密钥；支持密钥派生（KDF）从主密钥派生子密钥。

• Tweak 的工程含义：

• 性能考量：

核心安全分析

小域问题

FPE 的根本挑战是：有限域上的置换不可能完全伪随机。当域很小时（如只有 100 个值），攻击者可以：

• 收集足够多的明文-密文对
• 排除不可能的排列
• 利用统计方法推断密钥

• $|\mathcal{M}| \geq 2^{40}$（约 $10^{12}$）
• 收集明文-密文对远小于 $2^{80}$

完整性问题

FPE 算法仅提供机密性，不提供完整性——密文可以被篡改（例如两个密文互换），接收方无法检测。这意味着：

• 必须配合 AEAD 或 MAC：存储 FPE 密文时，建议额外存储 HMAC-SM3（或 SM4-GCM 的 auth tag）以验证完整性
• 数据库审计：密文字段仍需额外完整性列

与 AEAD 的对比

应用场景

1. 数据库字段级加密

信用卡号、身份证号、手机号、银行卡号——这些字段一旦被 FPE 加密，密文仍然是相同长度和格式的数值，对数据库 Schema 和业务代码的改造需求极小：

# 伪代码：SM4-FF1 字段加密示例
def encrypt_field(plaintext: str, master_key: bytes, field_name: str) -> str:
    """
    使用 SM4-FF1 加密字段
    - plaintext: 原始字段值（如 "6222021234567890"）
    - master_key: 主密钥
    - field_name: 字段名，用于派生 tweak
    """
    # derive field-specific key and tweak
    field_key = HKDF(master_key, salt=field_name.encode(), length=16)
    tweak = SM3(field_name.encode())[:8]  # tweak 用于区分不同字段
    
    # SM4-FF1 加密（细节略）
    ciphertext = sm4_ff1_encrypt(field_key, tweak, plaintext)
    return ciphertext  # 长度、格式与 plaintext 完全相同

2. 数据脱敏测试环境

使用 FPE 加密种子数据，密文看起来像真实数据（18 位数字、合法日期格式），既保护了敏感信息，又保持了数据的可读性（用于测试、开发环境）。

3. 金融 IC 卡行业

EMV 标准芯片的磁道数据（Track2）需要格式兼容加密。FPE 解决方案在发卡行加密数据后，保证数据长度不变（通常 37 位数字）。

FPE 标准的演进与国密标准化前路

国际标准

中国国密标准化现状

截至 2026 年，国密领域尚未发布独立的 FPE 国家标准，但以下动向值得关注：

• 海泰方圆等企业已推出具有自主知识产权的 FPE 产品，支持身份证号、手机号等多种格式自动识别加密。
• 金融行业标准：部分银行已在数据脱敏场景中使用类 FPE 方案，但缺乏统一标准。
• 国密迁移需求：随着等保 2.0 和密评要求深化，FPE 在数据库加密场景的合规使用需求强烈，预计国密标准化将提上日程。

工程实践中的常见错误

❌ 1. 将 FPE 当作 AEAD 使用

FPE 不提供完整性保护。如果攻击者可以直接操作数据库（如内部人员、备份泄露），可以互换两个密文、重放旧密文或构造格式正确但内容错的密文。

正确做法：在 FPE 密文之外，添加完整性校验（如 SM3-HMAC），将 computed_tag 和 stored_tag 分开存储。

❌ 2. 在小域上使用 FPE

小于 $2^{40}$ 的域（如 6 位随机数 PIN）在攻击者能收集足够多明密文对时，可以通过穷举分析恢复密钥。

正确做法：优先使用 AEAD 方案；或引入盐值（salt）辅助密钥派生以隔离每次加密。

❌ 3. 忽略 tweak 的设计

不同字段使用相同密钥时，如果不使用 tweak，相同明文会得到相同密文——等同于 ECB 模式，丢失数据格式。

正确做法：tweak = HMAC-SM3(master_key, table_name || column_name)[:8]，用 tweak 加扰区分不同字段。

❌ 4. 不记录主密钥元数据升级

未设计密钥轮换方案时，长期使用同一主密钥（如 5 年以上的密钥）会导致安全退化。

正确做法：在密文前添加版本号（如 v1$6222...），定期轮换主密钥并重新加密。

总结

保留格式加密（FPE）是现代密码学在"效率"与"格式约束"之间取得的平衡成果。从 Prefix 方法、Cycle-Walking 到 Generalized-Feistel，再到 NIST FF1/FF3-1 标准化，FPE 的实现越来越安全高效。在国密应用场景下，SM4 代替 AES 作为底层分组密码，可以实现兼顾合规与工程便利性的字段级加密方案。

FPE 不是万能药——它不提供完整性保护，小域性能差，可与 AEAD 方案互补使用。理解 FPE 的适用边界和安全约束，才能在国密改造中做出正确的技术选型决策。

参考来源

• NIST SP 800-38G: Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption (2016)
• NIST SP 800-38G Rev.1 (2020): FF3-1 修正版
• 保留格式加密技术及发展研究 — 安全内参
• 刘哲理等, "保留格式加密技术研究", 软件学报, 2012
• Rebellious FFF: A Differential Attack on FF3 (2017)
• FFEM: A Simple and Secure Feistel Scheme for Format-Preserving Encryption (2012)

相关实践

• SM4 国密算法实战：ECB/CBC/CTR/GCM 四种模式完整指南
• 国密 SM4 数据库字段级加密实战：MySQL 与 PostgreSQL 完整方案