Format Preserving Encryption
Format Preserving Encryption
保格式加密(format preserving encryption,简称FPE)是一种对称密码学工具,它能够在保证原有格式的情况下进行加密. 对于明文空间中的一条信息,其加密结果也应该是中的一条信息. 比如对于一个手机号的加密结果还是一个手机号. 因此,保格式加密相当于对进行了一次排列,将其映射到另一条信息.
形式化的说,FPE是一个四元函数
其中表示密钥集合,表示格式集合,表示调整键集合,表示域空间. 上述所有集合都非空并且. 对于一个特定的FPE可以缩写为,其表示为使用密钥和调整键在格式的情况下对进行加密. 一个理想的FPE表现为域中的一个随机排列. 对于FPE而言,目前主流的方法是使用块加密来构建. 关于块加密方法的对比可以参考这里. 视频教学可以参照这里.
应用
FPE主要应用在老旧系统的向下兼容:业已存在的系统不需要经过太大的改动就能够进行加密匹配. 例如系统中需要使用信用卡号,如果使用AES进行加密,那么其产生的结果将会包含16进制字符,因此系统需要进行较大修改才能够保证正常使用. 如果使用FPE,那么其结果同样会是一个信用卡号,对于已有系统的改动就会较小[1].
除此之外,FPE还能适用于数据库当中. 例如某个用户想将自己的加密信用卡号存储在一个数据库中,他就可以使用FPE加密自己的信用卡号,而服务端则会将其当作信用卡号进行存储. 如果使用AES进行加密,那么服务端将不能识别其为一个信用卡号[1].
算法
基本原理——排序加密法
由于之前关于FPE的介绍我们可以得知,FPE可以被抽象成3个过程:
- ——将域中所有数据进行排序,并把要加密的数据映射到一个索引
- ——将索引映射到
- ——将索引还原成其对应的数据
对于一个特定格式的域空间,设其域空间大小为. 那么对于该域中全部的个点,以某个方式将其排序为. 对于要加密的输入,先找到其在的索引,即在为. 然后再使用一个伪随机函数PRF将映射为中的一个元素. 即为加密后的结果.
该方案的有效性取决于以下几点:
-
是否能够高效将映射为中的索引
-
是否能够高效将映射为
-
是否能够高效将映射为
加密法
对于数据集较小的样本,可以使用块加密方法对其进行加密,将所得秘文看作一个数,然后对所有数进行排序. 所得结果就是得到的最终排列. 例如对于样本集*{0, 1, 2, 3}*,每个数据使用AES和某个密钥进行加密之后得到的结果如下:
对其进行排序我们可以得到:
因此对于FPE我们可以有如下输出:
John B等人证明了该方案的安全性取决于其所使用的块加密方案[2].
循环法
考虑一个块加密方案,例如AES,对于一个输入,AES会将x映射到一个固定长度的输出. 因此只要我们选择一个输出长度,其中M是明文空间,然后不断使用AES进行加密,那么我们一定可以得到一个输出O属于明文空间. 写成伪代码如下:
function cycleWalk(plaintext):
ciphertext = blockCipher(plaintext)
if inPlaintextSpace(ciphertext):
return ciphertext
return cycleWalk(ciphertext)
上述方案在样本空间很小时不适用,因为可能需要迭代很多次. 例如对于具有100个比特的样本空间,如果使用128位AES进行加密,那么迭代次数的期望为.
Feistel网络
Feistel网络是一种产生块密码的方式. 其基本原理如下图所示:
它将一个比特的输入拆成,每次对其中的一个进行操作,然后再进行交换. 它一共会涉及到轮,每轮都会使用伪随机函数和一个新的密钥来对其中一半bit产生新的随机数. 根据Patarin的工作,只要轮数足够多(比如3轮或更多)就能够保证Feistel的输出是一个伪随机排列.
对于伪随机函数一般采用块加密技术实现. 这里也会出现与循环法一样的问题:例如在中途产生的密钥可能比实际需要的密钥多(采用Feitel网络一般采用轮数来产生密钥,这样可以有效减少密钥保存的问题),这是只需要选取最低位符合要求的比特数即可. 即使这样,Feistel网络产生的输出可能还是会比实际密文空间要大. 例如对于16位的信用卡号,其总样本空间为. 因此在Feistel网络中需要选取54个比特,这样就会产生不符合要求的输出. 这是我们可以采用循环法,而这时我们迭代次数的期望为2.
形式的说,对于样本空间,我们总是可以选取,使得是最小满足下面不等式的偶数. 此时由
上面的分析可知循环法迭代次数的期望不会超过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轮,并且如果产生比特数为奇数,那么根据轮数的奇偶性来决定进行操作比特串是还是.
评论
发表评论