Format Preserving Encryption

保格式加密（format preserving encryption，简称FPE）是一种对称密码学工具，它能够在保证原有格式的情况下进行加密. 对于明文空间中的一条信息，其加密结果也应该是中的一条信息. 比如对于一个手机号的加密结果还是一个手机号. 因此，保格式加密相当于对进行了一次排列，将其映射到另一条信息.

形式化的说，FPE是一个四元函数​
$E: \mathcal{K}\times\mathcal{N}\times\mathcal{T}\times\mathcal{X}\rightarrow\mathcal{X}\cup\{\perp\}$

其中$\mathcal{K}$​表示密钥集合，​​​​​​$\mathcal{T}$表示格式集合，​$\mathcal{T}$表示调整键集合，​$\mathcal{X}$表示域空间. 上述所有集合都非空并且​. 对于一个特定的FPE可以缩写为​，其表示为使用密钥​和调整键​在格式​的情况下对​进行加密. 一个理想的FPE表现为域​中的一个随机排列. 对于FPE而言，目前主流的方法是使用块加密来构建. 关于块加密方法的对比可以参考这里. 视频教学可以参照这里.

应用

FPE主要应用在老旧系统的向下兼容：业已存在的系统不需要经过太大的改动就能够进行加密匹配. 例如系统中需要使用信用卡号，如果使用AES进行加密，那么其产生的结果将会包含16进制字符，因此系统需要进行较大修改才能够保证正常使用. 如果使用FPE，那么其结果同样会是一个信用卡号，对于已有系统的改动就会较小[1].

除此之外，FPE还能适用于数据库当中. 例如某个用户想将自己的加密信用卡号存储在一个数据库中，他就可以使用FPE加密自己的信用卡号，而服务端则会将其当作信用卡号进行存储. 如果使用AES进行加密，那么服务端将不能识别其为一个信用卡号[1].

算法

基本原理——排序加密法

由于之前关于FPE的介绍我们可以得知，FPE可以被抽象成3个过程：

• $Rank$——将域中所有数据进行排序，并把要加密的数据映射到一个索引$i$
• $Map$——将索引$i$映射到$j$
• $Unrank$——将索引$j$还原成其对应的数据

对于一个特定格式$N$的域空间$\mathcal{X}_N$，设其域空间大小为$n$. 那么对于该域中全部的$n$个点，以某个方式将其排序为$\mathcal{X}_N=\{X_0,\ldots,X{n-1}\}$. 对于要加密的输入$X\in \mathcal{X}_N$，先找到其在$\mathcal{X}_N$的索引$i$，即$X$在$\mathcal{X}_N$为$X_i$. 然后再使用一个伪随机函数PRF将$i$映射为$\mathbb{Z}_n$中的一个元素$j$. $X_j$即为$X_i$加密后的结果.

该方案的有效性取决于以下几点：

• 是否能够高效将$X$映射为$\mathcal{X}_N$中的索引$i$

• 是否能够高效将$i$映射为$j$

• 是否能够高效将$j$映射为$i$

加密法

对于数据集较小的样本，可以使用块加密方法对其进行加密，将所得秘文看作一个数，然后对所有数进行排序. 所得结果就是得到的最终排列. 例如对于样本集*{0, 1, 2, 3}*，每个数据使用AES和某个密钥进行加密之后得到的结果如下：
$AES_K(0)=0x56c644080098fc5570f2b329323dbf62 \\ AES_K(1)=0x08ee98c0d05e3dad3eb3d6236f23e7b7 \\ AES_K(2)=0x47d2e1bf72264fa01fb274465e56ba20 \\ AES_K(3)= 0x077de40941c93774857961a8a772650d$
对其进行排序我们可以得到:
$\{AES_K(3),AES_K(0),AES_K(2),AES_K(1)\}$
因此对于FPE我们可以有如下输出:
$FPE(0) = 3 \\ FPE(1) = 0 \\ FPE(2) = 2 \\ FPE(3) = 1$
John B等人证明了该方案的安全性取决于其所使用的块加密方案[2].

循环法

考虑一个块加密方案，例如AES，对于一个输入$x$，AES会将x映射到一个固定长度的输出$L$. 因此只要我们选择一个输出长度$L>=|M|$，其中M是明文空间，然后不断使用AES进行加密，那么我们一定可以得到一个输出O属于明文空间. 写成伪代码如下：

function cycleWalk(plaintext):

    ciphertext = blockCipher(plaintext)

    if inPlaintextSpace(ciphertext):

        return ciphertext

    return cycleWalk(ciphertext)

上述方案在样本空间很小时不适用，因为可能需要迭代很多次. 例如对于具有100个比特的样本空间，如果使用128位AES进行加密，那么迭代次数的期望为$2^{28}$.

Feistel网络

Feistel网络是一种产生块密码的方式. 其基本原理如下图所示：

它将一个$n$比特的输入拆成$L_0,R_0$,每次对其中的一个进行操作，然后再进行交换. 它一共会涉及到$n$轮，每轮都会使用伪随机函数$F$和一个新的密钥$K$来对其中一半bit产生新的随机数. 根据Patarin的工作，只要轮数足够多（比如3轮或更多）就能够保证Feistel的输出是一个伪随机排列.

对于伪随机函数$F$一般采用块加密技术实现. 这里也会出现与循环法一样的问题：例如在中途产生的密钥可能比实际需要的密钥多（采用Feitel网络一般采用轮数来产生密钥$K$，这样可以有效减少密钥保存的问题），这是只需要选取最低位符合要求的比特数即可. 即使这样，Feistel网络产生的输出可能还是会比实际密文空间要大. 例如对于16位的信用卡号，其总样本空间为$10^{16}\approx2^{53.1}$. 因此在Feistel网络中需要选取54个比特，这样就会产生不符合要求的输出. 这是我们可以采用循环法，而这时我们迭代次数的期望为2.

形式的说，对于样本空间$M$，我们总是可以选取$t$，使得$t$是最小满足下面不等式的偶数. 此时由
$2^{t-1}\le M \le 2^t$
上面的分析可知循环法迭代次数的期望不会超过2.

代码实现

虽然学术界提出了各种有关FPE的实现方法，但是到目前为止，被NIST（美国国家标准技术研究所）所审核并接受的方案只有Bellare等人提出的FFX Mode of Operation不支持在 Docs 外粘贴 block. 虽然当时发布的文件同意了两种方案FF1和FF3，但是后来被指出FF3存在漏洞. 目前对于NIST代码实现有Golang，C，Java，Python

FF1

FF1采用Feistel网络实现. 其基本原理是用将输入字符串看作一个​进制字符串，然后再将该字符串解码为一个2进制数，最后对该二进制数采用Feistel网络进行操作. 在这里Feistel网络一共要进行10轮，并且如果产生比特数为奇数，那么根据轮数的奇偶性来决定进行操作比特串是$L_i$还是$R_i$​.