保留格式加密的双扰工作模式

张玉安，王 野，漆骏锋，胡伯良

(1.北京海泰方圆科技股份有限公司，北京100094；2.电子科技大学，四川 成都611731)

0 引言

为防止一些敏感信息被偷窥，信息加密是一种较好的应对措施。但有些情形并不需要对大量明文进行加密，比如，有一些表格，每张表格上只有手机号、身份证号和电子邮箱地址等较为敏感，其他内容无需加密。如果将这些数字串或字符串用AES或者SM4 等分组密码算法加密，需要按128 bit(16 B)数据组作分组处理，产生的密文是16 B，有些字节是不方便打印的。如果将16 B 密文转换成十进制数字，一般会变为一个39 位数，不仅表格内写不下，操作起来也不方便。为解决这类问题，一些保留格式加密(Format Preserving Encryption，FPE)[1]算法方案被提出并开始走向应用。2011 年美国NIST 曾经推荐将源自FFX 方案[2]的保留格式加密算法FF1和FF3 确立为AES 标准工作模式[3-4]。

保留格式加密算法能够将N 个数字加密成N个数字，将一串字母加密成同样长度的一串字母，即加密后能使密文保持明文的长度和数据类型。近年来出现了很多种保留格式算法方案，但是多数方案都难以被推广应用。困扰这些方案的核心问题是实用性和安全性。如果不允许明文组(和密文组)空间较小则不实用；如果允许明文组(和密文组)空间很小，则可能会有安全隐患[5-7]。为此，本文提出一种专门的保留格式算法工作模式，可较好地规避因明密文空间较小可能引发的安全问题。

另外，近几年出现了一些以功率消耗少、内存占用少为特点的轻量级分组密码算法。有些轻量级分组密码算法的分组长度只有32 bit[8-9]，在较长的密文数据段中容易存在密文组重复。如果是ECB(电子密本)模式加密，密文组重复意味着出现了明文组重复。这意味着分组较小时报文明文格式特征易于外露。本文给出的双扰工作模式能够弥补分组密码算法因明文组 (密文组) 空间较小引发的某些安全缺陷。

1 保留格式算法的一种双扰工作模式

绝大多数保留格式加密算法都属于分组密码算法。分组密码的默认工作模式是ECB[10]。但是，如DES、AES 等密码算法还可以有OFB (输出反馈)、CFB(密文反馈)、CTR(计数器)等工作模式。当AES(或DES)算法以OFB、CFB 或CTR 模式[11]工作时，通常被称为分组密码算法以序列方式工作，本质上这已经是序列密码，不再拥有分组密码的代替作业特征。对于一般的保留格式加密算法，默认的工作模式也是ECB，即一组码符被替换成另一组码符，解密时把它替换回来。如果要对长段码符的多个分组进行保留格式加密，除了ECB 模式，能否采用类似OFB、CFB 或CTR 等序列模式呢？ 因为保留格式加密很可能要面对明密文空间较小的情形，以序列密码方式工作时会因为乱数序列周期较小而被破译。

正是由于保留格式加密方案允许明密文空间较小，当攻击者获得了很多个明密对以后，就有可能因为密文组碰撞导致更多报文的明文泄露，甚至成就攻击者有条件尝试一些针对密钥的已知明文攻击。为此，本文提出一种“双扰工作模式”。其基本思想是对明文组和密文组加扰。明文组(密文组)由若干个码构成，每个码可看作是一个m 进制数，加扰是码与码对应相加，约定其为按位模m 加（码间没有进位），用符号“◎”表示。其逆变换为按位模m 减,用符号“Θ”表示。例如，字符集大小m=10，每组码数N=4，分组码0567 与7538 的模10 加为0567◎7578=7035，0567 与7538 的 模10 减 为0567Θ 7578=3099。

设明文字符集大小为m，分组长度为N 个码符。用FPEnc(P，K)表示用密钥K 对明文组P 作ECB 模式保留格式加密。如果使用IV(初始向量)且IV 与明文组类型不同，则需要按某规则将IV 转化为N 位m 进制数，使IV 与明文组同类型。若不使用IV，则默认IV=0。双扰工作模式的加密方法如下：

(1)以N 个码为一组，将明文段分为t 个组P1，P2，P3，…，Pt。

(2)用密钥K 将IV 加密(如果不使用IV 则将“0”加密)，得S0=FPEnc(IV，K)，称S0为秘密IV。计算S1=FPEnc(0◎S0，K)=FPEnc(S0，K)。对i=2，3，…，t，计算Si=FPEnc((Si-1◎Si-2)，K)。得到扰序列S0，S1，S2，…，St。

(3)加密各个明文组。对i=1，2，3，…，t，作如下操作：

①将明文组Pi与扰码Si-1按位模m 加(明文加扰)，得P=Pi◎Si-1。

②将P 加密，即得到C=FPEnc(P，K)。

③将C 与Si按位模m 加(密文加扰)，即得Ci=C◎Si。Ci为 第i 个 密 文 组。

双扰工作模式分组加密流程如图1 所示。

双扰工作模式的解密方法与加密方法相似，需要加解密双方约定是否使用IV。解密时步骤(3)中的加密运算相应地变为解密运算，按位模m 加相应地变为按位模m 减,参见图2。即步骤(3)相应地变为对i=1，2，3，…，t，作如下操作：

①将密文组Ci与扰码Si按位模m 减(密文解扰)，得C=CiΘSi。

②将C 解密，即计算P=FPDec(C，K)。

③将P 与Si-1按位模m 减(明文解扰)，即解得明文组Pi=PΘSi-1。

上述三小步可用式子描述为：

Pi=FPDec((CiΘSi)，K)ΘSi-1。

IV 的作用在于产生扰码序列初值S0。对攻击者来说，IV 是可见的，但S0是不可预测的。不同的IV产生不同的S0，导致产生不同的扰码序列。

图1 双扰工作模式分组加密流程示意图

2 对双扰工作模式的性能分析

保留格式加密算法的双扰工作模式实际是将ECB 模式与序列加密模式相互混合，可以直观地理解为每个数据组的加密过程分为三步：(1)用一组扰码对输入的明文组实施加扰；(2)对加了扰的明文组作多轮迭代式分组加密；(3)用另一组扰码对分组加密后的输出密文进行加扰。对于实用的现代分组密码算法，唯密文攻击[12]几乎没有成功希望，所以，较为现实的攻击方向当属已知明文攻击[13-14]和选择明文(密文)攻击[15]。为了能够形成攻击所需要的数据条件，攻击者必须设法搜索和猜设一定数量的明密对。

在通常的ECB 或CBC(密文分组链接)工作模式下，当攻击者截获了某用户的长段密文后，通过研究密文产生场景、收集与该用户相关的相近长度明文数据、关注密文解译方公开流露出的等长明文段落等，将某些明文段与密文段形成明密对应，进而猜设到一些明密对。甚至有可能找到密文组重复，暴露明文结构特征，为猜设明文提供重要佐证。之后，可以开展一些已知明文攻击或选择明文攻击类研究课题。当明文组空间较小时，如果密文数据量较大，这类攻击有可能产生实质效果。

图2 双扰工作模式解密流程示意图

在CBC 工作模式下，假设用户加密明文段P=(p0，p1，p2，…，pn)产 生 了 密 文C=(c0，c1，c2，… ，cn)，而且用户在不变更密钥情况下又加密明文段Q=(q0，q1，q2，…，qm)产生了密文D=(d0，d1，d2，…，dm)。如果攻击者在C 和D 这两份密文之间找到了相同的 密 文 组，比 如 有ci=dk，1 ≤i ≤n，1 ≤k ≤m，那 么，依据分组迭代时相同的密文输出必定有相同的明文输入，攻击者可以推出ci-1⊕pi=dk-1⊕qk，得到ci-1⊙dk-1=pi⊙qk，这里“⊕”表示数据组异或，“⊙”表示逻 辑 同。进 而 有pi⊕qk=ci-1⊕dk-1。由 于ci-1和dk-1在密文中可见，ci-1⊕dk-1是已知的，因此，通过找到并研究相同密文组，攻击者可以发现两明文组间的差值，这将有助于猜设明文。同理，若在一份较长密文内找到了相同密文组，比如有ci=ck，可以获知明文组pi与pk间的差值。所以，若能在密文数据中找到相同的密文组，则CBC 模式是有安全缺陷的，而双扰工作模式不存在此类安全隐患。

在CTR 或OFB 模式下，如果用户不慎重复使用了IV，会导致信息泄露。而在双扰工作模式情形，重用IV 意味着分组序号相同的两个数据组，加在明文上的扰码相同、 加在密文上的扰码也相同，具体扰码是什么不可预测。其攻击难度大于ECB 模式只有两个明密对时，求取密钥或者预测其他明密对。即使同一个IV 重复使用 n 次，双扰工作模式的安全强度也会优于已知n 个明密对情形的已知明文攻击。

双扰工作模式的中心思想是通过多次加密IV产生秘密扰码序列，扰乱分组迭代的输入和输出。采用本文给出的双扰工作模式，即使攻击者获得了某密文段落的明文，仍然得不到明密对，因为攻击者不能准确地猜设用于明文组和密文组的扰码。当明文组序号不相同时，即使出现相同的密文组也无助于猜设明文信息。

拥有若干明密对构成的适度数据条件，是密码分析和破译的基本素材，也是破译成功的必备基础。双扰工作模式遏制了攻击者获取有效数据的能力，使攻击者不能具备开展密码分析研究的数据条件。破坏了攻击者的攻击能力，某个层面上等同于该工作模式增强了算法的安全强度。

由于双扰工作模式每加密一个明文组近似等于做两次ECB 加密和两次按位模m 加，在效率方面它只相当于通常CBC 或CTR 模式的近二分之一。大多数情形下，这不会影响实际应用。另外，由于扰码的产生与明密文无关，致使扰码序列可以预计算或并行计算，从而可以使双扰工作模式的运算时间在可并行环境下逼近CBC 模式。

3 结论

算法的工作模式也是算法安全性的一个组成部分。好的工作模式可以弥补算法设计上的某些不足，为算法安全性加分，但也可能为算法工作效率减分。安全与效率通常是相互制约的两个方面。对于保留格式加密算法，面对的场景可能是明文组空间较小，需要加密的数据量不大。所以，实际应用中用户对效率的要求不高，安全性更为重要，这将使得双扰工作模式拥有较好的应用前景。本文给出的双扰工作模式实质上是分组密码算法的一种通用工作模式，它并不局限于保留格式加密中的应用，仅仅是用于保留格式加密算法时，因为数据分组可能较小，安全性方面的优点较为突出。