白永祥

（1.渭南職業(yè)技術(shù)學(xué)院 陜西 渭南 714000；2.西北大學(xué) 信息科學(xué)與技術(shù)學(xué)院，陜西 西安 710127）

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

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

1 橢圓曲線密碼系統(tǒng)

1.1 ECC原理概述

橢圓曲線密碼體制的安全性基于有限域上橢圓曲線離散 對(duì) 數(shù) 問(wèn) 題 （Elliptic Curve Discrete Logarithm Problem，ECDLP）的難解性。這種密碼體制目前還沒(méi)有找到解決此問(wèn)題的亞指數(shù)時(shí)間算法，因而它具有一些其他公鑰密碼體制無(wú)法比擬的優(yōu)點(diǎn)。

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

應(yīng)用于密碼學(xué)中的橢圓曲線是由滿足該方程式的所有點(diǎn)（x，y）及一個(gè)無(wú)限遠(yuǎn)點(diǎn)所形成的集合，常用于應(yīng)用的橢圓曲線有3種：

1）實(shí)數(shù)域上的橢圓曲線：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 橢圓曲線上點(diǎn)的群運(yùn)算法則

給定一條Fq上的橢圓曲線E，及其上的任意兩點(diǎn)P和Q，連接P和Q的直線與E交于第3個(gè)點(diǎn)-R，由于-R和無(wú)窮遠(yuǎn)點(diǎn)O可決定一直線，該直線與E交于一個(gè)交點(diǎn)R定為P與Q的和，記為P+Q?？梢宰C明這樣定義E上點(diǎn)的加法后，就使E成為一個(gè)Abel群。具體的運(yùn)算法則如下：

設(shè) P=（x1，y1），Q=（x2，y2） 為實(shí)數(shù)域上橢圓曲線上任意兩點(diǎn)，且P≠O≠Q(mào)，則有橢圓曲線方程：y2=x3+ax+b

則兩點(diǎn)加法的運(yùn)算規(guī)則如下：

1）當(dāng) P≠Q(mào) 時(shí)，P+Q=R（x3，y3），如圖 1 所示；

2）當(dāng) P=Q 時(shí)，P+Q=R（x3，y3），如圖 2 所示；

3）當(dāng) x1=x2時(shí)，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

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

1.3 橢圓曲線加密解密算法

1.3.1 密鑰生成

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

1）Alice 隨機(jī)選取一個(gè)整數(shù) dA∈[1，n-1]；

2）然后 Alice計(jì)算 QA=dAP；

3）Alice的公鑰為點(diǎn) QA；

4）Alice的私鑰為整數(shù) dA。

對(duì)于Bob也要做同樣的工作，具體過(guò)程如下：

1）Bob 隨機(jī)選取一個(gè)整數(shù) dB∈[1，n-1]；

2）然后 Bob計(jì)算 QB=dBP；

3）Bob 的公鑰為點(diǎn) QB；

4）Bob的私鑰為整數(shù) dB。

1.3.2 加密、解密方案

現(xiàn)在假設(shè)Bob要發(fā)送信息給Alice，則Bob的加密過(guò)程如下：

1）找出 Alice的公鑰 QA；

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

3）隨機(jī)選取一個(gè)整數(shù) k∈[1，n-1]；

4）計(jì)算點(diǎn)（x1，y1）=kP；

5）計(jì)算機(jī)點(diǎn)（x2，y2）=kQA，若 x2=0，則返回第 3 步；

6）計(jì)算 c=m·x2；

7）將已加密數(shù)據(jù)（x1，y1，c）發(fā)送給 A。

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

1）計(jì)算點(diǎn)（x2，y2）=dA（x1，y1），得出 x2∈Fq；

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

1.4 橢圓曲線數(shù)字簽名算法（ECDSA）

1998年，橢圓曲線數(shù)字簽名算法（ECDSA）成為ISO標(biāo)準(zhǔn)，ECDSA相對(duì)傳統(tǒng)簽名算法具有速度快、強(qiáng)度高、簽名短等優(yōu)點(diǎn)，其應(yīng)用也逐漸廣泛了，例如Windows系列操作系統(tǒng)25位的CD-Key中就使用了橢圓曲線簽名算法[3]。ECDSA的工作原理與大多數(shù)簽名算法類似，都是使用私鑰進(jìn)行簽名，公鑰進(jìn)行驗(yàn)證。

下面給出的ECDSA方案是基于IEEE P1363標(biāo)準(zhǔn)草案給出的，具體算法描述過(guò)程如下：

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

1）將待發(fā)送信息M轉(zhuǎn)化為比特串；

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

3）隨機(jī)選取整數(shù) k∈[1，n-1]；

4）計(jì)算點(diǎn)（x1，y1）=kP；令 r=x1（mod n），若 r=0，返回第 3）步；

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

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

ECDSA簽名驗(yàn)證：當(dāng)Bob收到Alice對(duì)信息M的簽名（r，s），需要驗(yàn)證是否為Alice所簽，則Bob要完成下述過(guò)程：

1）找出 Alice的公鑰 QA；

2）計(jì)算 Hash值 e=H（M）；

3）計(jì)算 s－1mod n；

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

5）計(jì)算點(diǎn)（x1，y1）=uP1+vQA；

6）當(dāng)且僅當(dāng)x1mod n=r時(shí)，Alice對(duì)信息M的簽名被Bob認(rèn)可。

2 Hash函數(shù)

2.1 Hash函數(shù)定義

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

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

Hash函數(shù)其實(shí)就是一種將無(wú)限多個(gè)元素映射到有限個(gè)元素的一種特殊的數(shù)學(xué)函數(shù)。它是把任意長(zhǎng)度的輸入通過(guò)散列算法變換成一個(gè)固定長(zhǎng)度的輸出，稱該輸出為散列值或消息指紋，這種轉(zhuǎn)換是一種壓縮映射，也就是說(shuō)散列值所占的空間遠(yuǎn)遠(yuǎn)小于輸入的空間。Hash函數(shù)在現(xiàn)代密碼學(xué)中具有重要的作用。

2.2 Hash函數(shù)的安全性

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

2012年10月，美國(guó)NIST選擇了Keccak算法作為SHA－3的標(biāo)準(zhǔn)算法，Keccak擁有良好的加密性能以及抗解密能力。Keccak采用了創(chuàng)新的的“海綿引擎”散列消息文本，它設(shè)計(jì)簡(jiǎn)單，方便硬件實(shí)現(xiàn)。Keccak已可以抵御最小的復(fù)雜度為2n的攻擊，它具有廣泛的安全邊際，至目前為止，第三方密碼分析已經(jīng)顯示出Keccak沒(méi)有嚴(yán)重的弱點(diǎn)[6]。

3 智能卡

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

4 軟件設(shè)計(jì)

4.1 概要設(shè)計(jì)

軟件功能包括登錄密碼驗(yàn)證、密鑰設(shè)置、數(shù)字簽名及檢驗(yàn)，如果密碼輸入錯(cuò)誤，為了保護(hù)用戶賬號(hào)安全，最多只有三次機(jī)會(huì)，超過(guò)三次輸入，智能卡便會(huì)死鎖。具體應(yīng)用流程如圖4所示。

4.2 數(shù)字簽名設(shè)計(jì)

由于C++具有代碼效率高等優(yōu)點(diǎn)，所以數(shù)字簽名使用VC++6.0開(kāi)發(fā)環(huán)境進(jìn)行實(shí)現(xiàn)[8]，ECDSA主要過(guò)程代碼如下：

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 數(shù)字簽名檢驗(yàn)

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開(kāi)發(fā)環(huán)境，它不但能快速建立Windows界面，且能使用Crypto++代碼，使開(kāi)發(fā)時(shí)間大大縮短，軟件運(yùn)行主界面如圖5所示。

軟件主界面分為3個(gè)部分：

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

2）數(shù)字簽名部分：有3個(gè)分頁(yè)選項(xiàng)，分別是數(shù)字簽名生成、簽名驗(yàn)證及記錄IC卡處理過(guò)程的日志信息，方便用戶以后查詢。

3）IC卡設(shè)置功能按鈕部分：有關(guān)IC卡存取等常用功能按鈕，另外還有選項(xiàng)設(shè)定功能，用戶可以修改一些常用選項(xiàng)。右上角的彩色I(xiàn)C卡表明目前IC卡正確聯(lián)機(jī)使用，否則顯示為灰色。

6 結(jié) 論

基于Crypto++庫(kù)代碼設(shè)計(jì)了一個(gè)在實(shí)驗(yàn)室仿真的ECDSA簽名軟件，距離實(shí)際應(yīng)用還有大量后續(xù)工作要深入研究，目前，國(guó)內(nèi)外有許多密碼研究中心在這方面已經(jīng)取得了可喜的成績(jī)，甚至有成型的芯片出現(xiàn)，所有這些都預(yù)示著在不久的將來(lái)，ECC將會(huì)替代RSA成為公鑰密碼系統(tǒng)的標(biāo)準(zhǔn)。

[1]胡向東，魏琴芳，胡蓉.應(yīng)用密碼學(xué)[M].北京：電子工業(yè)出版社，2011.

[2]王學(xué)理，裴定一.橢圓與超橢圓曲線公鑰密碼的理論與實(shí)現(xiàn)[M].北京：科學(xué)出版社，2006.

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

[4]馮登國(guó).密碼學(xué)原理與實(shí)踐[M].2版.北京：電子工業(yè)出版社，2005.

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

[6]楊皇中.橢圓曲線密碼系統(tǒng)軟件實(shí)現(xiàn)技術(shù)之探討[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]吳世忠，祝世雄.應(yīng)用密碼學(xué)協(xié)議、算法與C源程序[M].北京：機(jī)械工業(yè)出版社，2010.

[8]張惟淙，楊中皇.結(jié)合Java的ECDSA數(shù)位簽章軟件設(shè)計(jì)與實(shí)現(xiàn)[M].臺(tái)灣：高雄師范大學(xué)出版社，2005.