了解一下：保形加密 Format Preserving Encryption

Question

wikipedia

原始需求

输入一个从 1 开始自然增长的级数数字（counter），得到一个看起来随机，具有不超过指定位数的加密数字

谷歌结果中的一条 StackOverflow：

利用保形加密算法 Format-Preserving Encryption 来实现（python 示例），例如：
000 733
001 374
002 882
003 684
004 593

算法简介

格式保留加密（FPE，Format Preserving Encryption，也被称之为保形加密）是一类特殊对称加密算法，它可以保证加密后的密文格式与加密前的明文格式完全相同，例如通过FPE算法对由16位数字组成的银行卡号进行加密后仍为16位数字。格式保留加密常用于数据脱敏项目中，由于其可以保持加密后的数据格式不变，从而具有无需更改数据库范式以及对上层应用透明的优势。

由于 FPE 保持密文和明文具有相同格式的特征，因此特别适用于数据脱敏领域。一方面FPE是一种加密方式，可以对敏感数据（例如手机号码、身份证号码、银行卡号等）进行加密存储，可以有效降低因黑客入侵导致的敏感信息泄露。

另一方面基于FPE实现数据脱敏在一定程度上可以替换传统基于掩码的数据遮蔽方案，并对敏感数据进行伪装转换使得加密后的数据看起来和真实数据一模一样，在测试、开发、外包等环境中使用更加友好。在使用FPE进行数据脱敏的时候如果不考虑解密，可以为FPE生成随机密钥，这样安全性会更好。

但如果需要解密操作就需要额外设计一套FPE密钥存储管理机制，以防止密钥被窃取。

FPE 和 AES 对比

FPE 算法可以保证加密前后数据格式保持不变，除此之外还包括以下特点:

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

FF1 算法

为了进一步规范 FPE 的实施，美国国家标准与技术研究院（National Institute ofStandards and Technology,NIST）针对 FPE 发布了标准草案 SP800-38G[7]，并给出了3种具体的加密算法：FF1、FF2 及 FF3。
这些算法的主体流程是类似的，其核心均为Feistel网络结构。其中FF1和FF3都是在128bit AES算法基础上实现的线性变化，而 FF2 被设计出来的时候不满足期望的128bit的安全强度被弃用。
FF1 和 FF3 不同是，FF1 基于经过 10 轮迭代，而FF3经过8轮迭代。FF3的性能略胜于FF1，但FF1的安全强度更高。因此从安全角度出发推荐利用FF1算法来实现FPE。
FF1 和 FF3 都有一个额外的输入参数，“tweak”（公开的参数）；tweak可以被视为密钥的可变部分，因为他们同时决定了加密解密函数。

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

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

1. Alphabet：有限字母的字典表，并规定了输出密文的范围，例如对于手机号码而言，是十进制纯数字格式的，其 Alphabet 包括字符 '0'-'9'。对于MAC地址而言，是十六进制数字格式，其Alphabet应该包括大写英文字母的'A'-'E'和数字'0'-'9'在内的十六个字母。
2. Character：Alphabet中的每一个字母称之为Character。
3. Radix：Alphabet中字母的个数总和，或者说Alphabet数组的长度。对于仅包含26个小写英文字母的Alphabet而言，其Radix=26。
4. Key：加密密钥，由于FF1是一种对称加密算法，其加密密钥和解密密钥都是相同的。FF1算法中Key长度必须是16、24 和32 Bytes（即 28、192 或256 bits）三种中的一种。
5. 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的长度必须是 16byte、24byte 和 32byte 三种中的一种。另外Key是一个秘密需要妥善保存。在不需要解密的情况下key可以随机选择，这样可以获取更高的安全性。
4.构造 FPE 算法对数据进行加密和解密操作。

扩展

【客座文章】强调资料格式不变，FPE与Tokenization加密保护崛起:

在资料加密的保护应用方式上，市面上出现了几种新的做法：一是格式保留加密技术（FPE），产生格式、长度相同的效果，翻转传统明、密文格式不同的印象，另一个则是记号化（Tokenization），可在资料库结构不用变动的情况下，即可满足资料保护的需求。

保留格式加密模型研究，本地

Format- Preserving Encryption演化

各语言实现

1. A format-preserving encryption implementation in Go
2. GO implementation of FF1 and FF3 from NIST Special Publication 800-38G
3. Format-Preserving Encryption Implementation in Java
4. Format-Preserving Encryption Library for Java