基于商密SM9 的高效標識簽密*

賴建昌, 黃欣沂, 何德彪, 伍 瑋

1. 福建師范大學 數(shù)學與信息學院 福建省網(wǎng)絡安全與密碼技術重點實驗室 福建省應用數(shù)學中心, 福州350007

2. 武漢大學 網(wǎng)絡安全學院 空天信息安全與可信計算教育部重點實驗室, 武漢430072

1 引言

互聯(lián)網(wǎng)、量子計算、云計算、區(qū)塊鏈等技術的發(fā)展和應用離不開加密和簽名等密碼技術的保障. 數(shù)據(jù)加密能有效保護數(shù)據(jù)的私密性, 數(shù)字簽名可以保證數(shù)據(jù)的完整性和真實性, 以及簽名者的不可否認性. 用戶可根據(jù)應用的需求選擇不同的密碼技術. 當同時需要簽名和加密時, 采用先簽名后加密的方法會增大計算開銷, 同時增加密文長度, 效率較低. 為了有效解決該問題, Zheng[1]在1997 年美密會上提出簽密的概念. 一次簽密運算就能同時實現(xiàn)簽名和加密的功能, 只有知道接收者的私鑰才能正確解密出簽名的數(shù)據(jù),進一步驗證簽名的有效性. 與先簽名后加密的方法相比, 簽密能顯著減少計算開銷和通信代價.

傳統(tǒng)公鑰密碼體制需要第三方機構為每個用戶頒發(fā)證書, 綁定用戶公鑰和身份, 確保用戶公鑰的真實有效性. 然而證書存在管理問題, 且證書的驗證開銷較大, 不適用于傳感器、智能卡等計算資源有限的設備. 為了解決證書問題, Shamir[2]1984 年提出標識密碼系統(tǒng)(Identity-Based Cryptosystem), 也稱為基于身份的密碼系統(tǒng). 在標識密碼系統(tǒng)中, 用戶的公鑰可以是郵箱地址、手機號碼等能唯一標識用戶的任意字符串, 相應的私鑰由密鑰生成中心(Key Generation Center, KGC) 統(tǒng)一計算. 標識密碼系統(tǒng)消除了證書, 有效解決了證書的驗證和管理問題. 自標識密碼概念提出后, 標識密碼得到國內外學者積極的研究, 但直到2001 年, Boneh 和Franklin[3]利用基于橢圓曲線的雙線性對(Pairing over Elliptic Curves)技術提出第一個實用可證明安全的標識加密方案. 接著, 不同性能的標識密碼方案被大量提出[4–11]. Malone-Lee在文獻[12] 中將標識密碼體制拓展到簽密系統(tǒng), 并提出實現(xiàn)標識簽密的有效方法. 隨后, 標識簽密在文獻[4,13–18] 中得到了進一步的研究.

雖然標識密碼得到了廣泛的研究, 取得了積極的進展, 但從整體上看, 標識密碼研究大多圍繞國外提出的算法展開. 秉承著核心技術自主創(chuàng)新、信息安全自主可控的理念, 我國積極推進標識密碼算法的研究,自主設計了包括數(shù)字簽名算法、密鑰交換協(xié)議、密鑰封裝機制和公鑰加密算法的SM9 標識密碼算法[19].2016 年3 月, 國家密碼管理局正式發(fā)布《GM/T0044-2016 SM9 標識密碼算法》密碼行業(yè)標準. 2020 年4 月, GB/T 38635.1-2020《信息安全技術SM9 標識密碼算法第1 部分: 總則》、GB/T 38635.2-2020《信息安全技術SM9 標識密碼算法第2 部分: 算法》兩項國家標準獲批發(fā)布, SM9 正式成為國家標準, 將于2020 年11 月1 日起實施. SM9 相關算法已被陸續(xù)納入ISO/IEC 國際標準, 相關研究取得了積極進展[20–25]. 然而, 目前未見基于SM9 的標識簽密方案在國際密碼學主流期刊和會議上正式發(fā)表, 現(xiàn)有標識簽密方案依然以國外設計為主.

1.1 本文貢獻

面向密碼技術自主先進安全可控的戰(zhàn)略需求, 本文根據(jù)SM9 標識密碼算法的特點, 凝練其核心技術,利用非對稱雙線性對提出首個基于我國SM9 商用密碼的標識簽密方案. 方案具有定長的系統(tǒng)公鑰、用戶私鑰和簽密密文, 其中用戶的私鑰由一個群元素組成, 密文由兩個群元素和n 比特組成, n 為簽名數(shù)據(jù)的長度. 與先采用SM9 數(shù)字簽名算法對數(shù)據(jù)進行簽名, 然后利用SM9 加密算法加密簽名后的數(shù)據(jù)相比, 本文方案的計算開銷和密文長度明顯減少. 在隨機諭言模型中, 基于q-BDHI 困難問題假設, 證明方案在適應性選擇密文攻擊模型下是不可區(qū)分的. 基于q-SDH 困難問題假設, 證明方案在適應性選擇消息和標識攻擊模型下滿足存在性不可偽造. 理論分析表明方案的通信開銷和計算開銷與現(xiàn)有高效標識簽密方案相當. 最后, 對方案進行實驗仿真, 簽密時間約為18 毫秒, 在實際應用中是可行的.

1.2 相關工作

本節(jié)回顧標識簽密和SM9 標識密碼算法的研究進展. 自2001 年Boneh 和Franklin 在文獻[3] 中利用基于橢圓曲線的雙線性對技術提出第一個實用可證明安全的標識加密方案后, 標識密碼得到飛躍式發(fā)展. Malone-Lee 在文獻[12] 中首次將標識密碼體制拓展到簽密系統(tǒng), 提出第一個標識簽密方案. Libert和Quisquater 在文獻[26] 中指出Malone-Lee 方案的設計采用先加密后簽名的方法, 無法達到語義安全(Semantic Security), 攻擊者很容易區(qū)分挑戰(zhàn)密文中的加密數(shù)據(jù), 并提出一個更安全、更高效的標識簽密方案. 2005 年, Barreto 等[27]提出一個在計算效率上優(yōu)于之前所有簽密方案的標識簽密方案, 并在隨機諭言模型中證明方案具有IND-CCA(Indistinguishability against Adaptive Chosen-Ciphertext Attasks)的安全性. 在給定標識和選擇消息攻擊下(Selective Identity and Chosen-Message Attacks, sID-CMA)滿足存在性不可偽造.

Yu 等[13]借鑒Waters 標識加密方案[7]中的構造技術, 提出了第一個在標準模型下可證明安全的標識簽密方案. 簽名的安全性和密文的安全性分別基于CDH 和DBDH 困難問題假設. 然而, 文獻[14] 指出Yu 等提出的方案存在和Malone-Lee 方案同樣的安全缺陷, 無法達到語義安全, 并對Yu 的方案進行改進, 在保證不可偽造安全性的同時實現(xiàn)語義安全. Selvi 等[15]結合Waters 標識加密方案[7]和Paterson等人的標識簽名方案[28], 設計一個在標準模型下可證明安全的標識簽密方案. 該方案在選擇消息和標識攻擊下具有強不可偽造的安全性(Strong Unforgeability against Chosen Message and Identity Attacks,SUF-CMIA). Li 和Takagi[16]提出一個在標準模型下完全安全的標識簽密方案, 代價是增加簽密密文長度和計算開銷. Li 等[17]對文獻[13] 中的方案進行修改, 實現(xiàn)安全高效的標識簽密方案. Karati 等[18]針對物聯(lián)網(wǎng)應用需求, 提出一個適用于物聯(lián)網(wǎng)的可證明安全的標識簽密方案. 方案的安全性基于修改的BDHI 困難問題假設和修改的B-SDH(Bilinear Strong Diffie-Hellman) 困難問題假設. 文獻[29–34] 分別研究了不同功能的簽密方案.

自2016 年正式公布SM9 標識密碼算法成為國家密碼行業(yè)標準后, SM9 標識密碼算法得到國內學者的積極研究. Cheng[35]給出了SM9 密鑰協(xié)商協(xié)議和加密算法的規(guī)范安全性證明. 文獻[21] 把盲簽名技術拓展到SM9 數(shù)字簽名算法中, 提出了一個基于SM9 的盲簽名方案. 文獻[20] 研究如何提高SM9 數(shù)字簽名算法的計算效率, 提出能夠實現(xiàn)快速簽名和驗證的具體方法, 有效降低了簽名算法的計算復雜度. 文獻[24] 研究SM9 標識密碼算法中用戶私鑰的生成, 提出可分離匿名分布式密鑰產生分發(fā)方案. 用戶私鑰生成是一個交互過程, 該過程無雙線性對運算且不需要通過安全信道發(fā)送私鑰. 文獻[22] 提出基于SM9算法的可證明安全區(qū)塊鏈隱私防護方案, 實現(xiàn)不可偽造、保證節(jié)點匿名和前向安全等性能. 文獻[25] 研究SM9 標識加密算法中用戶的撤銷, 提出具有魯棒性的安全用戶撤銷方案. 方案中用戶的撤銷通過服務器輔助實現(xiàn). 文獻[23] 研究了SM9 中R-ate 雙線性對的快速計算方法. 綜上, 目前尚未發(fā)現(xiàn)基于商密SM9 的標識簽密方案的公開研究成果.

1.3 本文組織結構

在第2 節(jié)回顧雙線性群、困難問題假設、標識簽密和安全模型的形式化定義等預備知識. 第3 節(jié)給出基于SM9 的簽密方案的具體構造. 在第4 節(jié), 根據(jù)安全模型證明了方案的安全性, 并在第5 節(jié)對提出的方案進行性能分析和編程實驗仿真. 第6 節(jié)對本文的工作進行總結.

2 預備知識

本節(jié)回顧雙線性群、困難問題假設、標識簽密和安全模型等基本知識.

2.1 雙線性群

設λ 為安全參數(shù), N 是與λ 相關的大素數(shù). G1, G2和GT都是階為N 的循環(huán)群, 雙線性映射e:G1×G2→GT滿足以下條件:

(1) 雙線性性(Bilinearity): 對任意的元素P ∈G1, Q ∈G2和a, b ∈ZN, 都有e(aP,bQ) =e(P,Q)ab;

(2) 非退化性(Non-degeneracy): 至少存在元素P ∈G1, Q ∈G2, 滿足e(P,Q)?=1;

(3) 可計算性(Computability): 對于任意的P ∈G1, Q ∈G2, 存在多項式時間算法高效地計算e(P,Q).

此外, 若P, Q 分別為群G1和G2的生成元, 則存在有效的公開可計算同構映射ψ :G2→G1, 使得ψ(Q)=P. 雙線性群BP 由以上五元組(G1,G2,GT,e,N) 組成.

2.2 困難問題假設

2.3 標識簽密方案的定義

一個標識簽密(Identity-Based Signcryption) 方案由以下四個多項式時間算法描述.

? Setup(λ): 以系統(tǒng)安全參數(shù)λ 為輸入,系統(tǒng)建立算法Setup 輸出系統(tǒng)主公鑰mpk 和主私鑰msk.該算法由密鑰生成中心(KGC) 運行.

? KeyGen(mpk,msk,ID): 以系統(tǒng)主公鑰mpk, 系統(tǒng)主私鑰msk 和用戶標識ID 為輸入, 用戶私鑰生成算法KeyGen 輸出用戶ID 對應的私鑰skID. 該算法由KGC 運行.

? Signcrypt(mpk,M,skIDS,IDR): 以系統(tǒng)主公鑰mpk, 明文數(shù)據(jù)M, 簽名加密者的私鑰skIDS和接收者標識IDR為輸入, 簽密算法Signcrypt 輸出簽密密文CT. 該算法由簽名加密者執(zhí)行. 在下文中, 默認簽名加密者和密文發(fā)送者是同一個實體.

? Unsigncrypt(mpk,CT,IDS,skIDR): 以系統(tǒng)主公鑰mpk,簽密密文CT,發(fā)送者標識IDS以及接收者IDR對應的私鑰skIDR為輸入, 解密驗證算法Unsigncrypt 輸出明文數(shù)據(jù)-簽名對(M,σ)或者⊥. 符號⊥表示該簽密密文的解密結果不是一個由發(fā)送者簽名的數(shù)據(jù). 該算法由密文解密者執(zhí)行.

標識簽密方案的正確性要求對任意的(mpk,msk)←?Setup(λ), skID←?KeyGen(mpk,msk,ID)和 CT ←? Signcrypt(mpk,M,skIDS,IDR), 當且僅當發(fā)送者 IDS對 M 進行了有效簽名,Unsigncrypt(mpk,CT,IDS,skIDR)=(M,σ).

2.4 安全模型

簽密既包含數(shù)據(jù)加密功能, 又包含數(shù)據(jù)簽名功能. 只有授權的接收者才能正確解密獲得明文數(shù)據(jù), 并驗證發(fā)送者是否對該數(shù)據(jù)進行簽名. 因此, 簽密的安全性不僅要求保護數(shù)據(jù)的私密性, 而且要求加密數(shù)據(jù)簽名的不可偽造性. 本文參考文獻[27], 針對數(shù)據(jù)私密性, 給出在適應性選擇密文攻擊下的不可區(qū)分性(Indistinguishbility against Adaptive Chosen-Ciphertext Attacks, IND-CCA) 安全模型; 針對簽名的不可偽造性, 給出適應性選擇消息和標識攻擊下的存在性不可偽造(Existentially Unforgeable against Adaptive Chosen Message and Identity Attacks, EUF-CMIA) 安全模型. 這兩個安全模型都是通過由挑戰(zhàn)者(challenger) 和攻擊者(adversary) 參與的游戲來定義. IND-CCA 安全模型的定義如下.

系統(tǒng)建立階段. 給定安全參數(shù)λ, 挑戰(zhàn)者運行算法Setup(λ), 生成主公鑰mpk, 并發(fā)送mpk 給攻擊者.

詢問階段1. 攻擊者可以適應性詢問以下諭言器.

猜測階段. 最后, 攻擊者輸出對μ 的猜測μ′∈{0,1}. 如果μ′=μ, 則攻擊者獲勝.

定義攻擊者A 獲勝的優(yōu)勢為

EUF-CMIA 的安全模型定義如下.

系統(tǒng)建立階段. 給定安全參數(shù)λ, 挑戰(zhàn)者運行算法Setup(λ), 生成主公鑰mpk, 并發(fā)送mpk 給攻擊者.

詢問階段. 攻擊者可適應性發(fā)起IND-CCA 安全模型中的詢問, 挑戰(zhàn)者按IND-CCA 安全模型回復攻擊者.

3 方案構造

本節(jié)給出基于SM9 的標識簽密方案的具體構造. 方案設計采用SM9 標識密碼算法中的符號, 方案的具體描述如下.

3.1 方案描述

3.2 方案正確性分析

假設簽密密文CT=(c,S,T) 由發(fā)送者IDS生成, 接收者為IDR, 則:

本文方案滿足標識基簽密系統(tǒng)的正確性要求.

4 安全性分析

本節(jié)分析上述方案的安全性. 從方案的構造可以看出,當系統(tǒng)的主公鑰確定后,hid 和N 是固定的. 為描述方便, H1(ID||hid,N) 和H2(M||w,N) 分別簡寫為H1(ID) 和H2(M||w). 方案的安全性由定理1和定理2保證. 安全性證明借鑒文獻[27] 中的證明技術.

定理1 令密碼雜湊函數(shù)H1,H2,H3是隨機諭言器. 如果q-BDHI 問題是難解的, 則本文提出的基于SM9 的標識簽密方案是IND-CCA 安全的.

? H3詢問. 針對三元組(Ti,wi,IDi) 的詢問, B 為H3建立列表L3, 列表中的元素以四元組(T,w,ID,R) 的形式存儲. 如果(Ti,wi,IDi) 在L3中, 則返回相應的Ri. 如果不存在, 從{0,1}n中隨機選取一個元素Ri, 設H3(Ti,wi,IDi)=Ri, 發(fā)送Ri給A 并以(Ti,wi,IDi,Ri) 更新L3.

詢問階段1.

其中等式(4)中的左邊是可計算的.

接著, B 執(zhí)行以下步驟:

S1 遍歷列表L3, 找出所有滿足Ti=T,IDi=IDv的四元組(Ti,wi,IDi,Ri). 若沒有對應的四元組, 則拒絕該密文并結束, 否則執(zhí)行步驟S2;

S2 計算Mi=c ⊕Ri, 遍歷列表L2, 找到(Mi,wi) 相應的hi, 如果不存在, 則拒絕該密文并結束,否則執(zhí)行步驟S3;

挑戰(zhàn)階段. A 輸出兩個等長的挑戰(zhàn)明文數(shù)據(jù)(M0,M1) 和發(fā)送者/接收者組合(IDS?,IDR?), 其中A沒有詢問過IDR?的私鑰. 如果IDR??= IDk, B 終止模擬. 否則, B 隨機選取t ∈Z?N, c?∈{0,1}n,S?∈G1, 計算T?=?tP1, 并返回挑戰(zhàn)密文CT?=(c?,S?,T?). 設r?=t/a, 因為α=?a ?Ik, 有

因此, A 不能分辨CT?是否是一個有效的簽密密文, 即模擬和真正的方案攻擊不可區(qū)分, 除非它詢問過H2或者H3關于w?=e(P1,Ppub)r?的值.

詢問階段2. A 繼續(xù)詢問私鑰, 簽密密文和解密. 但是, A 不能詢問IDR?的私鑰, 同時也不能詢問CT?對應(IDS?,IDR?) 的解密. B 根據(jù)詢問階段1 回復A.

因此, 可計算q-BDHI 問題的解為

最后分析解決q-BDHI 問題的概率. 從證明的設置可知, I= IDk, 即A 選擇IDk作為挑戰(zhàn)接收者的概率為1/qH1. 綜上, 如果A 以不可以忽略的優(yōu)勢? 攻破所提的方案, 則B 解決q-BDHI 問題的概率為

定理2 令密碼雜湊函數(shù)H1,H2,H3是隨機諭言器. 如果q-SDH 問題是難解的, 則本文提出的SM9標識簽密方案是EUF-CMIA 安全的.

? H3詢問. 針對三元組(Ti,wi,IDi)的詢問,B 為H3建立列表L3,列表元素以四元組(T,w,ID,R)的形式存儲. 如果(Ti,wi,IDi) 在L3中, 則返回相應的Ri. 如果不存在, 從{0,1}n中隨機選取一個元素Ri, 設H3(Ti,wi,IDi)=Ri, 發(fā)送Ri給A 并以(Ti,wi,IDi,Ri) 更新L3.

效果分為顯效、有效以及無效3個等級，顯效是指患者治療后的臨床癥狀明顯改善，透析過程中無低血壓發(fā)生；有效是指患者的臨床癥狀有所緩解，收縮壓在透析的過程中基本正常；無效則為患者在治療的過程中臨床癥狀和體征無明顯好轉，并出現(xiàn)低血壓[5]。

詢問階段.

其中等式(8)中的左邊是可計算的.

接著, B 執(zhí)行以下步驟:

S1 遍歷列表L3, 找出所有滿足Ti= T,IDi= IDv的四元組(Ti,wi,IDi,Ri). 若沒有對應的四元組, 則拒絕該密文并結束, 否則執(zhí)行步驟S2;

S2 計算Mi= c ⊕Ri, 遍歷列表L2, 找到(Mi,wi) 相應的hi, 如果不存在, 則拒絕該密文并結束, 否則執(zhí)行步驟S3;

S3 檢查所找到的hi是否滿足等式(8), 如果都不滿足, 則拒絕該密文并結束. 如果存在唯一滿足條件的三元組(Mi,wi,hi), 則輸出Mi和簽名(hi,S) 作為解密結果發(fā)送給A.

5 方案性能分析

本節(jié)從存儲效率、安全性、困難問題假設和計算效率等方面分析基于SM9 的簽密方案.

5.1 理論分析

首先從理論上比較本方案和相關的標識簽密方案, 對比結果見表1 和表2. 從表1 可知文獻[18] 和本方案具有定長的公鑰且安全性都基于q-type 類型的困難問題假設, 其他方案的公鑰長度是線性的, 安全性基于DBDH 和CDH 困難問題假設. 本方案的安全性依賴于隨機諭言模型, 其他方案都在標準模型下證明方案的安全性, 但文獻[13,14,16,17] 存在安全性不足. |G1|, |G2| 和|GT| 分別表示群G1, G2和GT中元素的大小, n 是消息的比特長度, ROM 表示隨機諭言模型, |G| 表示對稱雙線性對中群G 元素的大小(比較方案的設計都基于對稱雙線性對), N 為大素數(shù)且是群G, G1, G2和GT的階, k 是相應文獻方案中與哈希函數(shù)輸出長度和標識長度相關的整數(shù). 其中“*” 表示對應的安全性存疑.

從表2 可知, 本方案的計算效率和比較方案總體相當, 其中解密驗證算法的效率與文獻[18] 是可比的,僅包含兩個雙線性對運算, 優(yōu)于文獻[13–17] 中的方案. 對比方案都基于雙線性群設計且方案的構造都使用了密碼哈希函數(shù), 而生成雙線性群的操作可以預先完成, 所以本文忽略這部分的計算開銷. 由于比較文獻中使用的密碼哈希函數(shù)類型較多, 本文統(tǒng)一定義HB為映射到比特串的密碼哈希函數(shù), HZ為映射到的密碼哈希函數(shù), N 為大素數(shù)且是相應方案中群的階. 計算效率的對比結果見表2.

表1 標識簽密方案性能比較Table 1 Performance comparison of identity-based signcryption schemes

表2 標識簽密方案計算效率比較Table 2 Computation comparison of identity-based signcryption schemes

由于比較方案的設計采用乘法群表示, 本文使用加法群表示. 為方便比較, 本文統(tǒng)一在加法群下統(tǒng)計計算開銷并定義如下符號: sm1表示群G1中的標量乘運算(Scalar Multiplication)1在乘法群表示中, 該運算等價于相應群中的指數(shù)運算., sm2表示群G2中的標量乘運算, p 表示雙線性對運算, Et 表示群GT中的指數(shù)運算, sm 表示對稱群G 中的標量乘運算.表2 的統(tǒng)計不包含中的模運算(Modular), G, G1和G2中的點加運算(Point Addition), GT中的乘法運算.

5.2 實驗仿真

本節(jié)對方案進行編程仿真, 測試方案中各個算法的運行時間. 為測試方便, 忽略方案描述中ψ 函數(shù),并使用Type III 雙線性對仿真方案. 仿真中使用的庫為PBC (Pairing-Based Cryptography), 采用的橢圓曲線為Type F, 其中|G1| = 256 bits. 測試環(huán)境中所用的設備是一臺內存為16.0 GB 的筆記本電腦,操作系統(tǒng)為64 位的Windows 10, CPU 為Intel(R) Core(TM) i7-8558U@1.80Hz 2.00 GHz, 使用的編程語言為C++. 本文運行程序20 次后取平均值, 測試的結果如圖1 所示. 從圖1 可知, 本方案的簽密算法時間約為14.65 毫秒, 具有一定的可行性. 系統(tǒng)建立和解密驗證開銷較大, 系統(tǒng)建立時間約為54.4 毫秒, 主要開銷源自群元素的初始化和雙線性對運算及群G2上的標量乘法. 解密和驗證算法計算時間約為86.5毫秒, 主要開銷源自兩個雙線性對運算, 群G2上的標量乘法, 群GT上的指數(shù)運算和三個密碼哈希函數(shù)的計算.

圖1 方案算法的運行時間Figure 1 Computational overheads for each algorithm

6 總結

本文秉承核心技術自主創(chuàng)新、信息安全自主可控的理念, 結合我國商用密碼SM9 標識密碼算法, 設計了首個基于SM9 的高效標識簽密方案, 同時實現(xiàn)數(shù)字簽名和數(shù)據(jù)加密的功能, 有效保護了簽名數(shù)據(jù)的私密性. 與先采用SM9 簽名算法對數(shù)據(jù)簽名, 然后用SM9 加密算法加密簽名后數(shù)據(jù)的方法相比, 本方案能夠顯著減少計算開銷和通信開銷. 在隨機諭言模型中, 證明方案是IND-CCA 和EUF-CMIA 安全的.方案的安全性依賴于q-BDHI 和q-SDH 困難問題假設. 理論分析和實驗仿真結果表明本文提出的基于SM9 的標識簽密方案與現(xiàn)有國際主流高效標識簽密方案在計算效率和通信效率上相當, 在實際應用中是可行的.