高效的基于身份的认证密钥协商协议

文章编号:1001-9081(2012)01-0035-03 oi:10.3724/SP.J.1087.2012.00035

摘 要:王圣宝等(王圣宝,曹珍富,董晓蕾.标准模型下可证安全的身份基认证密钥协商协议.计算机学报,2007,30(10):1842-1854)提出的标准模型下可证明安全的基于身份的认证密钥协商协议不具有私钥产生中心(PKG)前向安全性。针对该安全缺陷，提出了一种新的基于身份的认证密钥协商协议，协议中给出了一种利用用户私钥和临时秘密信息联合计算共享秘密的方法，并在标准模型下证明了协议的安全性。与已有协议相比，新协议具有较高的执行效率。同时提出了一种PKG与用户共同协商私钥的方法，即用户的私钥由用户产生的部分秘密信息以及PKG的系统主密钥共同生成，从而有效解决了基于身份的认证密钥协商协议的PKG前向安全性问题。

关键词:基于身份的认证密钥协商协议；双线性对；钥产生中心前向安全性；标准模型

中图分类号: TP309.2; TP391 文献标志码:A

Abstract:Wang et al. (WANG SHENGBAO, CAO ZHENFU, DONG XIAOLEI. Provably secure identitybased authenticated key agreement protocols in the standard model. Chinese Journal of Computers, 2007,30(10):1842-1854) proposed an IDbased Authenticated Key Agreement (IDAKA) protocol which was proved secure under standard model but without attribute of Private Key Generator (PKG) forward security. In order to remedy the flaw, a new protocol was introduced in which the shared secret message was calculated by the private key and temporary secret information of users of the protocol, and its security was also proved in standard model. Compared with known protocols, the new protocol is more efficient. Additionally, a method of jointly generating private key by PKG and user was proposed. The private key of user was calculated by the main secret key of system and secret information provided by user. It effectively solves the problem of PKG forward security of IDbased authenticated key agreement protocol.

Key words:IDbased Authenticated Key Agreement (IDAKA) protocol; bilinear pairing; Private Key Generator (PKG) forward secrecy; standard model

0 引言

密钥协商协议是密码学的基本组件之一，是在不安全的信道上建立安全信道的最基本的需求。所谓认证密钥协商协议，就是通信双方确信对方的真实身份，同时，协议结束后双方确信两者共享了一个只有他们知道的秘密会话密钥。

自从2001年D.Boneh和M.Franklin利用双线性对设计出第一个实用的基于身份的加密方案以来，由于基于身份的公钥密码与PKI相比具有明显的优势，因此成为研究的热点。研究者们相继提出一些基于身份的认证密钥协商（IDbased Authenticated Key Agreement, IDAKA）协议［1-8］，这些IDAKA协议都是基于随机预言机模型下可证明安全的。在随机预言机模型中，杂凑函数被模拟为随机预言机。但是，近年来人们逐渐认识到某些在随机预言机模型下可证明安全的方案在实际应用中并不安全［9］，因为杂凑函数不能真正模拟随机预言机。因此，不借助随机预言机的标准模型下可证明安全的IDAKA协议的研究越来越受到研究者的重视。

2007年王圣宝等利用Gentry［10］的基于身份的加密方案，提出第一个标准模型下可证明安全的IDAKA协议［11］，本文将该协议简记为Wang协议。2008年，汪小芬等［12］对Wang协议进行了分析，指出该协议不满足私钥产生中心(Private Key Generator, PKG)前向安全性。所谓PKG前向安全性，是指PKG的主私钥的泄漏不影响以前协商的会话密钥的安全性。汪小芬等［12］提出了一个改进协议，该协议虽然克服了Wang协议的安全缺陷，但也降低了协议的执行效率。2009年，任勇军等［13］对Wang协议提出了一种改进方案，其方案主要在原协议的基础上增加了密钥提取部分，因其密钥提取函数需要用户双方事先共享一个密钥（密钥提取函数需要密钥的参与），因此该协议不具有实用性。基于上述分析，本文提出了一种新协议，简记为G1协议，G1协议是标准模型下可证明安全的，具有PKG前向安全性。与已有的标准模型下可证明安全的IDAKA协议相比，G1协议具有较高的执行效率。另外，为了设计具有PKG前向安全性的IDAKA协议，本文给出了一种解决方法，也即是PKG和用户共同协商私钥，从而保证了即使攻击者掌握了PKG的主密钥，也无法恢复出用户的私钥，从而得不到用户之间协商的会话密钥。为了说明该方法，本文给出了一个具体实例，简记为G2协议。

1 预备知识

1.1 双线性对和困难问题假设

G1,G2都是阶为素数p的乘法循环群，g为G1的一个生成元。双线性对e:G1×G1G2为具有如下性质的映射。

1)双线性性。对于任意的u,v∈G1,a,b∈Z*q，满足：e(ua,vb)=e(u,v)ab。

2)非退化性。e(g,g)≠1，1是G2的单位元。

3)可计算性。对任意的u,v∈G1，存在有效的多项式算法计算e(u,v)。

定义1 判定性q元双线性DiffieHellman指数（qAugmented Bilinear DiffieHellman Exponent, qABDHE）问题。给定一个q+3维的向量(g′,g′αq+2,g,gα,gα2,…,gαq)∈G q+31 和一个G2中的元素Z，判断Z=e(gαq+1,g′)是否成立。

Wang协议和本文提出的G1、G2协议都是在IDBJM模型下可证明安全的，有关IDBJM模型的具体模型详见文献［4］，这里不再具体描述。

1.2 Wang协议

Wang协议描述如下。

1)系统建立。

PKG随机选取3个生成元g,h,t∈G1以及α∈Z*P ，计算g1=gα。密钥生成函数H:{0,1}*{0,1}k，k表示会话密钥的长度。设置系统公开参数为(g,g1,h,t,H)，系统主密钥为α。

2)私钥生成。

对应身份ID∈Zp，随机选择rID∈Zp，计算私钥dID=〈rID,hID〉，其中hID=(ht-rID)1/(α-ID)。

3)密钥协商。

假设Alice（身份为IDA，私钥是hA）与Bob（身份为IDB，私钥是hB）进行会话密钥协商。令gA=g1g-IDA，gB=g1g-IDB和tT=e(g,t)。

步骤1 Alice随机选择x∈Z*p ，计算TA1=gxB，TA2=txT，将TA=TA1TA2发生给Bob。

步骤2 Bob随机选择y∈Z*p ，计算TB1=gyA，TB2=tyT，将TB=TB1TB2发生给Alice。

步骤3 Alice计算共享秘密KAB1=e(TB1,hA)(TB2)rA e(g,h)x和KAB2=(TB2)x，最后计算出会话密钥SKAB=H(IDAIDBTATBKAB1KAB2)。

Bob计算共享秘密KBA1=e(TA1,hB)(TA2)rB e(g,h)y和KBA2=(TA2)y，最后计算出会话密钥SKBA=H(IDAIDBTATBKBA1KBA2)。

根据双线性对的性质，容易得出Alice和Bob计算出相同的会话密钥为SK=H(IDAIDBTATBe(g,h)x+ye(g,t)xy)。

汪小芬等［12］指出，Wang协议不具备PKG前向安全性，并给出了改进协议，但改进协议降低了Wang协议的执行效率。下面是本文针对Wang协议的安全缺陷设计的新协议――G1协议。

2 G1协议

2.1 G1协议描述

G1协议包括三部分，分别是系统建立、私钥生成和密钥协商。描述如下。

1)系统建立。

PKG随机选取2个生成元g,h∈G1以及α∈Z*p，计算g1=gα。密钥生成函数H:{0,1}*{0,1}k，k表示会话密钥的长度。设置系统公开参数为(g,g1,h,H)，系统主密钥为α。

2)私钥生成。

对应身份ID∈Zp，随机选择rID∈Zp，计算私钥dID=〈rID,hID〉，其中hID=(hg-rID)1/(α-ID)。

3)密钥协商。

假设Alice（身份为IDA，私钥是hA）与Bob（身份为IDB，私钥是hB）进行会话密钥协商。令gA=g1g-IDA，gB=g1g-IDB和gT=e(g,g)。

步骤1 Alice随机选择x∈Z*p ，计算TA1=gxB，TA2=gxT，将TA=TA1TA2发生给Bob。

步骤2 Bob随机选择y∈Z*p ，计算TB1=gyA，TB2=gyT，将TB=TB1TB2发生给Alice。

步骤3 Alice计算共享秘密KAB=［e(TB1,hA)(TB2)rA］x，最后计算出会话密钥SKAB=H(IDAIDBTATBKAB)。

Bob计算共享秘密KBA=［e(TA1,hB)(TA2)rB］y，最后计算出会话密钥SKBA=H(IDAIDBTATBKBA)。

根据双线性对的性质，容易得出Alice和Bob计算出相同的会话密钥为SK=H(IDAIDBTATBe(g,h)xy)。

2.2 G1协议的安全性证明

在IDBJM［14］模型下，证明G1协议的安全性，得到定理1。

定理1 在qABDHE假设成立的条件下，G1协议是一个安全的认证密钥协商协议。

证明 首先说明条件1是满足的。因为若两个协议的参与者遵守协议规则，而且攻击者是良性的，则两个参与者都能正确地接收来自对方的消息，他们之间有匹配会话，因此KAB=KBA，两方能计算出相同的会话密钥SK。而参与者计算密钥的临时参数是随机均匀的，所以密钥SK在密钥空间是均匀随机分布的此处应该是随机分布的吧？请明确。。

下面证明第2个条件也满足。采用反证法，若存在多项式时间的敌手A能够以不可忽略的优势ε赢得游戏（假设敌手最多进行q次Corrupt查询，发起算法qs次会话），则存在一个模拟者S能够以不可忽略的优势ε′>ε/(qsq2)解判定qABDHE问题。

模拟者对于一个判定qABDHE问题的输入(g′,g′αq+2,g,gα,gα2,…,gαq,Z)，需要判断Z=e(gαq+1,g′)是否成立。

初始化阶段。为产生系统参数，模拟者S按照下述方式进行初始化。

随机选择一个q次秘密多项式f(x)∈Zp［x］，然后根据(g,gα,gα2,…,gαq)计算h=g f(α)。将系统参数(g,g1=gα,h)发生给A，S不知道主密钥α。这样设置的参数与真实系统参数具有同样的分布。

随机选择3个整数u,v∈{1,2,…,p}，n∈{1,2,…,qs}，IDu和IDv分别表示第u和第v个参与者，S选择检测预言机为Πnu,v。模拟者S为攻击者A模拟攻击游戏，他们之间进行如下交互。

1）Corrupt查询。输入为IDi。若IDi=α，直接用α解判定qABDHE问题；否则，若i≠v，令FIDi(x)=f(x)-f(IDi)x-IDi，FIDi(x)是一个q-1次多项式，计算rIDi=f(IDi)，hIDi=gFIDi(α)=(hg-f(IDi))1α-IDi，返回私钥〈rIDi,hIDi〉。由于f(x)是一个均匀随机多项式，它满足正确的分布，因此这一私钥对于攻击者A来说是有效的。若i=v，则报错推出（E1）。

2）A诚实回答除Πnu,v之外的其他预言机的Send查询。当对Πnu,v做Send查询时，产生两个多项式分别是f2(x)=xq+2，F2,IDv(x)=f2(x)-f2(IDv)x-IDv。预言机Πnu,v发送给预言机Πnv,u的消息是Tu1=g′f2(α)-f2(IDv)，Tu2=Z•e(g′,Πqi=0(gαi)F2,IDv,i)，这里F2,IDv,i表示F2,IDv(x)中xi的系数。若Z=e(gαq+1,g′)，则Tu1=gs(α-IDv)，Tu2=e(g,g)s。且e(Tu1 ,hv )Tu2 rv =e(g,h)s。假设预言机Πnu,v收到的消息为Tv1、Tv2，则生成的共享秘密是Kuv=［e(Tv1,hu)T ruv2］s，对应的会话密钥是SK=H(IDuIDvTuTvKuv)。

3）Reveal查询。当查询的预言机为Πnu,v或其匹配预言机Πn′v,u，报错退出（E2）；否则，返回对应的会话密钥。

4）Test(Πti, j)。在模拟过程的某个时刻，将选择一个预言机做Test查询。若A没有选择S事先猜测的预言机做Test查询，则报错退出（E3）；否则，返回SKuv。

输出 游戏结束后，A输出他的猜测值b′。

事件E表示模拟者S不报错退出，则：

Pr［E］=(1-Pr［E1］)(1-Pr［E2］)(1-Pr［E3］)=(1-1q)21qs≥1qsq2

假如Z=e(gαq+1,g′)，则A能以ε+1/2的概率正确猜测b；否则，A没有任何优势猜测正确b的值。

A若能以不可忽略的优势ε正确判断b的值，则S能以不可忽略的概率ε′判断Z=e(gαq+1,g′)是否成立。模拟者S不报错退出的概率至少为1qsq2。综上可得ε′>ε/(qsq2)。

总结上述结果，可得S能以不可忽略的概率ε′解判定qABDHE问题，这与判断qABDHE假设矛盾。因此，假设不成立。改进协议是安全的认证密钥协商协议。

协议满足PKG前向安全性。假设攻击者得到PKG的私钥，则攻击者能够计算出Alice和Bob的私钥，攻击者能够计算出gx、gy，但攻击者无法计算出共享秘密e(g,h)xy。因此G1协议具备PKG前向安全性。

2.3 G1协议的对比

目前，标准模型下可证明安全的IDAKA协议主要有文献［11-13］中分别提出的3个协议，现将这3个协议与本文提出的G1协议的执行效率对比如下。

表1中：M1、M2分别表示G1、G2上的乘法运算；E1、E2分别表示G1、G2上的指数运算；P表示双线性对运算；H表示Hash运算，带宽中的G2表示G2上的一个点。

通过表1可以看出，G1协议具有较高的执行效率。

3 G2协议

为了解决IDAKA协议的PKG前向安全性问题，本章提出了PKG与用户共同产生私钥的方法。下面给出一个实例――G2协议来说明该方法。

G2协议的系统建立和密钥协商过程与Wang协议完全一样，不同之处是改变了私钥产生过程。下面介绍G2协议中的私钥产生过程。

假设用户A的身份标识为IDA∈Z*p 。用户A与PKG的进行如下交互。

步骤1 A随机选择rA ∈Z*p ，计算hg-rA，将IDAhg-rA发送给PKG。

步骤2 PKG接收到IDAhg-rA后，计算hA=(hg-rA)1/(α-IDA)，并发送PKGhA给用户A。

步骤3 A验证e(g1g-IDA,hA)=?e(g,hg-rA)，若相等，则用户将〈rA,hA〉作为自己的私钥；否则继续向PKG申请私钥。

G2协议与Wang协议的安全性证明过程一样，这里不再具体证明。

G2协议满足PKG前向安全性。首先说明一点，用户A和B利用Wang协议协商出的密钥SK=H(IDAIDBTATBe(g,h)x+ye(g,t)xy)。在G2协议中，攻击者即使知道了PKG的主密钥α，但其不知道A的部分私钥rA以及B的部分私钥rB，因此，还是不能计算出e(g,h)x和e(g,h)y，所以不能计算出第一个共享秘密e(g,h)x+y。因此，G2协议具有PKG前向安全性。

4 结语

本文提出了一种新的基于身份的认证密钥协商协议，并在标准模型下证明了该协议的安全性。与已有协议相比，该协议具有较高的执行效率。另外，为了解决IDAKA协议的PKG前向安全性问题，本文提出了一种PKG与用户共同协商私钥的解决方法。本文提出的协议是在IDBJM模型下证明安全的，设计出在安全强度更高的安全模型下可证明安全的认证密钥协商协议是下一步要解决的问题。

参考文献:

[1]

SMART N. An identity based authenticated key agreement protocol based on the Weil pairing ［J］. Electronics Letters, 2002, 38(13): 630-632.

[2]

SCOTT M. Authenticated IDbased key exchange and remote log in with insecure token and PIN number ［EB/OL］. ［2010-08-20］. eprint.省略/2002/164.pdf.

[3]

SHIM K. Efficient IDbased authenticated key agreement protocol based on the Weil pairing ［J］. IEE Electronics Letters, 2003, 39(8): 653-654.

[4]

CHEN L, KUDLA C. Identity based authenticated key agreement from pairings ［C］// Proceedings of the 16th IEEE Computer Security Foundations Workshop. Washington, DC: IEEE Computer Society, 2003: 219-233.

[5]

YUAN Q, LI S. A new efficient IDbased authenticated key agreement protocol ［EB/OL］. ［2010-08-15］. eprint.省略/2005/309.pdf.

[6]

CHOW S S M, CHOO K R. Stronglysecure identitybased key agreement and anonymous extension ［C］// ISC 2007: Proceeding of the 10th International Conference on Information Security, LNCS 4779. Berlin: SpringerVerlag, 2007: 203-220.

[7]

HUANG HAI, CAO ZHENFU. An IDbased authenticated key exchange protocol based on bilinear DiffieHellman problem ［C］// Proceedings of the 4th International Symposium on Information, Computer, and Communications Security. New York: ACM Press, 2009: 333-342.

[8]

WANG Y. Efficient identitybased and authenticated key agreement protocol ［EB/OL］. [2010-08-20]. eprint.省略/2005/108.pdf.

[9]

CANETTI R, GOLDREICH O, HALEVI S. The random oracle methodology, revisited ［J］. Journal of the ACM, 2004, 51(4): 557-594.

[10]

GENTRY C. Practical identitybased encryption without random oracles ［C］// EUROCRYPT06: Proceedings of the 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: SpringerVerlag, 2006: 445-464.

[11]

王圣宝,曹珍富,董晓蕾.标准模型下可证安全的身份基认证密钥协商协议［J］.计算机学报,2007,30(10):1842-1854.

[12]

汪小芬，陈原，肖国镇.基于身份的认证密钥协商协议的安全分析与改进［J］.通信学报,2008,28(12):16-21.

[13]

任勇军，王建东，庄毅.标准模型下增强的基于身份的认证密钥协商协议［J］.电子与信息学报,2009,31(8):1990-1995.

[14]

KUDLA C J. Special signature schemes and key agreement protocols ［D］. London: Royal Holloway University of London, 2006.

收稿日期:2011-08-08 修回日期:2011-09-23

基金项目:国家自然科学基金资助项目(90604022)

作者简介:高海英（1978-），女，河南沈丘人，副教授，博士，主要研究方向：信息隐藏、密码理论。