安全高效的无证书签密方案

摘要：已有的无证书签密方案大都存在安全性及通信效率等方面的问题。通过对现有研究成果的分析，该文提出了一种安全高效的无证书签密方案。新方案无须借助安全信道生成秘钥，通信复杂度较低。安全性分析表明，在随机预言模型下，新方案可以抵抗两类敌手的伪造攻击。性能分析表明，新方案在签密和解签密算法中仅需要九次点乘运算，具有较高的效率。

关键词：无证书;签密;随机预言模型

中图分类号：TP309        文献标识码：A

文章编号：1009-3044（2022）13-0024-04

在公钥基础设施（Public Key Infrastructure，PKI）中，为了保证用户网上交易的安全性，用户必须拥有自己的数字证书，而数字证书的生成、发放和管理由第三方机构（证书机构）负责完成。一旦用户量增大，证书管理将会消耗大量的系统资源。1984年，Shamir提出了一种基于身份的密码体制[1]，用户的公钥由标识用户身份的信息实现。然而，由于KGC（Key Generation Center）生成用户的私钥，用户的签名很容易被恶意的KGC伪造。为了解决上述问题，2003年，AI-riyami等人[2]第一次提出了一种无证书公钥密码系统，KGC仅生成用户的部分私钥，用户的私钥由部分私钥和用户自己随机选择的秘密值共同组成。这样不仅解决了基于身份的密码体制存在的密钥托管问题，而且克服了传统公钥密码体制存在的证书管理问题。

在具体应用中，为了实现保密和认证两个安全目标，传统方式通常会对消息先签名后加密。1997年，签密的概念与具体的签密方案被Zheng[3]首次提出，签密方案具有计算量少、效率高的优势。2008年，Barbosa等人[4]提出了第一个无证书签密方案，该方案同时具有无证书密码体制和签密方案的优点，但存在可扩展伪造攻击威胁。随后，两种不同的无证书签密方案相继被Aranha等人[5]和Wu等人[6]分别提出，但两种方案都存在安全保密性问题[7]。在2010年，一种标准模型下的无证书签密方案被Liu等人[8]提出，但面对恶意且被动的KGC时，方案存在安全风险[9]。

分析表明，以上提到的无证书签密机制存在各种安全问题，并且都使用了双线性对操作。因此，安全高效的无证书签密机制成为新的研究热点。文献[10-11]指出进行一次双线性对操作花费的时间大约是椭圆曲线上点乘运算的21倍。因此，无双线性配对的无证书签密方案更有效。一种无双线性对操作的无证书签密方案被Barreto等人[12]提出，但文献[13]指出该方案不能抵抗类型I敌手的攻击。为改进性能，Xie等人[14]提出了一种不含双线性对运算的无证书签密方案，尽管与Barreto等人[12]提出的方案相比，具有较高的效率，但该方案需要验证用户公钥，违背了无证书密码体制的思想。随后，几种新的无双线性对的无证书签密方案相继被提出[15-19]。但文献[18]指出文献[15]中的方案不能抵抗类型I敌手的伪造攻击，而文献[16]中的方案在面对不诚实的KGC时存在安全风险，并且在秘钥生成阶段，已有的无证书签密方案均需要借助安全信道。因此，有必要设计出安全高效的无证书签密方案以适应目前网络环境下对签密算法的需求。

在文献[15]方案的基础上，本文提出一种安全高效的无证书签密方案。该方案基于无证书签密模型[20]，在随机预言模型下，被证明是安全的，并且秘钥生成无须借助安全信道，性能效率分析较为理想。

1计算困难问题

1）计算Diffie-Hellman困难问题（ComputationalDiffie-Hellman Problem，CDHP）：设G是一个阶为q的加法循环群，P是它的一个生成元，给定[aP，bP∈G]，对任意未知的[a，b∈z∗q]，计算[abP]。

2）离散对数问题（Discrete Logarithm Problem，DLP）：设G是一个循环群，阶为q，P是它的一个生成元，给定[P，aP∈G]，对任意未知的[a∈z∗q]，计算a。

2无双线性对的无证书签密方案

本文提出一个无双线性对的无证书签密方案，具体实现过程如下。

1） 系统参数的建立

输入一个安全参数k，生成大素数p和q，且两者满足q∣p-1。G是椭圆曲线上的一个循环群，P是G中任意一个阶为q的生成元，选择[H1：0，1∗×G→Z∗q]，[H2：0，1∗→Z∗q]和[H3：G→Z∗q]三个安全的哈希函数，明文可为任意比特长度的消息m， KGC随机选择[z∈Z∗q]作为主密钥秘密保存，并计算系统公钥[Ppub=zP]，最后公开系统参数[（p，q，Ppub，H1，H2，H3）]。

2）生成用户密钥

用户[IDi]随机选取一个秘密值[xi∈Z∗q]，并计算[Xi=xiP]，然后将[Xi]发送给KGC。KGC收到[Xi]后，随机选择[ri∈Z∗q]，并计算[Ri=riP]、[di=ri+zH1（IDi，Ri，Xi）+H3（zXi）]，然后将[（Ri，di）]发送给[IDi]，此阶段用户和KGC通信无须借助安全信道。

用户[IDi]收到[（Ri，di）]后，首先通过验证等式[Ri+PpubH1（IDi，Ri，Xi）+PH3（xiPpub）=diP]是否成立，确保接收的信息是有效的。然后计算自己的部分私钥[Di=di-H3（xiPpub）]。另外，KGC可以计算出用户[IDi]的部分私钥[Di=ri+zH1（IDi，Ri，Xi）]，而其他任何人要想通过[Ppub=zP]和[Xi=xiP]计算出[zxiP]，则要面临CDHP困难问题。

这样，用户A的私钥为[SKA=（DA，xA）]，公钥为[PKA=（RA，XA）]，用户B的私钥为[SKB=（DB，xB）]，公钥为[PKB=（RB，XB）]。

3）签密

用户A选取随机数[a∈Z∗q]，计算[TA=aXB/xA]、[h=H2（TA，IDA，IDB，m）]和[s=a/（xA（xA+DA+h））]得到签名[（h，s）]，接着计算[h1=H1（IDB，RB，XB）]、[VA=a（XB+RB+h1Ppub）/xA]和[C=H3（VA）⊕m]，发送签密消息[σ=（h，s，C）]给用户B。

4） 解密验证

收到密文[σ]后，用户B计算[h1′=H1（IDA，RA，XA）]，[VB=s（xB+DB）（XA+RA+h1′Ppub+hP）]，恢复出消息[m=H3（VB）⊕C]。然后验证等式（1）是否成立，如果等式成立，用户B就接受消息m 。

[h=H2（sxB（XA+RA+h1′Ppub+hP），IDA，IDB，m）]    （1）

3方案分析

3.1 正确性

1） 验证签名的正确性

[sxB（XA+RA+h1′Ppub+hP）]

[=（a/（xA（xA+DA+h）））×（xA+rA+h1′z+h）XB]

[=（a/（xA（xA+DA+h）））×（xA+DA+h）XB]

[=aXB/xA]

[=TA]

因此，等式（1）成立，签名验证通过。

2） 验证消息的正确性

[VB=s（xB+DB）（XA+RA+h1′Ppub+hP）]

[=（a/（xA（xA+DA+h）））（xB+DB）（xA+rA+h1′z+h）P]

[=（a（xB+DB）P）/xA]

[=（a（XB+RB+h1Ppub））/xA]

[=VA]

已知有[C=H3（VA）⊕m]，因此可由[H3（VB）⊕C]恢复出消息[m]。

3.2 安全性分析

接下来在随机预言模型下给出本文方案的安全性证明。

定理1（类型[Ι]攻击下的方案保密性）假设存在一个敌手[A1]能够在概率多项式时间内以优势[ε]在定义1[15]中的游戏中获胜（最多[qi]次[Hi]询问（i=1，2，3），[qs]次签密询问，[qun]次解签密询问），挑战者Q则能够在概率多项式时间内以[AdυIND-CCA2（A1）]≥[（ε/q13）（1-qs（2q2+q3+2qs）/2k）（1-qun/2k）]的优势解决CDH问题。

证明：假设Q是挑战者，其通过输入（uP， vP），利用[A1]解决CDH问题，即计算出uvP。Q设置[y=uP]，遵照游戏规则，Q需要发送信息[（p，q，P，y，H1，H2，H3）]给[A1]。Q保存列表[L=（L1，L2，L3，LD，LSK，LPK，LS，LU）]，用来存储[A1]对预言机[H1]、[H2]、[H3]、部分私钥、私钥、公钥、签密及解签密等的询问，列表L初始化为空。

[H1]询问：列表[L1]的格式为[（ID，R，X，h1，c）]，当收到[A1]对[H1（IDi，Ri，Xi）]的询问时，如果列表中存在[（ID，R，X，h1）]，Q就将相应的值返回给[A1];否则，Q将随机选择[c∈{0，1}]，其中[Pr[c=1]=δ]，当[c=0]时，Q随机选择[h1∈Zq∗]，在列表[L1]中加入[（ID，R，X，h1，c）]，并返回[h1]给[A1];当[c=1]时，令[h1=k]，并返回[k]给[A1]。

[H2]询问：列表[L2]的格式为[（IDA，IDB，T，m，h2）]，当收到[A1]对[H2（IDA，IDB，T，m）]的询问时，如果列表中存在[（IDA，IDB，T，m，h2）]，Q就将相应的值返回给[A1];否则，Q随机选择[h2∈Zq∗]，在列表[L2]中加入[（IDA，IDB，T，m，h2）]，并返回[h2]给[A1]。

[H3]询问：列表[L3]的格式为[（V，h3）]，当收到[A1]对[H3（V）]的询问时，如果列表中存在[（V，h3）]，Q就将相应的值返回给[A1];否则，Q随机选择[h3∈Zq∗]，在列表[L3]中加入[（V，h3）]，并返回[h3]给[A1]。

部分私钥提取询问：如果列表[LD]中存在[（ID，D，R）]，就将相应的值返回给[A1];否则，Q随机选择[D，h1∈Zq∗]，计算[R=DP-h1y]，在列表[LD]中加入[（ID，D，R）]，列表[L1]中加入[（ID，R，h1）]，并返回[（R，D）]给[A1]。

私钥提取询问：如果列表[LSK]中存在[（ID，D，x）]，就返回给[A1];否则，Q从列表[LD]中获取[D]，并随机选择[x∈Zq∗]，然后在列表[LSK]中加入[（ID，D，x）]。

公钥提取询问：列表[LPK]的格式为[（ID，R，X，c）]，当收到[A1]对[（ID，R，X）]的询问时，如果列表中存在[（ID，R，X）]，Q就将相应的值返回给[A1];否则，Q查询列表[LD]和[LSK]，计算[Xi=xiP]，在列表[LPK]中加入[（ID，R，X）]，并将[R，X]返回给[A1]。如果列表[LD]和[LSK]中不存在，Q就查询列表[L1]：若[c=1]，Q随机选择[r，x∈Z∗q]，计算[R=rP]，[X=xP]，在列表[LPK]中加入[（ID，R，X，c）]，并返回[R，X];若[c=0]，则执行部分私钥提取询问，获得[R，D]，Q随机选择[x∈Zq∗]，在列表[LSK]中加入[（ID，D，x）]，列表[LPK]中加入[（ID，R，X，c）]，并返回[（R，X）]。

公钥替换询问：[A1]可以选择一个新公钥将签名者[ID]的公钥替换。

签密询问： Q从列表[LPK]中查询[（IDB，RB，XB，c）]，若[c=1]，则放弃;否则，Q首先查询列表[（IDA，DA，xA）]，接着随机选择[a∈Zq∗]，然后计算[TA=aXB/xA]，[h1=H1（IDB，RB，XB）]，[h=H2（TA，IDA，IDB，m）]，[s=a/（xA（xA+DA+h））]，[V=a（XB+RB+h1Ppub）/xA]，完成签密[C=H3（V）⊕m]，最后将签密消息[σ=（h，s，C）]返回给用户[A1]。