一種抗替換攻擊的SM2簽名算法

嚴(yán)都力，薛李波，楊龑棟，劉 翼，延照耀

（1.延安大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院；2.延安大學(xué) 石油與環(huán)境工程學(xué)院，陜西 延安 716000）

SM2橢圓曲線公鑰密碼算法［1］是中國自主設(shè)計的公鑰密碼算法，具有存儲空間小、簽名速度快等優(yōu)勢，被廣泛用于教育、社保、金融、交通、公共安全、國防工業(yè)等重要領(lǐng)域。相關(guān)研究成果表明，雖然中國自主設(shè)計的國產(chǎn)密碼是實現(xiàn)信息系統(tǒng)安全可控的核心保障，但在使用過程中也將遭受一系列不同動機的分析和攻擊［2］。

算法替換攻擊［3-4］的主要攻擊對象是密碼算法本身，攻擊者在密碼算法設(shè)計或?qū)崿F(xiàn)過程中加入一些僅自己可知的秘密信息或陷門信息，即在密碼算法中設(shè)置陷門，用一個被嵌入陷門信息的算法來替換原誠實算法，攻擊者即可在用戶不知情的情況下竊取其密鑰信息［5-6］。替換攻擊最早起源于SIMMONS［7］提出的閾下信道，通信雙方借助密碼學(xué)技術(shù)構(gòu)建隱藏通道，隱藏傳輸?shù)拿孛苄畔ⅰｋS后，YOUNG 等［8］對RSA 加密、Diffie-Hellman 密鑰交換、ElGamal 簽名等算法給出了具體的攻擊方法。2015年，BELLARE等［9］給出了替換攻擊的形式化定義和安全模型。DEGABRIELE 等［10］克服了BELLARE 安全模型中設(shè)置攻擊者替換攻擊能力限制的局限性，提出了適用范圍更廣泛的輸入觸發(fā)替換攻擊。LIU等［11］研究了可拆分的特殊簽名體制的替換攻擊，攻擊者所持有的秘密后門信息無需嵌入替換算法便可提取簽名私鑰。JOONSANG 等［12］研究了DSA［13］簽名算法的替換攻擊，并給出了具體的顛覆方法和抵抗用戶利用簽名時間分析檢測顛覆攻擊的對策。BELLARE等［14］提出了參數(shù)顛覆的概念，并分析了非交互式零知識證明協(xié)議在公共參考串模型下遭受替換攻擊的安全性。DODIS 等［15］和DEGABRIELE 等［16］基于參數(shù)顛覆研究了偽隨機數(shù)生成器的替換攻擊問題。黃欣沂等［2］以中國商用密碼SM2的數(shù)字簽名算法和公鑰加密算法為分析對象，提出兩種高效難檢測的密鑰滲漏攻擊。此外，國內(nèi)外學(xué)者圍繞對稱加密、數(shù)字簽名、密鑰協(xié)商協(xié)議和零知識證明系統(tǒng)等不同密碼算法深入的開展了后門攻擊評估［17］。

隨著各種替換攻擊事件的不斷曝光，如何構(gòu)造抵抗替換攻擊的密碼算法，已經(jīng)成為密碼學(xué)界備受關(guān)注的一個熱點問題。目前已有相關(guān)研究學(xué)者提出了一些替換攻擊的方法，BELLARE等［18］和ATENIESE等［19］分別設(shè)計了唯一密文和唯一簽名方案的防御措施來抵制替換攻擊。RUSSELL 等［20］基于檢測安全思想提出了直接檢測并抵制算法替換攻擊的看門狗（Watchdog）安全模型。RUSSELL 等［21］基于分割融合技術(shù)，提出了一種對隨機化密碼算法的替換攻擊防范方法。MIRONOV等［22］提出了一種功能保留、安全保留、抗泄漏的密碼逆向防火墻（Cryptographic reverse firewall，CRF）來抵御顛覆攻擊。FISCHLIN等［23］提出了區(qū)別于CRF 與Watchdog 防御機制的自防御方法，同時為隨機化單鑰加密體制和具有同態(tài)性質(zhì)的公鑰加密體制設(shè)計了相應(yīng)的安全防護(hù)方法?？挡綐s等［24］提出了抵抗隨機數(shù)后門攻擊的密碼算法，并對已有的抗隨機數(shù)后門攻擊密碼算法進(jìn)行了總結(jié)和梳理。中國自主設(shè)計的國產(chǎn)商用密碼是實現(xiàn)信息系統(tǒng)安全可控的核心保障，雖然文獻(xiàn)［2］提出了針對SM2 簽名算法的秘鑰滲透攻擊，但尚未給出具體抗替換攻擊方案?；谖墨I(xiàn)［2］，在一般群模型下，本文設(shè)計了一種抗替換攻擊的SM2 簽名算法，主要研究內(nèi)容如下：

1）刻畫了針對簽名算法的替換攻擊模型，攻擊者利用這一攻擊方法能夠達(dá)到秘鑰提取和不可檢測性兩種安全目標(biāo)；

2）利用哈希函數(shù)將簽名私鑰、簽名消息與其隨機數(shù)的哈希結(jié)果作為簽名的隨機組件，對原始的SM2 簽名算法改進(jìn)，在一般群模型下，構(gòu)造具備抗替換攻擊的SM2 簽名方案，即使攻擊者替換原始SM2 簽名算法某些組件得到有效簽名，也無法獲得簽名私鑰的任何信息；

3）將抗替換攻擊的SM2 簽名算法與原始SM2簽名算法進(jìn)行效率測試，實驗結(jié)果驗證了抗替換攻擊的SM2簽名算法的可行性。

1 預(yù)備知識

1.1 哈希函數(shù)

定義1［25］一個安全的密碼學(xué)哈希函數(shù)h：{0，1}*→{0，1}n，滿足以下性質(zhì)：

1）抗碰撞性：找到2 個不同輸入M與M′，滿足h(M)=h(M′)在計算上是不可行的；

2）抗原像性：給定y=h(M)，對于概率多項式時間敵手找到一個M′，使得h(M′)=y在計算上不可行；

3）抗第二原像性：給定輸入M，對于概率多項式時間敵手找到一個M′(M′≠M)，使得h(M′)=h(M)在計算上是不可行的。

1.2 偽隨機函數(shù)

定義2［26］函數(shù)F：{0，1}λ×{0，1}ρ→{0，1}n記作一個有效的帶密鑰函數(shù)，函數(shù)表示所有f：{0，1}ρ→{0，1}n函數(shù)的集合。如果對所有概率多項式時間區(qū)分器D，存在一個可忽略的函數(shù)ε(λ)，滿足：

則稱F是一個偽隨機函數(shù)（Pseudorandom function，PRF）。區(qū)分器D、區(qū)分函數(shù)F與f優(yōu)勢定義為

1.3 SM2簽名算法

SM2 簽名算法是基于橢圓曲線的公鑰密碼算法，SM2 包含加解密算法、數(shù)字簽名算法和密鑰交換協(xié)議。定義SM2=(KeyGenSM2，SignSM2，VeyifySM2)為原始的簽名方案。選擇一個256 位素數(shù)域E(Fq)上的橢圓曲線，其參數(shù)定義為pp={q，F(xiàn)q，a，b，G，n，Hv，f，ZA}，其中p為Fp特征，參數(shù)a，b∈Fp確定了安全的橢圓曲線E(Fp)：y2=x3+ax+b，任意選取基點G=(xG，yG)，其中G≠O，O表示橢圓曲線上的無窮遠(yuǎn)點，素數(shù)n表示基點G的階；h：{0，1}*→Zn表示哈希函數(shù)，Hv：{0，1}*→{0，1}256表示消息長度為vbit 的哈希函數(shù)，在SM2 簽名算法中v取值為256；f：→Zn表示將橢圓曲線上的坐標(biāo)點轉(zhuǎn)化為整數(shù)；ZA=Hv(ENTL||ID||a||b||xG||yG||xP||yP)表示簽名身份標(biāo)識與系統(tǒng)參數(shù)的哈希值，ENTL由2個字節(jié)標(biāo)識的ID的bit 長度，ID為用戶身份標(biāo)識，xG、yG為基點，xP、yP為用戶的公鑰。SM2簽名算法描述如下：

1）秘鑰生成算法（KeyGenSM2）

①簽名者任意選取整數(shù)d，其中1 ≤d≤n；

② 計算P=dG=(xP，yP)，P表示簽名公鑰，d表示簽名私鑰。

2）簽名算法（SignSM2）

② 計算e=h()；

③任意選取隨機數(shù)k∈[1，n-1]，計算kG=(x1，y1)；

④ 計算x1=f(kG)；

⑤ 計算簽名r=(e+x1)modn，若r=0 或r+k=n，則重新選擇隨機數(shù)k；

⑥ 計算簽名s=(1+d)-1?(k-rd)modn，若s=0，則重新選擇隨機數(shù)k；

⑦ 輸出消息M的簽名σ=(r，s)。

3）驗證算法（VerifySM2）

①驗證者收到任意消息M的簽名σ=(r，s)，利用系統(tǒng)參數(shù)和簽名公鑰對簽名σ=(r，s)驗證是否有效；

② 驗 證r∈[1，n-1]和s∈[1，n-1]是否成立，若不成立，則驗證不通過；

④ 計算e=h()；

⑤ 計算t=(r+s)modn，若t=0，則驗證不通過；

1.4 一般群模型

一般群模型［27］是一種理想的安全模型。在該模型中，敵手只能訪問一個群中經(jīng)過隨機編碼后的元素，而非實際的元素，系統(tǒng)外部用戶即使知道群中的元素也必須訪問群預(yù)言機，預(yù)言機模擬群運算。預(yù)言機以2 個經(jīng)過隨機編碼的元素作為輸入，輸出則是第三個經(jīng)過隨機編碼的元素。與隨機預(yù)言機模型類似，敵手自身不能進(jìn)行群運算，必須以經(jīng)過隨機編碼的元素向預(yù)言機查詢，以獲得經(jīng)過隨機編碼的運算結(jié)果。

定義3［27］假設(shè)存在兩個同構(gòu)群G1、G2，在一般群模型中，設(shè)ζ是一個編碼函數(shù)，一個預(yù)言機O 模擬群G1上的運算，即：給定兩個元素∈G1和兩個整數(shù)e1和e2，O計算F3=e1F1+e2F2，并返回

2 替換攻擊模型

替換攻擊指攻擊者在密碼算法設(shè)計或?qū)崿F(xiàn)過程中時設(shè)置一些僅自己可知的陷門信息，用一個被嵌入陷門信息的算法來替換原始誠實算法，攻擊者即可在用戶不知情的情況下竊取其密鑰信息，替換攻擊的形式化定義如下。

定義4［5］SS=(KeyGen，Sign，Verify)記為原始簽名方案，攻擊者通過某種手段破壞SS，得到替換后的簽名方案具體算法描述如下：

替換后的簽名方案需滿足正確性要求，即

替換簽名方案除滿足正確性要求外，還需同時滿足“密鑰提取”和“不可檢測性”。其定義如下：

密鑰提?。↘eyExtract）：正常情況下，攻擊者從原始簽名中分析獲得簽名私鑰是計算上不可行的。假設(shè)存在攻擊者A 可通過在簽名方案中嵌入陷門信息，提取簽名私鑰或簽名中其他秘密信息，A首先需要對原始簽名進(jìn)行替換獲得有效的替換簽名，然后利用若干個替換后的簽名與替換密鑰提取簽名私鑰，這類攻擊是當(dāng)前最為普遍的替換攻擊方式，又被稱顛覆攻擊。其形式化定義如下：

定義5［5］SS=(KeyGen，Sign，Verify)記為原始簽名方案記作被嵌入陷門信息替換后的簽名方案，A 為概率多項式時間敵手，C 定義為挑戰(zhàn)者，A 提取密鑰游戲定義為

1）初始化：C 執(zhí)行KeyGen(1λ)與算法，生成正常簽名密鑰對(pk，sk)和替換密鑰subk，C將公鑰pk發(fā)送給A；

2）簽名詢問：A 任意選擇消息mi進(jìn)行簽名詢問，C將mi的簽名應(yīng)答給A；

A 成功提取密鑰的優(yōu)勢定義為安全參數(shù)λ的函數(shù)：

不可檢測性（detect）：該安全目標(biāo)從敵手A的視角定義，一般情況下?lián)碛泻灻借€的用戶對檢測替換簽名更加感興趣，即在不可檢測性定義中，用戶被賦予擁有簽名私鑰能力的檢測者來檢測簽名。對于沒有替換密鑰的用戶，他們無法檢測簽名是正常簽名算法還是替換后的簽名算法生成的簽名。用戶與挑戰(zhàn)者之間刻畫檢測替換簽名的游戲定義為

1）初始化：挑戰(zhàn)者C 執(zhí)行KeyGen(1λ) 和算法生成原始簽名密鑰對(pk，sk)和替換密鑰subk，C將公鑰pk發(fā)送給D；

2）訓(xùn)練：D詢問C關(guān)于消息mi的簽名，C將對應(yīng)的簽名σi返回給D；

3）挑戰(zhàn)：D輸入消息mi，C選擇b∈{0，1}，若b=0，C執(zhí)行σi=Sign(sk，mi)，得到簽名σi作為應(yīng)答，否則，C執(zhí)行將作為應(yīng)答；

4）猜測：D 輸出一個b′，如果b′=b，D 檢測替換簽名成功。

3 抗替換攻擊的SM2簽名算法

根據(jù)文獻(xiàn)［2］對SM2 簽名算法的替換攻擊，攻擊者在攻擊前，運行密鑰生成算法生成替換密鑰subk，然后借助密碼雜湊函數(shù)Fκ計算隨機數(shù)ki。被篡改后SM2簽名算法與原始SM2簽名算法區(qū)別在于隨機數(shù)k的選擇，ki為第i次運行被篡改SM2 簽名算法所使用的隨機數(shù)，該攻擊方法最終達(dá)到秘鑰提取和不可檢測性安全目標(biāo)，詳細(xì)攻擊方案及安全性分析見文獻(xiàn)［2］。

為了抵抗攻擊者對SM2 簽名算法的替換攻擊，對SM2 簽名算法進(jìn)行改進(jìn)，借助哈希函數(shù)和簽名私鑰計算簽名中輔助隨機數(shù)α=h(d||M||k)，其中，d是簽名私鑰，M是簽名消息，k為隨機數(shù)。針對不同簽名消息m計算得到不同的α，且α只能被簽名者計算，然后將α作為簽名組件應(yīng)用于生成簽名。簽名中輔助隨機數(shù)α的計算與簽名消息M、簽名私鑰d綁定目的為了保證α值的唯一性。由于改進(jìn)后的SM2簽名方案中使用的輔助隨機數(shù)α由特定方法計算，即使攻擊者嘗試通過替換k達(dá)到攻擊目的，簽名者也可以通過計算和判斷α來確定是否繼續(xù)執(zhí)行簽名算法。若簽名者計算α=h(d||M||k)，則繼續(xù)執(zhí)行簽名算法；否則，終止。此判斷過程保證了簽名算法中使用的隨機數(shù)α的正確有效性，抗替換的SM2簽名方案描述如下。

1）密鑰生成算法（KeyGenSM2）

①簽名者任意選取整數(shù)d，其中，1 ≤d≤n；

② 計算P=dG，P表示簽名公鑰，d表示簽名私鑰。

2）簽名算法（SignSM2）

② 計算e=h()；

③ 任意選取隨機數(shù)k∈[1，n-1]，計算α=h(d||M||k)；

④ 計算αG=(x1，y1)；

⑤ 計算x1=f(αG)；

⑥ 計算簽名r=(e+x1)modn，若r=0 或r+k=n，則重新選擇隨機數(shù)k；

⑦ 計算簽名s=(1+d)-1?(α-rd)modn，若s=0，則重新選擇隨機數(shù)k；

⑧ 輸出消息M的簽名σ=(r，s)。

3）驗證算法（VerifySM2）

①驗證者收到任意消息M的簽名σ=(r，s)，利用系統(tǒng)參數(shù)和簽名公鑰對簽名σ=(r，s)驗證是否有效；

② 驗 證r∈[1，n-1]和s∈[1，n-1]是否成立，若不成立，則驗證不通過；

④ 計算e=h()；

⑤ 計 算t=(r+s)modn，若t=0，則驗證不通過；

⑦ 計算x1′=f(sG+tP)；

4 安全性分析

4.1 正確性分析

由s=(1+d)-1?(α-rd)modn、t=(r+s)modn和P=dG得

4.2 抗替換攻擊性

定理1假設(shè)攻擊者A 在概率多項式時間qt內(nèi)，經(jīng)過qs次簽名詢問得到兩個連續(xù)有效的抗替換攻擊SM2 簽名，A 利用密鑰提取的方法提取出私鑰d的概率是可忽略的。

證明若攻擊者A獲得任意兩個連續(xù)消息Mi-1和Mi的替換攻擊SM2簽名，分別為和，A按照秘鑰提取方法提取簽名私鑰：

①計算ki=Fκ([ri]G)；

②計算αi=h(d||Mi||ki)；

③依據(jù)等式si=(1+d)-1?(αi-rid)modn；

⑤ 判斷d′=d是否成立。

上述步驟②等式中，因αi=h(d||Mi||ki)中d是簽名私鑰A 未知，A 無法計算出αi，即使A 已知其他簽名組件信息，也無法繼續(xù)計算得到d′，更無法判斷d′=d是否成立，所以A 提取私鑰d失敗。此外，即使可以替換每個抗替換攻擊SM2 簽名中使用的隨機數(shù)ki，當(dāng)A獲取x個有效簽名，其中x≤qs：

根據(jù)以上方程式，敵手A 已知簽名Mi、ri、si和ki，但A 仍然無法在概率多項式時間內(nèi)計算簽名中的αi，x個方程等式中有x+1個未知數(shù)，A 無法通過已知簽名信息提取出簽名私鑰d。

綜上得證，攻擊者A 利用密鑰提取的方法提取簽名密鑰d的概率是可忽略的，證畢。

4.3 存在性不可偽造

定理2若h是均勻一致且抗碰撞的哈希函數(shù)，f是幾乎可逆的函數(shù)，則抗替換攻擊的SM2 簽名方案在一般群模型下是滿足自適應(yīng)選擇消息攻擊下存在性不可偽造。

證明假設(shè)攻擊者A 不能直接訪問雙線性群的元素，而只能通過與預(yù)言機O 交互獲得群元素的隨機映射的像，群運算由預(yù)言機O 執(zhí)行，攻擊者可以通過訪問預(yù)言機O 獲得新的群元素。敵手可以從公鑰或者簽名預(yù)言機查詢中獲取群元素句柄。實際上，A 可以使用公鑰中的句柄和簽名作為“基礎(chǔ)”來執(zhí)行進(jìn)一步的群操作。

令(G，P)是公鑰中的群元素句柄是簽名查詢中創(chuàng)建的群元素句柄，qs表示簽名查詢詢問的次數(shù)，根據(jù)假設(shè)A 想要計算的所有群元素都有一個表單其中，是A 隨機選擇的已知整數(shù)，因此，可以通過以下方式統(tǒng)一群操作查詢系數(shù)向量(z1，z2，…，例如，將基本元素G乘以整數(shù)z可以表示為一個群操作查詢(z，0，…，0)。

假設(shè)存在一個概率多項式敵手A，存在挑戰(zhàn)者C模擬A 的攻擊環(huán)境，使A 的優(yōu)勢可以忽略不計。為了回答A 的群操作查詢，挑戰(zhàn)者C 將用一個L來記錄群查詢操作中生成的信息。挑戰(zhàn)者C首先選擇基點G，將(1，G，-，-)添加到列表L中，然后隨機選擇一個整數(shù)d∈Zn，計算P=dG，將(d，P，-，-)添加至L列表中，設(shè)qs表示敵手A 進(jìn)行簽名詢問的次數(shù)，qc表示C 與A 交互過程中當(dāng)前進(jìn)行簽名查詢的次數(shù)作為將在簽名查詢中生成的群元素處理。C 與A 交互過程中群操作查詢和簽名查詢的回答如下：

①令j為最大索引且zj≠0；

② 若j>qc+2，返回⊥退出；

③對于每一個i∈{1，2，…，j}，從(αi，Vi，-，-)列表中取αi計算z′=z1+z2d+z3α1+…+zjαjmodn；

④ 如果存在(z′，V′，-，-)在列表L中，挑戰(zhàn)者C返回V′給A，否則，分為以下兩種情形：

情形1 如果z2=0，任意選擇V′，將(z′，V′，(z1，添加至列表L，將V′返回給A；

情形2 如果z2≠0，任意選擇Z′∈{0，1}256，M′∈M3，計算h(Z′||M′))，然后將添加至列表L中，然后返回V′給A。

2）對于某些消息M的簽名詢問，挑戰(zhàn)者C任意選取k∈Zn，計算α=h(d||M||k)；然后，進(jìn)行群操作查詢(α，0，…，0)獲取V，計算x=f(V)，r=h(Z||M) +xmodn，s=(α-rd)/(1+d)modn，其中，Z為SM2簽名算法中已知確定的信息；最后，挑戰(zhàn)者C返回簽名(r，s)作為A的詢問應(yīng)答。

假設(shè)哈希函數(shù)h是均勻分布且抗碰撞的，敵手A 通過上述詢問，對于任意一個消息偽造出消息M*的簽名(r*，s*)的概率是可忽略的，下面進(jìn)行具體分析：

挑戰(zhàn)者C 誠實地生成了公鑰和簽名，如果C 能夠完美地回答群操作查詢，那么說明C 幾乎能夠為敵手A 模擬一個完美的攻擊環(huán)境。實際上，除了群操作查詢的情形2 之外，所有的群元素句柄都是隨機統(tǒng)一選擇的。現(xiàn)在，假設(shè)情形2 中生成的V′=也是均勻分布的，事實上，Z′和M′是隨機均勻選擇的，且h是均勻哈希函數(shù)，則情形2 中f-1的輸入是均勻分布的。根據(jù)f-1幾乎可逆的事實，有V′是均勻分布的。另外，根據(jù)Schwartz-Zippel 引理［28］，在列表L中存在兩個分量(z′，V′，-，-) 和(z′′，V′′，-，-)，其中，z′≠z″但V′≠V″，其概率是可忽略的，qG表示敵手A執(zhí)行的群操作查詢總數(shù)。

為了繼續(xù)完成上述證明，只需要證明(r*，s*)在M*上有效簽名的概率是可以忽略的。令α*=s*+(s*+r*)d，(r*，s*)是消息M*上有效的簽名，當(dāng)且僅當(dāng)(α*，V*，-，-) 出現(xiàn)在列表L中，其中V*=f-1(r*-h(Z||M*))。若要證明(r*，s*)在M*上的有效簽名概率是可以忽略不計的，就等價于證明(α*，V*，-，-)出現(xiàn)在表L中的概率是可忽略的。此處聲明，V*?{G，P}，否則，敵手A 可以通過使用s*≠0和s*+r*≠0確定地從(r*，s*)中計算d，此處與d對敵手A 完全隱藏的事實相矛盾。換句話說，V*只能在群操作查詢或簽名查詢時創(chuàng)建。有以下兩種情形：

情形1（V*在簽名查詢中被創(chuàng)建）：如果V*∈{V1，V2，…}，對于某個i設(shè)置V*=Vi，并設(shè)置(ri，si)為第i個簽名查詢消息Mi和輔助信息Zi的簽名。換句話說，存在s*+(s*+r*)d=si+(si+ri)d，由于私鑰d對敵手是完全隱藏的，所有只有當(dāng)s*=si和s*+r*=si+ri同時保持一致才成立，這種情況才會發(fā)生且概率不可忽略。在這種情況下，(r*，s*)是M*上的有效簽名，當(dāng)且僅當(dāng)方程h(Zi||Mi)=rf(V*)=h(Z||M*)保持成立。然而M*≠Mi，以上意味著敵手A 必須找到一個碰撞(Zi||Mi，Z||M*)，然而哈希函數(shù)h是抗碰撞的，所以以上情況只會以忽略不計的概率發(fā)生。

綜上，在哈希函數(shù)h是抗碰撞的假設(shè)下，簽名(r*，s*)是M*上有效簽名的概率是可以忽略的，證畢。

5 性能分析

5.1 計算復(fù)雜度分析

下面針對抗替換攻擊的SM2 簽名算法的模乘、模逆及點積運算進(jìn)行分析，一次模逆運算約等于算法執(zhí)行9 次點積運算。本文采用[mc]、[mn]和[dj]分別表示模乘、模逆與點積運算，設(shè)一次模乘運算的數(shù)據(jù)規(guī)模為n，則一次模乘、模逆與點積運算的復(fù)雜度分別為O(n2log2n)、O(9n2)和O(n2)，其中[mn]=9[dj]。T1、T2分別表示SM2 簽名算法與抗替換攻擊的SM2 簽名算法的總運算量，兩種簽名方案的運算量比較如表1所示。

表1 SM2簽名算法與抗替換攻擊的SM2簽名算法運算量比較

表1 中T1=O[(2 log2n+13)n2]，T2=O[(2 log2n+13)n2]，抗替換攻擊SM2 簽名算法的計算復(fù)雜度等于SM2簽名算法的計算復(fù)雜度。

5.2 算法執(zhí)行效率分析

下面分別對SM2 簽名算法和抗替換攻擊的SM2 簽名算法的效率進(jìn)行測試，并對每個算法執(zhí)行10 000 次，求其效率平均值。實驗環(huán)境為Inter（R）Core（TM）惠普i5-7400CPU@3.00 GHz 處理器、Ubuntu16.0.4 LTS，64位操作系統(tǒng)，內(nèi)存容量為6.00 GB的臺式機，編譯環(huán)境采用JetBrains PyCharm 2019.2.3版本，編譯語言采用python 3.6.5編譯程序。兩種簽名方案的密鑰生成、簽名及驗證算法執(zhí)行效率分別作對比如圖1所示。

圖1 兩種簽名算法執(zhí)行效率對比圖

根據(jù)圖1 分析，SM2 簽名方案與本文提出的抗替換攻擊SM2 簽名算法在密鑰生成算法、驗證算法執(zhí)行效率相同。由于抗替換攻擊SM2 簽名方案在計算簽名時引入了哈希函數(shù)計算輔助隨機數(shù)耗時的原因，簽名算法耗時比原始SM2 簽名算法耗時長0.023 ms。綜上，在簽名長度相同的情況下，抗替換攻擊的SM2 簽名算法執(zhí)行效率與原始SM2 簽名算法的執(zhí)行效率基本一致，而且還具備了抗替換攻擊性。

6 結(jié)論

本文首先簡要回顧了SM2 簽名算法遭受的替換攻擊；然后利用哈希函數(shù)將簽名私鑰、簽名消息與其簽名選擇的隨機數(shù)的哈希結(jié)果作為簽名的隨機組件，對原始的SM2 簽名算法改進(jìn)，構(gòu)造了具備抗替換攻擊的SM2 簽名方案，并在一般群模型下證明了方案的安全性；最后，對提出的抗替換攻擊SM2 算法與已有算法進(jìn)行了效率測試，實驗結(jié)果證明了提出的算法在計算復(fù)雜度與算法執(zhí)行效率方面與已有算法基本一致。該簽名算法的研究不僅有效的抵御了替換攻擊帶來的安全威脅，而且豐富了國產(chǎn)密碼體系。