（计算机应用技术专业论文）uc安全理论及应用研究.pdf

山东大学硕士学位论文 摘要 随着互联网和电子商务技术的发展，人们对于网络的依赖程度逐渐增强，如 电子现金交易、电子拍卖、电子招标和电子合同的签署等。与此同时，安全性问 题成为一个不容忽视的问题。在复杂的网络和分布式环境中，单个协议显然已经 不能满足人们的需求，越来越多地需要多个协议组合在一起使用，面原来各自安 全的协议在组合以后能否保证组合协议的安全性，成为安全领域中个重要的问 题。c a n e t t i 提出的u c 安全( u n i v e r s a l l yc o m p o s a b l es e c u r i t y ，通用可复合安全) 成为解决协议组合问题的重要工具。 作为一种可证安全的方法，u c 框架中定义了一整套安全性模型来证明复杂 环境下组合协议的安全性。u c 安全采用模块化的思想，在u c 框架中，被证明 是u c 安全的协议，在复杂的网络环境中作为一个模块，与其他协议进行组合时， 不破坏组合后协议的安全性，即几个分别在u c 框架中被证明是u c 安全的协议， 组合以后仍然是安全的。 本文主要研究u c 安全的理论和应用：对现有的u c 基本框架理论及其拓展 进行深入分析，提出从参与者角度分析u c 安全；对u c 框架在安全协议中的应 用进行研究，设计并证明u c 安全的签密协议。 首先，本文详细综述了u c 框架的理论发展、现有的信任模型和应用。对 u c 基础理论进行详细分析，引出u c 定理，进而分析了j u c 和g u c 。由于朴 素模型下，许多密码学协议仍然不能被u c 安全实现。为解决这一问题，提出许 多理想化的信任模型，本文对现有的一些典型的信任模型进行深入研究。 其次，作为安全模型的一种，本文将u c 框架模型与可证安全的两种典型模 型：随机预言模型和标准模型进行对比分析，从理论和应用方面找出其中的内在 联系和区别，对协议的可证安全性有更深入的认识。此外，还首次提出从参与者 角度，对u c 理论进行讨论。首先研究了具有权重的参与者，通过给每个参与者 引入一个权重的属性，来解决参与者具有不同权重时，敌手入侵参与者的问题。 然后提出从博弈论的角度考虑，对根据自身获得利益来决定行为的理性参与者进 行了摸索。 山东大学硕士学位论文 再次，u c 安全的重要意义，迫切地要求基本的密码学协议能够在u c 框架 下安全实现，从而可以当作基本的模块在组合协议时直接使用。现在已有一些密 码学协议基于u c 框架进行设计，并证明其安全性：如加密、数字签名、零知识 证明等。本文在u c 框架下，基于k r 模型，对签密协议进行研究。根据签密协 议的安全性要求，提出签密的理想功能函数，并依此设计协议的一般化形式：随 后基于u c 安全的定义，通过模拟技术，证明所设计的一般化协议安全实现了理 想的功能函数，即此一般化协议是u c 安全的；同时，在u c 框架下对所设计协 议的存在性不可伪造进行讨论，利用反证法证明其安全性；最后，设计了一个签 密协议，满足u c 安全性。 关键词：u c ( 通用可复合) ；安全协议：可证安全：签密 i i a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ei n t e m e ta n de b u s i n e s s ，t h eh u m a ns o c i e t y s r e l i a n c eo nt h en e t w o r kg r a d u a l l yi n c r e a s e s ，s u c ha st h et r a n s a c t i o no fe - c a s h 、 e a u c t i o n 、e - b i d d i n ga n dt h es u b s c r i p t i o no fe c o n t r a c t a tt h es a n l et i m e ，s e c u r i t y i s s u e sb e c o m eap r o b l e mt h a tc a nn o tb ei g n o r e d i nc o m p l e xa n dd i s t r i b u t e dn e t w o r k e n v i r o n m e n t ，at i n g l ep r o t o c o lh a sa p p a r e n t l yb e e nu n a b l et om e e tp e o p l e sn e e d s ，a n d i ti sn e c e s s a r yt oc o m b i n em a n yp r o t o c o l s w h e t h e rt h es e c u r i t yc a nb eg u a r a n t e e d w h e nas e c u r ep r o t o c o li sc o m p o s e d 、) v i t l la na r b i t r a r ys e to fp r o t o c o l s o rm o r e g e n e m a l l yw h e nt h ep r o t o c o li su s e da sac o m p o n e n to fa na r b i t r a r ys y s t e m s ，b e c o m e s a ni m p o r t a n ti s s u ei nt h ef i e l do fs e c u r i t y c a n e t t ip r o p o s e du cs e c u r i t y ( u n i v e r s a l l y c o m p o s a b l es e c u r i t y ) a sa ni m p o r t a n tm e a n st os o l v et h ep r o b l e mo fp r o t o c o l c o m p o s i t i o n i nt h i sp a p e r ，w ef o c u so nt h er e s e a r c ho fu cf r a m e w o r kt h e o r ya n d a p p l i c a t i o n s a sam e t h o do fp r o v a b l es e c u r i t y , u cf r a m e w o r kd e f i n e sas e to fs e c u r i t ym o d e l t os o l v et h es e c u r i t yo fc o m p o s e dp r o t o c o l si nc o m p l e xn e t w o r ke n v i r o n m e n t u c s e c u r i t ya d o p t st h em o d u l a ri d e a i nt h eu cf r a m e w o r k ，a sam o d u l ei nc o m p l e x n e t w o r ke n v i r o n m e n t ，t h ep r o t o c o lp r o v e dt ob eu cs e c t l r e ，c o m b i n e d 而t lo t h e r p r o t o c o l ，d o e sn o td e s t r o yt h es e c u r i t yo fc o m p o s e dp r o t o c 0 1 t h a ti s ，t h ep r o t o c o l w h i c hi sc o m p o s e do fs e v e r a ls e p a r a t e l yu cs e c u r ep r o t o c o l si ss t i l ls e c u r e i n t h i sp a p e r , w em a i n l ys t u d yo nt w oa s p e c t so fu cs e c u r i t ya n a l y s i s ：t h eu c t h e o r ya n dt h ea p p l l i c a t i o n so fu cf r a m e w o r ko ns e c u r ep r o t o c o l s w ed e e p l ys t u d y o nt h et h eb a s i cu cf r a m e w o r ko ft h e o r ya n di t se x p a n s i o n ，p r o p o s et oa n a l y s ef r o m t h ea n g l eo ft h ep a r t i c i p a n t s ，d e s i g na n dp r o v ea l lu cs e c u r es i g n c r y p t i o np r o t o c 0 1 f r i s to fa 1 1 ，w es u m m a r i z et h ed e v e l o p m e n to fu cf r a m e w o r kt h e o r y ，t h et r u s t a s s u m p t i o n sa n dt h ea p p l i c a t i o n si nd e t a i l aad e t a i l e da n a l y s i so fu ct h e o r yi s c o n d u c t e d , a n dt h ec r i t i c a lt h e o r y u ct h e o r e mi sg o t t h ej u ca n dg u ct h e o r ya r e a l s ol i s t e d i nt h ep l a i nm o d e l ，m a n yc r y p t o g r a p h yp r o t o c o ls t i l lc a nn o tb eu c i l l 山东大学硕士学位论文 s e c u r e l yi m p l e m e n t e d i no r d e rt os o l v et h i sp r o b l e m , m u c hi d e a l i z e dm o d e l sh a v e b e e np r o p o s e d i nt h e s em o d e l s , s o m et r u s ta s s u m p t i o ni sp r o p o s e d , w h i c ha r ed e e p l y r e s e a r c h e di nt h i sp a p e r a sas e c u r i i ym o d e l ，t h eu cf r a m e w o r km o d e li sc o m p a r e dw i t ht h er a n d o m o r a c l em o d e la n dt h es t a n d a r dm o d e l i no r d e rt oh a v eam o r ei n - d e p t hu n d e r s t a n d i n g ， w ea n a l y z et h e ma n dt r yt of i n dt h ei n t r i n s i cc o n t a c ta n dd i f f e r e n c e i na d d i t i o n ，f r o m t h ep e r s p e c t i v eo fp a r t i c i p a n t s ，t h eu ct h e o r yi sf i r s td i s c u s s e d f i r s t ，t h er e s e a r c h w i t ht h ew e i g h e d p a r t i e si sd o n e w eg i v ee a c hp a r t yap r o p e r t yo fw e i g h tt os o l v et h e p r o b l e mw h e np a r t i e sh a v ed i f f e r e n tw e i g h t s ，e s p e c i a l l yw h e nt h ea d v e r s a r yc o r r u p t s t h ep a r t i e s s e c o n d l y ，f r o mt h eg a m et h e o r yp o i n to fv i e w ，w ep r o p o s e dt oc o n s i d e r t h eb e h a v i o ro fr a t i o n a lp a r t i c i p a n t sa c c o r d i n gt ot h eb e n e f i t st h e yg e t f o rt h ei m p o r t a n ts i g n i f i c a n c eo fu cs e c u r i t y , i ti su r g e n t l yr e q u i r e dt ou c s e c u r e l yi m p l e m e n tt h ec r y p t o g r a p h yp r i m i t i v ei n u cf r a m e w o r k ，w h i c hc a r lb e u s e da sab a s i cm o d u l ei np r o t o c o lc o m p o s i t i o n s n o wt h e r eh a v eb e e ns o m e c r y p t o g r a p h yp r o t o c o ld e s i g n e di nu cf r a m e w o r ka n dp r o v e di t ss e c u r i t y ：s u c ha s e n c r y p t i o n ，d i g i t a ls i g n a t u r e s ，z e r o k n o w l e d g ep r o o f i nt h eu cf r a m e ，b a s e do nt h e k rm o d e l ，a ：s i g n c r y p t i o np r o t o c o li sd i s c u s s e d a c c o r d i n gt ot h es e c u r i t y r e q u i r e m e n t s o f s i g n c r y p t i o np r o t o c o l s ，t h ef u n c t i o n a l i t y i sp r e s e n t e d ，a n da g e n e r a l i z a b l ep r o t o c o li sd e s i g n e d t h ef o l l o w i n gi st h ep r o o fo fu cs e c u r i t yt h a ti s p r o v i n gt h a tt h ep r o t o c o ls e c u r e l yr e a l i z e st h ei d e a lf u n c t i o n a l i t y a tt h es a m et i m e ， t h eu cs e c u r e l ye x i s t e n t i a lu n f o r g e a b i l i t ya g a i n s tc h o s e nm e s s a g ea t t a c k si sa l s o d i s c u s s e da n di sp r o v e ds e c u r e a tl a s t ，ac o n c r e t es i g n c r y p t i o np r o t o c o li sg i v e n ， w h i c hi so fc o u r s eu cs e c u r e k e y w o r d s ：u c ( u n i v e r s a l l yc o m p o s a b i l i t y ) ；s e c u r i t yp r o t o c o l ；p r o v a b l es e c u r i t y ； s i g n c r y p t i o n i v 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 华 日 期： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：导师签名b 、孓 山东大学硕士学位论文 1 1 研究背景 第一章引言 随着网络技术和分布式系统的发展，信息交换和电子商务应用越来越普遍， 随之而来的信息安全问题日益突出。信息化程度越高，信息安全所面临的风险和 挑战越大。信息安全的目标应该是保证信息的保密性、认证性、完整性和不可抵 赖性。信息的保密性保证信息内容不被未经授权的人获取；认证性保证信息和信 息系统确实为授权者所用；完整性保证信息在传输过程中不被篡改；不可抵赖性 是防止行为人否认自己的行为。在当今信息社会，仅仅依靠物理手段或法律手段 来实现信息安全的上述目标是远远不够的，信息安全对于消息的机密性、数据的 完整性、认证和不可抵赖性提出了更高的要求。 密码学的研究为人们提供了实现信息安全的关键技术。密码学是研究通信安 全和保密的科学。1 9 世纪末2 0 世纪初，两次世界大战中对军事信息安全传输的 需要，使得密码学得到了空前的发展。1 9 7 6 年，d i f f i e 和h e l l m a n t l 】指出密码学 新方向，提出了公钥密码学的概念，此后公钥密码学在各个领域得到了广泛的应 用。 加密技术是密码学的基础和重要研究领域之一。公钥加密的主要目的之一是 提供信息的机密性，般加密方案包括三个过程：系统初始化过程、加密过程和 解密过程。系统的初始化过程产生加密方案用到的一切参数；加密过程由加密者 利用给定的加密算法对消息进行加密，产生密文：解密过程由解密者利用解密算 法对消息的密文进行解密，得到消息明文。 数字签名是实现认证、授权和不可抵赖性等要求的主要手段之一，也是现代 密码学研究的重要内容。数字签名的目的是为实体提供一种将其身份绑定到一段 信息的方法。一般数字签名方案包括三个过程：系统初始化过程、签名的产生过 程和签名的验证过程。系统的初始化过程产生数字签名方案用到的一切参数；签 名的产生过程由签名者利用给定的算法对消息产生签名：签名的验证过程由签名 的验证者利用公开的验证算法对给定消息的签名进行验证，得到签名的有效性。 安全协议是以密码学为基础的协议，它在网络和分布式系统中提供各种各样 山东大学硕士学位论文 的安全服务，有着大量的应用，起着“桥梁的作用，在信息系统安全中占据重 要的位置。安全协议的目标都与安全性有关，例如：认证主体的身份：在主体之 间分配会话密钥；实现机密性、完整性、匿名性、不可否认性等。 随着网络环境越来越复杂，单个协议已经不能满足人们的需求，往往要求多 个协议组合起来使用，这样就带了一个问题：原来各自安全的协议在组合后能否 保证组合协议的安全性。为解决上述问题，2 0 0 1 年，r a nc a n e t t i l 2 1 正式提出u c ( u n i v e r s a l l yc o m p o s a b l e ) 安全的框架，即通用可复合安全性框架，并在其中定 义了一套安全性模型来证明复杂环境下组合协议的安全性。近年来，随着密码学 研究的发展，u c 框架也不断完善，成为密码学技术中安全性证明的一个重要工 具。 1 2 本文的工作 本文对u c 安全理论的研究进展及应用进行了关注。对于包括u c 框架自身 的理论和u c 框架在各种密码学任务中的应用，如加密、签名、安全多方计算等， 进行了深入而广泛的研究，总结了各种方案当前的研究趋势和可能的研究方法及 方向，从参与者角度，对u c 框架理论进行探索，最后提出了一个可公开验证的 u c 安全的签密方案。 本文的主要工作及创新之处： l 对u c 框架的安全性理论和应用进行了广泛的研究，总结了主要的方法和 关键技术，对u c 安全的发展进行分析，提出了进一步研究需要解决的问题和在 应用方面的展望。 2 对u c 框架理论进行分析和探索，并将u c 与随机预言模型、标准模型进 行对比，分析其中的相同点和不同点，寻找u c 框架模型的特点和适用环境。此 外，还提出从参与者的角度进行分析，来拓展u c 框架的理论，主要有以下两个 方面： 1 ) 现有的u c 框架假设所有的参与者具有相同的权重，当参与者的权重 不同时，尤其在攻击者入侵参与者时，不能单以参与者的数目来衡量协议是否具 有u c 安全性，本文提出对参与者权重的分析，来解决这一问题。 2 ) 现有的u c 框架对于参与者的分类有两种：诚实参与者和恶意参与者。 2 山东大学硕士学位论文 本文引入博弈论的思想，参与者根据获取利益的多少来决定是否诚实地执行协 议。 3 本文提出一个可公开验证的u c 安全签密方案，相比以前的签密方案，该 方案具有以下特点： 1 ) 满足一个签密方案所需要的基本特性：机密性、可公开验证、不可伪 造性等。 2 ) 方案基于u c 框架，并证明其安全性，在复杂环境中，可以与其他协议 组合使用，不破坏整个系统的安全性。 1 3 本文的组织 本文首先介绍了u c 安全框架所需的预备知识。在第3 章给出了u c 安全理论 及应用的综述，在分析它们研究进展和典型方案的基础上，总结了最新的研究方 法，并提出了下一步的研究方向；第4 章从u c 框架理论出发，首先将u c 模型与 随机预言模型、标准模型进行比较分析，然后提出对参与者进行讨论，分别从参 与者的权重和诚实性上，对u c 框架理论进行了探索；第5 章提出了个可公开 验证的u c 安全签密方案；第6 章作为全文的总结，对u c 安全下一步的研究工作 进行了展望。 山东大学硕士学位论文 2 1 公钥密码学 第二章密码学基础知识 本节首先介绍公钥密码学的一般性观点，并对典型的公钥加密算法和数字签 名体制进行说明和分析。 2 1 1 公钥密码学的观点 公钥密码学，即非对称密码。它的基础主要包括公钥加密和数字签名。 在公钥加密系统中，每个实体a 有公钥e 和相对应的私钥d 。在安全系统 中，给定e 来计算d 在计算上是不可行的。公钥公开，私钥保密，事实上，只要 公钥的真实性能保证a 的确是唯一知道相应私钥的一方，我们就可以广泛的使 用它。该系统的一个主要优点是：提供可信公钥比在对称密钥系统中安全分发秘 密密钥通常要容易一些。公钥加密的主要目的之一是提供机密性或私密性。由于 a 的加密变换是公开的，公钥加密本身并不提供数据源认证和数据完整性。这种 保证需要使用额外的技术来提供，包括数字签名等。公钥加密方案与对称加密算 法相比，实质上要慢一些。因此，公钥加密在实际应用中用于密钥的传输，该密 钥随后用于对称算法的成批数据加密以及其他应用，如数据完整性和认证、加密 小数据项目( 如信用卡账号和p i n ) 。 数字签名在i s 0 7 4 9 8 2 标准中定义为：“附加在数据单元上的一些数据，或 是对数据单元所作的密码变换，这种数据和变换允许数据单元的接收者用以确认 数据单元来源和数据单元的完整性，并保护数据，防止被人( 例如接收者) 进行 伪造”。数字签名是目前电子商务、电子政务中应用最普遍、技术最成熟的、可 操作性最强的一种电子签名方法。它采用了规范化的程序和科学化的方法，用于 鉴定签名人的身份以及对一项电子数据内容的认可。它还能验证出文件的原文在 传输过程中有无变动，确保传输电子文件的完整性、真实性和不可抵赖性，它最 重要的一个应用是在大型网络的公钥证书中。 4 山东大学硕士学位论文 2 1 2 典型的公钥加密体制 1r s a 加密体制 r s a 为目前最著名的公钥密码算法，由m i t 的学者r i v e s t 、s h a r n i r 与 a d l e m a n l 3 1 于1 9 7 8 年提出。r s a 密码系统可作为加解密、数字签名、密钥交换 等之用，其安全性是建立于大整数因子分解( f a c t o r i z a t i o n ) 的困难度。大整数因子 分解( f a c ) l h - 题_ 是指给定一大整数n 为两个大质数p 与q 的乘积，分解n 在计算 上是不可行的，此问题是一个n p c 问题。 r s a 加密体制如下： 设萨p gp 和q 是素数，肋嘏，定义胙 ( 踢a 口，a ，6 ) ：确ag 是素数，a b 毫1 ( m o d ( ( 珂) ) ) ，值疗和b 公开，值ag 和盆保密。对嚣( 马ag 岛功，定义 e k ( x ) = x 6m o d n 和 d k ( y ) = y 。m o d n 工，y z 。 2e 1 g a m a l 加密体制 e l g a m a l 为目前著名的公钥密码系统之一，是由e i c r a m a l 4 1 于19 8 5 年提出。 e 1 g a m a l 密码系统可作为加解密、数字签名等之用，其安全性是建立于离散对数 ( d i s c r e t el o g 撕m m ) 问题，即给定g ，p 与y 2 g xm o d p ，求x 在计算上是不可行的。 e 1 g a m a l 加密体制如下： 设p 是一个素数，它满足在z p 中离散对数问题是难处理的。口z ；是一个本 原元，m = z ；，s = z ：xz p _ 1 ，定义 k = ( p ，口，a ，历：= 甜4m o d p ) 值p ，口，是公开的，口是保密的。 对k = ( p ，口，口，刃和一个秘密随机数蠹z ，1 ， 定义 p k ( z ，七) = ( 少1 ，y 2 ) 其中 山东大学硕士学位论文 对y 。，y ：z ：，定义 乃= 口2 m o d p ，y 2 = x p 。m o d p 以( 乃，y 2 ) = y 2 ? ) 1m o d p 2 1 3 典型的数字签名体制 1 r s a 签名体制 r s a 签名为第一个提出具有消息恢复( m e s s a g er e c o v e r y ) 功能的数字签名。此 外，r s a 的加密与签名动作正好相反。用接收方的公钥来加密，用自己的私钥 来解密；用自己的私钥来签名，用签名者的公钥来验证签名。为了增加安全性， 消息签名前可以先经过一个单向h a s h 函数h 的转换再进行签名，亦即 j = 五( 功dm o d n 。 r s a 签名体制如下： 设n = p q , p 和9 是素数，朋嘏，定义胙 ( 马1 9 , 仍县功：确1 9 , q 是素数，a b 三1 ( n l o d ( 矽( 疗) ) ) ，值力和b 公开，值a9 和占保密。对胙( 马b 仍 a ，功，定义 s 辔置( z ) = x 4m o d n 和 v e t k ( x ，y ) = t r u e c ，x 毫y 6r o o d nx , y z 。 2e i g a i n l 签名体制 为了避免选择密文攻击，e i g a m a l 方法子签名消息时用h ( m ) 取代m 。与r s a 方法比较，e 1 g a m a l 方法具有以下优点：i ) 系统不需要保存秘密参数，所有的系 统参数均可公开；i i ) 同一个明文在不同的时间由相同加密者加密会产生不同的 密文( 机率式密码系统) ，但e 1 g a m a l 方法的计算复杂度比r s a 方法要大。 e 1 g a m a l 签名体制如下： 设p 是一个素数，它满足在z ，中离散对数问题是难处理的。aez ：是个本 原元，m = z ；，s = z ；z ，_ l ，定义 山东大学硕士学位论文 = = = = ! = ! ! = ! m = i 二i i ：= ii i i i i = i = ! ! = ! = = = ! ! = ! ! ! ! ! = = = k = ( p ，口，a ，) ：夕= 口4r o o d p 值p ，口，是公开的，a 是保密的。 对足= ( p ，g ，a ，) 和一个秘密随机数量z ；， 定义 s i g 置“七) = ( 国 其中 y = a 七m o d p ，万= ( x a y ) k r o o d p - i 对工，厂2 ：和万z p 一1 定义 v e r k ( x ，y ，艿) = t r u e 7 y 占暮口。r o o d p 3 数字签名标准( d s s ) 1 9 9 4 年，美国联邦政府将基于有限域上的离散对数问题设计的d s a 算法采 纳为数字签名标准( d s s ) 5 1 。 数字签名标准( d s s ) 如下： 设p 是5 1 2 b i t 的素数，它满足z ，中离散对数问题是难处理的。且g 是一个整 w , p - 1 的1 6 0 b i t 的素数，口z ；是模p 的g 次单位根。m = z ；，s = z g xz g ， 定5 k = ( p ，q ，口，a ，f 1 ) ：夕= 口4m o d p ，值p ，q ，口，夕是公开的，口是保密的。 对趸= ( p ，g ，口，a ，夕) 和一个秘密随机数k ，l k g 一1 ， 定义 苫哲茁( x ，七) = ( 厂，万) 其中 y = ( 口2m o d p ) m o d q ，j = ( x + a y ) k 一1m o d q 对x z ：和y ，万z 2 ，验证是通过完成下列计算来进行的 e l5 x 6 1r o o d q e 2 = r a 一1m o d q v e r x ( x , y ，万) = t r u e ( 口 夕8 2r o o d p ) m o d q = y 7 山东大学硕士学位论文 2 2 多项式时间不可区分 u c 安全的分析、设计和证明都是通过模拟实现的，因此模拟在其中起了重 要的作用。模拟的结果又是通过多项式时间不可区分来判定的，首先给出多项式 时间不可区分的定义 6 1 ，下文的“不可区分”均为“多项式时间不可区分”。 定义1 ：总体分辨器设e = 和，p 2 ， ，e = ，e ：， 是两个总体，其中，够，p ，是 有限样本空间s 中的随机变量。记后= l o g ：券s ，设口= 口l ，口2 ，a f 是由e 或 者由f 生成的随机变量，联于椭多项式有界。 ( e ，f ) 的分辨器d 是一个概率算法，在关于朋勺多项式时间内终止，其输出 属于 0 ，1 ) ，满足( i ) d ( 口，e ) = l 当且仅当a n e 产生； ( i i ) d ( 口，e ) = 1 且仅当a 由e 产生。 称d 以优势a d v 0 区分( e ，f ) ，如果 么咖0 ) 爿p r d ( 口，e ) = l 卜p r 【d ( 口，e ) = l 】 定义2 ：多项式时间不可区分 设总体( ，f ) 和安全参数触口定义l 。如果对于所 有充分大的圾关于坏可忽略的优势a d v 0 ，不存在( e ，f ) 的分辨器， 则e ，e 称为是多项式不可区分的。 在计算复杂性理论中，广泛认为下述假设是合理的。 假设：一般不可区分性假设存在多项式不可区分总体。 总体e ，e t 被认为是多项式不可区分的，换句话说，如果给定多项式个整数， 它们或者都是由e 产生，或者都是由f 产生，即使用最好的算法作为分辨器， 也不能区分。 对许多密码学算法和协议，多项式不可区分是一个重要的安全准则。在现代 密码学中，有许多实用方法构造有用的多项式不可区分总体。例如，伪随机数生 成器是密码学中一个重要组成部分，这种生成器生成伪随机数，它的分布完全由 一个种子确定( 即以确定的方式) 。然而，好的伪随机数生成器生成的随机数和 真随机数是多项式不可区分的，也就是说从这种生成器输出的随机变量和长度相 山东大学硕士学位论文 同的均匀随机分布串而这的分布是不可区分的。 2 3h a s h 函数 在现代密码学方案的设计中，h a s h 函数用来保障数据的完整性，h a s h 函数 通常用来构造数据的短“指纹”：一旦数据改变，指纹就不再正确。即使数据被 存储在不安全的地方，通过重新计算数据的指纹并验证指纹是否改变，就能够检 测数据的完整性。通常指纹也被成为“消息摘要”。h a s h 函数，又称散列函数或 杂凑函数，它是一个确定的函数，能将任意长度的消息映射到规定长度的消息摘 要，在数字签名方案中有着特别重要的应用。h a s h 函数h 具有以下性质： 1 混合变换对于任意的输入x ，输出的h a s h 值办( 力应当和区间 0 , 2 脾i 】中 均匀的二进制串在计算上是不可区分的。 2 抗碰撞攻击找两个输入x 和y ，且x y ，使得h ( x ) = h ( y ) ，在计算上 应当是不可行的。为使这个假设成立，要求h 的输出空间应该足够大。l h l 最小为1 2 8 ，而典型的值为1 6 0 。 3 抗原像攻击已知一个h a s h 值h ，找一个输入串局使得h = j i l ( x ) ，在计 算上是不可行的。这个假设同样也要求h 的输出空间应该足够大。 4 实用有效性给定一个输入串而h ( x ) 的计算可以在关于j 的长度规模 的低阶多项式时间内完成。 h a s h 函数的上述特性使之广泛应用于密码学中，如： 1 在数字签名中，h a s h 函数一般用来产生“消息摘要”或“消息指纹”。这 种用法是为将要签署的消息增加一个可以验证的冗余，以便这个h a s h 消息 包含可以识别的信息。 2 在具有实用安全性的公钥密码系统中，h a s h 函数被广泛地应用于实现密 文正确性验证机制。对于要获得可证明安全的抗主动攻击的加密体制来说， 这个机制是必不可少的。 3 在需要随机数的密码学应用中，h a s h 函数被广泛地用作实用的伪随机函 数。这些应用包括：密钥协商( 如两个主体将他们自己的随机种子作为h a s h 函数的输入，得到一个共享的密钥值) ，认证协议( 如协议双方通过交换某 9 山东大学硕士学位论文 些h a s h 值来证实协议执行的完整性) ，电子商务协议( 如以赌博方式实现小 额支付的聚集) ，知识证明协议( 如实现非交互式的证明) 等。 2 4 基于模拟的技术 在基于模拟的安全当中，有两个模型：协议p 运行的实际环境，其中的敌手 为a d v ；协议的理想环境，其中的模拟者为s i m 。如果这两个系统中的行为是 不可区分的，那么p 至少和具有相同的安全性。换句话说，如果a d v 攻击协议 p 不能比s i r e 攻击协议获得更多的信息，那么协议p 至少和。一样安全。 模拟的概念最早是由m i c a l i 等人在零知识证明系统中提出的用，在安全函数 计算【8 1 中也有应用。2 0 世纪9 0 年代，各种模拟的技术不断出现。 2 0 0 1 年，c a n e t t i 把它引入到u c 安全中，创建了u c 框架，并指出，u c 安全 即： v a d v s s i m v e n v ：p l i4 咖i fe n v l ls i mi i e 聆v 【9 1 简单来说，对于任意的真实环境中的协议p 和理想环境中对应的o ，如果 对于任意的敌手a d v ，存在模拟者s i m ，使得对于环境e n v 而言，p 和是不可 区分的。显然，不可区分是针对环境e n v 而言的，即环境起到了“区分器”的作 用。模拟者的描述在环境之前保证了安全性定义的可组合性，因为在不考虑协议 p 运行的环境的前提下，模拟必须成功。 1 0 山东大学硕士学位论文 3 1 研究意义 第三章u c 安全的理论及应用综述 安全协议的设计和研究工作一直以来都是人们关注的课题。严格地说，要使 得一个协议安全实现目标，需要满足两方面的要求：首先，定义合适的数学模型 来表示协议；其次，在这个模型中，将安全定义形式化。然而，这两方面的要求 都不容易实现。首先，定义的数学模型应该足够强大，能描述现实世界中各种各 样的行为；其次，安全性定义应该足够直观的描述各种情况下都要达到的目标。 从这些方面考虑，由于难以顾及各种各样复杂的情况，现在大多数的研究者在设 计安全协议的时候，为了简化，都简单地考虑单一协议的运行情况，并证明其安 全性。也就是所谓的孤立安全，即协议运行与环境隔离，仅考虑安全目标和攻击 者的能力。 为了适应更加复杂和未知的环境，单一协议的运行显然不能满足需要，一个 协议经常会多次运行在并发环境中或其他协议运行的网络环境中。由于不同密码 算法或安全协议拥有不同的孤立安全性定义模型，所以对于由若干子协议组合构 成的复杂协议，子协议的孤立安全并不能保证复杂协议的安全，这就给协议设计 带来了巨大的困难。 一种解决方法是针对具体的情况和特定的应用来定义安全模型和形式化安 全性定义。一些方案也采用这种方法来实现组合协议，如，并发零知测1 0 】、不经 意传输f 1 1 】等。但由此引起协议运行的复杂性增长，大大降低了协议的运行效率， 此外，这种解决方法仅局限于特定的应用范围，并不具有一般性。于是，迫切地 需要一种通用的体制和方法来解决在复杂、未知的环境下，协议的组合问题。 2 0 0 1 年，c a n e t t i t 2 i 首次明确提出u c 安全( u n i v e r s a l l yc o m p o s i b l es e c u r i t y ， 通用可复合安全) ，并定义框架，为密码学协议的安全定义提供了一个统一精确 的方法。u c 框架采用模块化的设计思想，使用把协议独立看待的安全定义，但 保证组合协议的安全性。也就是说，只要单一的协议在u c 框架下被证明是安全 的，那么在与其他协议组合使用时，不破坏整个系统的安全性。换句话说，如果 多个在u c 框架中被证明是安全的协议组合使用，那么组合协议仍然是u c 安全 山东大学硕士学位论文 的。 所谓通用可复合( u n i v e r s a lc o m p o s i t i o n ) 是指并发的将同一协议或不同协 议的多个实例组合在一起的操作，而满足上述组合操作的安全定义的协议都是通 用可复合安全的( u n i v e r s a l l yc o m p o s a b l es e c u r i t y ) 。 3 2 基本的u c 框架 基本的u c 框架所基于具有理想认证信道的网络环境，即通信过程保证消息 的传输，且协议有输出。u c 框架主要有三个模型组成：真实环境模型、理想过 程模型和混合模型，并通过i t m ( 交互图灵机) 系统来实现。 3 2 1i t m i t m 是一种标准的数学模型。整个系统中每个i t m 都具有如下的带：身份 带、安全参数带、随机带、输入带、输出带、输入通信带、输出通信带、工作带 和1 比特的激活状态带。 使用i t m 具有以下优点：能够很好的表示交互和计算复杂性之间的关系； 很好的融合了复杂性理论中的标准模型；形象的表示了计算机工作的方式。从以 上三点出发，选择i t m 来实现u c 框架，但只能描述低层次的编程语言，因此 可以考虑将协议以子程序库的形式来描述。 3 2 2 真实环境模型 真实环境模型中主要具有以下实体：参与者p 1 ，p n ，攻击者a ，环境机z ， 协议。所有参与者可以直接交互，每个参与者都诚实地执行协议。攻击者a 可以入侵参与者，一旦a 入侵某个参与方p ；，a 将获得p i 的内部状态( 包括私 有信息) 。上述实体分别用一个对应的i t m 来表示。 真实环境模型中协议的运行可以用图3 1 来表示： 山东大学硕士学位论文 参与方都使用相同的安全参数k 。 1 当z 不停机时，按如下运行： a ) z 被激活( 激活位设为1 ) 。除了读它自己的可读的带以外，z 访问所有参 与者和敌手a 的输出带。当z 进入停机状态或者等待状态时，激活结束。 如果z 进入等待状态，那么它一定在某个实体( 或者敌手a ，或者参与者 b ，p o ) 的输入带上写了某个值，这个实体被激活。 b ) 一旦a 被激活，它运行自己的程序，并可能在它的输出带上写新的信息。 另外，a 会执行下述行为之一： i a 能查看所有参与者的输出通信带的内容。所要求的信息就被写在它的 输入通信带上。 i i a 能把消息m 传给参与者p i 。传输m 意味着在p i 的输入通信带上写m ， 同时把p i 作为消息的发送者。 i i i a 可以入侵参与者p i 。一旦入侵，a 可以知道p i