SM2橢圓曲線公鑰加密算法的研究與實(shí)現(xiàn)

李玉生

（南京理工大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210094）

SM2橢圓曲線公鑰加密算法的研究與實(shí)現(xiàn)

李玉生

（南京理工大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210094）

隨著互聯(lián)網(wǎng)的發(fā)展，越來(lái)越多的信息交換通過(guò)網(wǎng)絡(luò)進(jìn)行，在這些信息中包含著不能為人所知的私密信息，例如，信用卡賬號(hào)、銀行賬號(hào)、病歷、電子郵件等。由于私密信息泄露產(chǎn)生不良后果的事件時(shí)有發(fā)生，這些都牽扯到對(duì)數(shù)據(jù)信息的加密問(wèn)題。針對(duì)這一問(wèn)題，文章提出運(yùn)用SM2加密算法實(shí)現(xiàn)數(shù)據(jù)信息的加密，保證網(wǎng)絡(luò)通信的安全性。事實(shí)表明，SM2公鑰加密算法能夠更加安全地加密數(shù)據(jù)信息，且加密的數(shù)據(jù)很難破譯。

私密信息泄露；SM2加密算法；安全性；難破譯

保密通信催生了密碼技術(shù)，從古到今先進(jìn)的技術(shù)都首先應(yīng)用在軍事領(lǐng)域，軍隊(duì)歷來(lái)是使用密碼最頻繁的地方，保護(hù)己方秘密洞悉敵方秘密是克敵制勝的重要條件，正所謂“知己知彼，百戰(zhàn)不殆”，古代中國(guó)所使用的密碼技術(shù)主要有：陰符、陰書、虎符、信牌、字驗(yàn)和礬書等。西方的傳統(tǒng)密碼技術(shù)主要包含凱撒密碼、換字式密碼、多表替代密碼、轉(zhuǎn)制式密碼等。第二次世界大戰(zhàn)密碼學(xué)得到了長(zhǎng)遠(yuǎn)的發(fā)展，無(wú)論是在密碼學(xué)的技術(shù)、理論，還是在應(yīng)用方面，都發(fā)生了革命性的變化。

1976年，公鑰密碼算法的思想被提出，1978年，第一個(gè)公鑰密碼算法RSA誕生了，標(biāo)志著密碼學(xué)進(jìn)入了一個(gè)全新的時(shí)代。2010年國(guó)家密碼管理局提出了SM2橢圓曲線公鑰密碼算法主要包括數(shù)字簽名算法、密鑰交換協(xié)議和公鑰加密算法3部分。

本論文主要研究SM2公鑰加密算法并基于keil uVision 5軟件平臺(tái)采用C語(yǔ)言編程，將設(shè)計(jì)的模加、模減、模乘、模冪和模逆5個(gè)底層運(yùn)算函數(shù)封裝成庫(kù)函數(shù)，供點(diǎn)加、倍點(diǎn)、標(biāo)量乘函數(shù)和其他模塊調(diào)用，最后，在LPC1778硬件平臺(tái)上實(shí)現(xiàn)數(shù)據(jù)的加密與解密。

1　公鑰加密算法簡(jiǎn)介

公鑰加密算法又稱非對(duì)稱加密算法，相對(duì)于只有一個(gè)密鑰的對(duì)稱加密算法，非對(duì)稱加密算法中加密密鑰和解密密鑰是一對(duì)密鑰，可以由解密密鑰通過(guò)一定的數(shù)學(xué)算法計(jì)算出加密密鑰，而加密密鑰理論上即使知道了數(shù)學(xué)算法也很難推導(dǎo)出解密密鑰，這就是密鑰在數(shù)學(xué)上的大數(shù)難解問(wèn)題。由于加密密鑰是公開的，理論上任何人都可以獲得這個(gè)加密密鑰用來(lái)加密信息，但是使用加密密鑰加密的消息只有相應(yīng)的解密密鑰可以解開，而這個(gè)解密密鑰是保密的，是不公開的。非對(duì)稱密碼算法中，加密密鑰也叫作公開密鑰或公鑰，解密密鑰則稱為私人密鑰或私鑰。

例如，通信雙方A和B建立通信，公鑰密碼算法實(shí)現(xiàn)的是A和B之間的數(shù)據(jù)加密，加解密過(guò)程如圖1所示。

圖1　公鑰加密算法的加密和解密過(guò)程

A要發(fā)送消息給B，那么A必須持有B的公鑰作用于明文進(jìn)行加密將加密后的密文發(fā)送給接收方B，B在接收到密文后，用自己持有的私鑰作用于密文進(jìn)行解密操作，還原出A發(fā)送的明文。同樣B要發(fā)送數(shù)據(jù)給A則用自己的私鑰加密明文將生成的密文發(fā)送給接收方A，接收方A用B的公鑰解密收到的密文就能還原出B發(fā)送的明文了，但是這樣不能保證數(shù)據(jù)傳輸?shù)乃矫苄浴Ｒ驗(yàn)锽的公鑰是公開的所以理論上獲得B的公鑰的人，都可以解密出明文信息，要實(shí)現(xiàn)B向A發(fā)送密文數(shù)據(jù)，則B應(yīng)該持有A的公鑰，用A的公鑰加密數(shù)據(jù)把密文發(fā)送給A，A用自己的私鑰解密密文獲得明文信息，也就是說(shuō)A和B之間相互的通信需要A的公鑰、私鑰，B的公鑰、私鑰共4把鑰匙，A 和B各持有對(duì)方的公鑰，私鑰只有A和B自己知道。

在這一過(guò)程中要保證私鑰的私密性，這樣即使密文被人截獲了，在沒(méi)有私鑰的情況下也無(wú)法破譯出密文所對(duì)應(yīng)的明文信息，僅私鑰的持有者能夠解密密文獲取明文信息，保證了信息的安全性。公鑰密碼算法的公鑰和密碼算法是公開的。原則上，B的公鑰人人都可以獲取，所以數(shù)據(jù)加密不提供身份認(rèn)證和不可抵賴的功能。關(guān)于身份認(rèn)證的內(nèi)容，即A如何確定收到的公鑰是B的，可由SM2橢圓曲線公鑰密碼算法的數(shù)字簽名算法保證。

由于對(duì)稱密碼算法加密解密使用的是同一把鑰匙，密鑰在傳遞的過(guò)程中容易遭到竊取，導(dǎo)致密鑰泄露，使用公鑰密碼算法加密數(shù)據(jù)的一大好處是通信雙方不需要事先協(xié)商加密密鑰，減少了密鑰泄露的風(fēng)險(xiǎn)，也擴(kuò)大了通信對(duì)象的范圍，所有人都可以使用公鑰密碼算法輕易地建立安全的通信信道。

2　橢圓曲線大數(shù)運(yùn)算的數(shù)學(xué)基礎(chǔ)

2.1模運(yùn)算與素?cái)?shù)域

同余是數(shù)論中的等價(jià)關(guān)系，對(duì)于正整數(shù)m如果有a=b+km （a，b，k均是整數(shù)）那么記b=a mod（m），則稱a與b關(guān)于m同余。當(dāng)m=p（p為素?cái)?shù)）時(shí)，我們定義素?cái)?shù)域FP可由{0，1，2，3…p-1}中P個(gè)元素構(gòu)成，關(guān)于P的模運(yùn)算稱為素?cái)?shù)域上模運(yùn)算。

2.2有限域上的模運(yùn)算的設(shè)計(jì)與實(shí)現(xiàn)

有限域上的模運(yùn)算是SM2橢圓曲線公鑰密碼算法的基礎(chǔ)，主要包括模加和模減運(yùn)算、模乘運(yùn)算、模冪和模逆運(yùn)算。

模逆運(yùn)算是模運(yùn)算中最復(fù)雜運(yùn)算量最大的運(yùn)算，模逆運(yùn)算可以通過(guò)費(fèi)馬小定理（n是素?cái)?shù)的時(shí)候，和n互素的某個(gè)整數(shù)a有公式an-1=1modn成立）得到，即當(dāng)p為素?cái)?shù)時(shí)，有ap-1=1mod p，則可得到模逆運(yùn)算a-1=ap-2mod p，這樣就可以利用模冪運(yùn)算來(lái)表示模逆運(yùn)算。以上的這些模運(yùn)算都已在LPC1778硬件平臺(tái)上實(shí)現(xiàn)，如圖2所示。

圖2　模運(yùn)算測(cè)試結(jié)果

2.3有限域上標(biāo)量乘運(yùn)算的設(shè)計(jì)與實(shí)現(xiàn)

標(biāo)量乘的數(shù)學(xué)形式，P=（xp，yp）為橢圓曲線E（FP）上的點(diǎn)，k為正整數(shù)，P的k倍點(diǎn)為Q。Q=［k］P=P+P+…+P（k 個(gè)p）。標(biāo)量乘運(yùn)算是所有運(yùn)算中最耗時(shí)的運(yùn)算操作，主要由點(diǎn)加和倍點(diǎn)產(chǎn)生，點(diǎn)加和倍點(diǎn)運(yùn)算在不同坐標(biāo)系下的運(yùn)算規(guī)則不同。采用仿射與雅可比混合坐標(biāo)系下的運(yùn)算規(guī)則：y2=x3+axz4+bz6，其中，a，b為橢圓曲線上的整數(shù)，并且△= （4a3+27b2）mod p≠0。

三維坐標(biāo)P（x1，y1，z1），Q（x2，y2，1）的無(wú)窮遠(yuǎn)點(diǎn)為（1，1，0）。倍點(diǎn)運(yùn)算P+P=（ x3，y3，z3）聲明為Padd1（x1，y1，z1，x3，y3，z3），把2P的值存入（x3，y3，z3），點(diǎn)加運(yùn)算P+Q=（x3，y3，z3）聲明為Padd2（x1，y1，z1，x2，y2，x3，y3，z3），把P+Q的值存入（x3，y3，z3）。最后還要把結(jié)果（x3，y3，z3）從雅可比加重?cái)z影坐標(biāo)系下轉(zhuǎn)換到仿射坐標(biāo)系下，需要對(duì)參數(shù)進(jìn)行轉(zhuǎn)換：x3=x3/ z12，y3=y3/z13，即可得到所需的二維坐標(biāo)點(diǎn)（x3，y3）。

有了點(diǎn)加和倍點(diǎn)運(yùn)算就可以進(jìn)行標(biāo)量乘運(yùn)算，標(biāo)量乘從右往左的算法為：

3　SM2公鑰加密算法

素?cái)?shù)域橢圓曲線的參數(shù)：素?cái)?shù)域的模P，橢圓曲線E（FP）的系數(shù)：a，b；E（FP）上的基點(diǎn)G（Gx，Gy）≠0，基點(diǎn)G的解為n余因子h=1，用戶A持有的用戶B的公鑰PB，用戶B持有的私鑰dB。

3.1SM2加密算法

（1）用隨機(jī)數(shù)發(fā)生器生成隨機(jī)數(shù)k，0＜k＜n。

（2）計(jì)算橢圓曲線上的點(diǎn)C1=［k］G。

（3）計(jì)算橢圓曲線點(diǎn)S=［h］PB，若S為無(wú)窮遠(yuǎn)點(diǎn)則報(bào)錯(cuò)并退出，h為余因子，這里取為1。

（4）計(jì)算橢圓曲線上的點(diǎn)［k］PB=（x2，y2）。

（5）計(jì)算t=KDF（x2||y2，len）若t全為0則返回1。

（6）計(jì)算C2=M⊕t。

（7）計(jì)算C3= SM3（x2||M||y2）。

（8）計(jì)算密文C=C1||C2||C3。

SM2加密流程如圖3示。

圖3　SM2加密算法流程

3.2SM2解密算法

（1）從密文中取出C1，驗(yàn)證C1是否滿足橢圓曲線方程，若不滿足則報(bào)錯(cuò)并退出。

（2）計(jì)算S=［h］C1，若S為無(wú)窮遠(yuǎn)點(diǎn)則報(bào)錯(cuò)并退出。

（3）計(jì)算 ［dB］C1=（x2，y2）。

（4）計(jì)算 t=KDF（x2||y2，len）。

（5）從C中取出C2計(jì)算m= C2⊕t。

（6）計(jì)算u=SM3（x2||m||y2），若u與C3不相等，則報(bào)錯(cuò)并退出。

（7）輸出明文m。

SM2解密流程如圖4所示。

圖4　SM2解密算法流程

加密解密算法在LPC1778上實(shí)現(xiàn)通過(guò)串口RS232在超級(jí)終端上的顯示結(jié)果如圖5所示，待加密的消息M為“Hello World！”。

圖5　加解密測(cè)試結(jié)果

4　結(jié)語(yǔ)

SM2公鑰加密算法可以實(shí)現(xiàn)數(shù)據(jù)的加密，但相對(duì)于對(duì)稱密碼算法如DES，AES等對(duì)稱密碼算法計(jì)算量大，加密速度慢，所以在實(shí)際應(yīng)用中一般把公鑰密碼算法和對(duì)稱密碼算法結(jié)合起來(lái)使用，既利用了公鑰密碼算法的密鑰易于傳輸?shù)膬?yōu)點(diǎn)又利用了對(duì)稱密碼算法加密速度快、適合大批量數(shù)據(jù)加密的優(yōu)點(diǎn)。

[1]張明德，劉偉.PKI/CA與數(shù)字證書技術(shù)大全[M].北京：電子工業(yè)出版社，2015.

[2]盧開澄，盧華明.橢圓曲線密碼算法導(dǎo)引[M].北京：清華大學(xué)出版社，2008.

[3]劉合義.談數(shù)論中的同余及其應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，2004（1）：38-39.

[4]李學(xué)俊，敬忠良.基于橢圓曲線離散對(duì)數(shù)問(wèn)題的公鑰密碼[J].計(jì)算機(jī)工程與應(yīng)用，2002（6）：20-22.

[5]周宣武，楊曉元，黃德官，等.網(wǎng)絡(luò)中基于橢圓曲線密碼的密鑰管理方案[J].計(jì)算機(jī)工程，2004（11）：89-91.

[6]國(guó)家密碼管理局.SM2橢圓曲線公鑰密碼算法[EB/OL].（2016-10-25）[2010-12-18].http://wenku.baidu.com/view/6337c57c27284b73f242501a. html.

[7]劉鐸，戴一奇.計(jì)算橢圓曲線上標(biāo)量乘的快速算法[J].計(jì)算機(jī)學(xué)報(bào)，2008（3）：102-106.

[8]李輝，劉中華，易軍凱.基于偽隨機(jī)數(shù)生成器的標(biāo)量乘改進(jìn)算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2015（1）：151-155.

[9]牛廣平，馬建峰.橢圓曲線標(biāo)量乘的快速實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2004（16）：45-46.

[10]LAUTER K.The Advantages of Elliptic Curve Cryptography for Wireless Security.[J]Wireless Communications，2004（3）：62-67.

[11]NEAL K，ALFRED M，VANSTONE S.The State of Elliptic Curve Cryptography Designs[J].Codes and Cryptography，2010（1）：173-193.

Research and realization of SM2 elliptic curve public key encryption algorithm

Li Yusheng
（Automation School of Nanjing University of Science and Technology, Nanjing 210094,China）

With the development of the Internet, more and more information is exchanged through the network, among those information, there are some private information that can not be known by others, for example, credit card accounts, bank accounts, medical record, e-mail, etc. Bad consequences caused by private information leakage occurred frequently, which is involved in the encryption of data information. In view of this problem, this paper proposes the use of SM2 encryption algorithm to achieve data encryption and ensure the security of network communication. Facts show that the SM2 public key encryption algorithm can encrypt data more safely, and the encryption data is difficult to decipher.

private information leakage; SM2 encryption algorithm; security; difficult to decipher

李玉生（1989— ），男，江蘇徐州，碩士研究生；研究方向：arm嵌入式軟件開發(fā)，SM2公鑰密碼算法。