（系统理论专业论文）匿名口令基密钥交换协议和可净化数字签名的研究.pdf

2 01 1m a s t e rt h e s i s 删涨 s c h o o lc o d e ：10 2 6 9 s t u d e n tn u m b e r ：5 1 0 8 1 2 0 1 0 0 1 e a c 皿n an r m a l u n 姗r v r e s e a r c ho na n o n y m o u s p a s s w o r d b a s e da u t h e n t i c a t e d k e ye x c h a n g e p r o t o c o l sa n ds a n i t i z a b l e s i g n a t u r e s d e p a n m e n t ：s c h o ! 12 11 呈垫竺兰皇! ! 墅! ! 竺型里塑! ! ! 型一 d e p a n m e n to fc o n l p u t e rs c i e n c ea n dt 色c h n o l o g y 。二= 。一 m a j o r ： s u b j e c t ： t u t o r ： a u t l l o r ： 2 0 11 5 拿 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文匿名口令基密钥交换协议和可净化数字签名的研 究，是在华东师范大学攻读甄正博士( 请勾选) 学位期间，在导师的指导下进行的研究 工作及取得的研究成果。除文中已经注明引用的内容外，本论文不包含其他个人已经发表 或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均己在文中作了明确说 明并表示谢意。 位期 作者签名： 日期沙i1 年了月弓，日 华东师范大学学位论文著作权使用声明 大学所有本人同意华东师范大学根据相关规定保留和使用此学位论文，并向主管部门和 相关机构如国家图书馆、中信所和“知网”送交学位论文的印刷版和电子版；允许学位论 文进入华东师范大学图书馆及数据库被查阅、借阅；同意学校将学位论文加入全国博士、 硕士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编出版，采用影印、缩 印或者其它方式合理复制学位论文 本学位论文属于( 请勾选) () 1 经华东师范大学相关部门审查核定的“内部”或“涉密”学位论文+ ，于 年月，日解密 己；2 不保密 导师签 ，解密后适用上述授权。 本人签名： d 卅年盯3 1 日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学位论文( 需 附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未经上述部门审定的学位论文均 为公开学位论文此声明栏不填写的，默认为公开学位论文，均适用上述授权) 巩俊卿硕士学位论文答辩委员会成员名单 姓名职称单位备注 顾国庆研究员华东师范大学 主席 王新伟副教授华东师范大学 柳银萍 副教授华东师范大学 一 摘要 在当今的互联网中，( 对身份和内容的) 认证是一个基本的安全需求本文研究两类 特殊的认证技术，即匿名口令基密钥交换协议和可净化数字签名方案 口令基密钥交换协议允许协议双方通过共享的口令完成相互认证并协商一个安全的 会话密钥而匿名口令基密钥交换协议是一个具有用户匿名性的口令基密钥交换协议即 使是服务器也无法从认证过程中获取用户的身份信息针对现有协议4 i 够实用的问题，我们 首先利用同态加密方案构造个通用设备辅助的协议该协议在服务器( 计算和通信) 资 源消耗量和用户友好性之间达到了一个较好的平衡点，因而较以往的协议更为实用在此 基础上，我们还给出了一个扩展的协议该协议不需要任何额外设备的辅助，因此具有更好 的用户友好性尽管用户友好性的提升以公共参数数量增加为代价，但是该扩展协议在用 户存储空间充裕或口令空间较小的情况下依然可行。 可净化数字签名是一种特殊的数字签名技术，其允许签名者在对消息进行签名时指派 一个净化者该净化者可以对签名后的消息进行预先定义的修改操作本文首先对b r z u s l ( a 等人和c a n a r d 等人提出的两个方案进行密码分析我们将分别描述具体的攻击方法以证 明这两个方案不满足签名者可审计性然后，我们对上述两个方案进行改进以修补其安全 漏洞并同时获得较高的计算效率和较短的签名改进后的方案仍然沿用b r z u s k a 等人和 c a n a r d 等人的框架，即仍然采用变色龙哈希函数来构造方案在b r z u s l ( a 等人和c a n a r d 等 人提出的方案中，基本算法的计算代价和签名长度与可修改子消息或者实际修改子消息的 数量成正比相比之下，在我们的改进方案中，基本算法计算代价和签名长度不但较小而且 为常数这使得我们的方案具有更好的计算效率和反应速度，并且节省存储空间 关键词：口令，密钥交换，用户匿名性，数字签名，变色龙哈希，可净化数字签名 a b s t r a c t i nt o d a y si n t e m e t ，( i d e n t i t y 觚dc o n t e n t ) a u t h e n t i c a t i o ni saf u n d a m e n t a ls e c u n 哆r e q u l r e m e n t i nm i sp a p e r w ef o c u so nt w os p e c i a la u t h e n t i c a t i o nt e c h m q u e s ，m e ya r ea n o n y m o u sp a s s w o r db a s e da u t l l e n t i c a t e dk e ye x c h a l l g ep r o t o c o l sa i l ds a n i t i z a b l es i g n a t u r e s p a s s w o r db a s e da u t l l e n t j c a t e dk e ye x c h a n g ep r o t o c 0 1 sa l l o wt l l ep a r t i c i p a n t st oa u t h e n n c a t e e a c h0 t h e r 柚de s t a b l i s has e c u r es e s s i o nk e yu s i n gt h e i rp r e s h 删p a s s w o r d a n o n y m o u sp a s s w o r db a s e da u t l l e n t i c a t e dk e ye x c h a n g ep r o t o c 0 1 sa r ep a s s w o r db a s e da u t h e n t i c a t e dk e ye x c h a n g e p r o t o c o l sw i mc l i e n ta n o n y m i t y ，w h e r ee v e ns e n ，e rc a n n o te x t r a c tt h ei d e n d t yi n f o 珊a t i o no ft h e c l i e n tf j r o mp r o t o c 0 1e x e c u t i o n s i no r d e rt os o l v et h ei s s u et h a te x i s t i n gp r o t o c o l sa r en o tp r a c 。 t i c a le n o u g h ，w ef l r s tc o n s t m c tag e n e r i c - d e v i c e - a i d e dp r o t o c o lu s i n gh o m o m o 叩l l i ce n c r ) r p t l o n s t h i sp m t o c o lf i n d sag o o db a l a n c ep o i n tb e t w e e n ( c o m p u t a t i o na n dc o m m u m c a t l o n ) r e s o u r c e c o n s u m p t i o na n du s e r 硒e n d l i e n s s ，a i l dm u sm o r ep r a c t i c a lt h a np r i o ro n e s b a s e do nn l i sb a s i c p r o t o c o l ，w ea l s og i v ea ne x t e n d e dp m t o c o l ，w h i c hd on o tn e e da n ya u x i l i a d rd “i c e sa ta 1 1 ，a n d t i l e r e f o r ea c 量l i e v e sb e n e ru s e r - 衔e n d l i n e s s a l t h o u g ht h ei m p r o v 锄e n ti sa tt h ec o s to n n c r e a s l n g m en u m b e ro fp u b l i cp a r a m e t e r s ，m ee x t e n d e dp r o t o c 0 1 i ss t i l lf e a s i b l ei nm ea p p l i c a t i o n sw h e r e c l i e n t sh a v ee n o u g hm e m o r ys p a c eo rt h ep a s s w o r ds p a c ei sr e l a t i v e l ys m a l l e r s a i l i t i z a b l es i g n a t u r e sa r eas p e c i a lb n do fd i g i t a ls i g n a t u r e s ，w h i c ha 1 1 0 wt l l e 硎g i n a ls i g n e r t od e s i g n a t eas a n i t i z e ra tt h es i g n i n gs t a g e 1 飞e nt h ed e s i g n a t e ds a n i t i z e rc a nm o d i f i e dt h es i g n e d m e s s a g ei nap r e d e t e n i l i n e df a s h i o n w 色f i r s tc r y p t a n a l y z eb r z u s k a e ta 1 sa n dc a n a r de ta 1 s c o n s t l l l c t i o n s e s p e c i a l l y ，w ep o i n to u t m a tt h e ya r en o ts i g n e r - a c c o u n t a b l eb ys h o w m gc o n c r e t e a t t a c k sr e s p e c t i v e ly i 卫e nw ei m p r o v et h e i rc o n s t m c t i o n sa i m i n ga tf i x i n gt h es e c u r i t yf l a w sa i l d g a i n i n gh i 曲e rc o m p u t a t i o ne 瓶c i e n c ya n ds h o r t e rs i g n a t i l r e s o u ri m p r o v e ds c h e m e s t i l lf 0 1 1 0 w s t t l ep a r a d i g md u et ob r z u s k ae ta 1 a n dc a n a r de ta 1 ，廿1 a ti so u rs c h e m ei ss t i l lc o n s n l l c t e du s i n g c h a m e l e o nh a s h i nb r z u s k ae ta 1 sa n dc a n a r de ta 1 sc o n s t n l c t i o n s ，b o mf u n d a m e n t a la l g o d t h m s ，c o m p u t a t i o nc o s t sa i l dt h es i g n a t u r es i z ea r ep r o p o n i o n a l t ot h en u m b e r o fm o d 饰a b l eo r m o d i f i e db l o c k s b yc o n t r a s t i no u ri m p r o v e ds c h e m e ，b o t ho ft h e ma r en o to n l ys m a l l e r b u ta l s o c o n s t a n t t h i sa d v a j l t a g em a l ，e so u rs c h e m eb ea b l et op r o v i d eh 蟾h e re f ! f i c i e n c ya n dr e s p o n s e s p e e d ，a n db eh e l p f u li ns a v i n gm e m o 巧s p a c e a sw e l l k e yw o r d s ：p a s s w o r d ，k e ye x c h a n g e ，c h e n ta n o n y r n i t y ，d i g i t a ls i g n a t u r e ，c h a m e l e o nh a s h ， s a l l i t i z a b l es i g n a t u r e 第一章 1 1 1 2 1 3 1 4 第二章 2 1 2 2 2 3 2 4 2 5 第三章 3 1 3 2 3 3 3 4 3 5 第四章 4 1 4 2 4 3 4 4 4 5 目录 绪论 匿名口令基密钥交换协议 可净化数字签名 本文的工作 本文的结构 基础知识 基本概念和基本工具 口令基密钥交换协议的安全模型 匿名口令基密钥交换协议的用户匿名性。 可净化数字签名的形式化定义 可净化数字签名的安全性需求和模型 实用的匿名口令基密钥交换 方案描述 安全性分析 性能分析 扩展协议 小结 实用的可净化数字签名 两个可净化数字签名方案的密码分析 一个实用的町净化数字签名方案 安全性分析 性能分析 小绐 第五章总结和展望 5 1结论 5 2 开放问题 1 3 5 7 8 8 h 怕 侈 挖笱弘鲫 乱钔钙钉弱舛 弱弱巧 参考文献 致谢 在读期间完成的论文目录 5 7 6 3 6 4 第一章绪论弟一早三百y 匕 随着社会的信息化进程，越来越多的事务开始借助互联网运作诸如电子商务等新兴 行业的产生为日常生活提供了极大的便利然而，依赖互联网运作的模式也带米了安令 方面的挑战这在电子商务、网上银行等应用巾尤为明显其中相当晕要的一个需求就是 认证( a u t h e n t i c a t i o n ) 本文主要讨论两类特殊的认证技术一一匿名口令基密钥交换协议 ( a n o n y m o u sp a s s w o r db a s e da u t h e n t i c a t e dk e ye x c h a n g e ) 和可净化数宁签名方案( s a n i t i z a b l e s i g n a t u r e ) 前者主要用于身份认证，而后者较常用于内容认证 本章分为三个部分我们先分别介绍匿名口令基密钥交换协议和可净化数字签名方案 的相关背景和研究现状然后，我们简要介绍本文的主要工作和组织结构 1 1匿名口令基密钥交换协议 1 1 1 口令基密钥交换协议 密钥交换协议( k e ye x c h a n g ep r o t o c 0 1 ) f 2 6 】允许执行协议的双方使用共享的密钥认证 对方的身份并牛成一个安全的临时会话密钥该临时会话密钥可以用于为双方后续的通信 提供安全性保障( 包括机密性、完整性等) 在这类协议中，每个用户必须安全保存一个高 熵( h i g he n 仃o p y ) 的长期密钥( 1 0 n g t e 姗k e y ) 而在实际应用中，由于高熵的密钥不便于 记忆，所以它通常被存放在某种存储设备中如此一来，协议的安全性将很大程度上由所采 用的存储设备的安全性能决定 对这一问题的一种解决方案是使用便于记忆的、低熵( 1 0 w e n t r o p y ) 的口令( p a s s w o r d ) 做为长期密钥这样的密钥交换协议被称为口令基密钥交换协议( p a s s w o r db a s e da u m e n t i c a t e dk e ye x c h a n g ep r o t o c 0 1 ) 由于口令能够轻易地被用户记住，因而也就不需要存储设备 的协助然而，值得注意的是口令的低熵使得暴力穷举攻击( b r u t ef o r c ea t t a c k ) 成为可能 攻击者能够在较短的时间里测试所有可能的口令所以，口令基街钥交换协议在设计中要 重点防范的是离线攻击( o 昏l i n ea t t a c k ) 。即攻击者通过监听若干协议执行和离线穷举口 令破坏协议的安全性之所以要对此攻击重点防范是凶为这样的攻击不容易被服务器发现， 因而也无法采取进一步措施于此相对，口令基密钥交换协议允许出现在线攻击( o n l i n e a t t a c k ) ，即攻击者猜测口令并通过与服务器交互来验证猜测的正确性因为口令的熵较低， 所以在线攻击的成功概率不可忽略事实上，这是口令基协议同有的缺陷，任何同类协议均 无法避免这样的攻击在协议的设计中，我们要求口令基密钥交换协议的安全性与在线攻击 1 1 匿名口令基密钥交换协议第。章绪论 的次数成反比于是通过控制在线攻击的次数可以相应的提高协议的安全性较为常用的 策略有限制用户连续输入错误口令的次数这些策略可行是因为主动攻击能够被服务器察 觉，并且攻击者通过少量尝试猜对口令的概率并不大 总的米说，设计口令基密钥交换协议的目标是( 1 ) 离线攻击对攻击者没有明显的帮 助：( 2 ) 在线攻击是攻击者攻破协议安全性的唯一选择且攻击者成功的概率与在线攻击的 次数成正比事实上，这也是口令基密钥交换协议所能够达到的安全性的上限 对于口令基密钥交换协议的研究始于上世纪九十年代，b e l l o v i n 和m e r r i t t l l 2 】首先研究 了口令基密钥交换协议并提出了若干具体协议，但是他们没有给出这些协议的形式化分析 直到2 0 0 0 年，b o y k o ，m a c k e n z i e 和p a t e l f l 3 j 以及b e l l a r e ，p o i n t c h e v a l 和r o g a w a y 【1 5 j 分别提 出了用于口令基密钥交换协议安全性分析的安伞模型在此之后陆续出现了在随机预言机 模型【1 6 】下可证安全的协议【5 5 ，5 ，6 】和无随机预言机的协议【3 5 ，4 5 ，3 6 ，3 4 】除此之外，还有在通用 可组合模型【1 8 】下可证安全的协议【2 1 2 1 1 1 1 2 匿名口令基密钥交换协议 在普通口令基密钥交换协议的执行过程中，用户必须首先以明文形式向服务器表明身 份，这必然将用户的身份信息同时泄露给服务器和外部攻击者，继而允许攻击者通过记录用 户的访问历史、分析片j 户的行为模式来获取用户的隐私信息这些泄露的隐私信息可能会 给用户造成不小的困扰( 如垃圾邮件等) ，甚至被用于违法犯罪活动显然，这在实际应用 环境下是一个非常严重和棘手的问题为了解决这一问题，e t 等人删于2 0 0 5 年提出了匿 名口令基密钥交换协议( a n o n y m o u sp a s s w o r db a s e da u t l l e n t i c a t e dk e ye x c h a n g ep r o t o c 0 1 ) 的 概念该协议允许执行协议的双方认证对方的身份并生成一个安全的临时会话密钥，但不 将用户的身份信息泄露给服务器和外部攻击者事实上，服务器从认证过程中掌握的信息 仅仅是正在通信的用户是否合法，而对其具体身份一无所知我们通常将这一特性称为用 户匿名性( c l i e n ta n o n v m 时) 简单地说，匿名口令基密钥交换协议实际上是满足用户匿名 性的口令基密钥交换协议 正是由于其对用户隐私的保护，匿名口令基密钥交换协议适用于许多隐私敏感的应用 环境e t 等人【6 4 】描述了一个用于企业内部进行意见交流的系统设想某公司的经理希望 听取公司员工对于公司管理的意见以提高公司的管理水平从经理的角度考虑，他希望确 保能够获取内部员工的真实想法显然，他需要一个认证系统以确认提交意见的都是公司 的员工从员工的角度考虑，他希望向经理提出自己的看法但是又不希望因此冒犯经理所 以，匿名口令基密钥交换协议非常适合这样的场合通过协议的执行，经理与某位员工共享 一个临时会话密钥这样双方确认对方的身份且后续的交流可通过临时会话密钥进行一 定保护，而经理也不知道该员工的真实身份这样的技术有利于排除员工的顾虑从而提出 中肯的、富有建设性的意见除此之外，在线药房f 1 9 】和云计算等也是匿名口令基密钥交换 协议的重要应用环境这一协议还被用来构造更加复杂的密码学解决方案【3 0 ，3 1 | 2 l ，2 可净化数字签名第。章绪论 1 1 3匿名口令基密钥交换协议的研究现状 在文献中有两类匿名口令基密钥交换协议：仅基于口令的( p a s s w o r d o n l y ) 匿名口令 基密钥交换协议和设备辅助的( d e v i c e a i d e d ) 匿名口令基密钥交换协议前者仪要求用户 记忆口令，而后者在此基础上需要用户携带额外的辅助设备，如存储卡，智能卡等接下来， 我们分别回顾这两类协议的研究现状 仅基于口令的匿名口令基密钥交换协议第一个仅基于口令的匿名口令基密钥交换协议 由e t 等人【e ；4 】提出协议将普通的口令基密钥交换协议与高效的不经意传输协议结合来 提供密钥交换和用户匿名性在这之后，s h i n 等人【6 1 】和y a n g 等人【6 8 】提 “了各门的构造方 法这两个方案仍然沿用了e t 等人 6 4 】提出的框架我们特别指出，上述的三个方案均无 法提供良好的可扩展性( s c a l a b i l i t v ) ，它们所消耗的资源与系统中用广的数量成正比最 近。s h i n 等人f 6 2 】在提高协议执行效率方面取得了一定的进展他们提出了一个非常高效的 构造方法，其大量的计算可以离线完成，从而降低了服务器端的在线计算压力，有效地提高 了协议的执行效率此外，他们还通过使用公共白板来降低协议的通信代价值得注意的是， 其计算代价和通信代价均为常数这意味着该协议具有较好的可扩展性 设备辅助的匿名口令基密钥交换协议c h a i 等人【1 9 】最先提出了一个由智能卡辅助的匿名 口令基密钥交换协议由于该方案所需的大部分操作均为哈希操作和异或操作。所以其计算 代价较小，但是其通信代价仍然与系统中用户的数量成正比在这之后，l ( i m 等人1 4 7 】提出了 另一个由智能卡辅助的协议该协议i 一样高效且提供额外的特性一一可追踪性最近，y a n g 等人1 6 9 】提出了匿名口令认证的新方法用户在注册时从服务器处获得一个秘密的认证值并 使用其口令保护该认证值因为构造巾涉及到复杂的零知识证明，所以他们的方案显得不够 高效但是，其优势在于由口令保护的认证值可以存储于任何存储器，如移动电话，闪存和 公共目录等 从上面的介绍可以看出，这类协议还能够按照辅助设备的类型进一步细分具体地说， 前两个协议f 1 9 ，4 7 】采用的智能 属于专门设备( d e d e i c a t e dd e v i c e ) ，其需要使用专门的读卡 器且不便随意更换；而最后一个协议【6 9 】采用的是通用设备( g e n e r i cd e v i c e ) ，其仅仅要求具 有足够的存储空间，而没有其他额外的安全性要求于是，我们称前者为专门设备辅助的匿 名口令基密钥交换协议。而后者为通用设备辅助的匿名口令基密钥交换协议 1 2 可；争化数字签名 1 2 1数字签名 数字签名方案旨在保证消息内容的完整性和不可抵赖性除了签名者以外的任何人都 无法正确计算新消息的数字签名这一特性被称为不可伪造性所以，即使附带有数字签 名的消息被篡改，攻山者也无法为篡改后的消息生成可验证的数字签名因此，接收方可 3 j 2 可净化数字签名第1 章绪论 以检测消息在传送过程中是否发生异常数字签名是密码学中十分重要的研究方向之一 学术界几十年的研究贡献了许多著名的数字签名方案，如r s a 签名 5 6 】，e l g a m a l 签名【2 引， s c h n o 玎签名f 5 8 ，b l s 签名f l l f ，w a t e r s 签名f 6 5 j 等除此之外，文献中也出现了大量普通数字 签名方案的变种和扩展，如群签名【2 0 48 i ，环签名【蚓，肓签名【1 7 l ，代理签名【5 引，匿名签名f 矧， 在线离线签名【2 9 】等下而将要介绍的可净化数字签名也是数字签名方案的一个变种 1 2 2 可净化数字签名 尽管( 传统) 数字签名方案适用于许多实际应用环境，但是其严格的不可伪造性对于 某些应用环境来说过于苛刻这类应用要求不借助原始签名者的签名密钥来完成对已签名 消息的修改a t e n i e s e 等人【3 】列举了若干此类应用我们在这里仅描述其中的两个例子 首先，我们考虑一个由多媒体数据库、赞助商和用户组成的系统多媒体数据库中存放 大量的视频等资源，每当用户希望从数据库获取这些资源时，数据库将首先发送南赞助商提 供的广告假定用户希望确认广告确实f f l 赞助商提供而赞助商又希望广告的内容能够根据 用户进行一定的定制第一个要求可以通过赞助商对广告签名来解决为了在这种情况下 满足第二个要求，赞助商将对每一个用户都生成个性化的广告并签名该策略存在三个问 题：( 1 ) 赞助商将花费大量的计算资源来逐个计算个性化广告的签名：( 2 ) 多媒体数据库 将花费大量的存储资源保存每一个个性化广告的签名；( 3 ) 多媒体数据库的用户信息将泄 露给赞助商 其次，我们考虑医疗信息公开的问题主治医生为其患者生成一份电子病历并对病历签 名出于科研、统计等需求，医院可以在对病历进行匿名化等预处理后公开病历信息而在 使用这些公开数据前，确保其真实性是必不可少的因此，这又要求医院在处理病历时确保 附带的数字签名的可验证性然而，由于数字签名的彳i 可伪造性，这将要求每一名生成过病 历的医生均牵涉进病历预处理的事务当中，这无疑耗时费力 显然，传统数字签名方案在上面的两个应用中显得力不从心为了为类似的应用提供 有效的解决方案，a t e n i e s e 等人【3 】提出了可净化数字签名( s a n i t i z a b l es i g n a t u r e ) 的概念它 在提供传统的不可伪造性的同时还提供了一定的灵活性具体地说，可净化数字签名方案 允许签名者( s i g n e r ) 在生成签名时赋予某个净化者( s a i l i t i z e r ，c e n s o r ) 修改消息的权利并 严格限定其修改权限这一特殊的数字签名方案可以简单地应用到前而描述的环境中在 第一个例子中，赞助商生成一个广告模板，然后对模板进行签名并授权多媒体数据库按照客 户的信息对模板进行个性化定制这将为赞助商和多媒体数据库节省大量的资源，同时也保 护了用户信息在第二个例子中，主治医生对病历签名时授权医院对一些敏感信息进行一 定的处理那么，医院将可以在不打扰任何医生的情况下安全地公开每一份病历由此可见， 可净化数字签名为一些特殊的实际应用提供了便捷高效的解决方案 4 1 3 本文的i 作 第。章绪论 1 2 3 可净化数字签名的研究现状 在现有的文献中可以找到许多不同的可净化数字签名的定义、安全模型和具体构造方 法，如文献 1 ，8 ，2 4 ，2 5 ，3 9 ，4 0 ，4 1 ，4 2 ，4 3 ，5 0 ，5 1 ，5 2 ，5 9 ，6 0 ，6 6 它们的共同特征是允许修改 签名后的消息我们不打算详细介绍这些定义、模型和构造我们特别强调，本文中的术语 “町净化数字签名”是指由a t e n i e s e 等人在文献 3 中提出的概念 如前所述，a t e t l i e s e 等人f 3 】首先提出了可净化数字签名的概念他们描述了可净化数字 签名的基本算法并列出了五个基木的安全性需求，即不可伪造性、不可变性、透明性、保 密性和可审计性与此同时，他们还构造了第一个可净化数宁签名方案方案基于变色龙哈 希函数( c h a m e l e o nh a s h ) 【4 4 6 】构造但是，文献 3 】仅对方案的不可伪造性进行了形式化的 处理，而没有捉供针对其他四个安全性需求的形式化模型在2 0 1 0 年，该办案被证明是不 安伞的尽管如此，大部分后续的文献均采用了他们提出的基于变色龙哈希函数的框架进 行可净化数字签名方案的设计 不久之后k l o n o w s l ( i 等人在可净化数字签名的一般性定义中引入了若干个额外特 性。如限定某些修改操作的允许范闱，保证消息某些部分的一致性、限定消息的修改次数、 强透明性等他们同样没有给出完整的形式化模型，而仪仪给出具体的方案并对其进行了 一些简单的讨论 对于可净化数字签名的形式化处理始于2 0 0 9 年b r z u s k a 等人【7 】完善了可净化数字签 名的定义并提出了完整的安全模型首先，他们在原有定义中添加了两个算法一一证明算法 和仲裁算法其次，他们将可审计性详细地分为两类一一签名者可审计性和净化者可审计 性，并为所有的六个安全性需求提供了形式化的安全模型在此基础上，他们还发现了这六 个安全性需求之间的蕴含关系，即透明性蕴含保密性而可审计性蕴含不可伪造性最后，他 们在a t e n i e s e 等人【3 】方案的基础上引入了标签的概念，并在其定义的形式化模型下证明了 改进后方案的安全性 然后。c a n a r d 等人【2 2 】通过扩展b r z u s k a 等人【7 】的安全模型来形式化处理o n o w s h 等 人阻】提出的额外特性他们还使用提出的扩展模型分析l ( 1 0 n o w s l ( i 等人 4 4 】给出的具体方案 并提出了改进的版本 最近，b r z u s k a 等人【9 】又引入了一个新的安全性需求一一不可连接性，并使用群签 名【1 4 ，2 0 ，2 7 ，3 2 ，3 3 】构造了一个满足所有六个安全性需求和4 i 可连接性的新方案尽管该方案提 供了一个构造可净化数字签名方案的新框架，但是由丁使用了耗费资源较多的群签名而显 得不够高效和实用 1 3 本文的工作 本文的工作分为如下三个方面：我们首先提了一个实用的匿名口令密钥交换协议及 其扩展协议，其次我们对现有的可净化数字签名方案进行密码分析，最后我们改进现有的可 净化数字签名方案以获得一个可证安全且i 苗效实用的方案接下来，我们分别介绍这三个工 作的研究动机和研究内容 5 1 3 本文的i 作 第一章绪论 提出一个实用的匿名口令基密钥交换协议我们设想云计算非常普及的情况当某一个用 户希望利用云的强大处理能力来完成某一大型计算任务，她必须首先向服务器证明其为合 法注册的用户在这一过程中，用户显然不希望服务器识别其身份否则，服务器将能够从 用户提交的计算任务分析其隐私信息所以，用户和服务器之间应当采用匿名口令基密钥交 换协议进行身份认证和密钥交换在我们当前设想的环境下，我们需要注意以下两点首先， 每天将有大量的用户试图连接云中的服务器这要求服务器能够处理人量的认证请求所 以服务器的计算资源和通信资源的消耗量必须尽可能地减少其次，每一名用户可能需要 频繁地登录云，并且可能要求随时随地完成登录所以，服务提供商应当尽可能提供良好的 用户友好性我们在这里先给出用户友好性的粗略解释我们认为，仅基于口令的协议具有 较好的用户友好性。通用设备辅助的协议的用户友好性一般，而专用设备辅助的协议所能提 供的用户友好性较差 因此设计一个能够同时具备较低( 计算和通信) 资源消耗和较好用户友好性的协议 是有价值的而在现有的匿名口令基密钥交换协议中，m 等人【4 | 7 】提出的方案具有最小的 资源消耗量，但是它的用户友好性较差然而，与之相比，即使足仅基于口令的协议中消耗 资源最小的协议 6 2 也需要分别多耗费2 倍的计算资源和1 倍的通信资源也就是说，如 果从现有的协议中选择解决方案，那么用户友好性的提升将带来资源消耗量的急剧增大，反 之亦然所以，在现阶段构造一个能够在资源消耗量与用户友好性之问取得较好平街的协 议也具有相当的实用价值 本文将首先提出一个基于同态加密方案的通用设备辅助的协议我们的方法与y a n g 等人【6 9 】的方法类似我们的方案在资源消耗量和用户友好性之间寻找到了一个较为适中的 平衡点与文献【6 2 ，4 7 】相比，该方案的资源消耗和用户友好性均介于两者之间我们认为 我们的方案比以往的方案更加适用于需要兼顾资源消耗和用户友好性的应用环境，如之前 描述的云计算 在上述协议的基础上，我们提供一种去除协议中的通用存储设备的方法也就是说，我 们将原有的通用设备辅助的协议转化为一个仅基于口令的扩展协议特别地是，在扩展之 后。每个用户将需要记忆两个口令显然，这不会显著降低方案的用户友好性与此同时，我 们的转换方法不会增加服务器的计算和通信代价但是，系统的公共参数数量将随之增大 具体地说。公共参数的数量将与字典的大小成正比尽管如此，扩展后的方案仍然能够在存 储空间充裕或者字典较小的环境下正常工作 对现有的可净化数字签名方案进行密码分析b r z u s l ( a 等人 7 】和c a n a r d 等人【2 2 】均对 a t e i l i e s e 等人【3 】提出的方案进行了改进前者着力于在原有框架下提供更加有效的可审计 性，他们通过引入标签这一概念来区分签名者和净化者生成的签名后者在前者的基础上 提高了挣化算法的计算效率但是，本文将指出这两个方案实际上都不满足文献【7 中定义 的签名者不可伪造性为了说明这一点，我们分别描述针对这两个方案的攻击方法这两个 攻击十分相似，攻击者都是通过重用已经生成的证明信息来干扰仲裁者的判断 6 1 4 本文的结构第一章绪论 给出一个安全实用的可净化数字签名方案尽管b r z u s l ( a 等人【7 】和c a n 删等人【2 2 】的方案 均不满足签名者可审汁性，但是我们意识到两者的结合即可立即解决这一安全性问题与此 同时，我们的改进方案彳i 但通过应用上述的方法满足规定的安全性需求而且具有较高的实 用性在b r z u s k a 等人【7 】和c a n a r d 等人f 2 2 】的方案中，主要算法( 签名算法，净化算法，验证 算法) 的计算代价和签名长度均取决于可以修改的予消息的数量或者实际修改的子消息的 数量而我们的改进方案仅需要较小的常数计算代价来完成签名，净化和验证，且签名长度 也是一个较小的常数前者提供了快速稳定的算法反应速度，而后者有助于提高存储介质 的利用率并便于实现 1 4 本文的结构 本文的余下部分共包含四个章节我们在第二章中首先回顾一些本义涉及的基本概念 和基本工具。再分别介绍匿名口令基密钥交换协议和可净化数宁签名的语义和安仝性定义 第三章将描述一个实用的匿名口令基密钥交换协议及其扩展我们将给出这两个协议的详 细描述及其安伞性证明和性能分析在第四章中，我们首先对两个现有的可净化数字签名进 行密码分析，并在此基础上构造一个高效实用且可证安全的可净化数字签名方案最后一章 将总结全文并提出一些值得继续研究的课题 7 第二章基础知识 本章主要分为两个部分我们首先介绍与本文相关的密码学概念( 包括可忽略函数、 哈希函数、随机预言杌模型和若干计算性假设) ，以及本文涉及的密码学工具( 包括传统 数字签名、公钥加密方案、变色龙哈希函数、伪随机函数和伪随机生成器) 然后，我们分 别回顾匿名口令基密钥交换协议和可净化数字签名的语义和安全性定义 2 1 基本概念和基本工具 2 1 1 可忽略函数 设，( n ) 足一个函数如果对所有的多项式p d 2 可均存在整数使得不等式厂) 1 i 加f 可( n ) l 对所有的n 都成立，那么我们称函数厂( n ) 是一个可忽略函数( n e g l i g i b l e f l i n c t i o n ) 2 1 2 哈希函数和随机预言机模型 哈希函数( h a s hf u n c t i o n ) 是密码学中常用的工具而随机预言机模型( r a n d o mo r a c l e m o d e l ) 是哈希函数的理想化模型，它在密码学方案的构造和安全性分析中扮演着重要的角 色我们在本小节简要地回顾文献【4 9 】给出的相关定义和解释 哈希函数是一个确定的函数，它将任意长的比特串映射为定长比特串( 哈希值) 设 日表示一个哈希函数，其固定的输出长度用1 日l 表示我们希望日具有以下的性质： 混合变换：对于任意的输入z ，输出的哈希值日( z ) 应当和区间 o ，1 ) 1 日i 中均匀的二 进制串在计算上是不可区分的 抗碰撞攻击：对于所有的概率多项式时间攻击者么，概率p r 【( z ，可) 0 么( 日) ：日( z ) = 日( y ) 八z 引可忽略 抗原像攻击：对于所有的概率多项式时间攻击者么，概率p r k04 ( 日，可) ：= 日( z ) 】 可忽略 实用有效性：给定一个输入串z ，哈希值日 ) 的计算町以在关于z 的长度规模的低 阶多项式时问内完成 8 2 1 基本概念和基本i 具 第_ 二章基础知识 如果我们将上述混合变换的定义更改为：“对于任意的输入z ，输出的哈希值日( z ) 在 区间 o ，1 ) 俐中均匀分布”，那么我们就将该哈希函数变成了一个很强的、虚构的函数 一一随机预青机| 1 6 】随机预言机的确定性和均匀输出特性意味着随机预言机输出的熵大于 其输入的熵但是，根据香农的熵的理论，一个确定函数决不可能“放大”熵因此，在真实 的环境中不存在随机预占机 2 1 3 计算性假设 本文涉及两个密码学中常见的计算性假设：计算性d i f f i e h e l l m a j l 假设( c o m p u t a t i o n a l d i 伍e h e l l m a na s s u m p t i o n ，简称为c d h 假设) 和判定性d i 简e h e l l m a n 假设( d e c i s i o n a l d i 伯e h e l l m a na s s u m p t i o n ，简称为d d h 假设) 我们分别给出它们的描述 计算性d i 伯e - h e m a n