一种减少密文长度的基于身份的加密方法

摘要

本发明为一种减少密文长度的基于身份的加密方法，其包括的步骤为：步骤a：一私钥产生中心生成建立系统所需要的系统参数；步骤b：所述的私钥产生中心认证用户身份，认证通过后向用户提供私钥生成服务；步骤c：密文发出方用户实体仅仅利用密文接收方用户实体的身份信息作为所述密文接收方用户实体的公钥，对消息进行加密后，生成密文；步骤d：所述的密文接收方用户实体利用所述的私钥产生中心为其产生的与其身份信息相对应的私钥对密文进行解密，得到相应的明文消息。

说明书

技术领域

本发明涉及的是一种基于身份的加密方法，特别涉及的是一种减少密文中冗余信息，进而减少密文的长度的基于身份的加密方法。

背景技术

自1976年Diffie和Hellman提出公钥密码思想以来，密码学者设计出了许多公钥加密方案，同时也有许多方案被攻破。值得注意的是，有些方案是在其提出很多年以后才被攻破的，这促使人们考虑如何设计可证安全的密码算法。这种可证安全是从计算复杂理论的角度上考虑的。利用反证法，如果所设计的算法被攻破的话，那么将有效地解决该密码算法所基于的某个困难问题。而目前解决某个困难问题从计算复杂度上讲是不可行的，因此，所设计的算法也就不能被攻破。目前国际上使用较多的公钥加密算法的安全性主要有基于大整数分解问题的RSA公钥加密算法以及基于离散对数问题的ElGamal和ECC加密算法等。

现有的公钥密码体制需要一庞大的公钥基础设施(Public Key Infrastructure，简称PKI)。PKI中最主要的是证书机构(Certificate Authority，简称CA)，负责认证用户的身份，并向用户颁布公钥证书，并替各个用户管理所有的证书，同时提供公钥目录服务以支持用户查找其它用户的公钥证书。CA是通过自己对用户身份和用户公钥进行签名以解决公钥和公钥持有者身份间的绑定问题。传统的公钥加密方法中，用户的公钥一般是随机字符串，与自己的身份毫不相关。为了给一个用户发送加密的消息，发送方必须首先得到该用户的公钥证书，公钥证书是把用户的身份信息与其公钥联系起来的桥梁。证书有效时才能实施相关的密码操作。

Shamir在1984年提出了一种新的密码体制--基于身份的公钥密码体制。其主要特性是在这一密码体制下，公钥可以为任意字符串。于是我们可以将某一实体的身份信息直接作为其公钥，从而绕开了前述的公钥和其持有者身份的绑定问题，这会极大地减化了传统PKI中CA对用户证书进行的复杂管理。基于身份的公钥加密体制的亮点就是直接利用用户的身份信息作为用户的公钥。这样任何人都可以直接利用用户的身份信息直接加密明文，省去了公钥的认证步骤，也省去了CA对公钥证书的繁琐的管理。自Shamir于1984年提出基于身份加密的思想以来，直到2001年，真正实用的系统才有Boneh和Franklin以及Cocks开发出来。Boneh和Franklin提出了第一个基于身份的可证安全的加密方案。他们的方案基于BCDH(Bilinear Computational Diffie-Hellman)问题。在BCDH问题是困难的假设下，证明了该方案是选择密文安全的(即，在适应性选择密文攻击下是语义安全的)。在此之后，又出现了许多可证安全的基于身份的加密方案。

自Boneh和Franklin的开创性工作以来，几乎所有的基于身份的公钥加密体制都是基于双线性配对(Bilinear Pairing)的。

现对双线性配对的概念进行说明：

双线性配对：设G₁和G₂是两个循环群，两个群的阶都为p，其中p是一个至少160比特的大素数。不失一般性，现在假设这两个群都是乘法群。设双线性配对是一个从集合G₁×G₁到集合G₂的一个映射，表示为e：G₁×G₁→G₂，该映射具有如下性质：

双线性：对于任意g₁，g₂∈G₁和任意的整数a，b∈Z_p^*，有e(g₁^a，g₂^b)＝e(g₁，g₂)^ab；

非退化性：存在g₁，g₂∈G₁使得e(g₁，g₂)≠1；

可计算性：对任意的g₁，g₂∈G₁，都可以快速地计算e(g₁，g₂)的值。

基于身份的公钥加密体制都有一个私钥产生中心(Prviate Key Generator，简称PKG)。PKG管理所有的用户，并向用户提供在线服务。对于每一个向PKG提交身份信息进行私钥查询的用户，该PKG首先负责对用户进行认证，用户认证通过后，PKG为用户生成与身份信息相对应的私钥，并经过安全信道向用户发放私钥。

当某个用户A向用户B发送加密信息时，用户A直接利用用户B的身份信息ID_B对明文消息M进行加密，而无需向传统的PKI中先得到用户B的公钥证书，并验证证书的合法性和有效性后才能利用用户B的公钥对消息M进行加密。

为达到选择密文安全，这些方案中绝大部分的密文都存在冗余部分，利用冗余来保证密文的合法性。所谓密文合法，指的是密文是加密算法的输出。对于选择密文攻击而言，最普遍的威胁是对非法的密文进行解密询问时，因为解密预言机有可能泄露有用信息；而从一选择明文安全的加密方案构建一选择密文安全的加密方案的一种普遍的方法是在密文中加入一些冗余以检验密文的合法性，从而拒绝非法的密文的解密查询。由于冗余部分的存在，造成了密文的长度过长，从而增加了密文传输时所占的通信带宽，降低了传输效率。

鉴于上述缺陷，本发明创作者经过长时间的研究和实践终于创作出了本发明。

发明内容

本发明的目的在于，提供一种减少密文长度的基于身份的加密方法，用以克服上述缺陷。

为实现上述目的，本发明采用的技术方案在于，提供一种减少密文长度的基于身份的加密方法，其包括的步骤为：

步骤a：一私钥产生中心生成建立系统所需要的系统参数；

步骤b：所述的私钥产生中心认证用户身份，认证通过后向用户提供私钥生成服务；

步骤c：密文发出方用户实体利用密文接收方用户实体的身份信息作为所述密文接收方用户实体的公钥，对消息进行加密后，生成密文；

步骤d：所述的密文接收方用户实体利用所述的私钥产生中心为其产生的与其身份信息相对应的私钥对密文进行解密，得到相应的明文消息；

其中，所述的步骤a生成建立系统所需要的系统参数，其包括的步骤为：

步骤a1：根据安全参数λ，选择一个大的素数p；

步骤a2：选择阶为p的一个群G₁和G₂；

步骤a3：选取有效的双线性配对e：G₁×G₁→G₂；

步骤a4：从所述的群G₁中随机选取一个不是单位元的元素g；

步骤a5：随机地选取集合Z_p^*＝{1，2，...，p-1}上的元素s；

步骤a6：在所述的群G₁上计算μ＝g^s；

步骤a7：选择四个抗碰撞的哈希函数，记为：

H₀：{0，1}^*→G₁，H₁：G₂→{0，1}^l，H₂：G₁×G₁×G₂→{0，1}^l，$H:{\left\{\mathrm{0,1}\right\}}^l\to Z_p^{*};$

步骤a8：输出公开参数params＝<p，G₁，G₁，e，g，μ，H，H₀，H₁，H₂>和主密钥s；

其中，所述的步骤b：所述的私钥产生中心认证用户身份，认证通过后向用户提供私钥生成服务；其包括的步骤为：

步骤b1：根据用户的身份信息ID，计算Q_ID＝H₀(ID)；

步骤b2：利用主密钥s，计算用户ID的私钥为d_ID＝Q_ID^s；

其中，所述的步骤c：密文发出方用户实体利用密文接收方用户实体的身份信息作为所述密文接收方用户实体的公钥，对消息进行加密后，生成密文；其包括的步骤为：

步骤c1：获得系统参数params和明文M，设明文M∈{0，1}^l，即明文是l比特的消息；

步骤c2：随机地选取所述的集合Z_p^*上的元素r；

步骤c3：计算C′₁＝g^r，$C_2^{\prime }=M\oplus H_1\left(e{(\mu ,Q_{\mathrm{ID}})}^r\right);$

步骤c4：计算Δr＝H(C′₂)；

步骤c5：计算C₁＝g^r/Δr和$C_2=C_2^{\prime }\oplus H_2(Q_{\mathrm{ID}},g^{r/\mathrm{\Delta r}},e{(\mu ,Q_{\mathrm{ID}})}^{r/\mathrm{\Delta r}});$

步骤c6：利用用户ID加密明文M所得的密文为C＝(C₁，C₂)；

其中，所述的步骤d：所述的密文接收方用户实体利用所述的私钥产生中心为其产生的与其身份信息相对应的私钥对密文进行解密，得到相应的明文消息；其包括的步骤为：

步骤d1：根据密文C＝(C₁，C₂)计算$C_2^{\prime }=C_2\oplus H_2(Q_{\mathrm{ID}},C_1,e(C_1,d_{\mathrm{ID}}));$

步骤d2：计算Δr＝H(C′₂)；

步骤d3：计算C′₁＝C₁^Δr；

步骤d4：计算明文$M=C_2^{\prime }\oplus H_1\left(e(C_1^{\prime },d_{\mathrm{ID}})\right).$

与现有技术比较，本发明的有益效果在于，本发明加密所得的密文只是群G₁上的两个元素，而现在的基于身份的公钥加密系统中所得的密文大部分都需要G₁上的三个元素甚至更多。因此，本发明缩小了密文的长度，大大减少了密文传输时的带宽，提高了通信效率。同时，本发明还是一个可证明安全的加解密方法，其安全性依赖于Gap Bilinear Diffie-Hellman(GBDH)问题的困难性上。

附图说明

图1为本发明减少密文长度的基于身份的加密方法的流程图。

具体实施方式

以下结合附图，对本发明上述的和另外的技术特征和优点作更详细的说明。

本发明的实现有赖于一种基于身份加解密的系统，其包括：若干用户实体，其用以作为密文发出方或密文接收方；一私钥产生中心(PKG)，其作为可信第三方，所述的私钥产生中心对用户实体身份进行认证，同时为合法用户进行私钥生成服务。

请参阅图1所示，其为本发明减少密文长度的基于身份的加密方法的流程图。其包括的步骤为：

步骤a：一私钥产生中心生成建立系统所需要的系统参数；

步骤b：所述的私钥产生中心认证用户身份，认证通过后向用户提供私钥生成服务；

步骤c：密文发出方用户实体利用密文接收方用户实体的身份信息作为所述密文接收方用户实体的公钥，对消息进行加密后，生成密文；

步骤d：所述的密文接收方用户实体利用所述的私钥产生中心为其产生的与其身份信息相对应的私钥对密文进行解密，得到相应的明文消息。

一般来说，密文中的冗余部分的引入是为了从理论上证明方案的选择密文安全性。因此，为了消除密文中的冗余，必须采用新的方法来获得方案的抗击选择密文攻击的能力，以达到IND-CCA安全。本发明采用的方法是：允许对非法的密文进行询问。但当进行此询问时，解密预言机返回的是随机信息。既然返回的信息是随机的，那么解密预言机就不会泄露任何有关明文的有用信息。由于本发明采用的方法中不需要对密文的合法性进行验证，所以使得本发明中加密所得到的密文非常紧凑。

其中，所述的步骤a生成建立系统所需要的系统参数，其包括的步骤为：

步骤a1：根据安全参数λ，选择一个大的素数p；

步骤a2：选择阶为p的一个群G₁和G₂；

步骤a3：选取有效的双线性配对e：G₁×G₁→G₂；

步骤a4：从所述的群G₁中随机选取一个不是单位元的元素g；

步骤a5：随机地选取集合Z_p^*＝{1，2，...，p-1}上的元素s；

步骤a6：在所述的群G₁上计算μ＝g^s；

步骤a7：选择四个抗碰撞的哈希函数，记为：

H₀：{0，1}^*→G₁，H₁：G₂→{0，1}^l，H₂：G₁×G₁×G₂→{0，1}^l，$H:{\left\{\mathrm{0,1}\right\}}^l\to Z_p^{*};$

步骤a8：输出公开参数params＝<p，G₁，G₁，e，g，μ，H，H₀，H₁，H₂>和主密钥s；

其中，所述的步骤b：所述的私钥产生中心认证用户身份，认证通过后向用户提供私钥生成服务；其包括的步骤为：

步骤b1：根据用户的身份信息ID，计算Q_ID＝H₀(ID)；

步骤b2：利用主密钥s，计算用户ID的私钥为d_ID＝Q_ID^s；

其中，所述的步骤c：密文发出方用户实体利用密文接收方用户实体的身份信息作为所述密文接收方用户实体的公钥，对消息进行加密后，生成密文；其包括的步骤为：

步骤c1：获得系统参数params和明文M，设明文M∈{0，1}^l，即明文是l比特的消息；

步骤c2：随机地选取所述的集合Z_p^*上的元素r；

步骤c3：计算C′₁＝g^r，$C_2^{\prime }=M\oplus H_1\left(e{(\mu ,Q_{\mathrm{ID}})}^r\right);$

步骤c4：计算Δr＝H(C′₂)；

步骤c5：计算C₁＝g^r/Δr和$C_2=C_2^{\prime }\oplus H_2(Q_{\mathrm{ID}},g^{r/\mathrm{\Delta r}},e{(\mu ,Q_{\mathrm{ID}})}^{r/\mathrm{\Delta r}});$

步骤c6：利用用户ID加密明文M所得的密文为C＝(C₁，C₂)；

其中，所述的步骤d：所述的密文接收方用户实体利用所述的私钥产生中心为其产生的与其身份信息相对应的私钥对密文进行解密，得到相应的明文消息；其包括的步骤为：

步骤d1：根据密文C＝(C₁，C₂)计算$C_2^{\prime }=C_2\oplus H_2(Q_{\mathrm{ID}},C_1,e(C_1,d_{\mathrm{ID}}));$

步骤d2：计算Δr＝H(C′₂)；

步骤d3：计算C′₁＝C₁^Δr；

步骤d4：计算明文$M=C_2^{\prime }\oplus H_1\left(e(C_1^{\prime },d_{\mathrm{ID}})\right).$

本发明是一个可证明安全的加解密方法，其安全性依赖于Gap BilinearDiffie-Hellman问题的困难性上，下面将证明本发明的安全性。

Gap-Bilinear Diffie-Hellman困难问题(简称GBDH问题)：设G₁，G₂为两个p阶群(其中p为素数)以及一个有效的双线性配对e：G₁×G₁→G₂，g是G₁的生成元。<G₁，G₂，e>上的GBDH问题定义为：给定<g，g^a，g^b，g^c>以及DBDH判定预言机，其中$a,b,c\in Z_p^{*},$计算e(g，g)^abc。这里，DBDH判定预言机的作用是给定<g，g^a，g^b，g^c，z>，判断z＝e(g，g)^abc是否成立。

定理：假设H₀，H₁，H₂是随机预言机，如果GBDH问题是(t，ε)安全的，那么上述方案是(t′，ε′)-IND-ID-CCA安全的，其中t＝t′+Θ(q₀+q₁+q₂+q_e+q_d)，$ϵ={ϵ}^{\prime }(1/q_e)·{(1-1/(q_e+1))}^{q_e+1}.$(q₀，q₁，q₂，q_e，q_d)分别为方案敌手询问H₀，H₁，H₂，私钥，解密预言机的次数)

证明：假设存在一个(t′，ε′)攻击者攻击方案成功，那么可以构造一个(t，ε)算法利用的能力解决GBDH问题。首先获得一个GBDH难题实例<g，g^a，g^b，g^c>(同时获得一个DBDH判定预言机)，通过和之间的IND-ID-CCA游戏来解决该难题。作为的挑战者，在它们之间的IND-CCA游戏中，和的交互构成如下：

建立阶段：设置μ＝g^a并把公开参数params＝<p，G₁，G₁，e，g，μ，H，H₀，H₁，H₂>发送给。

询问阶段一：

H₀询问：任何时候都可以提出H₀询问。算法维护一个称为L₀的记录列表，L₀初始化为空。当就ID询问随机预言机H₀时，随机选取一比特coin∈{0，1}(我们假设取0的概率为ξ，取1的概率为1-ξ)，如果coin＝0，返回g^u∈G₁(其中$u\stackrel{R}{\leftarrow }{Z}_p^{*}$)；否则返回(g^b)^u∈G₁；同时把<ID，coin，u>加到L₀列表。

私钥询问：当询问ID的私钥时，调用上面的H₀询问，之后查询L₀列表获取<ID，coin，u>，如果coin＝0，返回(g^a)^u，否则游戏中止。

H₁询问：当就V询问随机预言机H₁时，查询L₁列表，如存在<V，ρ>项，则返回ρ；如无则随机选取ρ∈{0，1}^l，返回该值并存储<V，ρ>至L₁列表。

H₂询问：当就<Q_ID，U，W>询问随机预言机H₂时查询L₂列表，如存在<Q_ID，U，W，ω>项，则返回ω；如无则随机选取ω∈{0，1}^l，返回该值并存储<Q_ID，U，W，ω>至L₂列表，此外如果L_c列表(L_c列表初始时为空表)中存在<C₁，C₂，m>，其中U＝C₁，那么计算$C_2^{\prime }=C_2\oplus \omega ,$Δr＝H(C′₂)，$\rho =C_2^{\prime }\oplus m,$V＝W^Δr，存储<V，ρ>至L₁列表。

解密询问：收到密文<C₁，C₂>及ID时，执行如下过程：查询L₂列表获取<Q_ID，U，W，ω>(其中Q_ID＝H₀(ID)，U＝C₁，DBDH(μ，Q_ID，U，W)＝1)，如无该项，随机选取m∈{0，1}^l返回，否则计算$C_2^{\prime }=C_2\oplus \omega ,\mathrm{\Delta r}=H\left(C_2^{\prime }\right)$，Δr=H(C₂′)并返回m。此外，如果DBDH(μ，Q_ID，U，W)＝1，存储<C₁，C₂，m>至L_c列表。

挑战阶段：攻击者输出两个等比特长度的明文m₀，m₁∈{0，1}^l以及攻击对象ID^*，查询L₀列表获取<ID^*，coin^*，u^*>，如果coin^*＝0，抛弃，否则随机选取$C_2^{*}\in {\left\{\mathrm{0,1}\right\}}^l,$递交挑战密文$<C_1^{*}=g^c,C_2^{*}>.$

输出阶段：查询L₀列表获取<ID^*，coin^*，u^*>以及查询L₂列表获取<Q_ID^*，U^*，W^*，ω^*>(其中$U^{*}=C_1^{*},$$(\mu ,Q_{\mathrm{ID}}^{*},U^{*},W^{*})=1$)，返回作为GBDH的回答。

概率及时间计算：在整个过程中不抛弃的概率是而该值在ξ＝1-1/(q_e+1)时得到最大值当不抛弃时，其将利用解决GBDH问题。因为攻击成功的优势为ε′，所以成功解决GBDH问题的优势为$ϵ={ϵ}^{\prime }(1/q_e)·{(1-1/(q_e+1))}^{q_e+1}.$容易看出运行的时间t为运行的时间t′加上回答询问所须的时间。

从上面的分析可以看出，如果存在一个攻击算法攻破本方案，那么完全可构造出另外一个算法使得GBDH问题得以解决。而GBDH问题是一个公认的困难问题，该问题在多项式时间内是不可能解决的，所以本发明所提出的方案是不存在多项式时间的攻击算法，这说明本发明所提方案为可证明安全的方案。

以上所述仅为本发明的较佳实施例，对本发明而言仅仅是说明性的，而非限制性的。本专业技术人员理解，在本发明权利要求所限定的精神和范围内可对其进行许多改变，修改，甚至等效，但都将落入本发明的保护范围内。