基于ECDSA的智能卡軟件設計與實現

白永祥

（1.渭南職業技術學院 陜西 渭南 714000；2.西北大學 信息科學與技術學院，陜西 西安 710127）

數字簽名是公鑰密碼體系重要的應用，它在實現身份認證、數據完整性、不可抵賴性等方面都有重要應用，是實現電子交易安全的核心技術之一。目前，大部分的數字簽名軟件幾乎都是采用RSA作為標準算法，但隨著計算機性能和解密技術的不斷提高，RSA的安全性受到了不同程度的攻擊，為了提高RSA的安全性，不斷的增加鑰密長度，造成了計算機處理工作量的增大，從而影響了加密解密的速度。

橢圓曲線是一門古老而且內容豐富的數學分支，1985年，Miller和Koblitz各自獨立地提出橢圓曲線公鑰密碼學（Elliptic Curves Cryptography ECC），同 RSA算法相比較，ECC具有密鑰長度短，占用計算機存儲空間少，計算機處理速度快等特點[1]，同時橢圓曲線還具有豐富多樣的類型，所有這些都非常適合密碼學的應用。近年來，專家學者都在不加深橢圓曲線在密碼學方面的應用研究。

1 橢圓曲線密碼系統

1.1 ECC原理概述

橢圓曲線密碼體制的安全性基于有限域上橢圓曲線離散 對 數 問 題 （Elliptic Curve Discrete Logarithm Problem，ECDLP）的難解性。這種密碼體制目前還沒有找到解決此問題的亞指數時間算法，因而它具有一些其他公鑰密碼體制無法比擬的優點。

所謂橢圓曲線就是在有限域Fq上的Weierstrass方程式：

應用于密碼學中的橢圓曲線是由滿足該方程式的所有點（x，y）及一個無限遠點所形成的集合，常用于應用的橢圓曲線有3種：

1）實數域上的橢圓曲線：y2=x3+ax+b（a，b∈R，且滿足4a2+27b3≠0）；

2）有限域 GF（p）上的橢圓曲線：y2=x3+ax+b（mod p），a，b，x，y∈{0，1，…，p-1}；

3）有限域 GF（2m）上的橢圓曲線：y2+xy=x3+ax2+b，a，b，x，y∈GF（2m）。

1.2 橢圓曲線上點的群運算法則

給定一條Fq上的橢圓曲線E，及其上的任意兩點P和Q，連接P和Q的直線與E交于第3個點-R，由于-R和無窮遠點O可決定一直線，該直線與E交于一個交點R定為P與Q的和，記為P+Q。可以證明這樣定義E上點的加法后，就使E成為一個Abel群。具體的運算法則如下：

設 P=（x1，y1），Q=（x2，y2） 為實數域上橢圓曲線上任意兩點，且P≠O≠Q，則有橢圓曲線方程：y2=x3+ax+b

則兩點加法的運算規則如下：

1）當 P≠Q 時，P+Q=R（x3，y3），如圖 1 所示；

2）當 P=Q 時，P+Q=R（x3，y3），如圖 2 所示；

3）當 x1=x2時，P+（-P）=（x1+y1）+（x1，-y1）=O，如圖 3 所示；

定義：P+O=O+P=P。

圖 1 P+Q=R（x3，x3）Fig.1 P+Q=R（x3，x3）

圖2 P+Q=P+P=2P=RFig.2 P+Q=P+P=2P=R

圖 3 P+（-P）=OFig.3 P+（-P）=O

由于橢圓曲線加密算法具有密鑰長度短，占用存貯空間少、靈活性好等特點，所以橢圓曲線加密算法相對于RSA加密算法具有絕對的優勢，目前已成為非對稱密鑰加密體制中的研究熱點。

1.3 橢圓曲線加密解密算法

1.3.1 密鑰生成

參與者Alice發送信息給接收者Bob，Alice需要完成下述過程[2]：

1）Alice 隨機選取一個整數 dA∈[1，n-1]；

2）然后 Alice計算 QA=dAP；

3）Alice的公鑰為點 QA；

4）Alice的私鑰為整數 dA。

對于Bob也要做同樣的工作，具體過程如下：

1）Bob 隨機選取一個整數 dB∈[1，n-1]；

2）然后 Bob計算 QB=dBP；

3）Bob 的公鑰為點 QB；

4）Bob的私鑰為整數 dB。

1.3.2 加密、解密方案

現在假設Bob要發送信息給Alice，則Bob的加密過程如下：

1）找出 Alice的公鑰 QA；

2）將信息M表示為一個域元素m∈Fq；

3）隨機選取一個整數 k∈[1，n-1]；

4）計算點（x1，y1）=kP；

5）計算機點（x2，y2）=kQA，若 x2=0，則返回第 3 步；

6）計算 c=m·x2；

7）將已加密數據（x1，y1，c）發送給 A。

Alice收到密文（x1，y1，c）后的解密過程如下：

1）計算點（x2，y2）=dA（x1，y1），得出 x2∈Fq；

2）計算 m=c·x-12，得出信息 M。

1.4 橢圓曲線數字簽名算法（ECDSA）

1998年，橢圓曲線數字簽名算法（ECDSA）成為ISO標準，ECDSA相對傳統簽名算法具有速度快、強度高、簽名短等優點，其應用也逐漸廣泛了，例如Windows系列操作系統25位的CD-Key中就使用了橢圓曲線簽名算法[3]。ECDSA的工作原理與大多數簽名算法類似，都是使用私鑰進行簽名，公鑰進行驗證。

下面給出的ECDSA方案是基于IEEE P1363標準草案給出的，具體算法描述過程如下：

假設Alice要向Bob發送簽名后的消信M，Alice首先確定安全Hash函數，定義橢圓曲線也就是確定參數T=（p，a，b，G，n，h），然后建立密鑰對（dA，QA），其中 dA是私鑰，QA=dAG 是公鑰，并向用戶Bob發送Hash函數，橢圓曲線參數和公鑰QA。設Alice要對信息簽名后再發給用戶Bob那么Alice要完成下述步驟：

1）將待發送信息M轉化為比特串；

2）計算信息M的消息摘要：e=H（M）；

3）隨機選取整數 k∈[1，n-1]；

4）計算點（x1，y1）=kP；令 r=x1（mod n），若 r=0，返回第 3）步；

5）Alice 應用自己的私鑰 dA計算 s=k－1（e+rdA）（mod n），若s=0，則返回第 3）步；

6）Alice 將信息 M 和簽名（r，s）發給 Bob。

ECDSA簽名驗證：當Bob收到Alice對信息M的簽名（r，s），需要驗證是否為Alice所簽，則Bob要完成下述過程：

1）找出 Alice的公鑰 QA；

2）計算 Hash值 e=H（M）；

3）計算 s－1mod n；

4）計算 u=s－1e mod n 和 v=s－1r mod n；

5）計算點（x1，y1）=uP1+vQA；

6）當且僅當x1mod n=r時，Alice對信息M的簽名被Bob認可。

2 Hash函數

2.1 Hash函數定義

Hash函數又稱雜湊函數、消息摘要或消息指紋，它是把一段任意長度的比特串作為輸入，通過某種算法產生一個固定值為n的輸出比特串，稱其為消息的雜湊值[4]。

h:{0，1}*→{0，1}n，m→h（m）

Hash函數其實就是一種將無限多個元素映射到有限個元素的一種特殊的數學函數。它是把任意長度的輸入通過散列算法變換成一個固定長度的輸出，稱該輸出為散列值或消息指紋，這種轉換是一種壓縮映射，也就是說散列值所占的空間遠遠小于輸入的空間。Hash函數在現代密碼學中具有重要的作用。

2.2 Hash函數的安全性

在數字簽名中往往先使用雜湊函數對消息m實施 “壓縮”運算，接著對消息m的雜湊值實施簽名，這樣既起到了保密作用，又提高了加密速度。對于在數字簽名中使用的雜湊函數，要求它們具有更強的安全性能。常用的Hash算法有MD5、SHA－1和SHA－2等，而隨著計算機運算速度的不斷提高和解密技術的改進，這些算法都不同程度的受到安全性威脅。在2005年2月，王曉云以及他的同事使用差分路徑攻擊，只用了2的69次方次就完成了SHA－1的循環碰撞周期。SHA－1和SHA－2使用了相同的處理引擎，在處理消息文本時，對SHA－1的成功攻擊行為會影響到SHA－2的安全[5]。

2012年10月，美國NIST選擇了Keccak算法作為SHA－3的標準算法，Keccak擁有良好的加密性能以及抗解密能力。Keccak采用了創新的的“海綿引擎”散列消息文本，它設計簡單，方便硬件實現。Keccak已可以抵御最小的復雜度為2n的攻擊，它具有廣泛的安全邊際，至目前為止，第三方密碼分析已經顯示出Keccak沒有嚴重的弱點[6]。

3 智能卡

智能卡是以IC卡（Integrated Circuit Card）技術為核心，以計算機和通信技術為手段，一般制作在給定大小的塑料卡片上，表面封裝了集成電路芯片，用于存儲和處理數據，它由塑料基片、接觸面、集成電路三部分組成。智能卡已廣泛應用于金融、電信等領域。橢圓曲線密碼系統是目前已知的所有公鑰密碼體制中能夠提供最高比特強度的一種公鑰體制[7]。我們常把智能卡分成接觸卡和非接觸卡兩類，其中接觸卡主要是存儲卡，由于卡內資源有限，內存較小，而橢圓曲線密碼系統對時間和空間資源要求不高，剛好適用于智能卡，這樣不僅能大大提高智能卡的應用水平，而且還大大拓寬智能卡的應用領域。

4 軟件設計

4.1 概要設計

軟件功能包括登錄密碼驗證、密鑰設置、數字簽名及檢驗，如果密碼輸入錯誤，為了保護用戶賬號安全，最多只有三次機會，超過三次輸入，智能卡便會死鎖。具體應用流程如圖4所示。

4.2 數字簽名設計

由于C++具有代碼效率高等優點，所以數字簽名使用VC++6.0開發環境進行實現[8]，ECDSA主要過程代碼如下：

KEYPAIR_GE Random_key；

BIGINT x_value， k_value， signature_value， r_value；

BIGINT temp，quotient；

BIGINT random_k；

BIGINT key_value， point_order， u_value；

INDEX i， count；

Copy（&ECDSA_k， &Random_key，private_key）；

Print_field （“given random number k= ”，&random_key，private_key）；

/*computer k*G/

EC_multiple （&random_key，private_key，&public_curve －＞pnt，&random_key）；

/*display public key*/

Printf（“k*G= ”）；

Print_point（“”，&random_key，public_key）；

/*computer r=k*G（x） mod n*/

field_to_int（&public_curve－＞pnt_order，&point_order）；

field_to_int（&random_key，public_key，c，&x_value）；

int_div（&x_value，&point_order，"ient，&r_value）；

int_to_field（&r_value，&signature－＞r）；

/*computer s=k^－1（e+dr） mod n*/

4.3 數字簽名檢驗

EC_point temp1， temp2， Verify；

BIGINTr_value， s_value；

BIGINT temp， quotient，h1，h2；

BIGINT check_value，point_order；

INDEX I，count；

FIELD_Ph1_field，h2_field；

/*computer inverse of second signature_value*/

Field_to_int（&public_courve－＞pnt_order，&point_order）；

Field_to_int（&signature－＞s，&temp）；

Mod_inv（&temp，&point_order，&s_value）；

/*computer elliptic curve multipliers:h1=hash－3*s，h2=c*/

int_multiple（hash_value，&s_value，&temp）；

int_div（&temp，&point_order，"ient，&h1）

int_to_field（&h1，&h1_field）；

field_to_int（&signature－＞r，&r_value）；

int_multiple（&s_value，&r_value，&temp）；

int_div（&temp，&point_order，"ient，h2）；

int_to_field（&h2，h2_field）；

/*find hidden point from public data*/

EC_multiple （&h1_field，&public_curve －＞pnt，&temp1，&public_curve）；

EC_multiple （&h2_field，sigmature_point，&temp2，&public_curve－＞curve）；

EC_add（&temp1，&temp2，&Verify，&public_curve－＞crv）；

5 軟件仿真

我們使用VC++6.0開發環境，它不但能快速建立Windows界面，且能使用Crypto++代碼，使開發時間大大縮短，軟件運行主界面如圖5所示。

軟件主界面分為3個部分：

1）主菜單部分：IC卡功能、數字簽名、軟件設置及幫助功能，IC卡用戶名及資料只能在正確登錄后才能顯示出來。

2）數字簽名部分：有3個分頁選項，分別是數字簽名生成、簽名驗證及記錄IC卡處理過程的日志信息，方便用戶以后查詢。

3）IC卡設置功能按鈕部分：有關IC卡存取等常用功能按鈕，另外還有選項設定功能，用戶可以修改一些常用選項。右上角的彩色IC卡表明目前IC卡正確聯機使用，否則顯示為灰色。

6 結 論

基于Crypto++庫代碼設計了一個在實驗室仿真的ECDSA簽名軟件，距離實際應用還有大量后續工作要深入研究，目前，國內外有許多密碼研究中心在這方面已經取得了可喜的成績，甚至有成型的芯片出現，所有這些都預示著在不久的將來，ECC將會替代RSA成為公鑰密碼系統的標準。

[1]胡向東，魏琴芳，胡蓉.應用密碼學[M].北京：電子工業出版社，2011.

[2]王學理，裴定一.橢圓與超橢圓曲線公鑰密碼的理論與實現[M].北京：科學出版社，2006.

[3]Stallings W.Cryptography and network security principles and practice，fifth edition[M].北京：電子工業出版社，2011.

[4]馮登國.密碼學原理與實踐[M].2版.北京：電子工業出版社，2005.

[5]JoséR.C.Cruz， Keccak:The New SHA －3 Encryption Standard[J].2013， 5（7）:45－55.

[6]楊皇中.橢圓曲線密碼系統軟件實現技術之探討[J].資訊安全通信，2005，11（1）:15－25.YANG Huang-zhong.Software implementation technology of elliptic curve cryptosystem[J].Journal of Information Security Communication，2005，11（1）:15－25.

[7]吳世忠，祝世雄.應用密碼學協議、算法與C源程序[M].北京：機械工業出版社，2010.

[8]張惟淙，楊中皇.結合Java的ECDSA數位簽章軟件設計與實現[M].臺灣：高雄師范大學出版社，2005.