一种改进的无证书两方认证密钥协商协议

第40卷第5期计算机学报Vol. 40 No. 5 2〇17 年5月C H IN E S E J O U R N A L O F C O M P U T E R S May 2017一种改进的无证书两方认证密钥协商协议周彦伟杨波张文政2)1；)(陕西师范大学计算机科学学院西安710119)2)(保密通信重点实验室成都610041)3)(中国科学院信息工程研究所信息安全国家重点实验室北京100093)摘要在不使用双线性映射的前提下，文中提出可证安全的高效无证书两方认证密钥协商协议，并在eC K安全模型和随机谕言机模型下基于离散对数困难问题证明了文中协议的安全性和不可伪造性；与目前已有的同类协议相比，文中协议具有更高的计算效率，同时具有已知密钥安全、完美的前后向安全性、抵抗未知密钥共享和密钥泄露伪装攻击等安全属性.文中协议更适用于基于身份的公钥系统，并在带宽受限的通信环境（如无线传感器网络、八d-H〇c网络等）中具有较好的推广性.关键词无证书密钥协商；可证明安全；离散对数;无双线性映射安全模型中图法分类号TP309 DOl 号10. 11897/SP.J. 1016.2017. 01181An Improved Two-Party Authenticated CertificatelessKey Agreement ProtocolZ H O U Y a n-W e i1)，2)，3)Y A N G B o1)，2)，3)Z H A N G W e n-Z h e n g2)^ (School o f Computer Science »Shaanxi Normal University »X iyan710119)(Science and Technology on Communication Security Laboratory ^Chengdu610041)3) {.Stale K ey Laboratory o f Inform ation Security Insiiiuie o f Information Engineering »Chinese Academy o f Sciences »B eijin g100093)A b s tr a c tB ased o n d is c re te lo g a r ith m (D L)p r o b le m,th is p a p e r p ro p o s e s a s a fe ly a u th e n tic a te da n d e ffic ie n t tw o p a r ty c e rtific a te le s s k e y a g re e m e n t p ro to c o l w ith o u t u s in g th eb ilin e a r p a ir in g s,w h ic h is p ro v a b ly secu re and u n fo r g e a b ility in th e eC K s e c u rity m o d e l a n d ra n d o m o ra c le m o d e l (R O M)u n d e r th e D L a s s u m p tio n.C o m p a re d w it h o th e r s im ila r p r o to c o ls,th is one is m o ree ffic ie n t and a ls o has k n o w n k e y s e c u r it y,p e rfe c t fo r w a r d a n d b a c k w a rd s e c re c y,re s is ta n c e tou n k n o w n k e y-s h a re a tta c k s a n d k e y-c o m p ro m is e im p e rs o n a tio n a tta c k s,e tc.I t is m o re s u ita b lef o r th e id e n tity-b a s e d p u b lic k e y c r y p tog r a ph y,a n d has b e tte r p o p u la riz a tio n in th e re s tric te db a n d w id th o f th ec o m m u n ic a tio n e n v iro n m e n t(e.g.w ire le s s se n so rs n e t w o r k s,A d-H o cn e t w o r k s,e tc.).K e y w o rd s c e rtific a te le s s k e y a g re e m e n t；p r o v a b ly s e c u r ity；d is c re te lo g a r it h m；w ith o u t b ilin e a r p a ir in g；eC K s e c u rity m o d e l收稿日期：2015-10-05;在线出版日期：2016-01-18.本课题得到国家自然科学基金（61272436,61402275,61303092,61572303)、中国科学院信息工程研究所信息安全国家重点实验室开放课题（2015-M S-10)、保密通信重点实验室基金（9140C110206140C1105CI)、中央髙校基本科研业务费专项资金（GK2015CI4CI16)及陕西师范大学优秀博士论文项目（X2014YBCI1)资助.周彦伟，男，1986年生，博士研究生，主要研究方向为密码学、匿名通信技术等.E-m ail: Z yw_SnnU®丨oxm .杨波(通信作者），男，1邮3年生，博士，教授，博士生导师，陕西省“百人计划”特聘教授，主要研究领域为信息安全、密码学等.E-m ail: byang@sm . c n.张文政，男，1邮6年生，研究员，主要研究领域为信息安全等.1182计算机学报2017 年1引言公钥加密机制是信息安全领域的关键技术，然 而传统基于证书的密码体制中，由于证书保证了持 有人与公钥间的对应关系，故涉及证书的管理、颁发 和撤销等操作，导致证书的管理过程复杂且代价极 高•基于身份的公钥密码体制（Id e n tity-B a s e d P u b lic K e y C r y p to g r a p h y,I D-P K C)[1]改进 了传统公钥密 码体制中证书管理的问题.I D-P K C中由于身份信息 (如姓名、电子邮箱等)直接被作为公钥使用，使得公 钥无需与证书绑定；而用户的私钥由可信第三方密 钥生成中心（K e y G e n e ra tio n C e n te r,K G C)负责生 成，因此恶意的K G C具备伪造任意用户的合法密 文或替代用户进行解密的能力，即I D-P K C存在密 钥托管的不足，该不足制约了 I D-P K C在实际中的 应用.为了克服I D-P K C的密钥托管不足，无证书公 钥密码系统（C ertificateless P u b lic K e y C ry p to g ra p h y, C L-P K C)[2]被提出，C L-P K C中，依然存在拥有系统 主密钥的K G C，K G C根据用户的身份和系统主密 钥为用户生成部分私钥；用户基于K G C为其计算 的部分私钥和随机选取的秘密值生成完整的私钥；公钥由用户的秘密值、身份和系统参数计算得出，C L-P K C中用户参与其私钥的生成，增强了私钥生 成过程中用户的自主性，很好地解决了 I D-P K C的密钥托管问题.国内外研究者相继提出了不同的无证书两方密 钥协商协议[3_22]，其中文献[3-5]中的协议都不能抵 抗密钥泄露伪装攻击或临时私钥泄露产生的攻击，文献[6-8]分别介绍了针对上述方案的具体攻击算 法;相较于指数运算和点乘运算，双线性运算是更为 耗时的运算®，由于协议[9〜’2『21]都是基于双线性映 射构建的，因此运算量较大，均存在计算效率低的不 足；为提高协议的执行效率，无双线性运算的无证书 两方密钥协商协议％19]相继被提出，但是文献[17] 指出协议[15_16]均不安全；虽然文献[19 ]的协议相较 于其他方案而言具有较高的计算效率，但该方案的 安全性是在较弱的安全模型默B i?(m o d ifie d B e lla re-R o g a w a y)模型下进行证明的，分析发现文献[18-19] 中的协议易受到A:类敌手的伪造攻击，无法满足其 所声称的对此类敌手不可伪造性攻击的抵抗；协 议[17]是一个可证安全的无证书两方密钥协商协议，并在 eCK (extended Canetti-Krawczyk)强安全模型 下证明了方案的安全性，但该方案存在计算效率低 的不足;文献[20]提出了能同时满足前向安全性和 无密钥托管等安全属性的无证书两方密钥协商协 议，由于仅需进行1轮的消息通信，该协议的执行效 率较高；文献[21]基于数字签名技术提出了两方无 证书密钥协商协议，并分析了协议所具有的私钥泄 露安全等相关安全属性；遗憾的是文献[22]分析发 现文献[20-21]中的协议都无法满足其所声称的安 全性.由于文献[22]是从消息泄露的角度出发对文 献[20-21]进行安全性分析的；因此本文从安全模型 的敌手类型出发，在无消息泄露的前提下，基于公开 信息和敌手自身已有的攻击能力构造具体的伪造性 攻击算法，证明协议[2°]无法满足其所声称的对A类 敌手的不可伪造性，A类敌手对文献[18-19]中协议 的伪造攻击算法与文献[20]的相关算法的构造相类 似，本文以文献[20]为例详细介绍.针对现有方案[1521]所存在的不足，本文提出可 证安全的高效无证书两方认证密钥协商协议，并分 别在e C K强安全模型和随机谕言机模型下基于离 散对数困难问题的困难性证明了本文密钥协商协议 的安全性和不可伪造性；此外该协议还具有完美的 前后向安全性、抵抗重放攻击、抗伪造性攻击和无密 钥托管等安全属性，相较于现有的无证书密钥协商 协议，本文协议具有较高的计算和通信效率.2相关基础知识2.1相关困难问题离散对数（D is c re te lo g a r it h m,D L)问题.令 _P 是阶为大素数<7的循环群G的一个生成元；给定P 和cp e G，对任意未知的问题的目标是计算C.算法_4在概率多项式时间内成功解决D L问题的概率定义如下：A d v^(A)=P r[A(P,c P)=c\c e Z；J,其中概率来源于算法>4的随机选择及 <:在Z丨上的 随机选取.定义1.D L假设.对于任意的多项式时间算 法>4概率A c fo DL(_A)是可忽略的.①MIRACL. Multiprecision integer and rational arithmetic C/C H--h library, http：//indigo, ie/mscott/周彦伟等：一种改进的无证书两方认证密钥协商协议1183 5期计算性D if f ie-H e llm a(C D H)问题•令P是阶 为大素数g的循环群G的一个生成元；对于任意未 知的已知P，a P，6P e G，C D H问题的目 标为计算&P.算法>4在概率多项式时间内成功解 决C D H问题的概率定义如下：A d v C D U(y4) =P r^A i P,a P,b P)=a b P\a,b(z Z*^ ,其中，概率来源于算法的随机选择及〜6在上的随机选取.定义2.C D H假设.对于任意的多项式时间 算法>4概率/W DII(_A)是可忽略的.2.2安全属性及安全模型文献[13]详细介绍了认证密钥协商协议需满足 的协商密钥安全性、抵抗密钥泄露伪装攻击和会话 密钥托管等相关安全属性.参照文献[19]所定义的 安全模型，无证书密钥协商协议将面临两种类型的 敌手攻击，将这两种敌手分别简写为A和A n两类.A:此类敌手无法掌握系统的主密钥，但可利 用合法用户的公钥完成对密钥协商协议安全性的攻 击，即具有替换合法用户公钥的能力；则A类敌手 为恶意的用户.•A n:此类敌手可掌握系统的主密钥，但其不具 有替换合法用户公钥的能力；则类敌手为恶意的K G C.e C K安全模型[17]中将会话的相应参与者形式化 为谕言机；攻击者具有执行Sewfi?，i?eweaZ，C o rrw辦 和等询问请求的能力；并且攻击者在相应的攻 击游戏结束后输出对会话密钥的一个猜测.通过下 述敌手与挑战者间的游戏来定义密钥协商协议的安 全性；并且在该游戏中，敌手可自适应的对谕言机进 行查询.令i l f,和为第S次执行协议时的两个参与 者，其中*和_/为用户标号，即表示第z个用户r o,和第_；'个用户n v密钥协商游戏包2个阶段，在第1个阶段中，攻 击者可自适应地进彳了 Sew<i，i?ew eaZ和C o rrw外询问.相关询问的具体执行及新鲜参与者的定义详见 文献[17]，本文不再赘述.第1阶段的询问结束后，攻击者随机选取新鲜 参与者i l f,,，并对其执行T e M C ilf,,)请求，获得该请 求的相应输出消息.T扣:当i l f,是新鲜参与者时，挑战者选 取随机数6e{〇，i}，并根据6的取值返回相应的应答.若6=0,则输出相应的会话密钥；否则，输出会 话密钥空间中的一个随机值.攻击者收到(m,)询问的相应输出后，可 自适应地进行Sew<i，i?ew eaZ和C o rrw辦询问，但不 能对参与者i l f,,进行办^^/询问，不能对与£^相匹配的参与者进行只抑似/询问^也不能对参与者进行C o rrw外询问.游戏结束时，攻击者输出6'作为对随机数6的猜测，若6 =^/，则攻击者在攻击 游戏中获胜.综上所述，攻击者>4在上述攻击游戏中获胜的 优势为（是）=外[6' =6] —j，其中是是安全参数.定义3.密钥协商安全.当一个认证密钥协商 协议同时满足下述条件时，则称该协议是安全的认 证密钥协商协议.(1) 若敌手忠实地传送消息，对协议消息不任何修改，且参与者接受该会话，则参与者协商了相 同的会话密钥，并且该会话在密钥空间上服从均匀 分布；(2) 对于任意的多项式时间敌手在上述游中获胜的优势是可忽略的.3 Liu等人方案的安全性分析本节针对文献[20]所提出的方案构造具体的不 可伪造性攻击算法，证明该方案不具备其所声称的 对义:类敌手的不可伪造性.令用户A U c e和B o b分别为文献[20]中无证书 两方密钥协商方案的参与者，则A l i c e的公私钥为 〈=(i?A，X A)，S K A=(D A，:r A)〉，B o b 的公私钥 为（P K b = (R b，X b)，S K b = (D b，x b)>.A类敌手A具有替换合法用户公钥的能力，但 其不掌握系统主密钥.敌手A获悉A U c e的公钥P K A=CRA，X A)后，使用伪造公钥替代A U c e的公 钥，并生成伪造的密钥协商信息.敌手A与B o b间的具体交互过程如下所示：①A获悉A l i c e的公钥=(i?A，X A)和身份7队等信息后，计算X：； = —d+（J D A，))，其中:y为K G C计算的系统公钥；②儿使用P i C=(i?A，X；〇代替参与者A l 的原始公钥P K A=(i?A，X A)，则参与者B o b 认为1184计算 机学报2017 年A l i c e的公钥就为敌手A 按下述步骤伪装成A l i c e与参与者B o b 进行会话密钥协商：A 选取随机数计算T A=a P、// =H2(T A || J D A ||即生成签名 a 's')，将(I D A，//，S '，to )传递给 B o b .③B o b 收到消息（J D A ，//，S '，m )后，验证密钥 协商消息(V ，S ')的合法性.若合法性验证通过，则B o b 通过了对敌手A的身份合法性验证，即敌手A伪装A l i c e 成功.B o b 收到消息（J D A，//，S '，m )后，密钥协商消息的合法性验证过程如下所示：① 计算/4 =压(71^，1);② 计算 T ; = S ' (X ; +i?A + ；y //2 +) = a P =T a ；③由于n = T A ，则等式// = H2(n||J D a || m )成立，即B o b 认为签名是由A U c e 生成的合法签名.因此伪造消息通过了参与者B o b 的合法性验证，即A 类敌手A 具有伪装A U c e 的能力.由上述过程可知，敌手A 的伪造密钥协商消息通过了 B o b 的合法性验证，则A 伪装A U c e 成功.敌手A 通过B o b 的身份合法性验证后，与B o b间进行会话密钥协商，具体协商过程如下所述：B o b 选取随机数66^，计算=A(B o b 认为是与A U c e 在协商密钥），并计算：KB ,1= x b (X a +P a + T a ) = x b (a P ) =a x BP ;X B ,2 = DB (X ； +P A + TA ) = DB (a P ) = a D BP ;K b .i =b (X 'A-\-P a ~\-T a ) =b (a P ) = a b P .敌手A 收到消息（r o B ，i ?B )后，计算=i?B +^^(^^，私:^并计算：K a .i =〇.X b =a x BP =K b ,i =K i ;K a ,2 =a P B =a D BP =K b ,2=K 2 ;K a ,3 =a T B =a b P = K B,s = K S.B o b 与敌手A最终协商的会话密钥为K = H (I D a ,I D b ,X a ,X b ,T a ,T b ,K 1,K 2,K 3).综上所述，文献[20]的方案无法满足其所声称 的对A 类敌手的不可伪造性.4本文密钥协商协议本节提出可证安全的高效无证书两方认证密钥协商协议，具体细节如下所述.4.1 系统建立群G 是阶为大素数g C g 〉〗％々为安全参数）的循环群，P 是群G 的一个生成元；选择抗碰撞的单 向哈希函数f ^d C M f X G X G—$，只2:{0，1)^父{(Mf X G—S ，H :{0，1}*—{0，1}%其中 L 为用户身份标识的长度;K GC随机选择主密钥56之9%计算系统公开钥，并公开系统参数=W，G ，P p …6，执，执，H 〉，秘密保存 4.2用户密钥生成用户JA随机选取秘密值:rq6之9%计算公开参数X % =：r ro ';并发送身份标识J D ,和公开参数X% 给 K G C .给定用户的身份标识JA及公开参数Xq，K G C随机选取秘密数e z g *，并计算Y珥和：V q = （J A ，X q ，)，并通过安全信道将3^和返回给用户/认；用户J A 通过验证 等式:y r o , P +尸如A (J A ，X 珥，)是否成立，判断：V q 和的有效性；若上述等式成立， 则J A的公私钥为PK q=〉和S K q=(xid ’，yiD ’）_4.3身份认证及密钥协商用户A lic e (身份标识为J D A )与B o b (身份标识为n)B )间的消息交互及密钥协商过程如下所述：首先，A H c e 选取随机秘密数a i ，a 2分 别计算 SA = a ! 〇A + ；yA ) 1、Q a = 〇2 (X B ++)和 U a = W2 ( ，I Db，<2li 3，<22 f * );最后，A lic e 发送消息（J D A ，J DB ，U A ，SA ，QA )给 B o b .其中，B o b 收到（J D A ，J D B ，U A ，SA ，Q A )后，首先计算 f *B,l = S a (Xa"F Y a 和f *B ,2 = (A +3^ ) 1 〇A ，若有等式 u a = h 2(j d a ，^^，^^，^，。