书书书第 卷第期 年月计算机学报 收稿日期： ； 在线出版日期： 本课题得到国家自然科学基金（ ， ， ， ） 、 中国科学院信息工程研究所信息安全国家重点实验室开放课题（ ） 、 保密通信重点实验室基金（ ） 、 中央高校基本科研业务费专项资金（ ） 及陕西师范大学优秀博士论文项目（ ） 资助周彦伟， 男， 年生， 博士研究生， 主要研究方向为密码学、 匿名通信技术等 ： 杨波（ 通信作者） ， 男， 年生， 博士， 教授， 博士生导师， 陕西省“ 百人计划” 特聘教授， 主要研究领域为信息安全、 密码学等 ： 张文政， 男， 年生， 研究员， 主要研究领域为信息安全等一种改进的无证书两方认证密钥协商协议周彦伟） ，） ，）杨波） ，） ，）张文政）（ 陕西师范大学计算机科学学院西安 ）（ 保密通信重点实验室成都 ）（ 中国科学院信息工程研究所信息安全国家重点实验室北京 ）摘要在不使用双线性映射的前提下， 文中提出可证安全的高效无证书两方认证密钥协商协议， 并在犲 犆 犓安全模型和随机谕言机模型下基于离散对数困难问题证明了文中协议的安全性和不可伪造性； 与目前已有的同类协议相比， 文中协议具有更高的计算效率， 同时具有已知密钥安全、 完美的前后向安全性、 抵抗未知密钥共享和密钥泄露伪装攻击等安全属性文中协议更适用于基于身份的公钥系统， 并在带宽受限的通信环境（ 如无线传感器网络、 网络等） 中具有较好的推广性关键词无证书密钥协商； 可证明安全； 离散对数； 无双线性映射；犲 犆 犓安全模型中图法分类号 犇 犗 犐号 犃 狀犐 犿 狆 狉 狅 狏 犲 犱犜 狑 狅 犘 犪 狉 狋 狔犃 狌 狋 犺 犲 狀 狋 犻 犮 犪 狋 犲 犱犆 犲 狉 狋 犻 犳 犻 犮 犪 狋 犲 犾 犲 狊 狊犓 犲 狔犃 犵 狉 犲 犲 犿 犲 狀 狋犘 狉 狅 狋 狅 犮 狅 犾 ） ，） ，） ） ，） ，） ）（犛 犮 犺 狅 狅 犾 狅 犳犆 狅 犿 狆 狌 狋 犲 狉犛 犮 犻 犲 狀 犮 犲，犛 犺 犪 犪 狀 狓 犻犖 狅 狉 犿 犪 犾犝 狀 犻 狏 犲 狉 狊 犻 狋 狔，犡 犻犪 狀 ）（犛 犮 犻 犲 狀 犮 犲 犪 狀 犱犜 犲 犮 犺 狀 狅 犾 狅 犵 狔狅 狀犆 狅 犿犿 狌 狀 犻 犮 犪 狋 犻 狅 狀犛 犲 犮 狌 狉 犻 狋 狔犔 犪 犫 狅 狉 犪 狋 狅 狉 狔，犆 犺 犲 狀 犵 犱 狌 ）（犛 狋 犪 狋 犲犓 犲 狔犔 犪 犫 狅 狉 犪 狋 狅 狉 狔狅 犳犐 狀 犳 狅 狉 犿 犪 狋 犻 狅 狀犛 犲 犮 狌 狉 犻 狋 狔，犐 狀 狊 狋 犻 狋 狌 狋 犲 狅 犳犐 狀 犳 狅 狉 犿 犪 狋 犻 狅 狀犈 狀 犵 犻 狀 犲 犲 狉 犻 狀 犵，犆 犺 犻 狀 犲 狊 犲犃 犮 犪 犱 犲 犿 狔狅 犳犛 犮 犻 犲 狀 犮 犲 狊，犅 犲 犻 犼 犻 狀 犵 ）犃 犫 狊 狋 狉 犪 犮 狋 （ ） ， ， 犲 犆 犓 （ ） ， ， ， ， ， （ ， ， ）犓 犲 狔 狑 狅 狉 犱 狊 ； ； ； ；犲 犆 犓 引言公钥加密机制是信息安全领域的关键技术， 然而传统基于证书的密码体制中， 由于证书保证了持有人与公钥间的对应关系， 故涉及证书的管理、 颁发和撤销等操作， 导致证书的管理过程复杂且代价极高基于身份的公钥密码体制（ ， ）改进了传统公钥密码体制中证书管理的问题 中由于身份信息（ 如姓名、 电子邮箱等） 直接被作为公钥使用， 使得公钥无需与证书绑定； 而用户的私钥由可信第三方密钥生成中心（ ， ） 负责生成， 因此恶意的 具备伪造任意用户的合法密文或替代用户进行解密的能力， 即 存在密钥托管的不足， 该不足制约了 在实际中的应用为了克服 的密钥托管不足， 无证书公钥密码系统（ ， ）被提出， 中， 依然存在拥有系统主密钥的 ， 根据用户的身份和系统主密钥为用户生成部分私钥； 用户基于 为其计算的部分私钥和随机选取的秘密值生成完整的私钥；公钥由用户的秘密值、 身份和系统参数计算得出， 中用户参与其私钥的生成， 增强了私钥生成过程中用户的自主性， 很好地解决了 的密钥托管问题国内外研究者相继提出了不同的无证书两方密钥协商协议 ， 其中文献 中的协议都不能抵抗密钥泄露伪装攻击或临时私钥泄露产生的攻击，文献 分别介绍了针对上述方案的具体攻击算法； 相较于指数运算和点乘运算， 双线性运算是更为耗时的运算， 由于协议 ， 都是基于双线性映射构建的， 因此运算量较大， 均存在计算效率低的不足； 为提高协议的执行效率， 无双线性运算的无证书两方密钥协商协议 相继被提出， 但是文献 指出协议 均不安全； 虽然文献 的协议相较于其他方案而言具有较高的计算效率， 但该方案的安全性是在较弱的安全模型犿 犅 犚（ ） 模型下进行证明的， 分析发现文献 中的协议易受到犃类敌手的伪造攻击， 无法满足其所声称的对此类敌手不可伪造性攻击的抵抗； 协议 是一个可证安全的无证书两方密钥协商协议，并在犲 犆 犓（ ） 强安全模型下证明了方案的安全性， 但该方案存在计算效率低的不足； 文献 提出了能同时满足前向安全性和无密钥托管等安全属性的无证书两方密钥协商协议， 由于仅需进行轮的消息通信， 该协议的执行效率较高； 文献 基于数字签名技术提出了两方无证书密钥协商协议， 并分析了协议所具有的私钥泄露安全等相关安全属性； 遗憾的是文献 分析发现文献 中的协议都无法满足其所声称的安全性由于文献 是从消息泄露的角度出发对文献 进行安全性分析的； 因此本文从安全模型的敌手类型出发， 在无消息泄露的前提下， 基于公开信息和敌手自身已有的攻击能力构造具体的伪造性攻击算法， 证明协议 无法满足其所声称的对?类敌手的不可伪造性， ?类敌手对文献 中协议的伪造攻击算法与文献 的相关算法的构造相类似， 本文以文献 为例详细介绍针对现有方案 所存在的不足， 本文提出可证安全的高效无证书两方认证密钥协商协议， 并分别在犲 犆 犓强安全模型和随机谕言机模型下基于离散对数困难问题的困难性证明了本文密钥协商协议的安全性和不可伪造性； 此外该协议还具有完美的前后向安全性、 抵抗重放攻击、 抗伪造性攻击和无密钥托管等安全属性， 相较于现有的无证书密钥协商协议， 本文协议具有较高的计算和通信效率相关基础知识 相关困难问题离散对数（ ， ） 问题令犘是阶为大素数狇的循环群犌的一个生成元； 给定犘和犮 犘犌， 对任意未知的犮犣狇， 问题的目标是计算犮算法?在概率多项式时间内成功解决 问题的概率定义如下：犃 犱 狏（ ?）犘 狉犃（犘，犮 犘）犮犮犣狇 ，其中概率来源于算法?的随机选择及犮在犣狇上的随机选取定义 假设对于任意的多项式时间算法?概率犃 犱 狏（ ?） 是可忽略的计算机学报 年 ： 计算性 （ ） 问题令犘是阶为大素数狇的循环群犌的一个生成元； 对于任意未知的犪，犫犣狇， 已知犘，犪 犘，犫 犘犌， 问题的目标为计算犪 犫 犘算法?在概率多项式时间内成功解决 问题的概率定义如下：犃 犱 狏 （ ?）犘 狉 ?（犘，犪 犘，犫 犘）犪 犫 犘犪，犫犣狇 ，其中， 概率来源于算法?的随机选择及犪，犫在犣狇上的随机选取定义 假设对于任意的多项式时间算法?概率犃 犱 狏 （ ?） 是可忽略的 安全属性及安全模型文献 详细介绍了认证密钥协商协议需满足的协商密钥安全性、 抵抗密钥泄露伪装攻击和会话密钥托管等相关安全属性参照文献 所定义的安全模型， 无证书密钥协商协议将面临两种类型的敌手攻击， 将这两种敌手分别简写为?和? 两类?： 此类敌手无法掌握系统的主密钥， 但可利用合法用户的公钥完成对密钥协商协议安全性的攻击， 即具有替换合法用户公钥的能力； 则?类敌手为恶意的用户? ： 此类敌手可掌握系统的主密钥， 但其不具有替换合法用户公钥的能力； 则? 类敌手为恶意的 犲 犆 犓安全模型 中将会话的相应参与者形式化为谕言机； 攻击者具有执行犛 犲 狀 犱，犚 犲 狏 犲 犪 犾，犆 狅 狉 狉 狌 狆 狋和犜 犲 狊 狋等询问请求的能力； 并且攻击者在相应的攻击游戏结束后输出对会话密钥的一个猜测通过下述敌手与挑战者间的游戏来定义密钥协商协议的安全性； 并且在该游戏中， 敌手可自适应的对谕言机进行查询令犛犻，犼和犛犼，犻为第犛次执行协议时的两个参与者， 其中犻和犼为用户标号， 即表示第犻个用户犐 犇犻和第犼个用户犐 犇犼密钥协商游戏包个阶段， 在第个阶段中， 攻击者可自适应地进行犛 犲 狀 犱，犚 犲 狏 犲 犪 犾和犆 狅 狉 狉 狌 狆 狋询问相关询问的具体执行及新鲜参与者的定义详见文献 ， 本文不再赘述第阶段的询问结束后， 攻击者随机选取新鲜参与者犛犻，犼， 并对其执行犜 犲 狊 狋（犛犻，犼） 请求， 获得该请求的相应输出消息犜 犲 狊 狋（狋犻，犼） ： 当犛犻，犼是新鲜参与者时， 挑战者选取随机数犫， ， 并根据犫的取值返回相应的应答若犫， 则输出相应的会话密钥； 否则， 输出会话密钥空间中的一个随机值攻击者收到犜 犲 狊 狋（狋犻，犼） 询问的相应输出后， 可自适应地进行犛 犲 狀 犱，犚 犲 狏 犲 犪 犾和犆 狅 狉 狉 狌 狆 狋询问， 但不能对参与者犛犻，犼进行犚 犲 狏 犲 犪 犾询问， 不能对与犛犻，犼相匹配的参与者狋犻，犼进行犚 犲 狏 犲 犪 犾询问； 也不能对参与者犼进行犆 狅 狉 狉 狌 狆 狋询问游戏结束时， 攻击者输出犫 作为对随机数犫的猜测， 若犫犫 ， 则攻击者在攻击游戏中获胜综上所述， 攻击者?在上述攻击游戏中获胜的优势为犃 犱 狏?（犽）犘 狉犫 犫， 其中犽是安全参数定义 密钥协商安全当一个认证密钥协商协议同时满足下述条件时， 则称该协议是安全的认证密钥协商协议（） 若敌手忠实地传送消息， 对协议消息不做任何修改， 且参与者接受该会话， 则参与者协商了相同的会话密钥， 并且该会话在密钥空间上服从均匀分布；（） 对于任意的多项式时间敌手?在上述游戏中获胜的优势犃 犱 狏?（犽） 是可忽略的犔 犻 狌等人方案的安全性分析本节针对文献 所提出的方案构造具体的不可伪造性攻击算法， 证明该方案不具备其所声称的对犃类敌手的不可伪造性令用户 和 分别为文献 中无证书两方密钥协商方案的参与者， 则 的公私钥为犘犓犃（犚犃，犡犃） ，犛 犓犃（犇犃，狓犃） ， 的公私钥为犘犓犅（犚犅，犡犅） ，犛 犓犅（犇犅，狓犅） ?类敌手?具有替换合法用户公钥的能力， 但其不掌握系统主密钥敌手 ?获悉 的公钥犘犓犃（犚犃，犡犃） 后， 使用伪造公钥替代 的公钥， 并生成伪造的密钥协商信息敌手?与 间的具体交互过程如下所示：?获悉 的公钥犘犓犃（犚犃，犡犃） 和身份犐 犇犃等信息后， 计算犡 犃 （犚犃狔 犎（犐 犇犃，犚犃） ） ， 其中狔为 计算的系统公钥；?使用犘犓 犃（犚犃，犡 犃） 代替参与者 的原始公钥犘犓犃（犚犃，犡犃） ， 则参与者 认为期周彦伟等：一种改进的无证书两方认证密钥协商协议 的公钥就为犘犓 犃（犚犃，犡 犃）敌手?按下述步骤伪装成 与参与者 进行会话密钥协商：?选取 随 机 数犪犣狇， 计 算犜犃犪 犘、犺 犎（犜犃犐 犇犃犿） 、犛 犺 即生成签名（犺 ，犛 ） ， 将（犐 犇犃，犺 ，犛 ，犿） 传递给 收到消息（犐 犇犃，犺 ，犛 ，犿） 后， 验证密钥协商消息（犺 ，犛 ） 的合法性若合法性验证通过， 则 通过了对敌手?的身份合法性验证， 即敌手?伪装 成功 收到消息（犐 犇犃，犺 ，犛 ，犿） 后， 密钥协商消息的合法性验证过程如下所示：计算犺 犎（犐 犇犃，犚犃） ；计算犜 犃犛 （犡 犃犚犃狔 犺 犺 犘）犪 犘犜犃；由于犜 犃犜犃， 则等式犺 犎（犜 犃犐 犇犃犿）成立， 即 认为签名是由 生成的合法签名因此伪造消息通过了参与者 的合法性验证， 即?类敌手?具有伪装 的能力由上述过程可知， 敌手?的伪造密钥协商消息通过了 的合法性验证， 则?伪装 成功敌手?通过 的身份合法性验证后， 与 间进行会话密钥协商， 具体协商过程如下所述： 选取随机数犫犣狇， 计算犜犅犫 犘和犘犃犚犃狔犎（犐 犇犃，犚犃） ， 并发送消息（犐 犇犅，犚犅） 给敌手?（ 认为是与 在协商密钥） ， 并计算：犓犅，狓犅（犡 犃犘犃犜犃）狓犅（犪 犘）犪 狓犅犘；犓犅，犇犅（犡 犃犘犃犜犃）犇犅（犪 犘）犪 犇犅犘；犓犅，犫（犡 犃犘犃犜犃）犫（犪 犘）犪 犫 犘敌手?收到消息（犐 犇犅，犚犅） 后， 计算犘犅犚犅狔犎（犐 犇犅，犚犅） ， 并计算：犓犃，犪 犡犅犪 狓犅犘犓犅，犓；犓犃，犪 犘犅犪 犇犅犘犓犅，犓；犓犃，犪 犜犅犪 犫 犘犓犅，犓 与敌手?最终协商的会话密钥为犓犎（犐 犇犃，犐 犇犅，犡犃，犡犅，犜犃，犜犅，犓，犓，犓）综上所述， 文献 的方案无法满足其所声称的对?类敌手的不可伪造性本文密钥协商协议本节提出可证安全的高效无证书两方认证密钥协商协议， 具体细节如下所述 系统建立群犌是阶为大素数狇（狇犽，犽为安全参数） 的循环群，犘是群犌的一个生成元； 选择抗碰撞的单向哈希函数犎： ，犔犌犌犣狇，犎： ，犔，犔犌犣狇，犎： ，犽， 其中犔为用户身份标识的长度； 随机选择主密钥狊犣狇， 计算系统公开钥犘犘 狌 犫狊 犘， 并公开系统参数犘 犪 狉 犪 犿 狊狇，犘，犌，犘犘 狌 犫，犎，犎，犎 ， 秘密保存狊 用户密钥生成用户犐 犇犻随机选取秘密值狓犐 犇犻犣狇， 计算公开参数犡犐 犇犻狓犐 犇犻犘； 并发送身份标识犐 犇犻和公开参数犡犐 犇犻给 给定用 户 的 身 份 标 识犐 犇犻及 公 开 参 数犡犐 犇犻， 随机选取秘密数狉犐 犇犻犣狇， 并计算犢犐 犇犻狉犐 犇犻犘和狔犐 犇犻狉犐 犇犻狊 犎（犐 犇犻，犡犐 犇犻，犢犐 犇犻） ， 并通过安全信道将狔犐 犇犻和犢犐 犇犻返回给用户犐 犇犻； 用户犐 犇犻通过验证等式狔犐 犇犻犘犢犐 犇犻犘犘 狌 犫犎（犐 犇犻，犡犐 犇犻，犢犐 犇犻） 是否成立， 判断狔犐 犇犻和犢犐 犇犻的有效性； 若上述等式成立，则犐 犇犻的公私钥为犘犓犐 犇犻犡犐 犇犻，犢犐 犇犻 和犛 犓犐 犇犻狓犐 犇犻，狔犐 犇犻 身份认证及密钥协商用户 （ 身份标识为犐 犇犃） 与 （ 身份标识为犐 犇犅） 间的消息交互及密钥协商过程如下所述：首先， 选 取 随 机 秘 密 数犪，犪犣狇， 分别计算犛犃犪（狓犃狔犃）、犙犃犪（犡犅犢犅犘犘 狌 犫犺犅） 和犝犃犎（犐 犇犃，犐 犇犅，犪犘，犪犘） ； 最 后， 发送消息（犐 犇犃，犐 犇犅，犝犃，犛犃，犙犃） 给 其中，犺犅犎（犐 犇犅，犡犅，犢犅） 收到（犐 犇犃，犐 犇犅，犝犃，犛犃，犙犃） 后， 首先计算犘犅，犛犃（犡犃犢犃犘犘 狌 犫犺犃） 和犘犅，（狓犅狔犅）犙犃，若有等式犝犃犎（犐 犇犃，犐 犇犅，犘犅，犘犅，） 成立， 即 通过了 对其的身份合法性验证， 且 验证了消息的合法性， 即确认该消息是 为其发送的密钥协商消息； 否则终止对 的身份及消息合法性验证通过后， 首先 随机选取秘密数犫，犫犣狇， 分别计算犛犅犫（狓犅狔犅）、犙犅犫（犡犃犢犃犘犘 狌 犫犺犃） 和犝犅犎（犐 犇犃，犐 犇犅，犫犘，犫犘） ； 最后 发送消息（犐 犇犃，犐 犇犅，犝犅，犛犅，犙犅） 给 其中，犺犃犎（犐 犇犃，犡犃，犢犃） 计算共享秘密：计算机学报 年犓犅犫犛犃（犡犃犢犃犘犘 狌 犫犺犃） ；犓犅犫（狓犅狔犅）犙犃；犓犅犫犘（狓犅狔犅）犙犃 计算的会话密钥犓犅犃为犓犅 犃犎（犐 犇犃犐 犇犅犝犃犝犅犓犅犓犅犓犅） 收到（犐 犇犃，犐 犇犅，犝犅，犛犅，犙犅） 后， 首先计算犘犃，犛犅（犡犅犢犅犘犘 狌 犫犺犅） 和犘犃，（狓犃狔犃）犙犅， 若有等式犝犅犎（犐 犇犃，犐 犇犅，犘犃，犘犃，） 成立，即 通过了 对其的身份合法性验证， 且 验证了消息的合法性， 即确认该消息是 为其发送的密钥协商消息； 否则终止对 的身份及消息合法性验证通过后， 计算共享秘密：犓犃犪犛犅（犡犅犢犅犘犘 狌 犫犺犅） ；犓犃犪（狓犃狔犃）犙犅；犓犃犪犘（狓犃狔犃）犙犅 计算的会话密钥犓犃犅为犓犃 犅犎（犐 犇犃犐 犇犅犝犃犝犅犓犃犓犃犓犃） 正确性本节对本文密钥协商协议的正确性进行描述（） 密钥的合法性验证狔犐 犇犻犘（狉犐 犇犻犘犘 狌 犫犺犐 犇犻）犘犢犐 犇犻犘犘 狌 犫犎（犐 犇犻，犡犐 犇犻，犢犐 犇犻）其中犺犐 犇犻犎（犐 犇犻，犡犐 犇犻，犢犐 犇犻） 和狔犐 犇犻狉犐 犇犻狊 犺犐 犇犻（）身份合法性验证以 对 的身份合法性验证过程为例对验证过程进行分析：犘犃，犛犅（犡犅犢犅犘犘 狌 犫犺犅）犫（狓犅狔犅）（狓犅犘狉犅犘狊 犘 犺犅）犫犘；犘犃，（狓犃狔犃）犙犅犫（狓犃狔犃）（犡犃犢犃犘犘 狌 犫犺犃）犫犘；犝犅犎（犐 犇犃，犐 犇犅，犘犃，犘犃，）犎（犐 犇犃，犐 犇犅，犫犘，犫犘） 对 身份合法性验证过程的正确性分析与上述过程类似， 本文不在赘述（） 协商密钥的一致性 计算的共享秘密为犓犅犫犛犃（犡犃犢犃犘犘 狌 犫犺犃）犫犪（狓犃狔犃）（犡犃犢犃犘犘 狌 犫犺犃）犪犫犘；犓犅犫（狓犅狔犅）犙犃犪犫（狓犅狔犅）（犡犅犢犅犘犘 狌 犫犺犅）犪犫犘；犓犅犫犘（狓犅狔犅）犙犃犪犘犫犘 计算的共享秘密为犓犃犪犛犅（犡犅犢犅犘犘 狌 犫犺犅）犪犫犘；犓犃犪（狓犃狔犃）犙犅犪犫犘；犓犃犪犘（狓犃狔犃）犙犅犪犘犫犘则有犓犅犓犃、犓犅犓犃和犓犅犓犃； 因此犓犅 犃犓犃犅协议分析 安全性证明本节将在犲 犆 犓安全模型下对本文密钥协商协议的安全性进行证明定理 由于 问题是困难问题， 则本文协议是安全的认证密钥协商协议证明 （） 证明本文协议满足密钥协商安全定义的条件由协 议 的 正 确 性 分 析 可 知犓犅 犃犓犃 犅， 所 以 和 协商的会话密钥相等， 且相应参数的随机性确保会话密钥在密钥空间上满足均匀分布（） 证明本文协议满足密钥协商安全定义的条件声称 任意的?类概率多项式时间敌手?在游戏中获胜的优势犃 犱 狏?（犽） 是可忽略的构造解决 困难问题的模拟器?， 其输入为犮 犘犌， 对于任意未知的犮犣狇， 问题的目标是计算犮假设在攻击实验中?进行了下述操作：请求生成了狇犛个用户的私钥；执行了狇犝次密钥协商；游戏的第阶段询问中， 对狇犆（ 其中狇犛狇犆）个用户执行了犆 狅 狉 狉 狌 狆 狋询问模拟器? 任意选取随机数犑（，狇犝） ， 则犑是?猜测的在犜 犲 狊 狋询问中?要挑战的会话模拟器? 的构造如下：初始化： ? 运行犛 犲 狋 狌 狆（，狀） 算法， 发送公开参数犘 犪 狉 犪 犿 狊狇，犘，犌，犘犘 狌 犫，犎，犎，犎 给?， 其中令犘犘 狌 犫犮 犘； 同时， ? 维持列表犔犓 犌、犔犛 犓、犔犘犓、犔犛分别用于跟踪?的部分密钥生成、 私钥生成、 公钥生成和犛 犲 狀 犱询问， 初始时各列表均为空部分密钥生成询问收到?关于犐 犇犻和公开参数犡犻的部分密钥生成询问时， ? 进行下述操作：若 犐 犇犻，犡犻，犱犐 犇犻（狔犻，犢犻） ，狉犻，犜 狔 狆 犲犻犔犓 犌， 则? 返回犱犐 犇犻（狔犻，犢犻） 给?；期周彦伟等：一种改进的无证书两方认证密钥协商协议否 则，? 选 取 随 机 数犜 狔 狆 犲， ，且犘 狉犜 狔 狆 犲狇犛； 若犜 狔 狆 犲， 设置犐 犇所对应的元组为犐 犇，犡，若犔犓 犌中多个元组中的犜 狔 狆 犲或不存在犜 狔 狆 犲的元组， 但犔犓 犌的长度等于狇犛， 则? 终止模拟； 若犜 狔 狆 犲， 则随机选取狉犻犣狇， 计算犢犻狉犻犘， 选取随机数狔犻犣狇， 并添加犐 犇犻，犡犻，犱犐 犇犻（狔犻，犢犻） ，狉犻，犜 狔 狆 犲犻 到犔犓 犌中， 并返回犱犐 犇犻（狔犻，犢犻） 给?私钥生成询问收到?关于犐 犇犻的私钥生成询问时， ? 进行下述操作：若存在犐 犇犻，狓犻，狔犻犔犛 犓， ? 返回元组中相应的狓犻，狔犻 给?；否则， ? 选取随机数狓犻犣狇， 计算犡犻狓犻犘，就犐 犇犻，犡犻 进行部分密钥生成询问并获得相应的元组犐 犇犻，狔犻，犢犻 ， 添加犐 犇犻，狓犻，狔犻 到犔犛 犓中， 返回狓犻，狔犻 给?； 同时添加犐 犇犻，犡犻，犢犻 到犔犘犓中公钥生成询问收到?关于犐 犇犻的公钥生成询问时， ? 进行下述操作：若存在犐 犇犻，犡犻，犢犻犔犘犓， 则返回元组中相应的犡犻，犢犻 给?；否则， ? 随机选取狓犻犣狇， 计算犡犻狓犻犘， 就犐 犇犻，犡犻 进行部分密钥生成询问获得相应的元组犐 犇犻，狔犻，犢犻 ， 添 加 犐 犇犻，犡犻，犢犻 到犔犘犓中， 返 回犡犻，犢犻 给?； 同时添加犐 犇犻，狓犻，狔犻 到犔犛 犓中犛 犲 狀 犱（犛犻，犼，犕）列表犔犛中的元组格式为犛犻，犼，犪，犕，犕 ，犓，犛 犓 ， 其中犕 是犛犻，犼在会话过程中产生的消息，犕是犛犻，犼在会话过程中所接收到的消息，随机数犪犣狇由模拟器? 为犛犻，犼选取，犓（ 其中犓犓，犓，犓 ） 表示密钥协商过程中相应的共享秘密，犛 犓表示会话密钥， 初始时均设置犓和犛 犓为空；犚 犲 狏 犲 犪 犾询问过程中会对犔犛进行更新当? 收到犕时， 进行如下操作：若有犛犻，犼，犔犛， 且犛犻，犼是相应会话的发起者， 则? 接受该会话， 并设置犕为犛犻，犼所接收的消息； 否则，犛犻，犼不存在， 则进行公钥和私钥询问为犐 犇犻生成相应的密钥若犕， 则设置犐 犇犻为相应会话的发起者；否则， 设置犐 犇犻为相应会话的响应者， 并且将犕作为响应者犐 犇犻的输入， 同时设置犛犻，犼接受会话如果犛犑， ? 选取随机数犪，犪犣狇作为参与者犻的随机秘密数， 并初始化消息犕犝犻犎（犐 犇犻，犐 犇犼，犪犘，犪犘） ，犛犪（狓犻狔犻） ，犙犪（犡犼犢犼犘犘 狌 犫犺犼） ， 更新犔犛并返回犕； 否则犛犑， 则? 在犔犓犌中查找犐 犇犼对应的相关元组， 如果犜 狔 狆 犲， 则终止模拟； 如果犜 狔 狆 犲， 随机选择犫，犫犣狇， 并计算应答消息犕犝犼犎（犐 犇犻，犐 犇犼，犫犘，犫犘） ，犛犼犫（狓犼狔犼） ，犙犼犫（犡犻犢犻犘犘 狌 犫犺犻） ， 更新犔犛并返回犕犆 狅 狉 狉 狌 狆 狋（犻） ? 根据犐 犇犻查找犔犓犌， 若不存在相应的元组， 则进行公钥询问和私钥询问； 否则， ? 获得犔犓犌中相应的元组， 若犜 狔 狆 犲， 则终止模拟， 若犜 狔 狆 犲， 进行私钥生成询问， 并返回对应的私钥狓犻，狔犻犚 犲 狏 犲 犪 犾（犛犻，犼） ： 若犔犛中不存在犛犻，犼所对应的元组， 则? 返回； 若犛犻，犼未接受相应的会话， 则? 返回； 否则犔犛中必存在犛犻，犼所对应的元组， ? 进行下述操作犛 犓， 则返回元组中相应的犛 犓犛 犓， 若犔犓犌中不存在犐 犇犻所对应的元组， 则返回否则，犔犓犌中存在犐 犇犻对应的元组， 根据元组中犜 狔 狆 犲的取值分类讨论：如果犐 犇犻对应元组中的犜 狔 狆 犲， 则参与者犻拥有合法的用户私钥狓犻，狔犻 ， ? 根据输入消息犕（犝犼，犛犼，犙犼） 和随机数犪，犪犣狇计算犓， 计算犐 犇犻对应的犝犻犎（犐 犇犻，犐 犇犼，犪犘，犪犘） 和犓犓犪犛犼（犡犼犢犼犘犘 狌 犫犺犼） ，犓犪（狓犻狔犻）犙犼，犓犪犘（狓犻狔犻）犙犼 ， 计算犛 犓犐 犇犻，犐 犇犼，犝犻，犝犼，犓 ， 更新列表并返回 ；如果犐 犇犻对应元组中的犜 狔 狆 犲， 由于? 不具有计算参与者犐 犇犻私钥的能力， 因此无法直接获知相应的会话密钥； 若犔犛中存在与该会话相匹配的元组犛犻，犼，犪，犕，犕 ，犓，犛 犓 ， 返回犛 犓； 否则， 从密钥空间中随机选取犓犌和犛 犓，犽， 更新列表犔犛并返回犛 犓犜 犲 狊 狋（犛犻，犼）若第阶段询问结束， 并且攻击者完全遵循犲 犆 犓安全模型的相关要求攻击者选择新鲜的参与者狋犻，犼发起犜 犲 狊 狋询问收到相应的询问后， ? 进行下述操作若狋犼， 则? 停止， 并终止模拟；若狋犼且该会话已被打开， 并且会话标识与狋犻，犼相同， 则? 停止， 并终止模拟；否则， ? 在犔犛中查找狋犻，犼所对应的元组， 并输出相应的应答消息给?计算机学报 年猜测敌手?询问完成后， 输出会话密钥的猜测犛 犓 ，? 收 到 ?的 猜 测犛 犓 时，若犛 犓 犛 犓，则输出犮犙犪（犡犻犢犻） （犪犺犻犘）（ 其中犺犻犎（犐 犇犻，犡犻，犢犻） ，犙犪（犡犻犢犻犘犘 狌 犫犺犻） ） 作为 困难问题的解； 否则输出若?攻击本文协议成功， 则? 输出 困难问题的有效解； 否则， ? 没有解决 困难问题（） 若? 未终止， 则?无法区分攻击是真实攻击还是模拟攻击由于在模拟游戏中， 各参与者的输出消息均遵循本文协议的相关要求， 并且在消息空间上是均匀分布的， 因此敌手不具有区分攻击是真实攻击还是模拟攻击的能力（） 若?能以不可忽略的优势成功攻击本文密钥 协 商 协 议， 则 ? 至 少 能 以 不 可 忽 略 的 优 势狇犛狇犆犲 狇犝狇犛解决 困难问题在模拟过程中， 若? 未终止， 则?攻击本文密钥协商协议成功事件犈表示?进行部分密钥生成询问时? 未终止； 事件犈表示?进行犛 犲 狀 犱询问时?未终止； 事件犈表示?进行犆 狅 狉 狉 狌 狆 狋询问时? 未终止； 事件犈表示?进行犜 犲 狊 狋询问时? 未终止则有犘 狉犈（）狇犛；犘 狉犈狇犛；犘 狉犈狇犛狇犆狇犛；犘 狉犈狇犝当?以不可忽略的优势成功攻击本文密钥协商协议时， 模拟器? 输出正确 困难问题有效解的优势为犘 狉 ?狑 犻 狀 狊犘 狉犈犈犈犈犃狑 犻 狀 狊狇犛狇犆狇犝狇犛（）狇犛 由于狇犛， 则狇犛足够大时（）狇犛趋向于（是自然对数底数） ， 因此， 若? 在模拟过程中未终止， 且?以不可忽略的优势成功攻击本文协议，则? 赢得上述游戏的优势至少为狇犛狇犆犲 狇犝狇犛则? 输出 困难问题解的优势至少为狇犛狇犆犲 狇犝狇犛由于 问题是困难的， 因此?在游戏中获胜的优势犃 犱 狏?（狀） 是可忽略的， 即对于?类敌手本文协议满足密钥协商安全定义的条件声称 任意的? 类概率多项式时间敌手?在游戏中获胜的优势犃 犱 狏?（犽） 是可忽略的证明过程与声称证明相类似， 不再赘述由声称和声称可知， 本文协议满足密钥协商安全定义的条件综上所述， 若 困难假设成立， 则本文协议是安全的认证密钥协商协议证毕 不可伪造性证明定理 ?类敌手的不可伪造性若?类敌手?能以不可忽略的优势在多项式时间内赢得相关游戏（ ?最多进行狇犓次密钥协商询问、狇犇次部分密钥提取询问和狇犛次私钥提取询问） ， 则算法? 能以优势犃 犱 狏（ ? ） 狇犇（）犽狇犛（）犽（狇犓）（是自然对数底数） 在多项式时间内解决 困难问题证明 假设算法? 是一个 困难问题的解决者， 其困难问题的输入为（犘，犮 犘） ， 其中犮犣狇且未知， 其目标是计算出犮? 以?为子程序并充当游戏的挑战者? 运行初始化算法， 并发送公开参数犘 犪 狉 犪 犿 狊狇，犘，犌，犘犘 狌 犫，犎，犎，犎 给?， 令犘犘 狌 犫犮 犘， 同时? 维持列表犔，犔，犔犇，犔犛 犓，犔犘犓，犔犓，犔犝分别用于跟踪?对谕言机犎、犎、 部分密钥生成、 私钥生成、 公钥生成、 密钥协商和合法性验证询问， 开始时各列表均为空询问敌手?进行下述询问：犎查询当?向谕言机犎询问犎（犐 犇犻，犡犻，犢犻） 时， 若犐 犇犻，犡犻，犢犻，犺犔， 则返回犺给?； 否则， ? 选取满足，犺犔的随机数犺犣狇，并添加犐 犇犻，犡犻，犢犻，犺 到犔中， 同时返回犺给?犎查 询当 ? 收 到 ?对 谕 言 机犎的 询 问犎（犐 犇犻，犐 犇犼，犝犻，犛犻，犙犻） 时， ? 进行下述操作：若存在 犐 犇犻，犐 犇犼，犝犻，犛犻，犙犻，犺，犜 狔 狆 犲犻犔， 则返回犺给?；否则， ? 随机选取犜 狔 狆 犲， ， 且犘 狉犜 狔 狆 犲狇犓； 若犜 狔 狆 犲， ? 选取满足，犺，犔的随机数犺犣狇， 添加元组犐 犇犻，犐 犇犼，犝犻，犛犻，犙犻，犺，犜 狔 狆 犲犻 到犔中， 并返回犺给?；否则，犜 狔 狆 犲， 令犺， 并返回“” 给?部分密钥生成询问当? 收到?对身份犐 犇犻和公开参数犡犻的部分密钥生成询问时， 若存在犐 犇犻，狔犻，犢犻犔犇， 则返回相应的值狔犻，犢犻 给?； 否则， ?随机选取狔犻，犺犣狇， 计算犢犻狔犻犘犘犘 狌 犫犺， 添加元组犐 犇犻，狔犻，犢犻 到犔犇中， 并返回狔犻，犢犻 给?； 同时添加犐 犇犻，犡犻，犢犻，犺 到犔中期周彦伟等：一种改进的无证书两方认证密钥协商协议私钥生成询问当收到?对犐 犇犻的私钥生成询问时， ? 进行下述操作若存在犐 犇犻，狓犻，狔犻犔犛 犓， 则返回相应的私钥犛 犓狓犻，狔犻 给?；否则， ? 随机选取狓犻犣狇， 计算犡犻狓犻犘， 对身份犐 犇犻和犡犻进行部分密钥生成询问获得相应的元组犐 犇犻，狔犻，犢犻 ， 添加犐 犇犻，狓犻，狔犻 到犔犛 犓中， 返回狓犻，狔犻 给?， 并添加犐 犇犻，犡犻，犢犻 到犔犘犓中公钥生成询问当收到?对犐 犇犻的公钥生成询问时， ? 进行下述操作：若存在犐 犇犻，犡犻，犢犻犔犘犓， 则返回相应的公钥犘犓犡犻，犢犻 给?；否则， ? 查询犔， 若犜 狔 狆 犲， 则? 随机选取狓犻犣狇， 计算犡犻狓犻犘， 对身份犐 犇犻和犡犻进行部分密钥生 成 询 问 获 得 相 应 的 元 组 犐 犇犻，狔犻，犢犻 ， 添 加犐 犇犻，犡犻，犢犻 到犔犘犓中， 返回犘犓犡犻，犢犻 给?， 同时添加犐 犇犻，狓犻，狔犻 到犔犛 犓中； 若犜 狔 狆 犲， 则? 随机选取犡犻，犢犻犌， 并添加犐 犇犻，犡犻，犢犻 到犔犘犓中， 并返回犘犓犡犻，犢犻 给?公钥替换?可以选择一个新的公钥替换任意合法用户的原始合法公钥密钥协商询问当? 收到?对身份犐 犇犃，犐 犇犅的密钥协商询问时， ? 首先在列表犔中查询犐 犇犃，犐 犇犅 ：若犜 狔 狆 犲， 则? 放弃， 并终止模拟；否则， ? 根据身份犐 犇犃，犐 犇犅 分别在列 表犔犛 犓和犔犘犓中分别查询元组犐 犇犃，狓犃，狔犃 和犐 犇犅，犡犅，犢犅 ， 并选取随机秘密数犪，犪犣狇， 分别计算犝犃犎（犐 犇犃，犐 犇犅，犪犘，犪犘） ，犛犃犪（狓犃狔犃），犙犃犪（犡犅犢犅犘犘 狌 犫犺犅） （ 其中犺犅犎（犐 犇犅，犡犅，犢犅） ） ， 发送（犐 犇犃，犐 犇犅，犝犃，犛犃，犙犃） 给?合法性 验证 询 问当 ? 收 到 ?对 身 份 犐 犇犃，犐 犇犅 和消息（犝犃，犛犃，犙犃） 的合法性验证询问时， ?首先在列表犔和犔犘查询犐 犇犃，犐 犇犅 ：若犔中存在相应的元组且其对应的犜 狔 狆 犲，则? 首先在犔犘犓和犔犛 犓中分别查询犐 犇犃和犐 犇犅对应的元组犐 犇犃，犡犃，犢犃 和犐 犇犅，狓犅，狔犅 ， 计算犘犃，犛犃（犡犃犢犃犘犘 狌 犫犺犃） 和犘犃，（狓犅狔犅）犙犃， 验证等式犝犃犎（犐 犇犃，犐 犇犅，犘犃，犘犃，） 是否成立， 若成立则返回“ 通过” 给?， 否则结束， 并终止模拟；若犔中存在相应的元组且其对应的犜 狔 狆 犲 ，则返回“ 通过” 给?， 否则终止模拟；若列表犔犘犓中不存在相应的元组， 若存在元组犐 犇犃，犐 犇犅，犝犃，犛犃，犙犃，犺犔， 则返回“ 通过”给?， 否则终止模拟伪造经过多项式有界次上述询问后， ?随机选取秘密数犪，犪犣狇和犛犣狇， 计算犝犎（犐 犇犃，犐 犇犅，犪犘，犪犘） 和犙犪（犡犅犢犅犘犘 狌 犫犺犅） ， ?输出关于身份犐 犇犃和犐 犇犅的伪造密钥协商消息（犐 犇犃，犐 犇犅，犝，犛，犙） ， 并对该元组之前未进行过密钥协商询问， 同时? 知道被替换的公钥若?伪造成功， 同时身份犐 犇犃和犐 犇犅在犔中对应元组中的犜 狔 狆 犲， 则? 输出犮犙犪（犡犅犢犅） （犪犺犅犘）作为 困难问题的解； 否则， ? 没有解决 问题特别的， ?不能对挑战信息进行合法性验证询问在询问阶段， 当?出现下述询问时， 则? 会终止模拟：对身份犐 犇犃进行了部分密钥生成询问；对身份犐 犇犃进行了私钥生成询问定义事件犈表示?对犐 犇犃未进行部分密钥生成询问和私钥生成询问； 事件犈表示密钥协商询问过程中? 未终止； 则有犘 狉犈 狇犇（）犽狇犛（）犽，犘 狉犈（）狇犓因此， 询问阶段 ? 不终止的概率为狇犇（）犽狇犛（）犽（）狇犓； 伪造阶段?伪造正确密钥协商消息的概率为因此， 若? 在模拟过程中未终止， 并且?以不可忽略的优势攻破了本文密钥协商协议时， 则? 输出 困难问题有效解的优势至少为狇犇（）犽狇犛（）犽（）狇犓 由于狇犓， 则当狇犓足够大时， （）狇犓趋向于综上所述， 若? 在模拟过程中未终止， 并且敌手?能以不可忽略的优势攻破了本文密钥协商协议的不可伪造性， 则? 能以优势犃 犱 狏（ ? ） 狇犇（）犽狇犛（）犽（狇犓）成功解决 困难问题证毕定理 ? 类敌手的不可伪造性若? 类敌手?能以不可忽略的优势在多项式时间内赢得相关游戏（ ?最多进行狇犓次密钥协商询问、狇犇次部分密钥提取询问和狇犛次私钥提取询问） ， 则算法? 能以优势犃 犱 狏（ ? ） 狇犇（）犽狇犛（）犽（狇犓）（是自计算机学报 年然对数底数） 在多项式时间内解决 困难问题证明过程与定理证明相类似， 不再赘述效率及性能分析本节将从计算开销、 公私钥长度、 消息长度和消息交互次数等方面综合分析无证书密钥协商协议的计算和通信效率及安全性， 其中计算效率以参与者执行一次密钥协商协议的运算量来衡量， 通信效率以消息交互次数来衡量本节将本文协议与现有使用双线性映射， 和不使用双线性映射 的相关协议进行比较， 比较结果如表所示， 其中表中未统计协议中可提前计算的相关运算； 同时， 消息长度未统计参与者的身份、 公钥等公开信息表中相关符号的定义如下：犈犕表示群上的点乘运算；犈犲表示群上的双线性运算；犈犕 犪 犮表示消息认证码运算；犈犻 狀 狏表示模块倒置操作；犌表示群犌中元素的长度；犣狇表示犣狇中元素的长度；犛 犻 犵表示消息签名的长度；，犽表示字符串，犽的长度；犝 狀 犛 犲 犮表示协议不满足所声称的安全性，犛 犲 犮表示协议满足所声称的安全性由表可知， 文献， 的计算量较大， 导致相关方案的计算效率较低， 但上述方案， 具有公私钥长度较短的优势， 并且文献 实现了三方参与者间会话密钥的安全协商文献 的安全性较弱， 接收者无法确认消息的真实接收者； 文献 中协议参与者的运算量较大， 导致协议的执行效率较低； 虽然相关文献 声称其方案能够满足对任意敌手的安全性， 但是分析发现?类敌手能够伪造文献 中任意用户的密钥协商信息， 故上述方案 对?类敌手不具备不可伪造性； 文献 未实现双方的身份认证， 而文献 仅实现了单向的身份认证， 即发送者无法验证消息接收者的身份合法性本文协议在实现会话密钥安全协商的同时， 完成参与者身份合法性的双向认证； 由于本文协议实现了双向的身份合法性认证， 导致其消息长度较长表性能比较结果方案运算量安全性密钥长度私钥公钥交互次数消息长度文献犈犕 犾犈犲犈犕 犪 犮犛 犲 犮犣狇犌 犌 犈犕 犪 犮文献 犈犕犈犲犛 犲 犮犣狇犌 犌文献 犈犕犈犲犛 犲 犮犣狇犌犌 犌文献 犈犕犈犲犛 犲 犮 犌犌 犌文献 犈犕犈犲犛 犲 犮 犣狇犌 犌文献 犈犕犝 狀 犛 犲 犮 犣狇 犌 犌文献 犈犕犝 狀 犛 犲 犮 犣狇 犌 犌文献 犈犕犛 犲 犮犣狇犌犛 犻 犵 犌犛 犻 犵 犌文献 犈犕犈犻 狀 狏犝 狀 犛 犲 犮 犣狇犌犌 犌文献 犈犕犝 狀 犛 犲 犮 犣狇 犌 犌文献 犈犕犝 狀 犛 犲 犮犣狇犌犌犌 犣狇 犌本文方案犈犕犛 犲 犮 犣狇 犌 犣狇 犌综上所述， 在安全性方面， 由于犲 犆 犓安全模型优于犿 犅 犚模型， 所以协议 ， 的安全性是在较弱的安全模型下进行的证明； 文献 中的协议无法满足其所声称的安全性； 文献 中的协议都无法抵抗?类敌手的不可伪造性攻击（ ?类敌手对文献 的伪造攻击过程与文献 类似）在计算效率方面， 由于文献， 中的协议均基于双线性映射构建， 运算量较大， 计算效率较低； 同时， 文献 中协议的点乘运算次数较多， 导致协议的计算效率较低； 文献 ， 中协议的消息交互次数较多， 致使其通信效率较低； 由于在密钥协商过程中完成参与者身份合法性的双向认证， 因此本文协议的消息长度较长相较与现有的无证书密钥协商协议， 而言， 本文密钥协商协议在计算和通信效率及安全性方面具有明显的优势， 即本文协议的性能更优结束语本文提出了高效可证安全的无证书两方认证密钥协商协议， 并在犲 犆 犓强安全模型和随机谕言机模型下基于 困难问题分别证明了本文协议的安全期周彦伟等：一种改进的无证书两方认证密钥协商协议性和不可伪造性该协议具有无密钥托管、 完美的前后向安全性等安全属性； 同时本文协议的双方参与者实现了相互的身份认证， 具有更强的抗伪造能力相较于其他相关协议而言， 本文协议具有更高的计算和通信效率， 在带宽受限的网路环境（ 如无线传感器网络、 网络等） 下具有较好的推广性致谢感谢审稿专家和编辑老师的细致审阅！参考文献 ， ， ： ， ， ， ： ， ， ， ， ， ， （） ： ， ， （） ： ， ， ， ， ， （） ： ： ， ， ， ， ， ： ， ， ， ： ， ， ， （） ： ， ， ， ， ： ， ， ， ， ， （） ： ， ， ， （） ： （ ）（ 高志刚，冯登国高效的标准模型下基于身份认证密钥协商协议软件学报， ， （） ： ） ， ， ， ， （） ： ， ， ， ： ， ， ， ： ， ， ， ， ： ， ， ， ， （） ： ， ， ， ， ， （ ） ： ， ， ， （ ） ： （ ）（ 刘文浩，许春香无证书两方密钥协商方案软件学报， ， （ ） ： ） ， ， （ ） ， ， （） ： （ ）（ 杨浩民，张尧学，周悦芝基于双线性对的无证书两方认证密钥协商协议清华大学学报（ 自然科学版） ， ， （） ： ） ， ， ， （） ： （ ）（ 程庆丰，陆思奇两个无证书两方认证密钥协商协议分析洛阳师范学院学报， ， （） ： ）计算机学报 年犣 犎 犗 犝 犢 犪 狀 犠 犲 犻， ， 犢 犃 犖 犌 犅 狅， ， ， ， 犣 犎 犃 犖 犌 犠 犲 狀 犣 犺 犲 狀 犵， ， 犅 犪 犮 犽 犵 狉 狅 狌 狀 犱 （ ） ， ， ， 犲 犆 犓 ， ， ， ， （ ， ， ） ， ， ， ， ， ， ， ， ， ， 期周彦伟等：一种改进的无证书两方认证密钥协商协议