admin 管理员组

文章数量: 887021


2023年12月17日发(作者:电脑死机快捷键结束程序)

第52卷第1期 中山大学学报(自然科学版) V01.52 No.1 2013年1月 ACTA SCIENTIARUM NATURALIUM UNIVERSITATIS SUNYATSENI Jan.2013 基于混淆器的安全对称密码方案 袁征 2,龚高翔 2 (1.北京电子科技学院,北京100070; 2.西安电子科技大学通信工程学院,陕西西安710071) 摘 要:提出基于多比特输出点函数混淆器的、具有“动态”密钥的对称密码方案。满足完全熵的多比特输出 的点函数混淆器(MBPFO)等同于一个具有“错误密钥检测性”的语义安全的对称密码功能,该方案用此混淆 器实现了对称密码方案,方案用双密钥通过敏感函数构造的“动态”密钥,可以实现类似“一次一密”的密码 体制功能,因此该方案具有更高安全性,并且实现简单。 关键词:混淆;对称密码;具有多比特输出点函数混淆器;敏感函数 中图分类号:TP309 文献标志码:A 文章编号:0529—6579(2013)o1—0007—05 Secure Symmetric Encryption Scheme Based on Obfuscator YUAN Zheng .GONG Gaoxiang ’ (1.Beijing Electronic Science&Technology Institute,Bering 100070,China; 2.Communication Engineer Institute,Xidian University,Xi’an 710071,China) Abstract:An symmetric encryption scheme with dynamic key based on obfuscation of point functions with multibit output(MBPF)is presented.A MBPF obfuscator with fully—entropic security,implying virtual black-box property(VBB),can be used to construct semantically secure encryption schemes with wrong key detection for 0c( )一weak keys.The symmetirc encryption scheme is just the fully—entropic se— curity MBPF obfuscator,whose key is deduced by a sensitive function.The sensitive function with two inputs,one is a secret key and another is a random key,and thus output key is random.The symmetric encryption scheme is more secure and implement simple. Key words:obfuscation;symmetric encryption;Obfuscating point functions with muhibit output;sensi— rive function 密码学中的对称密码算法具有速度快、容易实 功能相同的新的程序的(有效的)算法,且输出 现、安全强度高、易于同步等特点,被广泛应用在 的程序还具有“难以识别性”。此概念要求混淆器 互联网中。但是对称密码算法也存在密钥更换困 表现的像一个“黑盒”。由于具有多比特输出的点 难、用同一密钥加解密容易给敌手提供破解密钥的 函数混淆器具有对称密码的特点和其它优点 J, 信息和时间等缺陷。本文利用混淆器设计了一个对 本文利用多比特输出的点函数混淆器构造的加密方 称密码方案。所谓混淆器就是输入一个程序(例 案不仅具有很高的安全性,而且实现了“动态” 如,图林机,或者回路)…,输出一个与原始程序 密钥 。 收稿日期:2012—04—01 基金项目:国家自然科学基金资助项目(61070250);北京市自然科学基金资助项目(4132066);“十二五”国家密 码基金资助项目(MMJJ201101026);信息安全国家重点实验室基金资助项目(01—0l,01—02—6);中 办信息安全重点实验室基金资助项目(YZDJ0905) 作者简介:袁征(1968年生),女,教授;E-mail:yuanzheng@besti.edu.on;zyuan@tsinghua.edu.cn 

8 中山大学学报(自然科学版) 第52卷 1 虚拟黑盒混淆与点函数混淆器 首先介绍混淆中最基础的概念——虚拟黑盒混 淆 ],然后介绍具有多比特输出点函数混淆器 。 1.1虚拟黑盒混淆 一个算法0,其输人为族C中的一个回路,输 出一个新的回路,被称为族c的黑盒混淆器。如果 算法0有如下三个特性,就被定义为虚拟黑盒混 淆: 1)保留功能性:存在一个可以忽略的函数 neg(n),使得对于任意输入长度n和每一个C∈ C ,有: Pr[ ∈{0,1} :0(C)( )≠C(x)]≤neg(n) (1) 式(1)是在随机Oracle(预言机)和0的coin (投硬币)上的概率。 2)多项式递减性:存在一个多项式P(/Z), 使得对于所有有限多的输入长度和每一个C∈C , 混淆器0仅能把C扩大P:f 0(C)f≤P(}C})的一 个因子。 3)虚拟黑盒特性(VBB):对于任意多项式 大小回路敌手A,存在一个多项式大小模拟器回 路S和一个可以忽略的函数neg(n),使得对于每 个输入长度为,z和每个C∈C ,有: lPr[A(0(C))=1]一Pr[S。(1 )=1]I≤neg(n) (2) 式(2)是在敌手、模拟器和混淆器的coin(投硬 币)上的概率。 虚拟黑盒混淆器O是运行在多项式时间内的, 所以是有效的l5 J。 1.2具有多比特输出的点函数混淆 设 ):. {0,1} u{J_}一{0,1} u上表示 为函数: ㈩={ 主 (3) 若给定密钥 ,式(3)输出消息m,否则输出 上。设I={, )I ,m∈{0,1} }为所有这样函数 的族,被称为具有多比特输出点函数族,简称多比 特点函数(MBPF)。 定义1(具有多比特输出的点函数混淆MB— PFO)E61 一个多比特点函数(MBPF)混淆器是 一个概率多项式时间算法O,其输入( ,m)值, 描述为一个函数 . )∈I,输出一个回路C,记 为O(, ))。但是这里一直假设O把 和 作为 描绘的输入。满足如下条件: 1)正确性:对于所有的( ,m)∈{0,l} ,  ll=n,l m I=poly(n),所有的 ∈{0,1},f,满 足: Pr[C( )≠ . )( )l C一0( . ))]≤negl(n) (4) 式(4)是混淆器算法的随机性上的概率。 2)多项式递减性:对于任意的 ,m,回路 =O(, ))的大小是在I I+l m I上的多项式 3)熵安全性:如果对于任意有1比特输出的 概率多项式时间敌手,任意多项式f(.),存在一 个概率多项式时间模拟器 ,使得对于所有的联合 分布{X , }h en,(其中 ∈{0,1} , ∈{0, 1}f( ,H ( )≥O/(n)),满足式(5),就说该 方案具有 (n)一熵安全性: I Pr[A(O( . )))=1]一 [5 , )“ (1 )=1]f≤negl(n) (5) 式(5)是( ,m)一( , )的随机性、混淆器0 的随机性和A,Js的随机性上的概率。 如果对于所有的Ol(n)∈ (1og(n)),方案具 有 (n)一熵安全,就说该方案具有完全熵安全 性。完全熵安全性暗示着虚拟黑盒特性(VBB), 但反过来不一定。 2构建一个基于混淆器的安全对称 密码方案 本部分首先介绍具有多比特输出点函数混淆器 与对称密码之间的关系。把一个公共私钥和一个随 机密钥(公开的)作为输入,通过一个敏感函数 产生“动态”密钥,然后构造出一个“随机”的 多比特输出点函数混淆器,此混淆器具有“动态” 密钥的对称密码功能。 2.1 具有多比特输出点函数混淆器(MBPFO)与 对称密码之间的关系 此部分介绍了具有多比特输出点函数混淆器暗 示了一个非常强对称密码类型(也叫着数字锁 [7])。 定义2(错误密钥检测 ) 如果对于所有的 ≠ ∈{0,l} ,所有m∈{0,1 ,有 Pr[Dec ,(Enc (m))≠上]≤neg(n),就说这个加 密方案满足错误密钥检测。 根据文献[8],有如下定理。 定理1 令Ol(n)∈ {log(n)},对于 (n) 一弱密钥,存在满足错误密钥检测的语义安全加密 

第1期 袁征等:基于混淆器的安全对称密码方案 9 方案的充分必要条件是对于消息独立,存在ot(/7,) 一熵安全MBPF混淆器。用“完全”代替 “ ( )”,该定理也成立。 用定理1构造(MBPFO到对称密码)。设O 为一个消息独立的MBPF混淆器,定义(概率的) 加密算法Enc (m)=0( . )和解密算法 Dec (C):C(k),其中C被理解为一个多比特输 出点回路(MBPC),k是从密钥D 域中选取的一个 密钥。 这里“MBPFO”和“对称密码”的概念是平 等的:首先它们满足相同的正确性,特别是给定密 钥,加密方案允许恢复消息;同样式(3)中给定 k,MBPFO允许恢复 。其次,它们有相似的保密 要求,除非给定k,式(3)的函数 . )( )混淆 隐藏了特殊的输出m;同样除非敌手拥有密钥, 对称密码隐藏了消息。但是,二者的不同是MB. PFO的定义域是所有可能输入的k,而对称密码不 能定义在错误密钥上,换句话说,至少在概念上认 为MBPFO为对称密码的特殊形式,通过解密算 法,错误密钥被迅速检测出来。 2.2基于混淆器的安全对称密码方案 与以前的对称密码相比,我们的对称密码方案 的加密算法被一个具有对称密码功能的多比特输出 的点函数混淆器所替代。而我们的加密方案的密钥 是“动态”的,改变了以前对称密码方案中密钥 的不变性。在敏感函数作用下产生的“动态”密 钥,增加了我们的对称密码方案的安全性。 用户甲和乙协商确定多比特输出点函数混淆算 法O、私钥k 和敏感函数日,具体对称密码方案 如下: 1)用户甲:任意选择一个公开的密钥k ,并 计算k=H(k ,k ); 2)用户甲:用具有对称密码功能的多比特点 函数混淆算法O和密钥k,对需要混淆加密的明文 m进行混淆加密,得到混淆后的密文C=Enc (m) =0( , )); 3)用户甲:在公共信道上,把k 和C同时传 送给用户乙; 4)用户乙:接收到密文c和密钥k。后,根据 私钥k 和k2,计算k:H(k ,k2); 5)用户乙:用以上的解密算法和k,对密文 C进行解密,得到明文m:Dec (C)=C( )。 以上方案中,私钥k 需要通过秘密通道交换 协商,密钥k 在混淆加密时随机选择。k 和k:的选 择相互无关,无论给出多少个k:,都不会推出 k ;k 和k 对于日(敏感函数)的敏感性,k 和k2 的细微变化都会引起k=H(k ,k:)的明显变化, 使产生的结果具有很好的扩散性与混淆性。 3 基于混淆器的对称密码方案的 性能分析 3.1 对称密码方案的正确性 定理2基于MBPFO的对称密码方案是正确的。 证明令加密密钥k=H(k ,k )、解密密钥 为k =H(k ,k ),通过错误密钥检测证明正确 性: 因为 Dec ,(C)=C( ,Enc (m)=0( .m】)(6) 任取m∈{0,1} ’,有: m:Dec ,(Enc (m))=Dec ,(0( . ))(7) 因为我们基于的多比特输出的点函数混淆器(MB. PFO)是完全熵安全的,所以我们的对称密码方案 满足错误密钥检测功能,即:若k≠k ∈{0,1} , 则:pr[Dec ,(Enc (m))≠上]≤neg(n), 所以,当且仅当k =k 时,rn= Dec ,(Eric (m))=Dec ,(0( . 、))=C(k)7--m, 正确。 3.2 “动态”密钥的安全性分析 “一次一密”密码体制的密钥是随机产生的, 其明文、密文和密钥三者是相互独立的,敌手不能 从密文中获得关于明文或者密钥的任何消息,即使 敌手获得一些密文及所对应的明文,也只能得到相 应的密钥,而不能得到其它密文对应的明文或者密 钥。因此“一次一密”的密码体制在理论上被认 为是绝对安全的¨ 。 我们的对称密码方案虽然与传统的“一次一 密”密码体制不同,但是通过随机密钥k ,可以 实现类似于“随机”的密钥k。我们的对称密码 方案还解决了传统“一次一密”密码体制中密钥 管理困难问题。实际上,如果函数日满足对私钥 _ic 和随机密钥 的单射性质,也就是: 当k ≠ ,或者k ≠ 时,H(k ,k2)≠ H(后 ,k2 ) (8) 我们的对称密码方案的安全性最高。 由于敏感函数H具有很强的敏感性,一般从 混沌系统中选取¨ 。在混沌系统中的特性之一就 是对初值的敏感依赖性。这样日对私钥 和动态 密钥 是敏感的,k 或 的细微变化,k=H( , )都会产生巨大的变化。这正如洛伦兹在一次演 讲中生动地指出:一只蝴蝶在巴西煽动翅膀,就有 

lO 中山大学学报(自然科学版) 第52卷 可能在美国的德克萨斯州引起一场风暴。由于密钥 在每次加密都在不断地变化,从而使得密文与明文 之间具有很高的非线性特性,从而提高了对称密码 方案的安全性能。 敏感函数对初始密钥和随机密钥敏感性的实验 分析。我们从敏感性很好的混沌系统中选取一个敏 感函数 ,敏感函数 定义如下: H( 1,k2)=mod(abs(round(F r(t)×k2)),256) (9) 其中,k。为敏感函数的初始密钥;k 为随机密钥;T 为一种采样规定;Fk (t)为采样后的混沌信号; round是四舍五入运算,abs是取绝对值;mod是取 余。敏感函数的输出值是在[0,255]上的整数 序列。 1)敏感函数对七 的敏感性分析:令 ( 。, k )为H(k ,k )的第 个元素、△ 。为k 的误差, 敏感函数 产生一个长度为t的序列 s={s(1),...,s(t)}:s(i)= O Hi( , z)= ( z+ , z)f 101 L1 其它 显然,密钥序列 表明了H(J]} +△ , )和日( , k,)之间对应元素的变动情况。 参数p=∑s(i)/n×100%表示当k 在产生 误差△ 时,由敏感函数产生的混沌序列中发生变 化的元素占序列元素总数的百分比。该参数表示敏 感函数对密钥 。的敏感性。△ .分别取值10一, 10 。,…,10 ,进行实验,实验结果如表1。 表1敏感函数日对初始密钥k,的敏感性 Table 1 Sensitivity of sensitive function H on initial key k1 △ l 10一 10 10 10一 10一 。 10 10 p/% 99.58 99.54 99.56 99.68 99.63 99.66 99.52 由此实验可知,初始密钥k 的细微变化,敏 感函数产生的密钥序列都会发生99.5%的变化。 2)同样,敏感函数对于随机密钥k:的敏感性 分析也可以采用以上的P作为评估标准,只是序列 定义成为: … f0 H。(k1,k2)=H ( l,k2+Ak2) ㈩ i1 其它 (11) 通过实验,同样也可以得到,随机密钥k 的 细微变化,序列密钥都会发生99.5%以上的很大 的变化。 综上所述,从混沌系统选取的敏感函数 对 密钥 和k 是非常敏感的,所以方案的安全性很 高。 3.3对称密码方案的安全性 定理3如果0是一个满足完全熵的MBPF混 淆器,则O也满足虚拟黑盒混淆。 说明此定理的具体证明思路方法是改编的条 件到多比特集 J,证明思路分为三步: 1)如果一个混淆器O满足完全安全,则其满 足分布的不可辨别性。 2)如果一个混淆器O满足分布的不可辨别 性,则其满足Oracle(预言机)不可辨别性。 3)如果一个混淆器O满足Oracle(预言机) 不可辨别性,则其满足虚拟黑盒性能。 定理4 基于满足完全熵的MBPFO的对称密 码方案是安全的。 证明对称密码方案安全性主要依赖于满足完 全熵的多比特输出的点函数混淆器(MBPFO)的 安全性和“动态”密钥的安全性。 根据前面定理3,我们对称密码方案基于的满 足完全熵的MBPFO,也满足虚拟黑盒混淆,是安 全的混淆器。 根据前面定理1,对于独立消息,存在 (n) 一熵安全的MBPFO,也存在有错误密钥检测的语 义安全加密方案。令C为多比特输出点回路(MB— PC),Vk∈D ,由该多比特输出的点函数混淆器 0到对称密码的表示是: Enc ( )=D(, )),和Dec (c)=C( ) (12) 根据文献[8],有以下结论:①对于 (n)一 弱密钥,存在CPA安全的、具有“错误密钥检测 性”的对称密码方案的充分必要条件是:对于独 立消息,存在 (n)一熵安全的、自我可组合的 MBPF混淆器;②对于O/(n)一弱密钥,存在密钥 独立消息(KDM)的、具有“错误密钥检测性” 的语义安全对称密码方案的充分必要条件是:对于 独立消息的标准概念,存在 (n)一熵安全的MB. PF混淆器。 另外,我们所基于的混淆器还有如下优点:① 混淆后函数的难以识别,这给敌手攻击增加难度, 此性质可以增加安全性;②该混淆器可以同时对多 个回路进行串行作用,大大提高了混淆器的运行速 度。③在文[12]中,多比特输出的点函数混淆 器暗示非常强的对称密码,对于密钥依赖消息和随 

第1期 袁征等:基于混淆器的安全对称密码方案 机弱密钥是安全的。④该}昆淆器包含弱密钥抵抗, 以及具有密钥依赖消息安全的¨ 。 综上所述,我们的基于满足完全熵的MBPFO 的对称密码方案选用的加密算法是具有很高安全性 的多比特输出的点函数混淆器,混淆本身还有结果 难以识别等优点;而只要密钥k 和 有细微变化, 用敏感函数日得到的“动态”密钥k都会产生 99.5%以上的变化,所以我们的方案的安全性很高。 4结语 满足完全熵的多比特输出的点函数混淆器 (MBPFO)等同于一个具有“错误密钥检测性”的 语义安全的对称密码功能,因此本文提出了~个基 于该混淆器的对称密码方案,方案具有虚拟黑盒性 能,保证了混淆的安全性,可以抵抗各种混淆攻 击。用敏感函数产生该对称密码方案的“动态” 密钥,敏感函数的输入是私钥k (混沌系统的初始 条件)和随机密钥k:,k 和k 中任意一个发生微 小的变化,由敏感函数产生的“动态”密钥k将 发生99.5%以上的改变。加密者通过改变k 使得 每次加密都用不同的密钥k,从而实现类似“一次 一密”的密码体制功能,使得我们对称密码方案 从密钥和算法两方面更加安全。 参考文献: [1] BOAZ B,ODED G,RUSSELL I,et a1.On the(im) possibility of obfuscating program[M].CRYPTO,2001: 1—18. [2] CANETTI R,DAKDOUK R R.Obfuscating point func— tions with muhibit 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 Cryptolo— gY—CRYPTO 2010,30th Annual Cryptology conference, Santa Barbara,CA,USA,August 15—19,2010.Pro— ceedings。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] CANEqq'I R,KALAI Y T,VARIA M.On symmetric en— cryption and point obfuscation[C]∥Micciancio,D. (ed.)TCC 2010.LNCS,Springer,Heidelberg,2010, 5978:52—71. [9] CANETYI R.Towards realizing random oracles:Hash functions that hide all partial information[C]∥CRYP— TO,Lecture Notes in Computer Science,Springer, 1997,1294:455—469. [10] SHANNON C E.Communication theory of secrecy sys— tems[J].Bell Systems Technical Journal,1949,28:656 —715. [11] 廖晓峰,肖迪,陈勇,等.混沌密码学原理及其应用 [M].北京:科学出版社,2009:2—18. [12] BITANSKY N,CANETYI 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— 2】9. 


本文标签: 密钥 混淆 密码 对称 方案