基于混淆器的安全对称密码方案*

袁 征，龚高翔

(1.北京电子科技学院，北京 100070； 2.西安电子科技大学 通信工程学院， 陕西 西安 710071)

密码学中的对称密码算法具有速度快、容易实现、安全强度高、易于同步等特点，被广泛应用在互联网中。但是对称密码算法也存在密钥更换困难、用同一密钥加解密容易给敌手提供破解密钥的信息和时间等缺陷。本文利用混淆器设计了一个对称密码方案。所谓混淆器就是输入一个程序(例如，图林机，或者回路)[1]，输出一个与原始程序功能相同的新的程序的(有效的)算法，且输出的程序还具有“难以识别性”。此概念要求混淆器表现的像一个“黑盒”。由于具有多比特输出的点函数混淆器具有对称密码的特点和其它优点[2]，本文利用多比特输出的点函数混淆器构造的加密方案不仅具有很高的安全性，而且实现了“动态”密钥[3]。

1 虚拟黑盒混淆与点函数混淆器

首先介绍混淆中最基础的概念——虚拟黑盒混淆[4]，然后介绍具有多比特输出点函数混淆器[2]。

1.1 虚拟黑盒混淆

一个算法O，其输入为族c中的一个回路，输出一个新的回路，被称为族c的黑盒混淆器。如果算法O有如下三个特性，就被定义为虚拟黑盒混淆：

1)保留功能性：存在一个可以忽略的函数neg(n)，使得对于任意输入长度n和每一个C∈Cn，有：

Pr[∃x∈{0,1}n:O(C)(x)≠C(x)]≤neg(n)

(1)

式(1)是在随机Oracle(预言机)和O的coin(投硬币)上的概率。

2)多项式递减性：存在一个多项式p(n)，使得对于所有有限多的输入长度和每一个C∈Cn,混淆器O仅能把C扩大p:|O(C)|≤p(|C|)的一个因子。

3)虚拟黑盒特性(VBB)：对于任意多项式大小回路敌手A，存在一个多项式大小模拟器回路S和一个可以忽略的函数neg(n)，使得对于每个输入长度为n和每个C∈Cn，有：

|Pr[A(O(C)) =1]-Pr[Sc(1n) =1]|≤neg(n)

(2)

式(2)是在敌手、模拟器和混淆器的coin(投硬币)上的概率。

虚拟黑盒混淆器O是运行在多项式时间内的，所以是有效的[5]。

1.2 具有多比特输出的点函数混淆

设I(k,m):{0,1}*∪{⊥}→{0,1}*∪⊥表示为函数：

(3)

若给定密钥k，式(3)输出消息m，否则输出⊥。设Ι={I(k,m)|k,m∈{0,1}*}为所有这样函数的族，被称为具有多比特输出点函数族，简称多比特点函数(MBPF)。

定义1(具有多比特输出的点函数混淆MBPFO)[6]一个多比特点函数(MBPF)混淆器是一个概率多项式时间算法O，其输入(k,m)值，描述为一个函数I(k,m)∈Ι，输出一个回路C，记为O(I(k,m))。但是这里一直假设O把k和m作为描绘的输入。满足如下条件：

1)正确性：对于所有的(k,m)∈{0,1}*， |k|=n,|m|=poly(n)，所有的x∈{0,1}n，满足：

Pr[C(x)≠I(k,m)(x)|C←O(I(k,m))]≤negl(n)

(4)

式(4)是混淆器算法的随机性上的概率。

2)多项式递减性：对于任意的k,m，回路C=O(I(k,m))的大小是在|k|+|m|上的多项式。

3)熵安全性：如果对于任意有1比特输出的概率多项式时间敌手，任意多项式l(.)，存在一个概率多项式时间模拟器S，使得对于所有的联合分布{Xn,Yn}n∈N，(其中Xn∈{0,1}n，Yn∈{0,1}l(n)，H∞(Xn)≥α(n))，满足式(5)，就说该方案具有α(n)-熵安全性：

|Pr[A(O(I(k,m)))=1]-

Pr[SI(k,m)l(.)(1n)=1]|≤negl(n)

(5)

式(5)是(k,m)←(Xn,Yn)的随机性、混淆器O的随机性和A,S的随机性上的概率。

如果对于所有的α(n)∈ω(log(n))，方案具有α(n)-熵安全，就说该方案具有完全熵安全性。完全熵安全性暗示着虚拟黑盒特性(VBB)，但反过来不一定。

2 构建一个基于混淆器的安全对称密码方案

本部分首先介绍具有多比特输出点函数混淆器与对称密码之间的关系。把一个公共私钥和一个随机密钥(公开的)作为输入，通过一个敏感函数产生“动态”密钥，然后构造出一个“随机”的多比特输出点函数混淆器，此混淆器具有“动态”密钥的对称密码功能。

2.1 具有多比特输出点函数混淆器(MBPFO)与对称密码之间的关系

此部分介绍了具有多比特输出点函数混淆器暗示了一个非常强对称密码类型(也叫着数字锁[7])。

定义2(错误密钥检测[8]) 如果对于所有的k≠k′∈{0,1}n，所有m∈{0,1}poly(n)，有Pr[Deck′(Enck(m))≠⊥]≤neg(n)，就说这个加密方案满足错误密钥检测。

根据文献[8]，有如下定理。

定理1 令α(n)∈w{log(n)}，对于α(n)-弱密钥，存在满足错误密钥检测的语义安全加密方案的充分必要条件是对于消息独立，存在α(n)-熵安全MBPF混淆器。用“完全”代替“α(n)”，该定理也成立。

用定理1构造(MBPFO到对称密码)。设O为一个消息独立的MBPF混淆器，定义(概率的)加密算法Enck(m)=O(I(k,m))和解密算法Deck(c)=C(k)，其中C被理解为一个多比特输出点回路(MBPC)，k是从密钥Dn域中选取的一个密钥。

这里“MBPFO”和“对称密码”的概念是平等的：首先它们满足相同的正确性，特别是给定密钥，加密方案允许恢复消息；同样式(3)中给定k，MBPFO允许恢复x。其次，它们有相似的保密要求，除非给定k，式(3)的函数I(k,m)(x)混淆隐藏了特殊的输出m；同样除非敌手拥有密钥，对称密码隐藏了消息。但是，二者的不同是MBPFO的定义域是所有可能输入的k，而对称密码不能定义在错误密钥上，换句话说，至少在概念上认为MBPFO为对称密码的特殊形式，通过解密算法，错误密钥被迅速检测出来。

2.2 基于混淆器的安全对称密码方案

与以前的对称密码相比，我们的对称密码方案的加密算法被一个具有对称密码功能的多比特输出的点函数混淆器所替代。而我们的加密方案的密钥是“动态”的，改变了以前对称密码方案中密钥的不变性。在敏感函数作用下产生的“动态”密钥，增加了我们的对称密码方案的安全性。

用户甲和乙协商确定多比特输出点函数混淆算法O、私钥k1和敏感函数Η，具体对称密码方案如下：

1)用户甲：任意选择一个公开的密钥k2，并计算k=Η(k1,k2)；

2)用户甲：用具有对称密码功能的多比特点函数混淆算法O和密钥k，对需要混淆加密的明文m进行混淆加密，得到混淆后的密文c=Enck(m)=O(I(k,m))；

3)用户甲：在公共信道上，把k2和c同时传送给用户乙；

4)用户乙：接收到密文c和密钥k2后，根据私钥k1和k2，计算k=Η(k1,k2)；

5)用户乙：用以上的解密算法和k，对密文c进行解密，得到明文m=Deck(c)=C(k)。

以上方案中，私钥k1需要通过秘密通道交换协商，密钥k2在混淆加密时随机选择。k1和k2的选择相互无关，无论给出多少个k2，都不会推出k1；k1和k2对于Η(敏感函数)的敏感性，k1和k2的细微变化都会引起k=Η(k1,k2)的明显变化，使产生的结果具有很好的扩散性与混淆性。

3 基于混淆器的对称密码方案的性能分析

3.1 对称密码方案的正确性

定理2 基于MBPFO的对称密码方案是正确的。

因为

Deck'(c)=C(k')，Enck(m)=O(I(k,m))

(6)

任取m∈{0,1}poly(n)，有：

m=Deck'(Enck(m))=Deck'(O(I(k,m)))

(7)

因为我们基于的多比特输出的点函数混淆器(MBPFO)是完全熵安全的，所以我们的对称密码方案满足错误密钥检测功能，即：若k≠k′∈{0,1}n，则：pr[Deck′(Enck(m))≠⊥]≤neg(n)，

所以，当且仅当k=k′时，m=Deck'(Enck(m))=Deck'(O(I(k,m)))=C(k)=m，正确。

3.2 “动态”密钥的安全性分析

“一次一密” 密码体制的密钥是随机产生的，其明文、密文和密钥三者是相互独立的，敌手不能从密文中获得关于明文或者密钥的任何消息，即使敌手获得一些密文及所对应的明文，也只能得到相应的密钥，而不能得到其它密文对应的明文或者密钥。因此“一次一密”的密码体制在理论上被认为是绝对安全的[10]。

我们的对称密码方案虽然与传统的“一次一密” 密码体制不同，但是通过随机密钥k2，可以实现类似于“随机”的密钥k。我们的对称密码方案还解决了传统“一次一密”密码体制中密钥管理困难问题。实际上，如果函数Η满足对私钥k1和随机密钥k2的单射性质，也就是：

(8)

我们的对称密码方案的安全性最高。

由于敏感函数Η具有很强的敏感性，一般从混沌系统中选取[11]。在混沌系统中的特性之一就是对初值的敏感依赖性。这样Η对私钥k1和动态密钥k2是敏感的，k1或k2的细微变化，k=Η(k1,k2)都会产生巨大的变化。这正如洛伦兹在一次演讲中生动地指出：一只蝴蝶在巴西煽动翅膀，就有可能在美国的德克萨斯州引起一场风暴。由于密钥在每次加密都在不断地变化，从而使得密文与明文之间具有很高的非线性特性，从而提高了对称密码方案的安全性能。

敏感函数对初始密钥和随机密钥敏感性的实验分析。我们从敏感性很好的混沌系统中选取一个敏感函数H，敏感函数H定义如下：

H(k1,k2)=mod(abs(round(Fk1.T(t)×k2)),256)

(9)

其中，k1为敏感函数的初始密钥；k2为随机密钥；T为一种采样规定；Fk1,T(t)为采样后的混沌信号；round是四舍五入运算，abs是取绝对值；mod是取余。敏感函数的输出值是在[0,255]上的整数序列。

1)敏感函数对k1的敏感性分析：令Hi(k1,k2)为H(k1,k2)的第i个元素、Δk1为k1的误差，敏感函数H产生一个长度为t的序列

s={s(1),...,s(t)}：s(i)=

(10)

显然，密钥序列s表明了H(k1+Δk1,k2)和H(k1,k2)之间对应元素的变动情况。

表1 敏感函数H对初始密钥k1的敏感性 Table 1 Sensitivity of sensitive function H on initial key k1

由此实验可知，初始密钥k1的细微变化，敏感函数产生的密钥序列都会发生99.5%的变化。

2)同样，敏感函数对于随机密钥k2的敏感性分析也可以采用以上的p作为评估标准，只是序列定义成为：

(11)

通过实验，同样也可以得到，随机密钥k2的细微变化，序列密钥都会发生99.5%以上的很大的变化。

综上所述，从混沌系统选取的敏感函数H对密钥k1和k2是非常敏感的，所以方案的安全性很高。

3.3 对称密码方案的安全性

定理3 如果O是一个满足完全熵的MBPF混淆器，则O也满足虚拟黑盒混淆。

说明此定理的具体证明思路方法是改编的条件到多比特集[9]，证明思路分为三步：

1)如果一个混淆器O满足完全安全，则其满足分布的不可辨别性。

2)如果一个混淆器O满足分布的不可辨别性，则其满足Oracle(预言机)不可辨别性。

3)如果一个混淆器O满足Oracle(预言机)不可辨别性，则其满足虚拟黑盒性能。

定理4 基于满足完全熵的MBPFO的对称密码方案是安全的。

证明对称密码方案安全性主要依赖于满足完全熵的多比特输出的点函数混淆器(MBPFO)的安全性和“动态”密钥的安全性。

根据前面定理3，我们对称密码方案基于的满足完全熵的MBPFO，也满足虚拟黑盒混淆，是安全的混淆器。

根据前面定理1，对于独立消息，存在α(n)-熵安全的MBPFO，也存在有错误密钥检测的语义安全加密方案。令C为多比特输出点回路(MBPC)，∀k∈Dn，由该多比特输出的点函数混淆器O到对称密码的表示是：

Enck(m)=O(I(k,m)),和Deck(c)=C(k)

(12)

根据文献[8]，有以下结论：①对于α(n)-弱密钥，存在CPA安全的、具有“错误密钥检测性”的对称密码方案的充分必要条件是：对于独立消息，存在α(n)-熵安全的、自我可组合的MBPF混淆器；②对于α(n)-弱密钥，存在密钥独立消息(KDM)的、具有“错误密钥检测性”的语义安全对称密码方案的充分必要条件是：对于独立消息的标准概念，存在α(n)-熵安全的MBPF混淆器。

另外，我们所基于的混淆器还有如下优点：①混淆后函数的难以识别，这给敌手攻击增加难度，此性质可以增加安全性；②该混淆器可以同时对多个回路进行串行作用，大大提高了混淆器的运行速度。③在文[12]中，多比特输出的点函数混淆器暗示非常强的对称密码，对于密钥依赖消息和随机弱密钥是安全的。④该混淆器包含弱密钥抵抗，以及具有密钥依赖消息安全的[13]。

综上所述，我们的基于满足完全熵的MBPFO的对称密码方案选用的加密算法是具有很高安全性的多比特输出的点函数混淆器，混淆本身还有结果难以识别等优点；而只要密钥k1和k2有细微变化，用敏感函数H得到的“动态”密钥k都会产生99.5%以上的变化，所以我们的方案的安全性很高。

4 结 语

满足完全熵的多比特输出的点函数混淆器(MBPFO)等同于一个具有“错误密钥检测性”的语义安全的对称密码功能，因此本文提出了一个基于该混淆器的对称密码方案，方案具有虚拟黑盒性能，保证了混淆的安全性，可以抵抗各种混淆攻击。用敏感函数产生该对称密码方案的“动态”密钥， 敏感函数的输入是私钥k1(混沌系统的初始条件)和随机密钥k2，k1和k2中任意一个发生微小的变化，由敏感函数产生的“动态”密钥k将发生99.5%以上的改变。加密者通过改变k2使得每次加密都用不同的密钥k，从而实现类似“一次一密”的密码体制功能，使得我们对称密码方案从密钥和算法两方面更加安全。

参考文献：

[1] BOAZ B, ODED G, RUSSELL I, et al. On the (im)possibility of obfuscating program[M]. CRYPTO,2001: 1-18.

[2] CANETTI R,DAKDOUK R R. Obfuscating point functions with multibit output[C]∥EUROCRYPT, Lecture Notes in Computer Science, 2008,4965:489-508.

[3] 陈鲁生，沈世镒. 现代密码学[M]. 北京：科学出版社,2002:36.

[4] GOLDWASSER S, ROTHBLUM G N.On best-possible obfuscation[C]∥Vadhan, S.P.ed. TCC 2007. LNCS, Springer, Heidelberg,2007,4392:194-213.

[5] 史扬.曹立明.王小平 混淆算法研究综述[J].同济大学学报:自然科学版,2005(6):813-819.

[6] NIR B,RAN C. On strong simulation and composable point obfuscation[C]∥CRYPTO, advances in Cryptology-CRYPTO 2010, 30th Annual Cryptology conference, Santa Barbara,CA,USA, August 15-19,2010. Proceedings,2010:520-537.

[7] NIR B,OMER P. Point obfuscation and 3-round zero-knowledge[EB/OL].(2011-09-21)[2012-03-28].http://eprint.iacr.org.

[8] CANETTI R, KALAI Y T, VARIA M. On symmetric encryption and point obfuscation[C]∥Micciancio, D. (ed.) TCC 2010. LNCS,Springer, Heidelberg,2010,5978:52-71.

[9] CANETTI R. Towards realizing random oracles: Hash functions that hide all partial information[C]∥CRYPTO,Lecture Notes in Computer Science, Springer, 1997,1294:455-469.

[10] SHANNON C E. Communication theory of secrecy systems[J]. Bell Systems Technical Journal, 1949,28:656-715.

[11] 廖晓峰，肖迪，陈勇,等.混沌密码学原理及其应用[M]. 北京：科学出版社, 2009:2-18.

[12] BITANSKY N, CANETTI R. On strong simulation and composable point obfuscation[EB/OL].(2010-07-25)[2012-03-28]. http://eprint.iacr.org.

[13] HAITNER I,HOLENSTEIN T. On the (im)possibility of key dependent encryption[C]∥TCC, 2009:202-219.