基于SM9 算法的无证书密码机制

李愿军， 付跃军， 刘 冰

（贵州中烟工业有限责任公司， 贵州 贵阳 550001）

0 引言

目前解决IBC 机制密钥托管问题的方法主要有：一种是使用多KGC 的方法[2-4]。 在这种方案中，IBC 系统的主密钥被分发给多个KGC，没有单独的KGC 拥有主密钥的完整信息。用门限密码的方式为一个身份产生私钥，通过使用分布式的系统成功地避免了把全部信任都放在一个实体上的问题。但是这种解决方案是以采用额外的基础设施和通信带宽以及牺牲计算性能为代价的。 同时， 这种方案需要用户向多个权威中心逐一证明自己的身份，并获取自己的私钥（通过一个安全通道完成），这对于用户来讲也是一种沉重的负担。 况且在互联网环境中， 相对于管理一个单独的KGC 来说， 保持多个实体的独立是很困难的。另一种是基于无证书公钥密码方案（CL-PKC，Certificateless Public Key Cryptosystem）。 该方案通过组合IBC 和PKI 机制的思想，使得用户的私钥由两个部分共同组成， 即用户的秘密值和KGC 生成的部分私钥，且这两个部分分别独立地由KGC 和用户生成，这样KGC 并不知道整个私钥的内容。 并且和PKI 体制不同的是，CL-PKC 方案的KGC 不需要颁发与用户所选取的部分私钥相对应的部分公钥的证书，而是直接发布该部分公钥，这样减少了证书的管理。因此，基于无证书公钥密码机制的方法可以从根本上解决IBC 机制的密钥托管问题。

1 SM9 无证书密码方案

SM9 算法是一种基于双线性对的标识密码算法，它可以根据用户的身份标识生成用户的公、私密钥对，主要用于数字签名、数据加密、密钥交换等。 SM9 密码算法的密钥长度为256 比特。 该算法于2016 年发布成为国家密码行业标准：GM/T 0044-2016 SM9 标识密码算法[8]。 SM9无证书密码方案综合了SM9 算法和无证书密码方案的优点，可以有效的解决SM9 算法中密钥托管的问题。

1.1 CL-PKC 机制

为了解决IBC 机制中KGC 可信问题，Al-Riyami 和Pertersonl 提出了无证书的公钥密码体制（Certificateless Public Key Cryptosystem，CL-PKC），在CL-PKC 中，用户私钥分为两部分，即用户的部分私钥和秘密值，密钥生成中心（Key Generation Center，KGC）作为半可信的第三方，其只为用户生成部分私钥， 而用户私钥中的秘密值部分则是由用户自主生成的。 因此，对于KGC 而言，敌手只能获取到用户的部分私钥，而不能获得用户的完整私钥，从而即使KGC 受到了攻击， 用户的完整私钥仍然是安全的，因此，基于无证书公钥密码体制可以解决IBC 机制中私钥托管问题。

基于标准算法的无证书机制（CL-PKC）包含无证书加密机制（CL-PKE）和无证书签名机制（CL-PKS）。

1.2 SM9 无证书加密方案

无证书公钥加密算法（CL-PKE）由以下七个算法组成：系统参数生成、部分密钥生成、设置秘密值、生成用户加密私钥、生成用户加密公钥、加密算法和解密算法，其中前面2 个算法由KGC 完成。 具体算法描述如下：

（1）系统参数生成：CL.PKE.Setup（ke）→（ke，PPub-e） 输入ke 是安全参数，输出系统的主公钥、主私钥和系统参数，主私钥和主公钥由KGC 安全保存，系统参数公开；

（2）部分密钥生成：CL.PKE.Extract.Partial.private.key（PPub-e，ke，IDA，Paras）→（PA-e，dA-e），输入系统参数、主加密密钥对、IDA用户身份标识， 输出部分私钥dA-e和部分公钥PA-e；

（3）设置秘密值：CL.PKE.Set.private.Value（Paras，IDA）→xA-e，输入用户的身份和系统参数，输出用户的秘密值xA-e；

（4）生成用户加密私钥：CL.PKE.Set.privatekey（Paras，IDA，xA-e，dA-e）→sA-e，输入系统参数、用户的部分私钥dA-e、用户的秘密值xA-e，由用户计算出完整的私钥sA-e；

（5）生成用户加密公钥：CL.PKE.Set.Publickey（Paras，PPub-e，IDA，PA-e，xA-e）→PkA-e， 输入系统参数、用户的秘密值xA-e和部分公钥PA-e，计算出完整的公钥PkA-e；

（6）加密 算法：CL.PKE.Enc（Paras，M，PPub-e），PkA-e）→C，输入明文M、系统参数Paras、主公钥PPub-e）、加密公钥PkA-e，输出密文C；

（7）解密算法：CL.PKE.Dec（Paras，C，sA-e） →M，输入密文C、系统参数Paras、用户解密私钥sA-e，输出明文M。

1.2.1 SM9 无证书加密密钥生成算法

（1）CL.PKE.Setup（ke）.输入安全参数及系统参数，生成加密主私钥和加密主公钥。 ①ke∈（0，n）； ②PPub-e=[ke]P1；③输出加密主密钥对：ke， PPub-e。

（2）CL.PKE.Extract.Partial.private.key （PPub-e，ke，IDA，Paras）.算法输入系统参数、主密钥、实体A 的标识IDA，输出用户的部分私钥dA-e， 和部分公钥PA-e。 ①计算t1=H1（IDA||hid，N）+s mod N，若t1=0，则需要重新产生加密主密钥，否则计算t2=t1-1s mod N；②dA-e=[t2]P2；③PA-e=[t1]P1；④输出dA-e、PA-e。

（3）CL.PKE.Set.private.Value（Paras，IDA）.输入系统参数及标识，输出秘密值xA-e。①xA-e∈（0，n）；②输出秘密值：xA-e。

（4）CL.PKE.Set.privatekey（Paras，IDA，xA-e，dA-e）.输入系统参数、实体A 的标识IDA、用户的部分私钥dA-e、用户的秘密值xA-e，由用户计算出完整的私钥sA-e。①sA-e=[xA-e] dA-e=[xA-et2] P2；②输出sA-e。

（5）CL.PKE.Set.Publickey （Paras，PPub-e，IDA，PA-e，xA-e）.输入系统参数、用户的秘密值xA-e和部分公钥PA-e，计算出完整的公钥PkA-e。 ①PkA-e=[xA-e-1]PA-e；②输出PkA-e。

1.2.2 SM9 无证书加密算法

SM9 无证书加密 算法CL.PKE.Enc （Paras，M，PPub-e，PkA-e）：

输入明文M、系统参数Paras、主加密公钥PPub-e、用户A 加密公钥PkA-e；输出密文C。

k1_len 为分组密码算法的密钥K1 长度，k2_len 为MAC 算法的密钥K2 长度。

（1）生成随机数r∈（0，n）；

（2）计算C1=[r]PkA-e；

（3）计算g=e（PPub-e，P2）；

（4）计算w=gr；

（5）按照明文加密方法分类进行计算：①基于密钥派生函数的序列密码算法： 计算整数klen=k1_len+k2_len，然后计算K=KDF（C1||w||IDA，klen）；计算C2=M⊕K1；②结合密钥派生函数的分组密码算法：

计算整数klen=k1_len+k2_len，然后计算K=KDF（C1||w||IDA，klen）；计算C2=Enc（M，K1）；

（6）计算C3=MAC（K2，C2）；

（7）输出密文C=C1||C3||C2。

1.2.3 SM9 无证书解密算法

SM9 无证书解密算法CL.PKE.Dec（Paras，C，sA-e）：

输入密文C、系统参数Paras、用户解密私钥sA-e；输出明文M。

k1_len 为分组密码算法的密钥K1 长度，k2_len 为MAC 算法的密钥K2 长度。

（1）判断C1∈G1是否成立，若不成立报错并退出；

（2）计算w'=e（C1，sA-e）；

（3） 按照明文加密方法分类进行计算： ①计算整数klen=k1_len+k2_len，然后计算K=KDF（C1||w'||IDA，klen）；计算M=C2⊕K1； ②结合密钥派生函数的分组密码算法：计算整数klen=k1_len+k2_len，然后计算K=KDF（C1||w||IDA，klen）；计算M=Dec（C2，K1）；

（4）计算u=MAC（K2，C2），判断C3=u 是否相等，如不相等则报错；

（5）输出明文M。

1.3 SM9 无证书签名方案

SM9 无证书签名方案（CL-PKS）由以下七个算法组成：系统参数生成、部分密钥生成、设置秘密值、生成用户签名私钥、生成用户签名公钥、签名算法和验签算法，其中前面2 个算法由KGC 完成。 具体算法描述如下：

（1）系统参数生成：CL.PKS.Setup（ks）→（ks，PPub-s）） 输入ks 是安全参数，输出系统的主签名公钥、主签名私钥和系统参数，主私钥和主公钥由KGC 安全保存，系统参数公开；

（2）部分密钥生成：CL.PKS.Extract.Partial.private.key（PPub-s，ks，IDA，Paras）→（PA-s，dA-s），输入系统参数、主签名密钥对、IDA用户身份标识，输出部分私钥dA-s 和部分公钥PA-s；

（3）设置秘密值：CL.PKS.Set.private.Value（Paras，IDA）→xA-s，输入用户的身份和系统参数，输出用户的秘密值xA-s；

（4）生成用户签名私钥：CL.PKS.Set.privatekey（Paras，IDA，xA-s，dA-s）→sA-s，输入系统参数、用户的部分私钥dA-s、用户的秘密值xA-s，由用户计算出完整的私钥sA-s；

（5）生成用户签名公钥：CL.PKS.Set.Publickey（Paras，PPub-s，IDA，PA-s，xA-s）→PkA-s， 输入系统参数、 用户的秘密值xA-s和部分公钥PA-s，计算出完整的公钥PkA-s；

（6）签名算法：CL.PKE.Sign（Paras，M，PPub-s，sA-s）→（h，S），输入明文M、系统参数Paras、主公钥PPub-s、用户私钥sA-s，输出签名（h，S）；

（7） 验签算法：CL.PKE.Verify （Paras，M'，PkA-s，PPub-s，h'，S'） →验证结果。

1.3.1 SM9 无证书签名密钥生成算法

（1）CL.PKS.Setup（ks）.输入安全参数及系统参数，生成签名主私钥和签名主公钥。 ①ks∈（0，n）； ②PPub-s=[ks]P2；③输出主密钥对：ks，PPub-s。

（2）CL.PKS.Extract.Partial.private.key（PPub-s，ks，IDA，Paras）.算法输入系统参数、主签名公钥、实体A 的标识IDA，输出用户的部分私钥dA-s，和部分公钥PA-s。 ①计算t1=H1（IDA||hid，N）+ks mod N，若t1=0，则需要重新产生加密主密钥，否则计算t2=t1-1.ks mod N；②dA-s=[t2]P1；③PA-s=[t1]P2；④输出dA-s、PA-s。

（3）CL.PKS.Set.private.Value（Paras，IDA）.输 入 系 统 参数及标识，输出秘密值xA-s。①xA-s∈（0，n）；②输出秘密值：xA-s。

（4）CL.PKS.Set.privatekey（Paras，IDA，xA-s，dA-s）.输入系统参数、实体A 的标识IDA、用户的部分私钥dA-s、用户的秘密值xA-s，由用户计算出完整的私钥sA-s。 ①sA-s=[xA-s] dA-s=[xA-st2] P1；②输出sA-s。

（5）CL.PKS.Set.Publickey （Paras，PPub-s，IDA，PA-s，xA-s）.输入系统参数、用户的秘密值xA-s和部分公钥PA-s，计算出完整的公钥PkA-s。 ①PkA-s=[xA-s-1]PA-s=[xA-s-1t1]P2；②输出PkA-s。

1.3.2 SM9 无证书签名算法

SM9 无证书签名算法CL.PKE.Sign（Paras，M，PPub-s，sA-s）：

（1）计算群GT中的元素g=e（P1，PPub-s）；

（2）产生随机数r∈（0，n）；

（3）计算群GT中的元素w=gr；

（4）计算整数h=H2（M||w，N）；

（5）计算整数l=（r-h） mod N，若l=0 则返回2；

（6）计算群G1中的元素S=[l]sA-s；

（7）输出消息M 的签名为（h，S）。

1.3.3 SM9 无证书验签算法

SM9 无证书验签算法CL.PKE.Verify（Paras，M'，PkA-s，PPub-s），h'，S'）：

（1）计算群GT中的元素g=e（P1，PPub-s）；（2）计算群GT中的元素t=gh'；

（3）计算群GT中的元素u=e（S'，PkA-s）；

（4）计算群GT中的元素w=u·t；

（5）计算整数h2=H2（M'||w'，N），验证h2=h' 是否成立，若成立则验证通过，否则验证不通过。

2 SM9 无证书密码方案正确性分析

2.1 SM9 无证书加密方案正确性分析

2.2 SM9 无证书签名方案正确性分析

SM9 无证书签名算法能正确的验签。

3 安全性分析

基于随机预言的模型对本密码方案[9]的进行安全性分析。

3.1 攻击模型

无证书公钥密码机制一般认为有两种攻击类型：攻击类型1：密钥替换攻击，敌手在获取用户私钥或/且替换用户公钥冒充用户；攻击类型2：恶意KGC 攻击，已知用户的部分密钥的恶意KGC 在不知道用户私钥且不能替换用户公钥的情景下冒充用户。

3.2 SM9 无证书加密方案安全性证明

不妨假设攻击者不会做重复的询问，并且τ≥q1。

初始化： 游戏开始时，B 发送系统参数给AI。 其中，Ppub=sP1。 B 维 护 列 表ListH1，Listkdf分 别 跟 踪AI对 预 言 机H1，KDF 的询问。

Request for Public Key：AI执行ReqPK（IDi）询问，B 根据IDi查询列表ListH1，获取xi-1（hiP1+Ppub）或者x-1（h0P1+Ppub）并返回。

Decryption Query：AI执行DQ（Ci，1｜｜Ci，2｜，IDi，Pki）。 B 按照如下步骤应答。

步骤1：根据检索。 如果已到达Listkdf末尾，则返回⊥；获取元组。

步骤2：输入（Ci，2，Ki，1）执行对称解密算法，获取Mi。

步骤3 执行ui=MAC （Ki，2，Ci，2）， 检查ui=Ci，3是 否成立。 如果成立，则返回Mi；否则返回步骤1。

Phase 1：此阶段，AI可执行一系列的询问，包括Partial Private Key Extraction，Private Key Extraction，Request for Public Key，Replace Public Key，KDF query， Decryption Query 等。 不妨假设AI在执行上述询问之前已对相关ID执行了H1（ID）询问。

Challenge Phase：由AI决定结束Phase 1 的时机。 此时，AI选择IDch以及等长的明文m0，m1进行挑战。 不妨假设AI已执行过H1（IDch）。 限定AI未执行过PK-Extract（IDch）和RepPK（IDch，*）。B 按照如下策略应答。①IDch≠IDI，B 退出；②随机选择y∈Zn*，令lenm0代表对m0进行对称加密后获得的密文的长度。 随机选择C2'∈{0，1}lenm0，令lenMAC代表MAC 计算结果的长度，随机选择C3'∈{0，1}lenMAC，返回C'=yP1｜｜C2'｜｜C3'

Phase 2： B 按照Phase 1 中的方式继续应答AI的询问。 对AI询问的限制与Phase 1 中相同。

Guess：最终，AI输出b'作为其对b 的猜测。 B 随机从列表Listkdf中选择w'，返回w'1/y作为对Gap-τ-BCAA1 问题的解答。

下面分析一下B 成功的概率。

用hI代表事件AI选择IDI作为IDch挑战身份，h0代表事件AI对IDI执行了Partial Private Key Extraction，h1代表事件AI对IDI执行了Replace Public Key。 如果B 在游戏过程中不退出，那么B 成功的概率取决于AI的优势。

首先分析一下B 在游戏过程中不退出的概率。 令hB代表事件B 不退出。

定理2：不存在II 类敌手AII能够破解SM9_cl。

证明： 由于敌手能够获取主密钥s， 对而言， 破解SM9_cl，等价于破解如下加密算法AII_sm9。

公开参数为， 其中Pk=x-1（H1+s）P1。 私钥Pk=xs（H1+s）-1P2。

加密：随机选择r∈Zn*计算C1=rPk，w=e（P1，P2）sr，K=kdf（C1｜｜w｜｜ID，klen），C2=Enc（M，K1），C3=MAC（K2，C2）。 输出密文C=C1｜｜C2｜｜C3。

解密：计算w'=e（C1，Sk），k'=kdf（C1｜｜w'｜ID，klen），M'=Dec（K1'，C2），判断u=C3是否成立。

对于攻击者，如果要计算w'，需要获取r 或者Sk。 而已知C1=rPk，Pk 求是r 困难的。要获取Sk，则需要获取x。而已知Pk=x-1（H1+s）P1，H1，s，P1求解x 是困难的。

3.3 SM9 无证书签名方案安全性证明

定理3：不存在I 类敌手AI或者II 类敌手AII能够伪造合法的SM9 无证书签名。

证明：构造签名的过程中，需要使用签名私钥sA-s。 而无论AI或者AII，都无法获取完整的签名私钥sA-s。 所以，不存在AI或者AII能够伪造合法的签名。

4 结束语

在基于身份密码机制中，用户的公钥，就是用户的身份标识信息，可以使用用户的IP 地址、email 地址和电话号码等信息来表示，这就使得用户身份和其公钥拥有了天然的绑定关系，从而避免了基于数字证书认证所带来证书管理的开销。为用户生成私钥的KGC 必须是完全可信的第三方， 因为KGC 可以获取到任意用户的私钥，若KGC 不是可信的，那么，其可以利用自己拥有的系统主密钥生成任意用户的完整私钥， 进而进行签名伪造及解密等安全威胁活动。 与基于传统PKI 的公钥密码系统相比，IBC 机制虽然避免了复杂的证书管理问题，但同时也引入了新的密钥托管问题。 因为用户的私钥是由系统主密钥生成，而KGC 拥有系统主密钥，若KGC 的完全可信性或者安全性受到威胁， 则整个系统的安全性都将受到威胁。

SM9 算法是我国自主研发的商用密码算法， 是一种基于标识密码算法， 算法在各个领域得到了越来越广泛的使用和发展。 由于SM9 算法也是IBC 机制中的一种，所以它也具备IBC 机制的密钥托管问题。 故本方案提出一种SM9 无证书密码方案，可以有效的解决密钥托管问题，而不需要消耗额外的设备以及性能的损耗，且与标准的SM9 算法兼容。另外，SM9 无证书密码算法保留了IBC机制的属性，可以摆脱对PKI 的依赖和证书更新、撤销等操作的复杂性。 因此SM9 无证书密码方案是一种适合应用的公钥密码机制。