一种关于SM9的安全密钥分发方案

许盛伟 任雄鹏 袁 峰 郭春锐 杨 森

1(北京电子科技学院 北京 100070)2(西安电子科技大学通信工程学院 陕西 西安 710071)

0 引 言

根据认证用户的公钥形式的不同，可以将公钥密码体制分为四种：基于证书、基于身份、基于无证书、基于自认证的公钥密码体制[1]。随着移动互联网和通信技术的发展，基于身份的密码体制的轻便易用性使其具有巨大的应用潜力。

1984年Shamir[2]首次提出基于身份的公钥密码体制的思想，直至2001年Boneh[3]提出第一个基于身份的加密算法。2007年12月国家密码管理局组织专家完成了标识密码算法的标准化工作，2008年确定了SM9密码算法型号，2014年完成了SM9算法曲线的选定工作，2016年国家密码管理局正式发布SM9为密码行业标准算法[4]。2017年11月SM9标识签名算法成为ISO/IEC国际标准[5]，2018年4月在ISO/IECJTC1/SC27国际网络安全标准化工作会议上SM9标识加密算法、SM9密钥协商协议获得国际标准提案立项[6]，对于推动国产密码算法在国际上的应用具有重大意义。由于IBC体制下用户私钥均由密钥产生中心集中生成，导致了密钥托管和私钥安全分发问题，其安全性只达到了Girauit等[7]提出的Level1，这将严重阻碍其未来的发展。

针对身份密码体制的密钥托管和私钥安全分发问题截止目前已有大量研究[8]。Sui等[9]基于双线性对提出了可分离且匿名的标识私钥分发方案，系统需要本地注册中心LRA和KGC两个责任主体，分发私钥时不需要安全通道，任何窃听者都无法知道申请私钥者的身份，但该方案中存在消息完整性保护攻击和潜在的KGC泄漏攻击。文献[10-11]针对上述问题分别基于双线性对给出改进的私钥分发方案。但是上述方案均未解决密钥托管问题。Wang等[12]给出了关于BF-IBE的基于秘密共享的密钥分发方案，将该方案应用于即时通信系统(IM系统)中，虽解决了密钥托管问题，但面临数据库泄露攻击和篡改攻击。Pedersen等[13]提出了参与方可验证且没有秘密分发者的秘密共享方案。Gennaro等[14]指出Pedersen的方案不能保证生成密钥的均匀随机分布，提出了更为安全的分布式密钥生成协议。Geisler等[15]提出了关于Sakai-Kasahara-IBE的分布式密钥生成方案，其解决了密钥托管问题，但是未提出安全的私钥分发方案。文献[16]利用可验证的门限方案提出了标识私钥共享方案只解决了密钥托管问题。为同时较好地解决用户私钥安全分发与密钥托管问题，文献[17]提出了基于椭圆曲线密码体制的动态密钥分发协议，利用托管代理有效阻止用户或密钥管理中心的欺诈，但是其托管私钥时利用了公钥加密，计算代价较大。文献[18]提出了新的用户私钥分发协议，但该协议中使用了影响效率的双线性对运算。文献[19]提出了一种有托管代理参与的IBC密钥生成与托管方案，遗憾的是，该方案也使用了双线性对运算，计算效率较低。目前经典的IBE体制主要包括三种类型[1]：Boneh-Franklin IBE、Sakai-Kasahara IBE和Boneh-Boyen IBE。由于SM9的密钥产生算法不同于这三种密码体制，目前还未有关于SM9的密钥托管以及用户私钥分发的研究。

本文首先分析指出Wang等关于BF-IBE的密钥分发方案未能满足的抗数据库泄露攻击、篡改攻击，同时考虑到Geisler等关于SK-IBE的密钥产生方案未实现安全密钥分发，针对SM9独特的密钥产生算法，通过改进并结合两者，提出关于SM9的无对运算的可分离匿名分布式密钥分发(SADKI)方案。该方案实现了SM9算法的用户私钥的安全高效分发，解决了密钥托管问题。不仅具备抗KGC数据库泄露攻击、篡改攻击、安全分布式密钥生成、公共信道传输、抵抗离线口令破解、可分离、匿名等安全属性，较前述方案还消除了双线性对运算，具有较高的运算效率。

1 困难问题

1.1 ECDL困难问题

已知椭圆曲线E(Fqm)(m≥1)，阶为n的点P∈E(Fqm)，Q属于以P为生成元生成的循环群中即Q∈〈P〉。ECDL困难问题是指，给定P与Q，确定整数l∈[0,n-1]，使得Q=lP成立是困难的。

1.2 ECDH困难问题

已知椭圆曲线E(Fqm)(m≥1)，阶为n的点P∈E(Fqm)，ECDH困难问题是指，给定aP与bP，计算abP是困难的。

2 Wang等[12]密钥分发方案

2.1 方案描述

方案分为系统初始化和用户注册、私钥分发三个步骤。

(1) 系统初始化。KGCs产生并公布系统参数(G1,G2,P,q,e,H0,H1,Pi)，其中(1≤i≤n)，Pi=siP是每个子密钥产生中心的公钥，si是子系统密钥。

(2) 用户注册。用户通过本地注册中心LRA离线认证，从而获得申请一次性口令pwd，同时元组(H0(ID),H0(pwd),H1(pwd))存储在IM应用服务器的数据库中，用来认证申请私钥时的用户身份。

IM服务器通过下式验证用户身份的有效性：

e(Q,T)=e(H0(ID),H0(pwd))e(Q,H0(pwd))H1(pwd),若成立，IM服务器对(H0(ID),wiP)进行BLS短签名发送给PKGi。PKGi验证签名后保存元组(H0(ID),wiP)到数据库中。

2.2 方案分析

经下述分析，该方案存在潜在的数据库泄露攻击与攻击者的篡改攻击。

(1) 数据库泄露攻击。若IM应用服务器数据库发生泄露，攻击者获得(H0(ID),H0(pwd),H1(pwd))后，选取随机数r和应用登录口令pwd0然后计算Q、T、wi。按照方案流程，IM服务器和PKGi均能验证相应等式成立，从而可以成功伪装合法用户得到私钥。故该方案不能抗潜在的数据库泄露攻击。

3 关于SK-IBE的密钥产生方案[15]

3.1 SK-IBE的密钥产生算法

3.2 方案描述

文献[15]利用了Shamir门限方案[20]和Cramer等[21-22]中的多方计算协议提出以下方案。

(1) Setup。借助Shamir(t,m)门限方案秘密共享系统私钥x，设t-1次多项式为Q(X)∈Zq(X)且Q(0)=x，m台服务器分别获得x的秘密共享值xi=Q(i)并秘密保存，其中1≤i≤m。每个服务端计算Ri=xiP1并公开(i,Ri)。

(2) Extract(ID)。假设n个服务端是在线的，分别执行下面的协议：

① 服务端分别自行计算zi=xi+H(ID)，该值为z=x+H(ID)的秘密共享值。

② 服务端通过Shamir门限方案分别获得随机数r的共享值ri。

③ 服务端各自调用Cramer等的多方计算协议并公布si，该值是s=zr(modq)的共享值。

④ 服务端利用公布的si恢复出s。

⑤ 服务端自行计算并秘密保存wi=ris-1(modq)。

通过下式恢复用户私钥:

(1)

式中：

(2)

注意：只有满足n≥2t才能恢复秘密值，因为该方案中在Extract(ID)阶段需要调用多方计算协议。

4 关于SM9的SADKI方案

4.1 SM9密钥产生算法

(1) 系统参数组。系统参数组包括阶为素数N的加法循环群G1、G2，生成元分别为P1、P2；密码杂凑函数H()，密码函数H1(Z,n)，该函数需要调用H()，输入为比特串Z和整数n，输出为整数∈[1,n-1]，还有其他系统参数详见文献[23]。

(2) 密钥产生。KGC产生随机数ke∈[1,N-1]作为主密钥，计算G1中的元素Ppub-e=ke×P1作为加密主公钥，则加密主密钥对为(ke,Ppub-e)。KGC秘密保存ke，公开Ppub-e。KGC选择并公开用一个字节标识的加密私钥生成函数识别符hid。

4.2 SADKI方案

方案涉及符号总结于表1。

表1 符号说明

下面介绍方案的具体通信过程：

用户A在本地注册机构进行离线认证后获得一次性口令pwd，并且LRA将[HID,H(pwd)P1]安全存储到KGCi的待定私钥数据库中。

(2) User→KGC。用户获得口令pwd后选择随机数r，计算U=rP2，H(pwd)Ppubi，防止申请报文篡改，需要计算M=H(HID,U,H(pwd)Ppubi)，最后发送HID，U，M给KGCi。

(3) KGC→User。KGCi收到H′ID、U′、M′后，将H′ID作为索引寻找对应的H(pwd)P1，计算keiH(pwd)P1并判断M′=H(H′ID,U′,keiH(pwd)P1)是否成立从而验证消息的有效性。若成立，则KGCi依次执行下面方案：

①KGCi计算zi=keiH′ID+1，其值是z=ke-1H′ID+1的共享值。

②KGCi利用Shamir门限方案获得随机数R的共享值Ri。

③KGCi各自调用Cramer等的多方协议计算si，该值是s=zR(modN)的共享值。

④KGCi分别公布si，从而计算s。

⑤KGCi自行计算并秘密保存wi=Ris-1(modN)。

⑥KGCi计算σi=wiU′和M1=H(σi,keiH(pwd)P1)并发送给用户。

(4) 提取私钥。用户接受到σ′i和M′1后，判断M′1=H(σ′i,H(pwd)Ppubi)是否成立从而验证消息的有效性，若成立，计算c′ir-1σ′i，用户接收到KGCi的n个有效回复(2t≤n≤m)后，计算下式得到用户私钥deA：

(3)

最后，用户申请成功后，可以删除数据库中的元组〈HID,H(pwd)P1〉，这样数据库中只保留待定发布私钥的元组，避免增长到传统PKI证书库的巨大规模。一次性口令也会失效，避免非法用户得到口令后重新申请私钥的泄露风险。

5 正确性分析

KGCi收到用户发来申请私钥的消息后，由于H(pwd)Ppubi=keiH(pwd)P1，故KGCi通过H(HID,U,H(pwd)Ppubi)=H(H′ID,U′,keiH(pwd)P1)可以验证消息有效性。

下面证明KGCi需秘密共享的z值为ke-1HID+1，依据SM9私钥产生算法有：

ke×(HID+ke)-1(modN)P2=

(ke-1HID+ke-1×ke)-1(modN)P2=

(ke-1HID+1)-1(modN)P2=

z-1(modN)P2

(4)

可知须改进Geisler等方案中的z值为ke-1HID+1。

下面证明zi=keiHID+1是z的共享值：

(5)

从而可知各个zi是z的共享值。

Rs-1P2=RR-1z-1P2=z-1P2=deA

(6)

从而用户私钥可以被正确恢复。

6 安全性和效率分析

6.1 安全性分析

(1) 不需要安全通道。即使敌手轻易截获传输通道中的消息σi、U，想要得到私钥前需计算r-1σi，由于r是用户选取的随机值，只能从U=rP2计算得到r，这是一个ECDL离散对数困难问题，从而只有掌握随机值r的合法者才能得到私钥，因此密钥分发中可以在公共信道传输。

(2) 完整性保护。在用户发送给KGC的消息HID、U、M中，若三者任意篡改，那么KGC可以立刻判断出消息的有效性。故M为HID、U提供了完整性保护，保证KGC按照方案生成正确的私钥，从而使合法请求者可以得到私钥。

(3) 抵抗潜在KGC泄露攻击。若存在某个KGC的数据库泄露，非法用户得到〈HID,H(pwd)P1〉后，需要伪造HID、U、M才可伪装成其他用户申请私钥，但若想成功伪造M需要计算H(pwd)Ppubi，已知H(pwd)P1、Ppubi计算出H(pwd)Ppubi是一个ECDH困难问题。故该方案可以抵抗潜在KGC数据库泄露攻击。

(4) 分布式密钥产生。由于用户的私钥由多方KGC合作生成，解决了单一KGC的密钥托管问题和部分KGC不诚实问题。由于本方案用户私钥产生方案与文献[15]类似，由该文中安全性分析可知本方案分布式密钥产生具有安全性。

(5) 可分离。可分离性继承自文献[9]的方案。类似于基于证书的PKI系统，认证和证书生成的工作是分离的，分别由RA和CA负责。在本方案中，LRA负责申请私钥的用户身份认证，KGC仅仅验证请求的有效性并负责私钥分发工作。

(6) 匿名性。传输的消息与KGC数据库中的数据均以H1(IDA‖hid,N)形式存在，所以敌手和KGC不会知道用户的真实身份，从而敌手和KGC不会知道是哪个用户成功请求到了私钥。

(7) 抵抗离线口令破解。由于每个用户拥有独一无二的一次性口令并秘密保存，用户成功申请到私钥后，口令将会失效，所以即使非法用户窃取到申请报文并成功离线破解口令，此时口令也已失效。

6.2 效率分析

与文献[16-18]方案相比，本文方案不仅实现了SM9密码算法私钥的分布式密钥产生，具备了抵抗KGC泄露攻击等更强的安全属性，更大的优势在于无需双线性对运算。用户端需花费n+2个点乘运算，每个KGC只需2个点乘。由于椭圆曲线中对运算是点乘运算时间的20倍[22]左右，所以运算效率大大提高。

如表2所示P代表双线性对运算，S代表椭圆曲线上的点乘运算，文献[16]方案只解决密钥托管问题，同时该过程需要安全通道秘密传输，并且服务端利用了双线性对运算，效率较低；文献[17]方案中虽解决了密钥分发与密钥托管问题，但是密钥托管时需要安全通道传输，而且服务端计算代价较大；文献[18]方案中安全性与本文方案相同，用户端计算量比本文较有优势，但是服务端利用了双线性对运算，计算效率较低；文献[9-12]的方案中用户端计算量至少需要2P+3S，这相当于43个点乘运算，服务端至少需要1P+1S，只有当KGC数量n≥41时本文方案用户端运算量才不小于其他方案。所以本方案不仅安全性具有优势，计算效率也得到很大提高；由于本文分布式密钥产生方法基于文献[15]方案，故与该方案的运算量相当，但是本文方案具有用户密钥安全分发的优势。

表2 本文方案与其他文献方案安全性和效率对比

7 结 语

移动互联网和通信技术的发展为国际标准SM9密码算法带来了广泛的应用前景。针对SM9天生的密钥托管局限性，本文指出文献[12]方案的攻击缺陷问题，基于SM9特有的密钥产生方法，改进该密钥分发方案和文献[15]密钥产生方案，提出了SM9的分布式私钥产生方案，实现了无双线性对的密钥分发，减少了计算量，提高了安全性。最终分析表明该方案在安全性和效率方面均具有优势。