基于橢圓曲線數(shù)字簽名系統(tǒng)的設(shè)計與實現(xiàn)

李海平　凌廣明　裴宸平

摘 要： 通過網(wǎng)絡(luò)傳輸獲取信息，這在人們?nèi)粘Ｉ钪腥找嫫占?。信息在網(wǎng)絡(luò)傳輸過程中面臨著被截獲、被修改等安全性威脅。數(shù)字簽名技術(shù)能夠在數(shù)據(jù)傳輸過程中提供一系列的安全保障服務(wù)。基于C/C++和橢圓曲線數(shù)字簽名算法，設(shè)計并實現(xiàn)了一個數(shù)字簽名系統(tǒng)。測試表明，該系統(tǒng)具有良好性能并滿足簽名算法的安全性要求。

關(guān)鍵詞： 網(wǎng)絡(luò)傳輸； 數(shù)字簽名； 橢圓曲線； 電子商務(wù)

中圖分類號：TP309 文獻標志碼：A 文章編號：1006-8228（2015）05-44-03

Abstract： Access to information through the network is becoming more and more popular in people's daily life. At the same time， the information during the network transmission is faced with the security threats such as being intercepted or modified and so on， while digital signature technology can provide a range of security services in the data transmission. This paper designs and implements a digital signature system with C/C++ and the elliptic curve digital signature algorithm. The test shows that the system has a good performance and meets the safety requirements of the signature algorithm.

Key words： network transmission； digital signature； elliptic curve； e-commerce

0 引言

隨著信息和電子技術(shù)的迅速發(fā)展以及網(wǎng)絡(luò)技術(shù)的廣泛應(yīng)用，世界已經(jīng)步入了信息社會。在政治、軍事、商業(yè)和日常生活中，人們經(jīng)常需要在紙質(zhì)材料上手寫簽名。手寫簽名具有確認、核準、生效、負責(zé)等多種作用。近些年隨著計算機網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，陸陸續(xù)續(xù)出現(xiàn)了電子商務(wù)、電子政務(wù)和電子金融系統(tǒng)。在這些系統(tǒng)應(yīng)用中，人們需要通過網(wǎng)絡(luò)信息傳輸對電子的文件、合同、信件及賬單等進行數(shù)字簽名以代替手寫簽名。計算機作為國家的關(guān)鍵基礎(chǔ)設(shè)施和戰(zhàn)略命脈，其安全狀況直接影響到國家的安全和發(fā)展。信息加密是保證信息安全的關(guān)鍵技術(shù)，其理論是信息安全的核心內(nèi)容之一。目前的數(shù)據(jù)加密、數(shù)字簽名、消息認證等信息安全技術(shù)都是以密碼技術(shù)作為基礎(chǔ)進行設(shè)計的。

在電子商務(wù)活動日益盛行的今天，數(shù)字簽名技術(shù)已經(jīng)受到人們的廣泛關(guān)注與認可，其使用已經(jīng)越來越普遍。各國對數(shù)字簽名的使用已頒布了相應(yīng)法案，我國也于2004年8月通過了《電子簽名法》。目前已有的簽名算法主要有RSA簽名方案、ELGamal簽名方案、橢圓曲線數(shù)字簽名算法、盲數(shù)字簽名方案等等。因此，設(shè)計出簡單、安全、高效的數(shù)字簽名系統(tǒng)對于電子商務(wù)、電子政務(wù)的推廣和應(yīng)用具有十分重要的意義。

1 橢圓曲線公鑰密碼系統(tǒng)簡介

1985年，Victor Miller和Neal Koblitz首次提出將橢圓曲線用于公鑰密碼學(xué)的思想。其理論基礎(chǔ)是定義在有限域上的某一橢圓曲線上的有理點可構(gòu)成有限交換群[1]。

1.1 橢圓曲線密碼體制

如果能通過某種方法將明文通過適當?shù)木幋a方式嵌入到橢圓曲線E上的點，則可以定義基于橢圓曲線E的ElGamal公鑰密碼系統(tǒng)[2]。

密鑰生成算法：設(shè)（E，+）是有限域Fp上的橢圓曲線，G是E的循環(huán)子群，生成元為P，其階n足夠大，使得循環(huán)子群G上的離散對數(shù)問題是難解的。隨機挑選一個整數(shù)a，使得1?a?n-1，計算Q=a·P；公開公鑰（Q，P，G），保存私鑰a。

加密算法：假設(shè)Bob想把明文m加密發(fā)送給Alice，Bob首先獲取Alice的公鑰（Q，P，G），將明文m編碼為群G中的元素Pm，再選取隨機數(shù)r，1?r?n-1，然后計算c1=r·P=（x1，y1），c2=Pm+r·Q=（x2，y2），則密文為（c1，c2）。

解密算法：Alice收到密文（c1，c2）后，利用私鑰a計算出Pm=c2-a·c1，再對Pm解編碼得到明文m[3]。

1.2 橢圓曲線數(shù)字簽名算法

橢圓曲線數(shù)字簽名算法ECDSA的安全性是基于有限域上橢圓曲線有理點群上離散對數(shù)問題的困難性。ECDSA已于1999年接受為ANSI X9.62標準，于2000年接受為IEEE 1363及FIPS 186-2標準[4]。

1.2.1 參數(shù)建立

⑴ 設(shè)q（>2160）是一個素數(shù)冪，E是有限域Fq上的一條橢圓曲線（q為素數(shù)或2m。當q為素數(shù)時，曲線E選為y2=x3+ax+b。當q=2m時，曲線E選為y2+xy=x3+ax2+b）。

⑵ 設(shè)G是E上有理點群E（Fq）上的具有大素數(shù)階n（>2160）的元，稱此元為基點。

⑶ h是單向Hash函數(shù)h，可選擇SHA-1或SHA-256等。

⑷ 隨機選取整數(shù)d：1⑸ （q，E，G，h）是公開參數(shù)，d與P分別是簽名者的私鑰和公鑰。

1.2.2 簽名生成過程

⑴ 對消息，Alice隨機選取一個整數(shù)k，1?k

⑶ 記r=x1modn。如果r為0，返回第一步。

⑷ 計算s=k-1（h（m）+dr）modn。如果s為0，則返回第一步。

⑸ （r，s）是Alice對消息m的簽名。將（r，s）發(fā)送給Bob。

1.2.3 簽名驗證過程

Bob收到（r，s）后執(zhí)行以下操作。

⑴ 檢驗r與s是否滿足：1?r，s?n-1，如不滿足，則拒絕此簽名。

⑵ 獲取公開參數(shù)（q，E，G，h）及Alice的公鑰P。

⑶ 計算w=s-1modn。

⑷ 計算u1=h（m）wmodn及u2=rwmodn。

⑸ 計算標量乘R=u1G+u2P。

⑹ 如果R=O，則拒絕簽名，否則將R的x坐標轉(zhuǎn)換成整數(shù)，并計算。

⑺ 檢驗v=r是否成立，若成立，則Bob接受簽名，否則拒絕該簽名。

2 簽名系統(tǒng)分析及設(shè)計

本節(jié)主要討論橢圓曲線數(shù)字簽名系統(tǒng)的總體分析和設(shè)計。

2.1 域參數(shù)的選取

橢圓曲線密碼體制的安全性是基于有限域上橢圓曲線離散對數(shù)問題的難解性。為了使簽名系統(tǒng)更加安全，應(yīng)該選取更加安全的橢圓曲線，基于某條橢圓曲線的離散對數(shù)問題求解難度很大。

設(shè)定義于有限域上的橢圓曲線E，其中q=pn，p是一個素數(shù)。橢圓曲線E的有理子群E（）的階用表示。橢圓曲線好壞的標準在于的大小。Hasse定理給出的是域上橢圓曲線的階，其中q=pn。

對于超奇異橢圓曲線：

⑴ n是偶數(shù)，。

⑵ n是偶數(shù)，。

⑶ n是奇數(shù)或偶數(shù)，p≠1mod4，t=0。

對于非超奇異橢圓曲線，t滿足性質(zhì)。

2.2 簽名系統(tǒng)流程

該簽名系統(tǒng)包括簽名和驗證兩個主要過程，分別如圖1和圖2所示。

2.3 系統(tǒng)總體設(shè)計

簽名系統(tǒng)總體流程圖如圖3所示。

[開始][系統(tǒng)登錄][合法

圖4中，密鑰生成模塊主要負責(zé)生成簽名所需密鑰；摘要處理模塊主要針對需要簽名的文檔生成HASH摘要；簽名生成模塊主要對數(shù)字摘要進行簽名并將簽名附加到源文檔末尾；驗證模塊即對簽名進行驗證并返回驗證結(jié)果，用數(shù)字1表示驗證通過、數(shù)字0代表未通過。

3 橢圓曲線數(shù)字簽名算法的實現(xiàn)

該系統(tǒng)利用C/C++基于.NET平臺設(shè)計并實現(xiàn)[5]。系統(tǒng)中常用的運算法則為加減乘除和取余運算（取余運算被包含在除法運算中）。因為ECDSA算法均是大整數(shù)的運算，所以此系統(tǒng)所有運算方法均采用有符號的二進制運算方法且結(jié)果同樣為有符號二進制數(shù)。由于加法和減法運算較為簡單，下面主要列出乘法和取余數(shù)算法的具體過程。

乘法運算算法描述：

step 1 被乘數(shù)與乘數(shù)按低位對齊；

step 2 取乘數(shù)為運算的低位與被乘數(shù)相乘；

step 3 使用加法算法將此次step 2的結(jié)果與step 3的結(jié)果相加；

step 4 重復(fù)step 2直至加數(shù)位數(shù)取完。

取余數(shù)運算算法描述：

step 1 被除數(shù)與除數(shù)按低位對齊；

step 2 依次取被除數(shù)未被運算高位直至取出的數(shù)大于等于除數(shù)。當此數(shù)值小于除數(shù)是商，上0，否則上1；

step 3 將step 2的得數(shù)按減法算法減去除數(shù)；

step 4 重復(fù)step 2直至被減數(shù)取完，step 3的結(jié)果即為余數(shù)。

因為ECDSA算法的效率很大程度上取決于倍點算法的效率，所以在此詳述此系統(tǒng)中的倍點算法[6]。在系統(tǒng)運行中無論是簽名過程還是驗證過程均需要計算k*G（x，y）即k倍的點G。k的取值是從1到n（n為基點G的階）n為一個大素數(shù)，所以k的取值可能很大。這就意味著逐步點加的方法將消耗大量的時間。因此，在此系統(tǒng)中設(shè)計了一種較為快速的倍點算法，需要輸入橢圓曲線上的點G及整數(shù)K，輸出橢圓曲線上的點P=k*G（x，y），具體過程描述如下：

step 1 令num=1，i=1，P=G；建立數(shù)組point以儲存每一步的點值，Point[0]=G；

step 2 如果num<=k，則計算num=2*num； P=2*P； 將P值存入point[i]中，對i值加1；重復(fù)這個過程至num<=k不再成立；

step 3 計算num=num/2，n=num，i=i-2；P=point[i]；執(zhí)行下列循環(huán)：

for j from i to 1

如果 num=k 則輸出P；否則 n=n/2，num=num+n；

P=P+point[j-1]；

系統(tǒng)實現(xiàn)時初始化過程主要確定簽名系統(tǒng)中各個參數(shù)，簽名過程使用的是ECDSA中的簽名生成算法，可以對本地文件進行簽名。打開系統(tǒng)后，點擊簽名可以對選定的文檔（TXT文件或者DOC文件）進行電子簽名。

簽名成功后，簽名結(jié)果會追加在文檔末尾，如圖5所示。

文檔驗證人收到文檔后，選擇驗證按鈕來對已簽名文檔進行驗證。若文檔從未被篡改過，則會顯示驗證成功，如圖6所示；若在傳輸過程中或者是在驗證該文當前，有人對簽名后的文檔進行修改，則驗證結(jié)果提示文件不可信（即有人篡改文檔內(nèi)容）。演示文檔中以刪除“war”為例進行驗證，結(jié)果如圖7所示。

4 安全性分析

該簽名系統(tǒng)是基于有限域Fq上的橢圓曲線數(shù)字簽名系統(tǒng)，其安全性基于橢圓曲線密碼體制的安全性即橢圓曲線上離散對數(shù)問題的難解性。具體實現(xiàn)時還有幾點需要考慮[7]。第一，系統(tǒng)參數(shù)組中使用安全的隨機數(shù)。簽名算法中使用了隨機數(shù)，每一次的隨機數(shù)需要安全生成、保存和使用并銷毀，并且每次都使用不同的隨機數(shù)，這在一定程度上可以提高系統(tǒng)的安全性。第二，確定合適的系統(tǒng)參數(shù)。選擇恰當?shù)南到y(tǒng)參數(shù)可以保證ECDLP問題的難解性，可以使用NIST推薦的系統(tǒng)參數(shù)。第三，使用安全的Hash函數(shù)。算法中需要使用Hash函數(shù)對文檔內(nèi)容進行處理，好的Hash函數(shù)應(yīng)具有如下特點：函數(shù)的正向計算容易；函數(shù)盡可能隨機且不可逆。可以選取SHA-1等安全的Hash函數(shù)。

5 結(jié)束語

近年來，在電子商務(wù)、電子政務(wù)等快速發(fā)展的推動下，數(shù)字簽名技術(shù)也得到了快速發(fā)展和應(yīng)用，并且日益成為內(nèi)容豐富、應(yīng)用廣泛的信息安全技術(shù)領(lǐng)域的核心技術(shù)之一。其中，橢圓曲線數(shù)字簽名算法是眾多簽名算法中廣受關(guān)注的一種算法。本文基于橢圓曲線數(shù)字簽名算法，采用C/C++編程實現(xiàn)了一個橢圓曲線數(shù)字簽名系統(tǒng)。通過測試表明，所設(shè)計和實現(xiàn)的簽名系統(tǒng)完全滿足信息防篡改等安全性要求，在電子商務(wù)、電子政務(wù)以及電子金融等領(lǐng)域具有一定的實用前景。

參考文獻：

[1] 張龍軍，沈鈞毅，趙霖.橢圓曲線密碼體制安全性研究[J].西安交通大學(xué)學(xué)報，2001.35（10）.

[2] 何大可，彭代淵，唐小虎等.現(xiàn)代密碼學(xué)[M].人民郵電出版社，2009.

[3] 趙澤茂.數(shù)字簽名理論及應(yīng)用研究[D].南京理工大學(xué)博士學(xué)位論文，2005.

[4] 徐茂智，游林.信息安全與密碼學(xué)[M].清華大學(xué)出版社，2007.

[5] 鄭阿奇，丁有和.Visual C++教程（第2版）[M].機械工業(yè)出版社，2008.

[6] 賴忠喜，陶東婭，張占軍.GF（2～n）域橢圓曲線密碼體制中快速標量乘算法的研究[J].計算機應(yīng)用與軟件，2014.8.

[7] 秦曉東，辛運帷，盧桂章.基于橢圓曲線的數(shù)字簽名系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機工程與應(yīng)用，2003.28：151-155