基于橢圓曲線數字簽名系統的設計與實現

李海平　凌廣明　裴宸平

摘 要： 通過網絡傳輸獲取信息，這在人們日常生活中日益普及。信息在網絡傳輸過程中面臨著被截獲、被修改等安全性威脅。數字簽名技術能夠在數據傳輸過程中提供一系列的安全保障服務。基于C/C++和橢圓曲線數字簽名算法，設計并實現了一個數字簽名系統。測試表明，該系統具有良好性能并滿足簽名算法的安全性要求。

關鍵詞： 網絡傳輸； 數字簽名； 橢圓曲線； 電子商務

中圖分類號：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 引言

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

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

1 橢圓曲線公鑰密碼系統簡介

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

1.1 橢圓曲線密碼體制

如果能通過某種方法將明文通過適當的編碼方式嵌入到橢圓曲線E上的點，則可以定義基于橢圓曲線E的ElGamal公鑰密碼系統[2]。

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

加密算法：假設Bob想把明文m加密發送給Alice，Bob首先獲取Alice的公鑰（Q，P，G），將明文m編碼為群G中的元素Pm，再選取隨機數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 橢圓曲線數字簽名算法

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

1.2.1 參數建立

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

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

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

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

1.2.2 簽名生成過程

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

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

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

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

1.2.3 簽名驗證過程

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

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

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

⑶ 計算w=s-1modn。

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

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

⑹ 如果R=O，則拒絕簽名，否則將R的x坐標轉換成整數，并計算。

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

2 簽名系統分析及設計

本節主要討論橢圓曲線數字簽名系統的總體分析和設計。

2.1 域參數的選取

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

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

對于超奇異橢圓曲線：

⑴ n是偶數，。

⑵ n是偶數，。

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

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

2.2 簽名系統流程

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

2.3 系統總體設計

簽名系統總體流程圖如圖3所示。

[開始][系統登錄][合法

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

3 橢圓曲線數字簽名算法的實現

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

乘法運算算法描述：

step 1 被乘數與乘數按低位對齊；

step 2 取乘數為運算的低位與被乘數相乘；

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

step 4 重復step 2直至加數位數取完。

取余數運算算法描述：

step 1 被除數與除數按低位對齊；

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

step 3 將step 2的得數按減法算法減去除數；

step 4 重復step 2直至被減數取完，step 3的結果即為余數。

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

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

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

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

for j from i to 1

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

P=P+point[j-1]；

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

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

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

4 安全性分析

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

5 結束語

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

參考文獻：

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

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

[3] 趙澤茂.數字簽名理論及應用研究[D].南京理工大學博士學位論文，2005.

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

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

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

[7] 秦曉東，辛運帷，盧桂章.基于橢圓曲線的數字簽名系統的設計與實現[J].計算機工程與應用，2003.28：151-155