基于SM9 算法的無(wú)證書密碼機(jī)制

李愿軍， 付躍軍， 劉 冰

（貴州中煙工業(yè)有限責(zé)任公司， 貴州 貴陽(yáng) 550001）

0 引言

目前解決IBC 機(jī)制密鑰托管問題的方法主要有：一種是使用多KGC 的方法[2-4]。 在這種方案中，IBC 系統(tǒng)的主密鑰被分發(fā)給多個(gè)KGC，沒有單獨(dú)的KGC 擁有主密鑰的完整信息。用門限密碼的方式為一個(gè)身份產(chǎn)生私鑰，通過使用分布式的系統(tǒng)成功地避免了把全部信任都放在一個(gè)實(shí)體上的問題。但是這種解決方案是以采用額外的基礎(chǔ)設(shè)施和通信帶寬以及犧牲計(jì)算性能為代價(jià)的。 同時(shí)， 這種方案需要用戶向多個(gè)權(quán)威中心逐一證明自己的身份，并獲取自己的私鑰（通過一個(gè)安全通道完成），這對(duì)于用戶來講也是一種沉重的負(fù)擔(dān)。 況且在互聯(lián)網(wǎng)環(huán)境中， 相對(duì)于管理一個(gè)單獨(dú)的KGC 來說， 保持多個(gè)實(shí)體的獨(dú)立是很困難的。另一種是基于無(wú)證書公鑰密碼方案（CL-PKC，Certificateless Public Key Cryptosystem）。 該方案通過組合IBC 和PKI 機(jī)制的思想，使得用戶的私鑰由兩個(gè)部分共同組成， 即用戶的秘密值和KGC 生成的部分私鑰，且這兩個(gè)部分分別獨(dú)立地由KGC 和用戶生成，這樣KGC 并不知道整個(gè)私鑰的內(nèi)容。 并且和PKI 體制不同的是，CL-PKC 方案的KGC 不需要頒發(fā)與用戶所選取的部分私鑰相對(duì)應(yīng)的部分公鑰的證書，而是直接發(fā)布該部分公鑰，這樣減少了證書的管理。因此，基于無(wú)證書公鑰密碼機(jī)制的方法可以從根本上解決IBC 機(jī)制的密鑰托管問題。

1 SM9 無(wú)證書密碼方案

SM9 算法是一種基于雙線性對(duì)的標(biāo)識(shí)密碼算法，它可以根據(jù)用戶的身份標(biāo)識(shí)生成用戶的公、私密鑰對(duì)，主要用于數(shù)字簽名、數(shù)據(jù)加密、密鑰交換等。 SM9 密碼算法的密鑰長(zhǎng)度為256 比特。 該算法于2016 年發(fā)布成為國(guó)家密碼行業(yè)標(biāo)準(zhǔn)：GM/T 0044-2016 SM9 標(biāo)識(shí)密碼算法[8]。 SM9無(wú)證書密碼方案綜合了SM9 算法和無(wú)證書密碼方案的優(yōu)點(diǎn)，可以有效的解決SM9 算法中密鑰托管的問題。

1.1 CL-PKC 機(jī)制

為了解決IBC 機(jī)制中KGC 可信問題，Al-Riyami 和Pertersonl 提出了無(wú)證書的公鑰密碼體制（Certificateless Public Key Cryptosystem，CL-PKC），在CL-PKC 中，用戶私鑰分為兩部分，即用戶的部分私鑰和秘密值，密鑰生成中心（Key Generation Center，KGC）作為半可信的第三方，其只為用戶生成部分私鑰， 而用戶私鑰中的秘密值部分則是由用戶自主生成的。 因此，對(duì)于KGC 而言，敵手只能獲取到用戶的部分私鑰，而不能獲得用戶的完整私鑰，從而即使KGC 受到了攻擊， 用戶的完整私鑰仍然是安全的，因此，基于無(wú)證書公鑰密碼體制可以解決IBC 機(jī)制中私鑰托管問題。

基于標(biāo)準(zhǔn)算法的無(wú)證書機(jī)制（CL-PKC）包含無(wú)證書加密機(jī)制（CL-PKE）和無(wú)證書簽名機(jī)制（CL-PKS）。

1.2 SM9 無(wú)證書加密方案

無(wú)證書公鑰加密算法（CL-PKE）由以下七個(gè)算法組成：系統(tǒng)參數(shù)生成、部分密鑰生成、設(shè)置秘密值、生成用戶加密私鑰、生成用戶加密公鑰、加密算法和解密算法，其中前面2 個(gè)算法由KGC 完成。 具體算法描述如下：

（1）系統(tǒng)參數(shù)生成：CL.PKE.Setup（ke）→（ke，PPub-e） 輸入ke 是安全參數(shù)，輸出系統(tǒng)的主公鑰、主私鑰和系統(tǒng)參數(shù)，主私鑰和主公鑰由KGC 安全保存，系統(tǒng)參數(shù)公開；

（2）部分密鑰生成：CL.PKE.Extract.Partial.private.key（PPub-e，ke，IDA，Paras）→（PA-e，dA-e），輸入系統(tǒng)參數(shù)、主加密密鑰對(duì)、IDA用戶身份標(biāo)識(shí)， 輸出部分私鑰dA-e和部分公鑰PA-e；

（3）設(shè)置秘密值：CL.PKE.Set.private.Value（Paras，IDA）→xA-e，輸入用戶的身份和系統(tǒng)參數(shù)，輸出用戶的秘密值xA-e；

（4）生成用戶加密私鑰：CL.PKE.Set.privatekey（Paras，IDA，xA-e，dA-e）→sA-e，輸入系統(tǒng)參數(shù)、用戶的部分私鑰dA-e、用戶的秘密值xA-e，由用戶計(jì)算出完整的私鑰sA-e；

（5）生成用戶加密公鑰：CL.PKE.Set.Publickey（Paras，PPub-e，IDA，PA-e，xA-e）→PkA-e， 輸入系統(tǒng)參數(shù)、用戶的秘密值xA-e和部分公鑰PA-e，計(jì)算出完整的公鑰PkA-e；

（6）加密 算法：CL.PKE.Enc（Paras，M，PPub-e），PkA-e）→C，輸入明文M、系統(tǒng)參數(shù)Paras、主公鑰PPub-e）、加密公鑰PkA-e，輸出密文C；

（7）解密算法：CL.PKE.Dec（Paras，C，sA-e） →M，輸入密文C、系統(tǒng)參數(shù)Paras、用戶解密私鑰sA-e，輸出明文M。

1.2.1 SM9 無(wú)證書加密密鑰生成算法

（1）CL.PKE.Setup（ke）.輸入安全參數(shù)及系統(tǒng)參數(shù)，生成加密主私鑰和加密主公鑰。 ①ke∈（0，n）； ②PPub-e=[ke]P1；③輸出加密主密鑰對(duì)：ke， PPub-e。

（2）CL.PKE.Extract.Partial.private.key （PPub-e，ke，IDA，Paras）.算法輸入系統(tǒng)參數(shù)、主密鑰、實(shí)體A 的標(biāo)識(shí)IDA，輸出用戶的部分私鑰dA-e， 和部分公鑰PA-e。 ①計(jì)算t1=H1（IDA||hid，N）+s mod N，若t1=0，則需要重新產(chǎn)生加密主密鑰，否則計(jì)算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）.輸入系統(tǒng)參數(shù)及標(biāo)識(shí)，輸出秘密值xA-e。①xA-e∈（0，n）；②輸出秘密值：xA-e。

（4）CL.PKE.Set.privatekey（Paras，IDA，xA-e，dA-e）.輸入系統(tǒng)參數(shù)、實(shí)體A 的標(biāo)識(shí)IDA、用戶的部分私鑰dA-e、用戶的秘密值xA-e，由用戶計(jì)算出完整的私鑰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）.輸入系統(tǒng)參數(shù)、用戶的秘密值xA-e和部分公鑰PA-e，計(jì)算出完整的公鑰PkA-e。 ①PkA-e=[xA-e-1]PA-e；②輸出PkA-e。

1.2.2 SM9 無(wú)證書加密算法

SM9 無(wú)證書加密 算法CL.PKE.Enc （Paras，M，PPub-e，PkA-e）：

輸入明文M、系統(tǒng)參數(shù)Paras、主加密公鑰PPub-e、用戶A 加密公鑰PkA-e；輸出密文C。

k1_len 為分組密碼算法的密鑰K1 長(zhǎng)度，k2_len 為MAC 算法的密鑰K2 長(zhǎng)度。

（1）生成隨機(jī)數(shù)r∈（0，n）；

（2）計(jì)算C1=[r]PkA-e；

（3）計(jì)算g=e（PPub-e，P2）；

（4）計(jì)算w=gr；

（5）按照明文加密方法分類進(jìn)行計(jì)算：①基于密鑰派生函數(shù)的序列密碼算法： 計(jì)算整數(shù)klen=k1_len+k2_len，然后計(jì)算K=KDF（C1||w||IDA，klen）；計(jì)算C2=M⊕K1；②結(jié)合密鑰派生函數(shù)的分組密碼算法：

計(jì)算整數(shù)klen=k1_len+k2_len，然后計(jì)算K=KDF（C1||w||IDA，klen）；計(jì)算C2=Enc（M，K1）；

（6）計(jì)算C3=MAC（K2，C2）；

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

1.2.3 SM9 無(wú)證書解密算法

SM9 無(wú)證書解密算法CL.PKE.Dec（Paras，C，sA-e）：

輸入密文C、系統(tǒng)參數(shù)Paras、用戶解密私鑰sA-e；輸出明文M。

k1_len 為分組密碼算法的密鑰K1 長(zhǎng)度，k2_len 為MAC 算法的密鑰K2 長(zhǎng)度。

（1）判斷C1∈G1是否成立，若不成立報(bào)錯(cuò)并退出；

（2）計(jì)算w'=e（C1，sA-e）；

（3） 按照明文加密方法分類進(jìn)行計(jì)算： ①計(jì)算整數(shù)klen=k1_len+k2_len，然后計(jì)算K=KDF（C1||w'||IDA，klen）；計(jì)算M=C2⊕K1； ②結(jié)合密鑰派生函數(shù)的分組密碼算法：計(jì)算整數(shù)klen=k1_len+k2_len，然后計(jì)算K=KDF（C1||w||IDA，klen）；計(jì)算M=Dec（C2，K1）；

（4）計(jì)算u=MAC（K2，C2），判斷C3=u 是否相等，如不相等則報(bào)錯(cuò)；

（5）輸出明文M。

1.3 SM9 無(wú)證書簽名方案

SM9 無(wú)證書簽名方案（CL-PKS）由以下七個(gè)算法組成：系統(tǒng)參數(shù)生成、部分密鑰生成、設(shè)置秘密值、生成用戶簽名私鑰、生成用戶簽名公鑰、簽名算法和驗(yàn)簽算法，其中前面2 個(gè)算法由KGC 完成。 具體算法描述如下：

（1）系統(tǒng)參數(shù)生成：CL.PKS.Setup（ks）→（ks，PPub-s）） 輸入ks 是安全參數(shù)，輸出系統(tǒng)的主簽名公鑰、主簽名私鑰和系統(tǒng)參數(shù)，主私鑰和主公鑰由KGC 安全保存，系統(tǒng)參數(shù)公開；

（2）部分密鑰生成：CL.PKS.Extract.Partial.private.key（PPub-s，ks，IDA，Paras）→（PA-s，dA-s），輸入系統(tǒng)參數(shù)、主簽名密鑰對(duì)、IDA用戶身份標(biāo)識(shí)，輸出部分私鑰dA-s 和部分公鑰PA-s；

（3）設(shè)置秘密值：CL.PKS.Set.private.Value（Paras，IDA）→xA-s，輸入用戶的身份和系統(tǒng)參數(shù)，輸出用戶的秘密值xA-s；

（4）生成用戶簽名私鑰：CL.PKS.Set.privatekey（Paras，IDA，xA-s，dA-s）→sA-s，輸入系統(tǒng)參數(shù)、用戶的部分私鑰dA-s、用戶的秘密值xA-s，由用戶計(jì)算出完整的私鑰sA-s；

（5）生成用戶簽名公鑰：CL.PKS.Set.Publickey（Paras，PPub-s，IDA，PA-s，xA-s）→PkA-s， 輸入系統(tǒng)參數(shù)、 用戶的秘密值xA-s和部分公鑰PA-s，計(jì)算出完整的公鑰PkA-s；

（6）簽名算法：CL.PKE.Sign（Paras，M，PPub-s，sA-s）→（h，S），輸入明文M、系統(tǒng)參數(shù)Paras、主公鑰PPub-s、用戶私鑰sA-s，輸出簽名（h，S）；

（7） 驗(yàn)簽算法：CL.PKE.Verify （Paras，M'，PkA-s，PPub-s，h'，S'） →驗(yàn)證結(jié)果。

1.3.1 SM9 無(wú)證書簽名密鑰生成算法

（1）CL.PKS.Setup（ks）.輸入安全參數(shù)及系統(tǒng)參數(shù)，生成簽名主私鑰和簽名主公鑰。 ①ks∈（0，n）； ②PPub-s=[ks]P2；③輸出主密鑰對(duì)：ks，PPub-s。

（2）CL.PKS.Extract.Partial.private.key（PPub-s，ks，IDA，Paras）.算法輸入系統(tǒng)參數(shù)、主簽名公鑰、實(shí)體A 的標(biāo)識(shí)IDA，輸出用戶的部分私鑰dA-s，和部分公鑰PA-s。 ①計(jì)算t1=H1（IDA||hid，N）+ks mod N，若t1=0，則需要重新產(chǎn)生加密主密鑰，否則計(jì)算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）.輸 入 系 統(tǒng) 參數(shù)及標(biāo)識(shí)，輸出秘密值xA-s。①xA-s∈（0，n）；②輸出秘密值：xA-s。

（4）CL.PKS.Set.privatekey（Paras，IDA，xA-s，dA-s）.輸入系統(tǒng)參數(shù)、實(shí)體A 的標(biāo)識(shí)IDA、用戶的部分私鑰dA-s、用戶的秘密值xA-s，由用戶計(jì)算出完整的私鑰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）.輸入系統(tǒng)參數(shù)、用戶的秘密值xA-s和部分公鑰PA-s，計(jì)算出完整的公鑰PkA-s。 ①PkA-s=[xA-s-1]PA-s=[xA-s-1t1]P2；②輸出PkA-s。

1.3.2 SM9 無(wú)證書簽名算法

SM9 無(wú)證書簽名算法CL.PKE.Sign（Paras，M，PPub-s，sA-s）：

（1）計(jì)算群GT中的元素g=e（P1，PPub-s）；

（2）產(chǎn)生隨機(jī)數(shù)r∈（0，n）；

（3）計(jì)算群GT中的元素w=gr；

（4）計(jì)算整數(shù)h=H2（M||w，N）；

（5）計(jì)算整數(shù)l=（r-h） mod N，若l=0 則返回2；

（6）計(jì)算群G1中的元素S=[l]sA-s；

（7）輸出消息M 的簽名為（h，S）。

1.3.3 SM9 無(wú)證書驗(yàn)簽算法

SM9 無(wú)證書驗(yàn)簽算法CL.PKE.Verify（Paras，M'，PkA-s，PPub-s），h'，S'）：

（1）計(jì)算群GT中的元素g=e（P1，PPub-s）；（2）計(jì)算群GT中的元素t=gh'；

（3）計(jì)算群GT中的元素u=e（S'，PkA-s）；

（4）計(jì)算群GT中的元素w=u·t；

（5）計(jì)算整數(shù)h2=H2（M'||w'，N），驗(yàn)證h2=h' 是否成立，若成立則驗(yàn)證通過，否則驗(yàn)證不通過。

2 SM9 無(wú)證書密碼方案正確性分析

2.1 SM9 無(wú)證書加密方案正確性分析

2.2 SM9 無(wú)證書簽名方案正確性分析

SM9 無(wú)證書簽名算法能正確的驗(yàn)簽。

3 安全性分析

基于隨機(jī)預(yù)言的模型對(duì)本密碼方案[9]的進(jìn)行安全性分析。

3.1 攻擊模型

無(wú)證書公鑰密碼機(jī)制一般認(rèn)為有兩種攻擊類型：攻擊類型1：密鑰替換攻擊，敵手在獲取用戶私鑰或/且替換用戶公鑰冒充用戶；攻擊類型2：惡意KGC 攻擊，已知用戶的部分密鑰的惡意KGC 在不知道用戶私鑰且不能替換用戶公鑰的情景下冒充用戶。

3.2 SM9 無(wú)證書加密方案安全性證明

不妨假設(shè)攻擊者不會(huì)做重復(fù)的詢問，并且τ≥q1。

初始化： 游戲開始時(shí)，B 發(fā)送系統(tǒng)參數(shù)給AI。 其中，Ppub=sP1。 B 維 護(hù) 列 表ListH1，Listkdf分 別 跟 蹤AI對(duì) 預(yù) 言 機(jī)H1，KDF 的詢問。

Request for Public Key：AI執(zhí)行ReqPK（IDi）詢問，B 根據(jù)IDi查詢列表ListH1，獲取xi-1（hiP1+Ppub）或者x-1（h0P1+Ppub）并返回。

Decryption Query：AI執(zhí)行DQ（Ci，1｜｜Ci，2｜，IDi，Pki）。 B 按照如下步驟應(yīng)答。

步驟1：根據(jù)檢索。 如果已到達(dá)Listkdf末尾，則返回⊥；獲取元組。

步驟2：輸入（Ci，2，Ki，1）執(zhí)行對(duì)稱解密算法，獲取Mi。

步驟3 執(zhí)行ui=MAC （Ki，2，Ci，2）， 檢查ui=Ci，3是 否成立。 如果成立，則返回Mi；否則返回步驟1。

Phase 1：此階段，AI可執(zhí)行一系列的詢問，包括Partial Private Key Extraction，Private Key Extraction，Request for Public Key，Replace Public Key，KDF query， Decryption Query 等。 不妨假設(shè)AI在執(zhí)行上述詢問之前已對(duì)相關(guān)ID執(zhí)行了H1（ID）詢問。

Challenge Phase：由AI決定結(jié)束Phase 1 的時(shí)機(jī)。 此時(shí)，AI選擇IDch以及等長(zhǎng)的明文m0，m1進(jìn)行挑戰(zhàn)。 不妨假設(shè)AI已執(zhí)行過H1（IDch）。 限定AI未執(zhí)行過PK-Extract（IDch）和RepPK（IDch，*）。B 按照如下策略應(yīng)答。①IDch≠IDI，B 退出；②隨機(jī)選擇y∈Zn*，令lenm0代表對(duì)m0進(jìn)行對(duì)稱加密后獲得的密文的長(zhǎng)度。 隨機(jī)選擇C2'∈{0，1}lenm0，令lenMAC代表MAC 計(jì)算結(jié)果的長(zhǎng)度，隨機(jī)選擇C3'∈{0，1}lenMAC，返回C'=yP1｜｜C2'｜｜C3'

Phase 2： B 按照Phase 1 中的方式繼續(xù)應(yīng)答AI的詢問。 對(duì)AI詢問的限制與Phase 1 中相同。

Guess：最終，AI輸出b'作為其對(duì)b 的猜測(cè)。 B 隨機(jī)從列表Listkdf中選擇w'，返回w'1/y作為對(duì)Gap-τ-BCAA1 問題的解答。

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

用hI代表事件AI選擇IDI作為IDch挑戰(zhàn)身份，h0代表事件AI對(duì)IDI執(zhí)行了Partial Private Key Extraction，h1代表事件AI對(duì)IDI執(zhí)行了Replace Public Key。 如果B 在游戲過程中不退出，那么B 成功的概率取決于AI的優(yōu)勢(shì)。

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

定理2：不存在II 類敵手AII能夠破解SM9_cl。

證明： 由于敵手能夠獲取主密鑰s， 對(duì)而言， 破解SM9_cl，等價(jià)于破解如下加密算法AII_sm9。

公開參數(shù)為， 其中Pk=x-1（H1+s）P1。 私鑰Pk=xs（H1+s）-1P2。

加密：隨機(jī)選擇r∈Zn*計(jì)算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。

解密：計(jì)算w'=e（C1，Sk），k'=kdf（C1｜｜w'｜ID，klen），M'=Dec（K1'，C2），判斷u=C3是否成立。

對(duì)于攻擊者，如果要計(jì)算w'，需要獲取r 或者Sk。 而已知C1=rPk，Pk 求是r 困難的。要獲取Sk，則需要獲取x。而已知Pk=x-1（H1+s）P1，H1，s，P1求解x 是困難的。

3.3 SM9 無(wú)證書簽名方案安全性證明

定理3：不存在I 類敵手AI或者II 類敵手AII能夠偽造合法的SM9 無(wú)證書簽名。

證明：構(gòu)造簽名的過程中，需要使用簽名私鑰sA-s。 而無(wú)論AI或者AII，都無(wú)法獲取完整的簽名私鑰sA-s。 所以，不存在AI或者AII能夠偽造合法的簽名。

4 結(jié)束語(yǔ)

在基于身份密碼機(jī)制中，用戶的公鑰，就是用戶的身份標(biāo)識(shí)信息，可以使用用戶的IP 地址、email 地址和電話號(hào)碼等信息來表示，這就使得用戶身份和其公鑰擁有了天然的綁定關(guān)系，從而避免了基于數(shù)字證書認(rèn)證所帶來證書管理的開銷。為用戶生成私鑰的KGC 必須是完全可信的第三方， 因?yàn)镵GC 可以獲取到任意用戶的私鑰，若KGC 不是可信的，那么，其可以利用自己擁有的系統(tǒng)主密鑰生成任意用戶的完整私鑰， 進(jìn)而進(jìn)行簽名偽造及解密等安全威脅活動(dòng)。 與基于傳統(tǒng)PKI 的公鑰密碼系統(tǒng)相比，IBC 機(jī)制雖然避免了復(fù)雜的證書管理問題，但同時(shí)也引入了新的密鑰托管問題。 因?yàn)橛脩舻乃借€是由系統(tǒng)主密鑰生成，而KGC 擁有系統(tǒng)主密鑰，若KGC 的完全可信性或者安全性受到威脅， 則整個(gè)系統(tǒng)的安全性都將受到威脅。

SM9 算法是我國(guó)自主研發(fā)的商用密碼算法， 是一種基于標(biāo)識(shí)密碼算法， 算法在各個(gè)領(lǐng)域得到了越來越廣泛的使用和發(fā)展。 由于SM9 算法也是IBC 機(jī)制中的一種，所以它也具備IBC 機(jī)制的密鑰托管問題。 故本方案提出一種SM9 無(wú)證書密碼方案，可以有效的解決密鑰托管問題，而不需要消耗額外的設(shè)備以及性能的損耗，且與標(biāo)準(zhǔn)的SM9 算法兼容。另外，SM9 無(wú)證書密碼算法保留了IBC機(jī)制的屬性，可以擺脫對(duì)PKI 的依賴和證書更新、撤銷等操作的復(fù)雜性。 因此SM9 無(wú)證書密碼方案是一種適合應(yīng)用的公鑰密碼機(jī)制。