一种基于ECDLP的无证书密钥管理方法和系统

本发明属于信息安全领域，涉及一种基于椭圆曲线离散对数问题(ECDLP)的无证书密钥管理方法和系统。

在公钥密码技术的应用中，通常采用基于证书的公钥基础设施(Public KeyInfrastructure，PKI)，通过证书权威机构(Certification Authority，CA)颁发证书的形式来建立用户身份与其所拥有的公钥之间的联系，CA的数字签名可保证用户公钥的真实性。然而证书的管理过程需要消耗大量的系统资源和网络资源，在对用户进行认证和对签名进行验证时过分依赖CA中心的支持。2003年，Al-Riyami等人首次提出了一种无证书公钥密码体制(Certificateless Public key Cryptography，简称CLPKC)，在该体制中，用户的密钥由密钥生成中心和用户自己分别独立生成，用户对私钥具有完全控制权；用户公钥可通过用户标识和用户部分公钥计算得出，不需要使用公钥证书；减少了传统PKI中的证书管理问题，提高了系统的运行效率，减少了系统的复杂性；在用于身份认证、数字签名和密钥协商时，可以脱离密钥生成中心独立进行。由于无证书公钥密码体制不使用证书，占用资源少，计算效率高，适合于具有海量用户的超大规模系统应用，适合于低功耗设备使用。但是，由于无证书公钥密码体制是一种全新的公钥密码技术，需要一种可行的密钥生成算法、密钥管理方法和密钥管理系统来实现无证书公钥密码体制，发挥无证书公钥密码体制的优势。本发明基于椭圆曲线离散对数计算难题(ECDLP)创设了一种可实现无双线性对运算的无证书公钥密码体制和相应的无证书密钥管理系统。

本发明公开了一种基于椭圆曲线离散对数难题的无证书公钥密码体制、无证书密钥管理方法和密钥管理系统，其作用是为用户生成无证书公私钥对，签发用户公钥的证明(称为用户公钥标识)。

本发明公开了一套规范化的密钥管理方法和系统，实现系统建立、用户密钥生成、用户密钥撤销、用户公钥标识下载、用户公钥状态查询等功能，对用户密钥进行有效管理，为无证书公钥密码应用提供强有力支持。

一、系统结构

本发明所述无证书密钥管理系统，包括密钥生成子系统(Key GenerationSystem，简称KGS)、密钥注册子系统(Key Registe System，简称KRS)、密钥目录服务子系统(Key Directory System，简称KDS)和用户实体。

1.密钥生成子系统(KGS)

本发明所述密钥生成子系统(KGS)负责生成和保存系统主密钥，发布系统参数，负责为用户实体生成部分私钥，签发用户公钥标识。负责面向密钥注册子系统(KRS)提供密钥生成、密钥挂失、密钥注销和密钥恢复等服务。并对生成的密钥进行归档管理，将用户公钥标识和用户公钥状态发布到密钥目录服务子系统(KDS)。一个KGS下可以有多个KRS和多个KDS。

2.密钥注册子系统(KRS)

本发明所述密钥注册子系统(KRS)负责为用户实体提供用户注册、密钥生成、密钥挂失、密钥注销等服务。

所述密钥注册系统还包括密钥注册点。密钥注册点是密钥注册系统的客户端，负责受理用户申请，对用户信息进行录入、审核，保证用户标识与用户实体真实对应，为用户提供密钥生成、密钥挂失、密钥注销等服务。

3.密钥目录服务子系统(KDS)

本发明所述密钥目录服务子系统(KDS)负责发布所有用户的公钥标识和用户公钥状态，提供用户公钥标识下载和公钥状态查询服务。

4.用户实体

本发明所述用户实体为系统中个人用户、机构用户和设备。个人用户可以是网络用户、手机用户和其它用户；机构可以是政府行政机构、企业和各种组织团体等；设备可以是网络上的服务器、打印机、路由器、网卡、个人计算机、移动终端、仪器、设备、货物和商品等。用户实体的密钥载体为密码机、密码卡、USBKEY、IC卡、PSAM卡、电子标签或安全模块等。

二、系统建立

本发明所述无证书密钥管理方法和系统，采用的是一种建立在常规椭圆曲线之上的、不使用双线性对运算的无证书公钥密码体制。本发明优选使用国家标准SM2安全椭圆曲线参数和SM2签名算法、加密算法、密钥协商算法以及国家SM3标准HASH算法。

本发明所述系统建立由密钥生成子系统(KGS)按以下步骤完成。

取E(a，b)：y2＝x3+ax+b为有限域Fq上的安全椭圆曲线，q和n为素数，G是E(a，b)上的一个n阶基点，H1()、H2()、H3()和H4()是一组{0，1}*--＞[1，n-1]的HASH函数，Kex()和K()是一对密钥交换函数，满足Kex(y，K(x))＝Kex(x，K(y))。

所述KGS随机选择一个系统主私钥s∈[1，n-1]，计算系统主公钥Ppub＝[s]G，KGS保密s，公开系统参数(a，b，q，n，G，H1()，H2()，H3()，H4()，K()，Kex()，Ppub)。

三、密钥管理

本发明所述无证书密钥管理方法和系统中的密钥包括KGS的根密钥和用户实体密钥。

系统对密钥进行生命周期的全过程管理，包括密钥生成、密钥更新、密钥存储、密钥备份、密钥撤消、密钥销毁，还包括用户公钥标识的发布和下载、用户密钥状态的发布和查询等。

1.密钥生成

本发明所述密钥生成子系统(KGS)的密钥已经在系统建立阶段生成，因此以下所述的密钥生成主要指用户实体的密钥生成，用户密钥由用户和KGS通过以下步骤交互完成。

步骤1：标识为ID的用户实体随机选择私密值x∈[1，n-1]和随机数u∈[1，n-1]，计算X＝[x]G和U＝[u]G，发送(ID，X，U)至KRS子系统，请求生成用户密钥和用户公钥标识。

步骤2：所述KRS子系统在收到(ID，X，U)后，审核用户ID和身份的合法性，确定用户密钥的有效期T，将(ID，X，U，T)发送到KGS子系统。

步骤3：所述KGS子系统在收到(ID，X，U，T)后，随机选择y，v∈[1，n-1]，计算V＝K(v)，W＝Kex(v，U)，Y＝[y]G，k1＝H3(ID||W||X)，k2＝H4(ID||W||Y)，P＝[k1]X+[k2]Y(这里的符号||表示数据的串接，下同)，其中的P称为用户的部分公钥，再将ID、P和T通过编码构成一个用户公钥标识PID(简记PID＝ID||P||T)，用Info记与系统公开参数有关的信息，例如在Info中可包含系统名称、系统公钥等信息，计算h1＝H1(PID||Info)，h2＝H2(PID||Info)，如果k1、k2、h1和h2中有一个为0，则重新选择y和v。最后生成用户部分私钥z＝h1*k2*y+h2*s(mod n)，通过KRS子系统回送(Y，V，P，z，PID)到客户端，并通过KDS子系统发布所述用户公钥标识PID。

步骤4：用户收到(Y，V，P，z，PID)后，计算W＝Kex(u，V)，k1＝H3(ID||W||X)，k2＝H4(ID||W||Y)，验证P＝[k1]X+[k2]Y是否成立，再计算h1＝H1(PID||Info)，h2＝H2(PID||Info)，d＝h1*k1*x+z(mod n)，Q＝[d]G，并验证Q＝[h1]P+[h2]Ppub是否成立。若成立，则设置d为用户的私钥，PID为用户公钥标识，Q为用户的实际公钥。

如果记r＝k1*x+k2*y，则有d＝h1*r+h2*s(mod n)，P＝[r]G，Q＝[h1]P+[h2]Ppub。

2.公钥标识发布和下载

本发明所述KDS发布所有用户的公钥标识，提供用户公钥标识的下载服务，公众用户可通过工具或接口方便地下载其他用户的公钥标识。

3.密钥状态发布和查询

本发明所述KDS发布所有用户的密钥状态，提供用户密钥状态的查询服务，公众用户可通过工具或接口方便查询其他用户的密钥状态。KDS对于回送的密钥状态进行带时间戳的数字签名，保证查询状态的真实性和可信性。

4.密钥存储

本发明所述KGS和用户实体的私钥需要进行安全存储，可保存在密码机、密码卡、IC卡、USBKEY、或安全模块等密码设备内部，并通过安全的方式加以保护，所有涉及到私钥的密码运算都在密码设备内部进行，私钥不外露。

5.密钥备份

本发明所述KGS的系统密钥通过5选3门限算法分散后进行安全备份，在必要时可任选其中3个备份恢复系统密钥。

6.密钥更新

本发明所述用户实体密钥在达到使用期限或者密钥泄露的情况下，可以申请重新生成密钥。

7.密钥撤消

本发明所述用户密钥载体丢失，或者怀疑密钥已泄露，可通过KRS申请撤消密钥。

8.密钥销毁

本发明所述各类密钥如果已过期或不再使用，则应采取安全的方式进行销毁。

四、密钥使用

1.KGS系统密钥使用

本发明所述KGS是全系统的信任源点，而系统密钥是系统的信任根。KGS的私钥主要用于生成用户实体密钥，系统公钥用于生成和验证用户实体的公钥。

2.用户实体密钥使用

(1)用户私钥使用

本发明所述无证书公钥密码体制中的用户在使用私钥时，与普通公钥密码算法相同，可直接使用私钥进行密码运算。

由于本发明所述用户私密值x是用户独立生成的，用户的实际私钥d对其他人是不可知的，即使对KGC也是如此，因此用户对私钥具有完全控制权。

(2)用户公钥使用

本发明所述无证书公钥密码体制中的公钥依赖方(即公众用户)首先通过某种途径获取到用户公钥标识PID，例如可以在与私钥所有方交互时获取所述用户的公钥标识或者从KDS子系统下载所述用户的公钥标识，再通过所述PID计算h1＝H1(PID||Info)，h2＝H2(PID||Info)，从所述PID中取出用户的部分公钥P，最后使用用户部分公钥P和系统公钥Ppub按公式Q＝[h1]P+[h2]Ppub计算用户的实际公钥Q，计算出的所述实际公钥Q可用于公钥加密或者对签名进行验证。

在必要时，所述公众用户还可以通过KDS子系统查询用户密钥的有效性。

(3)密码算法应用

本发明所述无证书公钥密码体制生成的用户密钥对(Q，d)实际上就是常规椭圆曲线上的公私钥对，所以适用于所有关于椭圆曲线上的标准公钥密码算法，如ECDSA签名算法，Schnorr签名算法，国家SM2标准签名算法、公钥加密算法和密钥协商算法等，在使用这些公钥密码算法时，不需要使用双线性对运算。

如果用户在签名、认证和密钥协商时，将自己的部分公钥作为签名结果、认证凭据和密钥协商数据的一部分提交，接收者则可直接计算用户的实际公钥而不依赖密钥生成中心的支持。因此，除公钥加密外，基于本发明所述无证书公钥密码体制的签名、认证和密钥协商则相当于基于身份的签名、基于身份的认证和基于身份的密钥协商。

下面以签名算法为例进行说明：

设签名者为用户A，其标识为IDA，公钥标识为PIDA，用私钥dA对消息M的标准签名记为SIGN(dA，M)，则σ＝(SIGN(dA，M)，PIDA)就是该用户对消息M的标识签名。

其他用户收到该用户的公钥标识PIDA、消息M和签名σ后，首先根据用户公钥标识PIDA和系统公钥Ppub计算该用户的实际公钥QA，再用公钥QA按标准签名算法验证对消息M的签名SIGN(dA，M)。这个验证过程完全由验证者独立完成，不需要第三方协助，因此等同于一种基于标识的签名算法。

公钥加密算法和密钥协商算法可用类似的方法处理。

下面对本发明所述无证书公钥密码体制和系统的安全性和高效性进行说明。

1.安全性

本发明所述无证书公钥密码体制和系统的安全性基于以下两个假设：

a)KGS是可信的。

b)解椭圆曲线上离散对数难题(ECDLP)在计算上是不可行的。

(1)系统密钥安全性

抗私钥穷举攻击：根据ECDLP假设，攻击者从系统公钥Ppub求出系统私钥s在计算上是不可行的。

抗共谋攻击：即抵抗所有用户合谋对系统密钥的攻击。

假定攻击者获取了一组用户私钥和公钥标识：

PIDi，di，i＝1，2，...，t t＜＜n

其中，di＝hi，1*ri+hi，2*s(mod n)，hi，1＝H1(PIDi||Info)，hi，2＝H2(PIDi||Info)，希望从中求出系统私钥s。

在这组式子中，s，r1，...，rt对攻击者是未知的，将t个方程联立组成含t+1个未知元的线性方程组：

{hi，1*ri+hi，2*s＝di(mod n)|i＝1，2，...，t}

这个方程组的解空间至少是1维的，得到真实解s的概率为1/n，与求解ECDLP相当。因此，从任意多组用户密钥推导系统私钥s是计算上不可行的，这说明本发明所述系统密钥能够抵抗共谋攻击。

(2)用户密钥安全性

本发明所述用户部分公钥与用户私钥组成的对(P，d)能够映射到所述系统私钥对用户ID的一个Schnorr签名。文献证明，在随机预言模型下，Schnorr签名算法是安全的。事实上，目前还没有发现对Schnorr签名算法的有效攻击方法，已有的攻击方法基本上都等同于解椭圆曲线上离散对数难题。因此本发明所述用户密钥生成算法是安全的，所述用户部分公钥与私钥组成的对(P，d)是不可伪造的。

(3)算法安全性

本发明所述无证书公钥密码体制实现方法采用标准的签名算法、加密算法、身份认证协议和密钥协商协议，它们的安全性已经得到公认。

(4)用户公钥的自证性

在本发明所述无证书公钥密码体制实现方法中，当使用系统公钥从用户标识ID和部分公钥P计算用户的实际公钥Q时，实际上是对系统私钥签名(P，d)的一个验证。如果验证正确，即Q计算正确，则Q必是用户ID对应的实际公钥。如果由于某种原因(如攻击者伪造了一个用户部分公钥)使Q计算错误，则随后使用Q所作的验签或公钥加密都不会得到预期的结果，原因是攻击者不能伪造出与Q对应的私钥。这说明本发明所述用户密钥具有一种自认证性，当使用系统公钥从用户标识ID和部分公钥P计算用户的实际公钥Q时，自动隐含了对用户公钥的认证，只有标识为ID的用户才具有与P和Q对应的私钥。

(5)用户密钥不存在托管

在本发明所述的无证书公钥密码体制实现方法中，用户的私钥对KGC也是未知的，因此不存在用户密钥的托管问题。原因是用户密钥由用户和KGC共同生成，用户私钥d＝h1*k1*x+z(mod n)，其中x对KGC是未知的，因此KGC不能知道用户的私钥d。

2.高效性

本发明所述的无证书公钥密码体制和系统中，不使用双线性对运算，不使用数字证书，计算效率高，占用资源少，整体效率达到了一个新的高度。

根据测算，在密码安全强度相当的基础上，如果采用超奇异椭圆曲线上的双线性对运算实现CLPKC，一次双线性对运算耗费的计算时间是一次多倍点运算的10-20倍，即使在最新的BN曲线上经过优化了的双线性对运算，一次双线性对运算耗费的计算时间是一次多倍点运算的8-10倍。本发明所述的无证书公钥密码体制，不使用复杂的双线性对运算，仅需要少量的多倍点运算和点加运算，计算用户实际公钥降低到1/10个多倍点计算量，签名/验签、加密/解密等运算也采用标准的密码算法，计算量达到最小。因此，本发明所述无证书公钥密码体制是高效的。

本发明所述无证书公钥密码体制和系统中，KGS保存系统私钥和系统参数。每生成一个用户密钥，系统只需要保存用户的公标标识。由此可见系统的存储开销相当小，因此本发明所述无证书公钥密码体制适合于大规模海量用户的系统应用。

本发明所述无证书公钥密码体制和系统中，用户只需要保存系统参数、用户私钥、用户公钥和公钥标识，存储开销非常小，节省了存储资源和网络带宽。用户端密码设备只需要支持普通椭圆曲线密码算法，能够使用现有的芯片。

本发明所述无证书公钥密码体制和系统，适用于标准的椭圆曲线签名算法，如ECDSA、SM2、Schnorr等算法，具有签名格式简单、签名数据短的优点，加上签名者的用户公钥标识，一个数字签名只占用相当于2个椭圆曲线点的存储空间。例如，当有限域Fq和n的规模为256bit时，如果用户标识长度不超过32字节，则签名与用户公钥标识的总长度不超过128字节。因此，采用本发明生成的无证书签名有利于签名的传递和验证。

图1为本发明的无证书密钥管理系统的结构。

图2为本发明的无证书密钥生成流程。

图3以签名为例说明本发明的无证书密钥使用流程。

下面详细描述本发明的具体实施方式。应理解，下述实施例是用于说明本发明而不是限制本发明的保护范围。

一、系统建立

系统建立由KGS子系统完成。

所述KGS按国密SM2标准选择有限域Fq上安全椭圆曲线E(a，b)：y2＝x3+ax+b，取E(a，b)上的一个n阶点G作为基点，其中q和n为素数且比特数都是256；再选取国密标准SM3杂凑函数作为HASH函数H1()、H2()、H3()和H4()，选取ECDH密钥交换函数作为Kex()和K()，定义K(x)＝[x]G，Kex(x，K(y)＝[x]K(y)＝[xy]G，对x，y∈[0，n-1]，有Kex(x，K(y)＝Kex(y，K(x)成立。

所述KGS随机选择一个系统主私钥s∈[1，n-1]，计算系统主公钥Ppub＝[s]G，KGS保密s，公开系统参数(a，b，q，n，G，Ppub)，再令Info＝a||b|G||Ppub。

二、用户密钥生成

用户密钥生成由KGS和用户通过以下几个步骤交互完成。

步骤1：标识为ID的用户实体随机选择私密值x∈[1，n-1]和随机数u∈[1，n-1]，计算X＝[x]G和U＝[u]G，发送(ID，X，U)至KRS子系统。

步骤2：KRS子系统在收到(ID，X，U)后，审核用户ID和身份的合法性，确定用户密钥的有效期T，将(ID，X，U，T)发送到KGS子系统。

步骤3：KGS子系统在收到(ID，X，U，T)后，随机选择y，v∈[1，n-1]，计算V＝K(v)，W＝[v]U，Y＝[y]G，k1＝SM3(ID||W||X)，k2＝SM3(ID||W||Y)，P＝[k1]X+[k2]Y，再将ID、P和T通过编码构成一个用户公钥标识PID，计算h1＝SM3(PID||Info||′1′)，h2＝SM3(PID||Info||′2′)，如果k1、k2、h1和h2中有一个为0，则重新选择y和v。最后生成用户部分私钥z＝h1*k2*y+h2*s(mod n)，通过KRS回送(Y，V，P，z，PID)至用户端，并通过KDS子系统发布用户公钥标识PID。

步骤4：用户收到(Y，V，P，z，PID)后，计算W＝[u]V，k1＝SM3(ID||W||X)，k2＝SM3(ID||W||Y)，验证P＝[k1]X+[k2]Y是否成立，再计算h1＝SM3(PID||Info||′1′)，h2＝SM3(PID||Info||′2′)，d＝h1*k1*x+z(mod n)，Q＝[d]G，并验证Q＝[h1]P+[h2]Ppub是否成立。若成立，则设置d为用户的私钥，PID为用户公钥标识，Q为用户的实际公钥。

三、用户公钥标识和公钥状态发布

1.用户公钥标识发布和下载

KDS公开发布所有用户实体的公钥标识，通过LDAP或HTTP对外提供用户公钥标识的查询和下载服务。

公众用户可通过KDS提供的工具或接口，查询和下载用户的公钥标识。

2.用户密钥状态

用户密钥状态为有效、失效、挂失、注销等状态。用户密钥生成之后，在设定的有效期内，其缺省状态为有效，超出有效期后自动转为失效。而在有效期内，如果发生用户密钥丢失、密钥泄露，用户可通过KRS申请密钥挂失、密钥注销。在用户身份改变等情况下，也可以由系统对用户密钥进行强制注销，使用户密钥进入已注消状态。

3.用户密钥状态发布和查询

KDS公开发布用户密钥状态，通过LDAP或HTTP对外提供用户密钥状态的查询服务。

公众用户可通过KDS提供的工具或接口，按用户标识或用户公钥标识查询用户密钥状态。KDS对所有回送的用户密钥状态进行数字签名，并在签名中带有时间戳。

四、用户密钥使用

本实施例以用户A和用户B之间发生的数字签名和对签名进行验证的过程来说明用户密钥的使用流程，并假定用户A为签名者，用户B为验证者。

设用户A的标识为IDA，私钥为dA，公钥为QA，公钥标识为PIDA，待签名消息为M，使用的签名算法为SM2，使用的HASH算法为SM3。

用户A的签名流程：

A1：计算ZA＝SM3(IDA||a||b||G||QA)，e＝SM3(ZA||M)，其中a，b为SM2曲线参数；

A2：产生随机数k∈[1，n-1]，计算椭圆曲线点(x1，y1)＝[k]G；

A3：计算r＝x1+e(mod n)，若r＝0或r+k＝n则返回A2；

A4：计算v＝(1+dA)-1(k-rdA)(mod n)，若v＝0则返回A2；

A5：对消息M的签名为(r，v)。

最后，用户A发送用户公钥标识PIDA和签名(r，v)至用户B。

用户B的验签流程：

用户B收到用户A的公钥标识PIDA和对消息M的数字签名(r，v)后，首先检查用户A的密钥的有效性，从公钥标识中取出用户A的部分公钥PA，并计算hi＝SM3(PIDA||Info||′1′)，h2＝SM3(PIDA||Info||′2′)，QA＝[h1]PA+[h2]Ppub。再执行以下运算步骤：

B1：计算Z’A＝SM3(IDA||a||b||G||QA)，e’＝SM3(Z’A||M)；

B2：计算t＝r+v(mod n)，若t＝0，则验证不通过；

B3：计算椭圆曲线点(x’1，y’1)＝[v]G+[t]QA；

B4：计算R＝(e’+x’1)(mod n)，检验R＝r是否成立，若成立则验证通过；否则验证不通过。

上述实例仅用于说明本发明的实质精神和技术构思，以便于本发明的使用和实施，并不能以此限制本发明的保护范围。凡根据本发明精神实质进行的等效变换和修饰，都应涵盖在本发明的保护范围之内。