FPE

定义

FPE（Format-Preserving Encryption，格式保留加密，也称为保形加密）是一种特殊的对称加密算法。FPE可以保证加密后的密文格式与加密前的明文格式完全相同。例如这样：

FPE加密前后格式完全相同，而直接使用AES的其他模式达不到此种效果。

FPE使用场景

格式保留加密常用于数据脱敏，可以对敏感数据(如手机号码，银行卡号等)进行加密存储，可以有效降低黑客入侵导致敏感信息泄露。另外，由于FPE可以保持加密后数据的格式不变，在一定程度上可以替代传统基于掩码的数据遮蔽方案。

FPE特征

• 数据长度不变。加密前长度是N，加密后长度仍然是N
• 数据类型不变，加密前是数字类型，加密后仍然是数字类型。
• 加密过程可逆，加密后的数据可以通过密钥解密还原原始数据。

需要注意：

• 数据必须能被确定加密。如对数据库中作为索引值字段的数据加密，加密后保留其所在列索引值的特性。
• 对于短明文数据，安全性不会降低。

FPE 发展历史

学术界关于格式保留加密的研究已经持续多年，2002年，Black 和 Rogaway 提出了 3 种 FPE 构建方法：Prefix, Cycle-Walking 和 Generalized-Feistel。

这 3 种方法成为构造 FPE 模型的基本方法。Generalized-Feistel方法的适用性更为广泛，其核心思路是基于 Feistel 网络来构建符合整数集大小的分组密码，并结合 Cycle-Walking 方法使最终密文输出在合理范围内。Feistel 网络可以通过定义分组大小、密钥长度、轮次数、子密钥生成、轮函数等来构造一个分组密码，其主要流程如下图所示：

其加密算法逻辑如下：

令 F 为轮函数；令 K1，K2，……，Kn 分别为第 1，2，……，n 轮的子密钥。那么 Feistel 加密过程如下：

1. 将明文信息均分为两块：（L0, R0）；
2. 在每一轮中，进行如下运算（i为当前轮数）：

   Li+1= Ri；
   Ri+1= Li⊕F（Ri,Ki）。（其中⊕为异或操作）

3. 所得的结果即为：(Ri+1，Li+1)。

其解密算法逻辑如下：

对于密文（Rn+1,Ln+1），我们将 i 由 n 向 0 进行，即 i=n，n-1，……，0。然后对密文进行加密的逆向操作，如下：

1. Ri = Li+1；
2. Li = Ri+1⊕ F（Li+1,Ki）。（其中⊕为异或操作）
3. 所得结果为（L0,R0），即原来的明文信息。

FPE 发展历史 FF1

为了进一步规范 FPE 的实施，美国国家标准与技术研究院（National Institute ofStandards and Technology,NIST）针对 FPE 发布了标准草案 SP800-38G，并给出了 3 种具体的加密算法：FF1、FF2 及 FF3。

这些算法的主体流程是类似的，其核心均为 Feistel 网络结构。其中:

• FF2 被设计出来的时候不满足期望的 128bit 的安全强度被弃用。
• FF3 算法存在安全漏洞已于 2019 年 2 月更新为 FF3-1，见 SP800-38G Rev1。
• FF1 和 FF3-1 算法均以 128bit AES 为底层算法，在 AES 算法的基础上实现线性变换，FF1 经过 10 轮迭代，FF3 经过 8 轮迭代。因此 FF3 的性能高于 FF1，但 FF1 的安全性更高。从安全角度出发推荐利用 FF1 算法来实现 FPE。

FF1 算法简介

下面重点介绍 FF1 算法的使用方法和应用场景，关于该算法的安全证明和实现细节可以参阅 NISTSP800-38G（连接在reference）。另外可以在 Github 上找到 FF1 的开源实现，例如 Java 版本的、Golang 版本等；

实现 FF1 算法之前需要先了解该算法的一些基本概念和定义：

• Alphabet： 有限字母的字典表，并规定了输出密文的范围，例如对于手机号码而言，是十进制纯数字格式的，其Alphabet包括字符’0’-‘9’。对于MAC地址而言，是十六进制数字格式，其Alphabet应该包括大写英文字母的’A’-‘E’和数字’0’-‘9’在内的十六个字母。
• Character： Alphabet中的每一个字母称之为Character。
• Radix： Alphabet中字母的个数总和，或者说Alphabet数组的长度。对于仅包含26个小写英文字母的Alphabet而言，其Radix=26。
• Key： 加密密钥，由于FF1是一种对称加密算法，其加密密钥和解密密钥都是相同的。FF1算法中Key长度必须是16bit、24bit和32bit三种中的一种。
• Tweak： 对于FF1算法来说Tweak是一个重要的概念，相当于第二密钥，可以和Key相互配合完成加密操作。例如，将FF1算法应用在手机号码FPE加密中的话，如果我们仅仅加密中间4位，前3位和后4位保持不变。中间4位数字会产生1万种可能。对于有着1百万条手机号码记录来说，大概每100张会有相同的中间4位数字，也就是对于不同的明文FPE加密结果是相同。这种情况下，我们可以把手机号码的前3位和后4位作为tweak，然后再把中间4位加密，那么其结果相同的概率就会大大降低。

FF1 算法使用流程如下：

1. 设计 Alphabet 字典表。例如手机号、银行卡号等字段可以采用数字字母字典表（’0’-‘9’），对于英文姓名等采用英文字母字典表（小写字母’a’-‘z’、大写字母’A’-‘Z’），对于 Mac 地址、IMEI 等可以采用十六进制数字字母字典表（’0’-‘9’和’A’-‘E’）；
2. 设计 Tweak 取值。Tweak 是为了解决因局部加密而导致结果冲突问题，通常情况下将数据的不可变部分作为 Tweak。例如对手机号码 FPE 而言，可以将手机号码的前3位和后4位联合起来当做 Tweak，将把中间 4 位通过 FPE 加密。
3. 设计 Key。对于 FPE 而言 Key 的长度必须是 16bit、24bit 和 32bit 三种中的一种。另外 Key 是一个秘密需要妥善保存。在不需要解密的情况下 key 可以随机选择，这样可以获取更高的安全性。
4. 构造 FPE 算法对数据进行加密和解密操作。

Reference

文献

• https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-38G.pdf
• https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-38Gr1-draft.pdf
• https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/examples/FF1samples.pdf
• EVALUATION OF FORMATPRESERVING ENCRYPTION ALGORITHMS FOR CRITICAL INFRASTRUCTURE PROTECTION
• 保留格式加密模型研究
• default.pdf

实现

• Golang:

  • https://github.com/capitalone/fpe
  • https://github.com/cloudtrust/fpe

• Java：

  • https://github.com/idealista/format-preserving-encryption-java
  • https://github.com/robshep/JavaFPE
  • https://sourceforge.net/projects/format-preserving-encryption/
  • https://apidoc.gitee.com/dromara/hutool/cn/hutool/crypto/symmetric/fpe/FPE.html
    • https://www.nnmutong.com/article/6501892314d37004001 这篇博客写了怎么用

• C：

  • https://github.com/0NG/Format-Preserving-Encryption

博客中的代码，待验证

• 基于SM4的FPE算法测试

  • 只有加密的代码，没有解密的代码。

• http://wed.xjx100.cn/news/202303.html?action=onClick