李海平　凌廣明　裴宸平

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

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

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

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

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

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

1.1 橢圓曲線密碼體制

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

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

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

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

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

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

1.2.1 參數(shù)建立

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

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

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

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

1.2.2 簽名生成過(guò)程

⑴ 對(duì)消息，Alice隨機(jī)選取一個(gè)整數(shù)k，1?k

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

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

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

1.2.3 簽名驗(yàn)證過(guò)程

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

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

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

⑶ 計(jì)算w=s-1modn。

⑷ 計(jì)算u1=h（m）wmodn及u2=rwmodn。

⑸ 計(jì)算標(biāo)量乘R=u1G+u2P。

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

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

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

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

2.1 域參數(shù)的選取

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

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

對(duì)于超奇異橢圓曲線：

⑴ n是偶數(shù)，。

⑵ n是偶數(shù)，。

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

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

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

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

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

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

[開(kāi)始][系統(tǒng)登錄](méi)[合法

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

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

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

乘法運(yùn)算算法描述：

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

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

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

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

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

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

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

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

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

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

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

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

step 3 計(jì)算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)實(shí)現(xiàn)時(shí)初始化過(guò)程主要確定簽名系統(tǒng)中各個(gè)參數(shù)，簽名過(guò)程使用的是ECDSA中的簽名生成算法，可以對(duì)本地文件進(jìn)行簽名。打開(kāi)系統(tǒng)后，點(diǎn)擊簽名可以對(duì)選定的文檔（TXT文件或者DOC文件）進(jìn)行電子簽名。

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

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

4 安全性分析

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1] 張龍軍，沈鈞毅，趙霖.橢圓曲線密碼體制安全性研究[J].西安交通大學(xué)學(xué)報(bào)，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].機(jī)械工業(yè)出版社，2008.

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

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