基于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 無證書密碼方案是一種適合應用的公鑰密碼機制。