（计算机软件与理论专业论文）可认证密钥交换研究.pdf

摘要 摘要 在信息技术和通信产业如此重要的今天，面对越来越多样化的攻击手段，如 何保证通信数据的机密性、完整性、可认证性、可授权及不可抵赖性正成为计算 机和信息安全领域越发重要的研究课题。作为目前核心技术之一的可认证密钥交 换( a u t h e n t i c a t e dk e ye x c h a n g e ，a k e ) 为通信的双方提供了两种服务。一种是 a k e 为通信双方建立会话密钥( s e s s i o nk e y ) ，即只有彼此所知的对称密钥，该 密钥用来实现接下米传输过稃中的数据机密性和数据完整性。另一种是a k e 能 使通信双方确认彼此的身份。根据认证要素不同，a k e 可分为基于口令 ( p a s s w o r d ) 、基于对称擀钥( s y m m e t r i ck e y ) 、基于公钥( p u b l i ck e y ) 和基于 混合因素等不同种类。本文研究了基于e l 令的可认证密钥交换系统( p a k e ) 和 无线网络中a k e 系统的安全性和复杂性，主要研究工作创新之处如下： ( 1 ) 完全基于口令的双服务器刈认证密钥交换系统 本文设计了一个新的完全基于口令的双服务器可认证密钥交换系统 ( p a s s w o r d o n l yt w o s e r v e ra k e ，p t a k e ) 。该系统同时克n 艮- j 传统单服务器系统 的单点失败和多服务器系统高昂的系统开销的不足。新设计的系统不但满足此类 系统的最强安全需求，即在主动攻击者( a c i t v e a d v e r s a r y ) 攻破两台服务器中的 任何一台时系统仍能抵御离线字典攻击，而且总共只需要6 次消息传输。与目前 唯一一个具有相同安全水平的系统比较，新系统的通信复杂度降低了4 0 而且计 算复杂度没有增加。本文还利用同态单向函数和同态加密机制首次提出了一个泛 型设计的p t a k e ( g e n e r i cp t a k e ) ，证明了即使在主动型攻击者控制两台服务 器中的前台服务器或者被动攻击者( p a s s i v ea d v e r s a r y ) 控制后台服务器时，该 系统仍能抵御离线宁典攻击。 ( 2 ) 对双重指数模运算快速算法的复杂度研究 双重指数模运算广泛应用丁包括上述p t a k e 在内的诸多基于数论的密码系 统中，是这些系统中开销最大的运算，它的执行效率将直接影响到整个系统的性 能。本文对当前此运算的主流快速算法进行了比较与分析，特别是利用马尔科夫 概率模型对此前认为最快的w l l c 算法进行了复杂度分析。理论分析和实验数 据表明，w l l c 算法需要的平均模乘次数为1 5 5 6 k ( 后表示指数的长度) ，修正 了原有的分析结果1 3 0 6 k 。这表明目前基于标准符号数位码的双重指数模运算算 法复杂度仍然无法降低到1 5 七次模乘运算以下。 i 摘要 ( 3 ) 匿名无线安全漫游协议 匿名无线安全漫游协议( s e c u r ew i r e l e s sr o a m i n g ，s w r ) 在帮助漫游用户 和外地服务器之间建立安全信道的同时能够保护该用户的隐私，其核心是用户以 匿名的方式与外地服务器进行可认证密钥交换。本文在已有工作的基石i | ；上提出了 更加完善的匿名s w r 安全需求，包括用户身份可认证、服务器身份可认证、安 全会话密钥的建立、向前安全性、用户匿名性和不可追踪性等。我们采用c k 模 型下的模块化构造法设计了一个完拿基于对称密钥的匿名s w r 协议。该协议仅 需要4 次消息传输，是目前同类协议中通信代价最低的。由于该协议仅需要对称 密钥加密和消息认证码而不涉及公钥基础结构( p u b l i ck e yi n f r a s t r u c t u r e ，p k i ) ，所 以计算复杂度也是已知协议中最低的。 “) 向前安全可撤回群签名机制 作为重要的密码学基础工具，可撤回群签名机制可以用来构造一种新的 a k e 以实现本地化漫游( l o c a l i z e da n o n y m o u sr o a m i n g ) 。虽然此举可以降低服 务器间通信负载，但是，群签名机制的使用会人幅度增加计算复杂度且导致用户 撤回机制过于复杂。为了降低该类协议的复杂度，本文设计了一种高效的向前安 全可撤回群签名机制。该机制的签名、验证和用户撤回计算复杂度以及群公钥长 度、用户私钥长度和签名长度均为常量级，不依赖于群中用户数量或者已撤回用 户数，是第一个常量级的可撤回群签名机制。 关键词：可认证密钥交换口令双重指数模运算无线安全漫游群签名 a b s t r a c t ab s t r a c t n o w a d a y s i n f o r m a t i o n t e c h n o l o g i e s a n dc o m m u n i c a t i o ni n d u s t r i e s p l a y i m p o r t a n tr o l e si nh u m a nc o m m u n i t y w i t ht h er a p i dd e v e l o p m e n to fv a r i o u sa t t a c k s t h r o u g hn e t w o r k ，p r o v i d i n gc o n f i d e n t i a l i t y , i n t e g r i t y , a u t h e n t i c a t i o n ，a u t h o r i z a t i o na n d n o n - r e p u t a t i o no fd a t ab e c o m e sav e r yc r i t i c a lt o p i ci nc o m p u t e rs c i e n c ea n d i n f o r m a t i o ns e c u r i t y a sak e yt e c h n o l o g y , a na u t h e n t i c a t e dk e ye x c h a n g e ( a k e ) p r o t o c o lp r o v i d e st w ok i n d so fs e r v i c e sf o rt w oc o m m u n i c a t i o np a r t i e s f i r s t , i ta l l o w s t h et w op a r t i e st oe s t a b l i s has e s s i o nk e yw h i c hi sp u r es y m m e t r i ck n o w nb ye a c h o t h e ro n l y t h ee s t a b li s h e dk e yi su s e df o rr e a l i z i n gt h ed a t ac o n f i d e n t i a l i t ya n dd a t a i n t e g r i t yi nt h ec o m i n gd a t at r a n s m i s s i o n s e c o n d ，i tp r o v i d e sam e c h a n i s mf o rt w o p a r t i e st ob ec o n v i n c e dt h a ti t i sc o m m u n i c a t i n gw i t ht h ei n t e n d e dp a r t y a c c o r d i n gt o t h ed i f f e r e n ta u t h e n t i c a t i o n f a c t o r s ，t h e r e a r es e v e r a lk i n d so fa k e ，s u c ha s p a s s w o r d o n l ya k e ( p a k e ) ，s y m m e t r i ck e yb a s e da k e ，p u b l i ck e yb a s e da k ea n d h y b r i da k e t h i sd i s s e r t a t i o nf o c u s e so nt h es e c u r i t ya n dc o m p l e x i t yi s s u e so fp a k e a n da k ef o rw i r e l e s sn e t w o r k t h em a i nw o r ka n dc o n t r i b u t i o na r es h o w na sf 0 1 1 0 w s ： ( 1 ) p a s s w o r d o n l yt w o s e r v e ra u t h e n t i c a t e dk e ye x c h a n g e ( p t a k e ) i n t h i sd i s s e r t a t i o n ，w ep r o p o s ean o v e lp t a k e i to v e r c o m e st h ed i s a d v a n t a g e o ft h ec o n v e n t i o n a ls i n g l e s e r v e rs c h e m et h a tt h es i n g l ep o i n to ff a i l u r ea sw e l la st h e d i s a d v a n t a g eo ft h em u l t i - s e r v e rs c h e m et h a tt h ee x p e n s i v es y s t e mc o s t s i tn o to n l y s a t i s f i e st h es t r o n g e s ts e c u r i t yr e q u i r e m e n tf o rp t a k et h a tt h es y s t e mi ss e c u r e a g a i n s to f f li n ed i c t i o n a r ya t t a c k se v e ni fa n yo n eo ft h et w os e r v e r si sc o r r u p t e db ya n a c t i v ea d v e r s a r y , b u ta l s oi tr e q u i r e ss i xc o m m u n i c a t i o nr o u n d so n l y n a m e l y , o u r s c h e m er e d u c e st h en u m b e ro fc o m m u n i c a t i o nr o u n d sb y4 0 w h e nc o m p a r e dw i t ho t h e r m o s te f f i c i e n ts c h e m ew h i l em a i n t a i n i n ga b o u tt h es a m ed e g r e eo fc o m p u t a t i o n a l c o m p l e x i t y f u r t h e r m o r e ，w ep r o p o s eag e n e r i cp t a k ew i t hs a t i s f y i n gt h el o w e r s e c u r i t yl e v e lf o rp t a k e t h a tt h es y s t e mi ss e c u r ea g a i n s to f f l i n ed i c t i o n a r ya t t a c k s e v e ni ft h ef r o n to n eo ft h et w os e r v e r si sc o r r u p t e db ya na c t i v ea d v e r s a r yo rt h e b a c k e n ds e r v e ri sc o r r u p t e db yap a s s i v ea d v e r s a r y ( 2 ) c o m p l e x i t ya n a l y s i so f a nf a s tm o d u l a rd u p l e x e x p o n e n t i a t i o na l g o r i t h m i i i a b s t r a c t t h ep t a k es c h e m e sm e n t i o n e da b o v ea n dm a n yo t h e re x i s t i n gc r y p t os y s t e m s r e q u i r ee f f i c i e n tm o d u l a rd u p l e x - e x p o n e n t i a t i o no p e r a t i o n s i no r d e rt om a k et h e s y s t e m sf a s ti np r a c t i c ea si t i st h em o s te x p e n s i v eo p e r a t i o n sf o rt h e m i nt h i s d i s s e r t a t i o n ，w et a r g e tt oe x a m i n et h ec o m p u t a t i o n a lc o m p l e x i t yo ft h ef a m o u sf a s t a l g o r i t h m s p a r t i c u l a r l y , w ep r o v i d eaf o r m a lc o m p l e x i t ya n a l y s i s f o rw l l c a l g o r i t h mu n d e rm a r k o vp r o b a b i l i s t i cm o d e l ，w h i c hw a sc l a i m e dt ob et h ef a s t e s t a l g o r i t h m t h ec o m p l e x i t ya n a l y s i sa n dt h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea c t u a l c o m p u t a t i o n a lc o m p l e x i t yo fw l l ca l g o r i t h ms h o u l db e1 5 5 6 kr a t h e rt h a n1 3 0 6 乞 w h e r eki st h el a r g e rb i tl e n g t ho ft h et w oe x p o n e n t s i ti m p l i e st h a tt h eb e s tm o d u l a r d u p l e x e x p o n e n t i a t i o n sa l g o r i t h mb a s e do nc a n o n i c a l - s i g h e d - d i g i tt e c h n i q u ei ss t i l l n o ta b l et oo v e r c o m et h e1 5 七b a r r i e r ( 3 ) a n o n y m o u ss e c u r ew i r e l e s sr o a m i n g ( a n o n y m o u ss w r ) i no r d e rt ob u i l das e c u r ec h a n n e lb e t w e e nt h er o a m i n gu s e ra n dt h es e r v i c e p r o v i d e rw i t hp r o v i d i n gu s e rp r i v a c y ( i e u s e ra n o n y m i t ya n du s e ru n t r a c e a b i l i t y ) ，t h e a n o n y m o u ss e c u r ew i r e l e s sr o a m i n gp r o t o c o lh a sb e e np r o p o s e d ，t h ec o r ef u n c t i o n o fw h i c hi st op r o v i d ea k eb e t w e e nt h et w op a r t i e s i nt h i sd i s s e r t a t i o n ，w ef o c u so n t h ep r o p o s a lo ft h ea l l r o u n ds e c u r i t yr e q u i r e m e n t sf o ra n o n y m o u ss w rw h i c h c a p t u r e st h ef o l l o w i n gs e c u r i t yp r o p e r t i e si n c l u d i n gm u t u a la u t h e n t i c a t i o nb e t w e e n r o a m i n gu s e ra n df o r e i g ns e r v e r , k e ye s t a b l i s h m e n ta n dk e yp r i v a c ya g a i n s tb a c k e n d s e r v e r , f o r w a r ds e c r e c y , u s e ra n o n y m i t ya n du s e ru n t r a c e a b i l i t y a n dw ep r o p o s ea p u r es y m m e t r i ck e yb a s e da n o n y m o u ss w rp r o t o c o lu s i n gt h ec km o d u l a ra p p r o a c h t ob e s to fo u rk n o w l e d g e ，i ts e e m st ob et h ef i r s tp u r es y m m e t r i ck e yb a s e d a n o n y m o u ss w r c o m p a r e dw i t ho t h e re x i s t i n ga n o n y m o u ss w rp r o t o c o l s ，b o t ho f t h ec o m p u t a t i o nc o m p l e x i t ya n dc o m m u n i c a t i o nc o m p l e x i t yo fo u rp r o t o c o la r c l o w e s t ，s i n c ei ti n v o l v e so n l y4m e s s a g ef l o w sa n dn op k i ( p u b l i ck e yi n f r a s t r u c t u r e ) b u to n l yh i g h l ye f f i c i e n tc r y p t o g r a p h i co p e r a t i o n sa r en e e d e dw h i c hi n c l u d em e s s a g e a u t h e n t i c a t i o nc o d e ( m a c ) a n ds y m m e t r i ck e ye n c r y p t i o n ( 4 ) g r o u ps i g n a t u r ew i t hf o r w a r ds e c u r er e v o c a t i o n a sa ni m p o r t a n tc r y p t o g r a p h i ct o o l ，g r o u ps i g n a t u r eh a sb e e nw i d e l ye m p l o y e d b yv a r i o u sc r y p t os y s t e m s ，e s p e c i a l l y i t i s e m p l o y e d t oc o n s t r u c tal o c a l i z e d a n o n y m o u sr o a m i n gp r o t o c o la sac o r eb u i l d i n gb l o c k a l t h o u g hf o rt h i sr o a m i n g i v a b s t r a c t p r o t o c o l ，t h ec o m m u n i c a t i o nb u r d e no ft h es e r v e r sw i l lb ea l l e v i a t e dm u c h ，t h e c o m p u t a t i o n a lc o m p l e x i t ya n du s e rr e v o c a t i o nc o m p l e x i t yw i l li n c r e a s eq u i c k l yd u et o t h eu s a g eo f g r o u ps i g n a t u r e i no r d e rt oo v e r c o m et h i sd i s a d v a n t a g e ，w ep r o p o s ea n e f f i c i e n tg r o u ps i g n a t u r ew i t hf o r w a r ds e c u r er e v o c a t i o nw i t hs a t i s f y i n gc o n s t a n t s i g n i n ga n dv e r i f y i n gc o m p l e x i t ya sw e l la sc o n s t a n ts i z ei ns i g n a t u r ep u b l i ck e ya n d s i g n i n gk e y k e yw o r d s ：a u t h e n t i c a t e dk e ye x c h a n g e ，p a s s w o r d ，d u p l e x - e x p o n e n t i a t i o n ， s e c u r ew i r e l e s sr o a m i n g ，g r o u ps i g n a t u r e v 口录 图表目录 图2 1 多服务器p a k e 架构l0 图2 2y a n g - d e n g b a op t a k e 协议15 图2 3 新的p t a k e 协议。16 图2 4 可扩展的p t a k e 架构2 0 图2 5g e n e r i cp t a k e 2 4 图3 1a m o w h e e l e rc s d b r 编码方案。3 5 图3 2 海明距离耋k 2 的k 比特数的标准符号二进制码中0 比特的平均比例 趋势图。3 9 图4 1 无线移动网络架构图4 3 图4 2j l s s i 协议4 5 图4 3j l s s i i 4 6 图4 4s y m s w r 协议4 8 图4 5 基于对称密钥的m t - a u t h e n t i c a t o r 5 2 图4 6 改进的基于计数器的一次性m t - a u t h e n t i c a t o r 5 3 图4 7 全新的基于计数器的一次性m t - a u t h e n t i c a t o r 5 3 图4 8a m 下的s w r 协议5 6 图4 9u m 下的s w r 协议5 7 图5 1 构造知识签名f 6 5 图5 2 构造知识签名k 6 5 表2 1p t a k e 的安全需求1 2 表2 2y a n g d e n g b a o 协议中相关符号说明1 3 表2 3 第一个构造模块15 表2 4 第二个构造模块。l5 表2 5p t a k e 性能对比19 表2 6g e n e r i cp t a k e 符号说明2 3 表3 1 各种双重指数模运算算法复杂性比较3 0 表3 2 复数编码。3l i x 口录 表3 3w l l c 算法3 2 表3 4d j m i i 算法3 4 表3 5 状态定义及转换关系3 5 表3 6 海明距离耽的k 比特数的标准符号二进制码巾0 比特的平均比例 3 9 表4 1j l s s i 协议符号说明4 4 表4 2s y m s w r 协议符号说明一4 7 表4 3 漫游协议性能比较5 9 x 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：么龇 签字日期： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权巾国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中国学 位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 泓开口保密( - 年) 作者签名：墓区塑邑 导师签名： 签字日期： 笫l 章绪论 1 1 研究背景及意义 第1 章绪论 随着人类社会进入信息时代，信息的网络化数字化极大地促进了社会的发展 并改善了人们的生活。i 司时各种网络攻击手段的不断涌现对数据安全构成了严重 的威胁。由于数据通过有线或者无线网络传输，攻击者很容易通过偷听、截获、 篡改、延迟发送等手段进行窃取秘密信息，冒充合法用户入侵信息系统窃取资料 或者进行系统破坏等非法行动。数据安全主要涉及以下几个方面：机密性、可认 证性、完整性及不可抵赖性。机密性是保障传输的数据内容不会被合法接受者以 外的人获得。可认证性是保证数据的接收方能确认数据的真实来源。完整性是保 证数据没有被篡改。不可抵赖性是防止数据发送方否认数据的发送。目前保证上 述数据安全的手段主要有以+ f j l t 中：流加密，对称密钥分组加密、公钥加密、数 字签名、消息认证码、数宁水印、哈希值技术等。然而在需要大量数据通信时， 由于考虑到系统开销不宜过大，常见的做法是使用对称密钥进行数据加密并计算 消息认证码来保障数据安全。因此通信双方必须在数据传输之前共享这样一个对 称密钥。我们把该对称密钥的建立过程称为密钥交换( k e ye x c h a n g e ，k e ) 【1 刀。同 时通信双方在此过程中必须能够彼此确认身份并确信密钥被对方共享，这样的 k e 称为可认证密钥交换( a u t h e n t i c a t e dk e ye x c h c a n g e ，a k e ) p ，4 l 。进行认证时， 用户可以使用他所知道的( 例如口令) ，他所拥有的( 例如s i m 卡) 或者他本身 具备的( 例如虹膜、指纹) 等认证要素证明其身份。因此根据所使用的认证要素 不同，a k e 可分完全基于口令的a k e ( p a s s w o r d o n l ya k e ，p a k e ) 1 - 5 l ，基于 对称密钥的a k e 6 , 7 ( 例如使用指纹的数字化信息时) ，基于公钥的a k e s , 9 】( 例 如使用s i m 卡内的公钥时) 和混合冈素a k e m ，i l 】。同时，针对不同的应用，各 种不同的a k e 也相继出现。例如安全性要求更高时，可能就需要多因素a k e ， 即同时需要使用口令、s i m 卡、虹膜信息完成认证的a k e 。还比如在无线网络 漫游情况下，通信双方不能直接进行相互认证，这时就需要通过可信第三方帮助 完成认证，这样的a k e 称为漫游安全协议。 尽管目前已有不少关于a k e 的研究成果，但无论是相关基础研究还是各种 应用协议的研究都尚不充分。例如，基础安全模型的建立，基础工具的效率和安 第1 章绪论 全性分析还有待深入研究；a k e 目前所涉及的应用问题也远远没有满足广阔的 应用需求。综上所述，由于基础理论研究的复杂性和应用问题的多样性，可认证 密钥交换的研究尚不充分，因此还需要我们进一步的工作。 1 2 研究的问题及现状 1 2 1 完全基于口令的双服务器a k e 系统 作为应用最广泛的一类a k e 系统，完全基于u 令的可认证密钥交换系统 ( p a k e ) 允许用户使用简短的1 ：3 令完成与服务器间的相互认证和密钥交换。与基 于对称密钥的机制等其他类型的可认证密钥交换机制【卜5 】相比，p a k e 的实用性很 强，原因在于用户只需要记住较短的口令。目前普遍存在两种类型的p a k e 即单 服务器架构p a k e 和多服务器p a k e 。然而由于p a k e 系统容易遭受字典攻击 1 2 , 1 3 】，单服务器的攻破很容易造成用户1 2 令的泄露( 即单点失败i 口- j 题) 。虽然多服 务器架构克服了此问题，但由于用户需要同时和多个服务器交互导致系统开销太 大。为了兼顾安全性和性能，第三类双服务器架构的基于口令的可认证密钥交换 系统( p t a k e ) 于2 0 0 3 年由b r a i n a r d 等人提出【14 1 。作为传统单服务器架构的扩 展，双服务器架构能在健壮性和系统复杂度之问取得较好的平衡。除了用户和一 台服务器，p t a k e 还额外增设一台服务器。与用户直接通信的服务器称为业务 服务器( s e r v i c es e r v e r , s s ) ，而增设的只与s s 通信的服务器称为控制服务器 ( c o n t r o ls e r v e r , c s ) 。p t a k e 系统有许多优点非常符合实际应用。其中最重要 的优点之一是即使两台服务器中的任何一台被主动攻击者攻破时，整个系统仍能 抵御离线字典攻击。 第一个p t a k e 由b r a i n a r d 等人于2 0 0 3 年提出【1 4 】。该协议仅支持s s 服务器 对用户的单项认证。之后在此协议基础上，s z y d l o 和k a l i s k i 做出了改进【i6 i 这两 个协议的安全性虽然都基于相同的困难性假设，但后者比前者的证明更容易归约 过程也更紧凑。不过该协议同样只支持单向认证。不久，y a n g 等人提出两个新 的p t a k e t l 7 。1 8 】。然而这两个协议不满足当c s 被攻破时系统仍能抵御离线字典攻 击的安全需求。另一个问题是他们的性能都较低。当协议【1 7 l 运行时，用户需要和 s s 服务器通信4 次而且c s 服务器与s s 服务器也需要通信4 次，因此总共需要 8 次消息传输。遵照他们关于内外网络的设定( 即c s 与s s 之间属于内部网络， 用户与s s 之间为属于外部网络) ，此协议的安全性建立在如下假设，即假设主动 2 第l 章绪论 攻击者无法攻破内部网络。该假设钊。对某些应用或许是可能的，但不具有普遍性。 个获准接入c s 服务器但无权接入s s 服务器的内部成员可以与外部攻击者串 通从而成功发动离线字典攻击。该协议的另外一个诟病之处是为了确保会话密钥 的安全，两台服务器之间的信道必须保证不被监听。这又增加了该系统实际执行 过程中的额外开销。最近，同- 。研究团队又提出了新的p t a k e i i g 解决了上述两 个问题。而且该协议进一步提高了关于会话密钥的安全等级，即c s 无法计算出 s s 和用户生成的会话密钥。这是符合实际的需求，一般来说s s 是实际的服务提 供者而c s 只需要帮助完成用户认证，而没有必要让c s 知道会话密钥从而增加 c s 知道用户隐私的危险。尽管如此，该协议也将消息传输次数增加到了1 0 次。 因此，一个显而易见的问题是能否在不增加安全风险的情况下，有效的降低 p t a k e 通信代价。本文通过给出一个高效的p t a k e 肯定地回答了这个问题。新 的p t a k e 协议只需要6 次消息传输且不增加计算复杂度。 上述多个p t a k e 协议中，大量使用双重指数模运算，即给定整数彳，x ，】，和 ，计算c = a x b 7 ( m o d n ) 。作为开销最大的运算之一，该运算的执行效率将对 这些密码学系统的性能产生重要影响。该运算计算复杂度的任何改进都将直接提 高系统的整体性能。因此，本文对已提出的快速双重指数模运算算法 2 0 - 2 3 】的进行 了调查和研究。其中，最常见的是基于标准符号数二进制码( c a n o n i cs i g n e d d i g i t b i n a r yr e p r e s e n t a t i o n ，c s d b r ) 设计的算法。最近w n ，l o u ，l a i 和c h a n g 在文献 【2 4 】中提出了对d j m i i 算法的一种改进( 以下称之为w l l c 算法) ，该算法声 称将原d j m i i 所需的1 5 5 6 k 次模乘显著地减少到1 3 0 6 k 。若性能属实，该算法 将成为迄今为止最快速的双重指数模算法。本文对目前此类运算的快速算法进行 了比较与分析，特别是利用马尔科夫概率模型对目前认为最快的算法进行了复杂 度分析。通过理论证明和实验数据分析，得出该算法平均需要的模乘次数为 1 5 5 6 k ( 七表示指数的长度) ，修正了原有的分析结果1 3 0 6 k 。 1 2 2 匿名无线安全漫游 另一方面，作为a k e 一个重要的应用领域，无线漫游( w i r e l e s sr o a m i n g ) 服务允许人们不受地理位置的限制通过移动设备穿梭于不同的无线网络享受不 同服务商提供的服务。该服务已在许多系统中实现，如g s m t 2 5 1 ，3 g p p t 2 6 1 和蜂窝 ( c e l l u l a r ) 网络【2 7 1 。支持无线漫游的网络具有如下结构。包括漫游用户u ，其访 问的外地服务器v 及用户u 的隶属服务器h 。从属于h 的用户u 正漫游在由v 3u 第1 章绪论 控制的移动网络中，并期望接入v 提供的服务。其r f lu 和v 、v 和h 之间可直 接通信，u 和h 之间则不能。绝大多数漫游协议 1 6 , 2 8 - 3 5 1 均基于此结构。就安全性 来说，u 和v 必须互相进行身份认证。否则，一则用户可能在不知情的情况下 被恶意的外地服务商索取高额费用，二则外地服务商的资源也可请兽被恶意用户滥 用。另外，u 和v 之间的通信数据应该被加密，因为用户周围可能遍布着攻击 者，包括本地网络的其他用户、网络偷听者、恶意的外地服务器等。除此之外， 还需要保护漫游用户u 的隐私( 包括用户匿名性及不可追踪性) 。为解决上述所 有安全性问题，本文提出了种新的匿名无线安全漫游协议( a n o n y m o u ss 、脉) 。 它允许漫游用户与外地服务器以一种安全的方式完成相互身份认证并建立安全 的会话密钥。同时它还保证即使在所有的外地服务器串通的情况下，漫游用户的 匿名性和不可追踪性仍能得到保护。类似于有线网络的情况，最基础的任务之一 就是建立安全的信道。本文展示了建立安全信道最核心的部分即为无线网络构建 a k e 的新技术和方法。 已有许多关于匿名s w r 协议的研究【16 2 8 。3 】。第一个此类协议是由s a m f a t 等 人于1 9 9 5 年提出【l6 1 ，文中讨论了各种级别的匿名性和不可追踪性。然而当以y a n g 等人在文献【3 3 】中提出的匿名s w r 的4 个安全需求来衡量，文献【1 6 】的协议不支持 漫游用户与外地服务器之间的相互认证。v a r a d h a r a j a n 等人在文献【2 9 】巾提出了若 干匿名s w r 协议。不过文献【3 6 峙旨出这些协议不满足用户匿名性和不可追踪性， 而且该文献还指出g o 和k i m 提出的若干匿名s w r 协议 2 e l 也均不满足用户匿名 性和不可追踪性。不久前，l e e 等人在文献【3 0 】中提出了一组匿名s w r 协议。然 而这些协议不但无法抵御离线字典攻击而且不提供用户认证。在文献【) 4 j 中，j i a n g 等人提出了2 个匿名s w r 协议。然而这两个协议均不支持用户不可追踪性。本 文将在5 3 小节展示对这两个协议的攻击。由于匿名s w r 协议运行在漫游用户 的移动设备上，协议复杂度至关重要：1 ) 首先要考虑移动设备的低运算能力， 这就意味着在需要复杂计算的安全协议是不合适的【3 7 - 3 9 1 ；2 ) 相比有线网络，无 线网络的带宽较低而信道差错率较高，因此设计安全协议时应该尽量减少消息传 送次数和消息长度。在文献【3 1 4 0 】中，y a n g 等人第一次提出了满足匿名s w r 所有 安全需求的可证明安全的协议。该协议只需要4 次消息传送，然而数字证书和数 字签名的引入导致该协议计算复杂度和消息长度都大大上述其他协议。而且该协 议在多个会话同时进行时会遇到同步失败问题( 详见5 5 4 小节) 。w a n 等人提出 了另一个只需要4 次消息传输的匿名s w r 协议【4 1 1 。该协议不但计算复杂度高而 4 第l 章绪论 且对漫游用户的访问次数有限制，每当次数快达到限制时用户必须回到本地网络 与隶属服务器重新更新组别名，因此不适用于长期漫游的用户。在文献【3 3 1 中， y a n g 等人构造了一个泛型的匿名s w r ，即利用任何传统的2 参与者密钥交换协 议转换为一个匿名s w r 协议。不足之处是该协议总共需要8 次消息传送，而本 文将提出的新协议仅需要4 次。 1 2 3 向前安全可撤回群签名 近来人们提出了本地化漫游( 1 0 c a l i z e dr o a m i n g ) 的概念【4 2 4 4 】以进一步减轻 服务器问的通信负担。然而这类协议面临的最大问题是用户撤回机制( 比如由 于欠费、安全等原因，隶属服务器要求注销某一用户) 复杂且开销巨大。最近， y a n g 等人将动态群签名作为构造模块设计了一个新的匿名s w r 协议【4 2 1 。为了简 化该协议的用户撤咧机制并提高此类群签名的性能，本文研究并设计了安全且高 效的可撤回群签名机制。 主要有两类可撤回群签名机制。第一种签名 4 5 - 4 7 1 采用v l r ( v e r i f i e r - l o c a l r e v o c a t i o n ) 方法。通过设置c r l ( c e r t i f i c a t er e v o c a t i o nl i s t ) 目录登记了已被 撤回用户的信息。该信息用来在验证阶段判断签名是否是由撤回用户生成的。然 而v l r 方法的验证机制复杂度通常和被撤回用户数量成正比。第二种签名1 4 8 巧1 1 采用基