國(guó)密SM2中k值選取的研究與改進(jìn)

郇靜 趙連軍

摘要：區(qū)塊鏈技術(shù)中的安全問題一部分取決于移動(dòng)設(shè)備的能源算例和應(yīng)用情況，這決定了設(shè)備會(huì)具有安全隱患，特別是智能卡等嵌入系統(tǒng)，它們特定應(yīng)用情況下是無法支持隨機(jī)源的，解決隨機(jī)源選取問題從而加強(qiáng)密鑰對(duì)的安全性是非常重要的。隨著我國(guó)自主提出的公鑰密碼算法SM2的地位不斷提高，該算法應(yīng)用到設(shè)備和系統(tǒng)中是必然趨勢(shì)，通過HMAC算法改進(jìn)SM2簽名生成中隨機(jī)值k的選取方式，最終使SM2轉(zhuǎn)換為確定性方案，提高嵌入式系統(tǒng)中隨機(jī)源的質(zhì)量，增加算法安全性，使之普遍適用。

關(guān)鍵詞： SM2; HMAC; 隨機(jī)源; ECDSA; ECC ;交易可鍛性

中圖分類號(hào)：TP9309.7? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）30-0054-03

Abstract：Part of the security problems in blockchain technology depend on the energy calculation examples and applications of mobile devices， which determines that devices will have security risks， especially embedded systems such as smart cards， which can not support random sources in specific applications. It is very important to solve the problem of random source selection so as to enhance the security of key pair. With the improvement of the status of public key cryptography algorithm SM2， which is proposed by our country， it is an inevitable trend to apply this algorithm to devices and systems. Through HMAC algorithm， we can improve the selection of random value K in SM2 signature generation， and finally transform SM2 into a deterministic scheme， improve the quality of random sources in embedded systems， increase the security of the algorithm， and make it universally applicable.

Key words：SM2; HMAC; random source ; ECDSA; ECC; transaction malleability

1 引言

自國(guó)家大力發(fā)展區(qū)塊鏈技術(shù)以來，區(qū)塊鏈技術(shù)在金融、政務(wù)、醫(yī)療等領(lǐng)域發(fā)揮著重要的作用。從中本聰創(chuàng)造的比特幣問世，到第二代以太坊等各種區(qū)塊鏈類型都會(huì)存在一個(gè)共性的問題——交易可鍛性（Transaction Malleability），而這個(gè)問題是由區(qū)塊鏈自身的特性決定的，是杜絕不了的，但可以規(guī)避它。在交易中，私鑰等數(shù)據(jù)在發(fā)送之前對(duì)其進(jìn)行加密和簽名，接著最終獲得哈希值為交易ID返回給用戶。在驗(yàn)證交易的真實(shí)性時(shí)，大部分簽名算法都是基于橢圓曲線數(shù)字簽名算法（Elliptic Curve Digital Signature Algorithm ，ECDSA）[1]，它存在的一個(gè)問題是修改某個(gè)字節(jié)后而簽名依然校驗(yàn)成功，交易依然能夠成功進(jìn)行，這就會(huì)導(dǎo)致非法攻擊，使交易平臺(tái)資金大量損失。

交易可鍛性問題實(shí)質(zhì)是加密和簽名中的安全性問題。2010年底，我國(guó)國(guó)家密碼管理局發(fā)布了SM2橢圓曲線公鑰密碼算法[2-6]，成為我國(guó)首個(gè)公鑰密碼算法標(biāo)準(zhǔn)，區(qū)塊鏈中的密碼學(xué)體系將逐漸被國(guó)密體系取代。SM2和ECDSA都采用了橢圓曲線密碼體制（Elliptic Curve Cryptography，ECC）[7]，其中的數(shù)字簽名技術(shù)應(yīng)用廣泛，電子商務(wù)和網(wǎng)絡(luò)安全認(rèn)證的核心技術(shù)就是數(shù)字簽名，區(qū)塊鏈技術(shù)其底層技術(shù)之一就是數(shù)字簽名。相較其他公鑰體制，橢圓曲線密碼體制的主要優(yōu)勢(shì)是計(jì)算參數(shù)小，密鑰更短[8]，運(yùn)算速度更快，簽名也更加短小[9]，效率也更高[10]，因此性能優(yōu)良，應(yīng)用廣泛，尤其適用于存儲(chǔ)空間、處理能力、帶寬及功耗受限的場(chǎng)合[11]，比如智能卡嵌入設(shè)備、區(qū)塊鏈應(yīng)用設(shè)備等。

ECDSA是標(biāo)準(zhǔn)的數(shù)字簽名方案，在各種協(xié)議中提供了真實(shí)的數(shù)據(jù)的完整性和可驗(yàn)證性。SM2作為與ECDSA同源的公鑰密碼算法，存在隨機(jī)源k值的選取問題， 本文將對(duì)簽名過程中的隨機(jī)值k的選取進(jìn)行改進(jìn)，在隨機(jī)選擇的基礎(chǔ)上加上HMAC算法，提高k值選取質(zhì)量，增加加密和簽名中隨機(jī)源的安全性。

本文描述的方法過程具有以下特點(diǎn)：

（1）制定的簽名與普通SM2完全兼容。驗(yàn)證簽名的實(shí)體不需要更改，甚至不需要知道用于生成k的過程。

（2）密鑰對(duì)的生成不會(huì)改變。現(xiàn)有的密鑰對(duì)可以被用于確定性SM2。

（3）使用確定性SM2可以與普通的SM2應(yīng)用在相同的輸入上，即在要簽名的消息上計(jì)算哈希值，使用安全加密哈希函數(shù)。

本文規(guī)定的確定性SM2定義采取了一些相對(duì)任意的選擇;這樣做是為了使它盡量普遍適用，以便最大化包含測(cè)試向量的有用性。

需要注意的是，密鑰對(duì)的生成仍然需要一個(gè)隨機(jī)源。在嵌入式系統(tǒng)的隨機(jī)性是一個(gè)質(zhì)量問題，它通?？梢园焉擅荑€對(duì)發(fā)生在更多控制條件下，生成的關(guān)鍵可能是其他地方和進(jìn)口設(shè)備。確定性SM2只處理簽名生成時(shí)的隨機(jī)性需要。

2 預(yù)備知識(shí)

國(guó)外標(biāo)準(zhǔn)中的數(shù)字簽名算法有很多，我們用ECDSA來代表國(guó)外標(biāo)準(zhǔn)中基于ECC的數(shù)字簽名算法。ECDSA中在Hash函數(shù)選取中沒有明確規(guī)定，通常采用SHA-256。

SM2算法的密鑰生成過程與ECDSA算法一致，但其簽名及驗(yàn)證過程與ECDSA算法有一定的不同，在Hash函數(shù)的選取上，ECDSA沒有明確指定，而SM2中規(guī)定使用SM3[12]哈希算法。SM2簽名算法為：設(shè)待簽名的消息為M，為了獲得M的數(shù)字簽名，作為簽名用戶A實(shí)現(xiàn)以下步驟：

SM2的一個(gè)特點(diǎn)是對(duì)于每一次簽名生成，都需要產(chǎn)生一個(gè)新的隨機(jī)值（以下稱為k），為了有效性和安全性，k必須從一組模整數(shù)中隨機(jī)并且一致的選取，并且整個(gè)過程使用加密安全。

對(duì)加密安全隨機(jī)源的需求阻礙了SM2簽名方案的部署。在加密算法系統(tǒng)中，RSA[13]簽名算法用于指定的公開密鑰加密標(biāo)準(zhǔn)PKCS#1[14][RFC3447]，它計(jì)算更昂貴，由于RSA（這種填充方案）是確定的，因此不需要隨機(jī)性的來源。

SM2的隨機(jī)性由于隨機(jī)源的選取困難，使實(shí)現(xiàn)更難測(cè)試。自動(dòng)測(cè)試無法可靠地檢測(cè)是否使用了足夠高質(zhì)量的隨機(jī)源。這使得實(shí)現(xiàn)過程更容易出現(xiàn)災(zāi)難性故障的攻擊，而這種攻擊通常是在系統(tǒng)部署并成功攻擊之后才被發(fā)現(xiàn)的。

通過使用產(chǎn)生“隨機(jī)”值k的確定性過程，可以將SM2轉(zhuǎn)換為確定性方案。該過程必須滿足一定的密碼特性，才能維持簽名方案的可驗(yàn)證性和不可偽造性，也就是說對(duì)于不知道簽名私鑰的人來說，從輸入消息到對(duì)應(yīng)的k值映射在計(jì)算上必須從隨機(jī)且一致的選擇函數(shù)（從消息集合到可能的k值集合）來返回。

3 SM2與ECDSA的比較

ECDSA與SM2兩個(gè)數(shù)字簽名算法都是基于相同的橢圓曲線（如素?cái)?shù)域與二進(jìn)制域），它們的安全性都是基于橢圓曲線離散對(duì)數(shù)同題求解的困難性。ECDSA已經(jīng)成為國(guó)際標(biāo)準(zhǔn)，其依賴的橢圓曲線可以使用NIST等推薦的曲線，而SM2并沒有給出推薦的曲線，曲線參數(shù)的產(chǎn)生需要利用一定的算法產(chǎn)生[15]。

（1）對(duì)于簽名信息的預(yù)處理，ECDSA中隊(duì)消息M不做任何處理，而在SM2中，消息=ZA‖M，ZA=（ENTLA‖IDA‖a‖b‖xG‖yG‖xA‖yA），串接用戶和曲線信息后，大大提高安全性，加強(qiáng)抗抵賴性。

（2）ECDSA和SM2中都存在隨機(jī)數(shù)k，在k和dA都不知道的情況下需要解決兩個(gè)橢圓曲線離散對(duì)數(shù)問題，在計(jì)算上是不可行的。我們可以認(rèn)為它們屬于同一個(gè)安全性級(jí)別的。

（3）ECDSA沒有規(guī)定哈希算法的使用，SM2中規(guī)定使用SM3，SM3輸出比特串為256，安全性于SHA-256相當(dāng)，但高于MD5、SHA-1、SHA-224。

（4）綜合來看，SM2是與ECDSA同源相似的一種密鑰算法，但其安全性要高于ECDSA，是一種可信賴的安全算法。

4 選取k值方法的改進(jìn)

基于SM2與ECDSA的相似性，我們可以針對(duì)隨機(jī)源的確定性隨機(jī)選取過程進(jìn)行改進(jìn)，我將它定義為確定性SM2。

確定性SM2是通過使用標(biāo)準(zhǔn)的SM2簽名生成過程在輸入消息M上生成SM2簽名的過程，只是k值不再是隨機(jī)生成的，而是通過下面描述的過程得到的。

4.1 構(gòu)建塊HMAC

HMAC[16][RF2014]是使用哈希函數(shù)和密鑰構(gòu)造的消息身份驗(yàn)證代碼（Hash-based Message Authentication Code）的縮寫。這里，我們使用HMAC，其哈希函數(shù)H與用在簽名生成或驗(yàn)證之前處理輸入消息的哈希函數(shù)H相同。我們用以下方式表示鍵值為K的HMAC在數(shù)據(jù)V上的應(yīng)用過程：

HMAC_K（V）

它的返回長(zhǎng)度為hlen（底層哈希函數(shù)的輸出長(zhǎng)度H）的比特序列。

4.2 k的產(chǎn)生

首先給定輸入消息m，應(yīng)用以下過程：

a.通過哈希函數(shù)H處理m，得到

h1=H（m）

（h1是hlen位的序列）

b.設(shè)置：V=0x01 0x01 0x01 ... 0x01

使V的長(zhǎng)度（以比特為單位）等于8×ceil（hlen/8）。例如，在一個(gè)八進(jìn)制的系統(tǒng)中，如果H是SHA-256，那么V被設(shè)置為一個(gè)值位1的32個(gè)八進(jìn)制序列。需要注意的是，在這一步和后面的所有步驟中，我們使用與步驟a相同的H函數(shù)來處理輸入消息。

c.設(shè)置：K = 0x00 0x00 0x00 ... 0x00

這樣K的長(zhǎng)度（以比特為單位）等于8×ceil（hlen/8）。

d.設(shè)置：

K = HMAC_K（V||0x00||int2octets（x）||bits2octets（h1））

其中“||”表示連接。換句話說，我們使用K值計(jì)算HMAC，按照以下順序鏈接：V的當(dāng)前值、值0的八位序列、SM2私鑰x的編碼和散列消息（可能根據(jù)bits2octets的變換來指定被截?cái)嗪蛿U(kuò)展的信息），HMAC的結(jié)果是K的新值。請(qǐng)注意，私鑰x在[1，q-1]范圍內(nèi)，因此為int2ocets提供了適當(dāng)?shù)妮斎耄瑥亩a(chǎn)生輸出的rlen位，即整數(shù)個(gè)八位字節(jié)（rlen是8的倍數(shù)）。

e.設(shè)置：V = HMAC_K（V）

f.設(shè)置：K = HMAC_K（V||0x01||int2octets（x）||bits2octets（h1））

注意內(nèi)部八位字節(jié)這時(shí)候是0x01.

g.設(shè)置：V = HMAC_K（V）

h.應(yīng)用以下算法直接找到k

1.將T設(shè)置為空序列。T的長(zhǎng)度（以位為單位）表示為tlen;因此在這一步上，tlen=0.

2.當(dāng)tlen

V = HMAC_K（V）

T = T || V

4.3 計(jì)算

k = bits2int（T）

如果k的值在[1，q-1]范圍內(nèi)，并且適用于SM2（即它產(chǎn)生的r值不是0），則k的生成完成，所得k值用于SM2。否則，計(jì)算

K = HMAC_K（V || 0x00）和V = HMAC_K（V）并循環(huán)（嘗試生成一個(gè)新的T）。

請(qǐng)注意，當(dāng)k由T生成時(shí)，bits2int的結(jié)果與G進(jìn)行比較，而不是取q的模，如果值不在1到q-1之間，則進(jìn)行循環(huán)。執(zhí)行一個(gè)簡(jiǎn)單的模塊簡(jiǎn)化會(huì)對(duì)簽名安全性產(chǎn)生有害的偏差。

5 結(jié)束語

從區(qū)塊鏈的交易可鍛性問題出發(fā)，發(fā)現(xiàn)此問題是受使用的簽名算法安全性影響的，簽名算法的安全性受隨機(jī)源影響，SM2國(guó)密算法以ECC橢圓曲線數(shù)字簽名算法為基礎(chǔ)，本文通過改進(jìn)ECC密碼算法中的隨機(jī)數(shù)k的生成算法，修改隨機(jī)源的選取辦法，提高了隨機(jī)源的確定性，降低了智能系統(tǒng)當(dāng)中因?yàn)殡S機(jī)源的不確定性而產(chǎn)生安全隱患的可能性。

參考文獻(xiàn)：

[1] Johnson D，Menezes A，Vanstone S. The elliptic curve digital signature algorithm（ECDSA）[J]. International Journal of Information Security，2001，1：36-63.

[2] 國(guó)家密碼管理局. SM2橢圓曲線公鑰密碼算法第1部分：總則 ：GM/T 0003.1-2012[S].北京：中國(guó)標(biāo)準(zhǔn)出版社，2012：8.

[3] 國(guó)家密碼管理局.SM2橢圓曲線公鑰密碼算法第2部分：數(shù)字簽名算法：GM/T 0003.2-2012[S].北京：中國(guó)標(biāo)準(zhǔn)出版社，2012：8.

[4] 國(guó)家密碼管理局.SM2橢圓曲線公鑰密碼算法第3部分：密鑰交換協(xié)議：GM/T 0003.3-2012[S].北京：中國(guó)標(biāo)準(zhǔn)出版社，2012：8.

[5] 國(guó)家密碼管理局.SM2橢圓曲線公鑰密碼算法第4部分：公鑰加密算法：GM/T 0003.4-2012[S].北京：中國(guó)標(biāo)準(zhǔn)出版社，2012：8.

[6] 國(guó)家密碼管理局. SM2橢圓曲線公鑰密碼算法第5部分：參數(shù)定義 ：GM/T 0003.5-2012[S].北京：中國(guó)標(biāo)準(zhǔn)出版社，2012：8.

[7] Miller V. Uses of Elliptic Curves in Cryptography[J].Proc. Ann. Intl Cryptology Conf. Advances in Cryptology，1985： 417-426.

[8] Gura N，Patel A，Wander A，et al.Comparing elliptic curve cryptography and RSA on 8-bit CPUs[C]//Cryptographic Hardware and Embedded Systems（CHES 2004）.Berlin，Heidelberg：Springer，2004：119-132.

[9] Lenstra A K，Verheul E R.Selecting cryptographic key sizes[J].Journal of Cryptology，2001，14（4）：255-293.

[10] Potlapally N R，Ravi S，Raghunathan A，et al.A study of the energy consumption characteristics of cryptographic algorithms and security protocols[J].IEEE Trans on Mobile Comput，2006，5（2）：128-143.

[11] 楊曉元，魏立線.計(jì)算機(jī)密碼學(xué)[M].西安：西安交通大學(xué)出版社， 2015.

[12] 國(guó)家密碼管理局.SM3密碼雜湊函數(shù);GMT 0004.5-2012[S].北京：中國(guó)標(biāo)準(zhǔn)出版社，2012：8.

[13] Rivest R L，Shamir A，Adleman L M.A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the ACM，1978，21（2）：120-126.

[14] Jonsson J，Kaliski B.Public-key cryptography standards （PKCS）#1：RSA cryptography specifications version2.1[R]. 2003.

[15] 孫榮燕，蔡昌曙，周洲，等.國(guó)密SM2數(shù)字簽名算法與ECDSA算法對(duì)比分析研究[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2013（2）：60-62.

[16] Pub F.the keyed-hash message authentication code（HMAC）[J].Federal Information Processing Standards Publication，2002，198.

【通聯(lián)編輯：代影】