鄧婕 卓碧華

中圖分類號：TN918.1 文獻(xiàn)標(biāo)識碼：A

摘要：提出一種基于橢圓曲線離散對數(shù)問題的數(shù)字簽名方案。避免將明文信息嵌入到橢圓曲線EP（a，b） 上的實際困難，從而提高了加密的效率；同時將DES、ECC和Hash三種算法有機(jī)結(jié)合達(dá)到數(shù)字簽名雙向認(rèn)證的效果。

關(guān)鍵詞：數(shù)字簽名；橢圓曲線加密；單向Hash加密

1.引言

RSA公鑰密碼的安全性基于大整數(shù)因子分解這一數(shù)學(xué)難題，已經(jīng)在信息安全領(lǐng)域得到廣泛的應(yīng)用。

橢圓曲線公鑰密碼（Elliptic Curve Cryptography ，ECC）是在20世紀(jì)80年代由Miller[1]和Koblitz[2]分別獨(dú)立提出的，是繼RSA之后其安全性得到密碼界公認(rèn)的又一公鑰密碼。ECC的安全性基于計算橢圓曲線的離散對數(shù)這一數(shù)學(xué)難題。ECC使用較短的密鑰可以達(dá)到RSA使用較長密碼時同樣的安全性，因此橢圓曲線公鑰密碼在運(yùn)算速度和傳輸帶寬上都有優(yōu)勢，尤其在諸如IC卡、單片機(jī)和移動通信等低端環(huán)境中，存儲資源和計算速度都有很大的限制，橢圓曲線就顯得更為合適。

ECC的安全性依賴于給定G和kG的條件下計算出k的困難程度，這被稱為橢圓曲線對數(shù)問題。取橢圓曲線對數(shù)的最快的技術(shù)是稱為Pollard rho的方法。表一比較了ECC 和RSA的工作效率。我們可以看到，和RSA比較ECC可以用小得多的密鑰大小。另外，在密鑰大小相等時，ECC 和RSA 所要求的計算工作量差不多。因而，在安全性差不多的情況下，使用較短密鑰的ECC比使用RSA具有計算上的優(yōu)勢。

2.數(shù)字簽名

數(shù)字簽名由公鑰密碼發(fā)展而來，是實現(xiàn)電子交易安全的核心技術(shù)之一，它在身份認(rèn)證、數(shù)據(jù)完整性、不可否認(rèn)性以及匿名性等方面有著重要的應(yīng)用。

在數(shù)字簽名協(xié)議中，數(shù)字簽名必須能保證：接收者能夠核實發(fā)送者對報文的簽名；發(fā)送者事后不能抵賴對報文的簽名；接收者不能偽造對報文的簽名。

數(shù)字簽名的基本原理是：發(fā)送者A用自己的私鑰d對報文m進(jìn)行解密（指一個運(yùn)算動作），將結(jié)果D（m）傳送給接收者B。B用已知的A的公鑰e對密文加密得出E（D（m））=m。因為除A外沒有人能具有A的私鑰，所以除A外沒人能產(chǎn)生密文D（m）。這樣，實現(xiàn)了A對報文m的簽名。

3.基于橢圓曲線的數(shù)字簽名

本方案為實現(xiàn)數(shù)字簽名的目的，它的基本原理是：數(shù)據(jù)通信之前，進(jìn)行Hash運(yùn)算得到信息摘要（因為對整個報文實施加密通常是不切實際的，且對于大的數(shù)據(jù)分組的使用，像ECC這樣的函數(shù)可能也太昂貴了。在這種情況下可以采用Hash函數(shù)，因為Hash函數(shù)具有兩個重要特性：①它的輸出一般相對較短，通常為128位；②也是更重要的一點(diǎn)，Hash函數(shù)具有抗碰撞性，就是說能保證不會有兩個不同的數(shù)據(jù)產(chǎn)生相同的Hash值，即當(dāng)x≠y是f（x）≠f（y）。因此，攻擊者不能根據(jù)截獲到的真正的散列值，構(gòu)造出欺騙明文并通過鑒別），然后使用ECC對信息摘要進(jìn)行數(shù)字簽名，然后產(chǎn)生一個DES密鑰對信息明文和摘要進(jìn)行加密，同時通過ECC對DES密鑰進(jìn)行加密和實現(xiàn)數(shù)字簽名。

3.1橢圓曲線的定義

ECC是在1985年由V.Miller[1]和 N.Koblitz[2]分別獨(dú)立提出的。對于ECC來說我們最關(guān)心的是一種受限形式的橢圓曲線，這種橢圓曲線定義在一個有限域（Fp）上 。密碼編碼學(xué)特別感興趣的是被稱為模p橢圓群的對象，其中p（p≥3）是一個素數(shù)。這個群的定義如下。選擇兩個滿足下列條件的小于p的非負(fù)整數(shù)a和b：

4a3+27b2（modp）≠0

那么EP（a，b）表示滿足下列條件的模p橢圓群：這個群中的元素（x，y）是滿足如下方程的小于p的非負(fù)整數(shù)另外加上無窮點(diǎn)0：

y2≡x3+ax+b（modp）（1）

我們在這個有限域橢圓曲線E上定義“+”運(yùn)算，P+Q=R，R是過P，Q 的直線上與曲線的另一個交點(diǎn)關(guān)于x的對稱點(diǎn)；當(dāng)P=Q 時，R 是P 點(diǎn)的切向量與曲線的另一個交點(diǎn)關(guān)于x 軸的對稱點(diǎn)。這樣，（E，+）構(gòu)成可交換群（Abel群），O是加法單位元（零元）。橢圓曲線上的所有點(diǎn)外加一個叫做無窮遠(yuǎn)點(diǎn)的特殊點(diǎn)構(gòu)成的集合連同一個定義的加法運(yùn)算構(gòu)成一個Abel群。在等式mP=P+P+···+P=Q中，已知m和點(diǎn)P求點(diǎn)Q比較容易，反之已知點(diǎn)Q和點(diǎn)P求m卻是相當(dāng)困難的，這個問題就被稱為橢圓曲線上的離散對數(shù)問題。橢圓曲線密碼體制正是利用這個困難問題設(shè)計而來[5，6]。

3.2橢圓曲線加密方案

設(shè)E為有限域Fp（p≥3為素數(shù)）上的橢圓曲線，選擇一個素數(shù)p≈2180和方程（1）的橢圓曲線參數(shù)a和b，這就定義了點(diǎn)組成的橢圓群EP（a，b）。又設(shè)G為EP（a，b）上選定的一個點(diǎn)（稱為基點(diǎn)），選擇G的重要準(zhǔn)則是滿足nG=0的最小n值是一個非常大的素數(shù)，我們稱n為G的階，且選擇的n為一個不等于p的大素數(shù)。以eA（1

橢圓曲線加密：

該方案要同時具有認(rèn)證功能，則它需要利用一個信息認(rèn)證碼HMAC=（T，V）和2個hash函數(shù)H1和H2。這里T=T（k，x）是信息認(rèn)證碼的生成算法，它根據(jù)輸入的密鑰k和信息x，輸出標(biāo)簽T。V=V（k，x，T）∈{0，1}是信息認(rèn)證碼的驗證算法，這里k為密鑰，x為信息，T為待驗證的標(biāo)簽。當(dāng)信息可以接受時，V 的輸出為1；當(dāng)信息不能接受時，V 的輸出的0。

設(shè)用戶A欲將明文m加密后發(fā)送給B。Hash函數(shù)H1和H2的輸出為192比特，明文和密鑰也都取為192比特。

用戶A的加密算法：

①A隨機(jī)選取整數(shù)r∈[1，n-1]，計算R=rG；

②計算D=rPB=（Dx，Dy）；

③將有限域元素Dx作為輸入字節(jié)串Z，計算K1=H1（Z），K2=H2（Z）；

④計算c=m⊕K1，T=T（K2，c）；

⑤發(fā)送（c，R，T）給B。

用戶B的解密運(yùn)算：

①計算D=eBR=（Dx，Dy）；檢查D≠0，如果D=0，則輸出“無效”且結(jié)束。

②將有限域元素Dx作為輸入字節(jié)串Z，計算K1=H1（Z），K2=H2（Z）

③計算V（K2，c，T），若V=0，則拒絕接受該信息；若V=1，則進(jìn)行下一步。

④4）計算m=K1⊕c，輸出明文m.

在上述算法中，將Z的Hash值K1與明文m進(jìn)行c=m⊕K1運(yùn)算，有利于隱蔽Z的特性。而采用信息認(rèn)證碼，一方面得到認(rèn)證的功能，另一個方面防止了攻擊方對密文的篡改，從而攻擊者不能利用選擇密文攻擊法進(jìn)行攻擊。

3.3橢圓曲線的數(shù)字簽名過程

（1）發(fā)送方A準(zhǔn)備好要傳送的明文信息。

（2）發(fā)送方A對信息進(jìn)行Hash運(yùn)算，得到一個信息摘要。

（3）發(fā)送方A用自己的橢圓曲線加密算法的私鑰（SK）對信息摘要進(jìn)行加密，得到發(fā)送方A的數(shù)字簽名，并將其附在明文信息m之后。

（4）發(fā)送方A隨機(jī)產(chǎn)生一個加密密鑰（DES密鑰），并用此密鑰對要發(fā)送的信息（此時要發(fā)送的信息中包含明文和發(fā)送方的數(shù)字簽名）進(jìn)行加密，形成密文。

（5）發(fā)送方A用接受方B的公鑰（PK）對剛才隨機(jī)產(chǎn)生的加密密鑰（DES密鑰）進(jìn)行加密，將加密后的DES密鑰連同密文一起傳送給接受方B。

（6）接受方B收到發(fā)送方A傳過來的密文和加過密的DES密鑰，先用自己的私鑰（SK）對加密的DES密鑰進(jìn)行解密，得到DES密鑰。

（7）然后接受方B用DES密鑰對收到的密文進(jìn)行解密，得到明文信息和數(shù)字簽名，再將DES密鑰拋棄（即DES密鑰作廢）。

（8）接受方B用發(fā)送方A的公鑰（PK）對發(fā)送方A的數(shù)字簽名進(jìn)行解密，得到信息摘要，同時實現(xiàn)了雙向認(rèn)證的效果。

（9）接受方B用相同的Hash算法對收到的明文再進(jìn)行一次Hash運(yùn)算，得到一個新的信息摘要。

（10）接受方將收到的信息摘要和新產(chǎn)生的信息摘要進(jìn)行比較。由于單向Hash函數(shù)具有良好的抗碰撞性，所以如果兩份信息摘要內(nèi)容一致，則可以說明收到的信息沒有被修改過。

4.結(jié)束語

本方案加密和簽名過程中，并沒有將明文m嵌入到橢圓曲線上的形成可逆的Pm點(diǎn)域，同時也避開橢圓曲線加密的求逆的運(yùn)算，從而降低了橢圓曲線加密運(yùn)算的難度；而且對比較龐大的明文信息進(jìn)行Hash運(yùn)算，也對龐大的明文信息和簽名信息使用速度最快的DES進(jìn)行加密，且對需要保密的DES密鑰和信息摘要則采用強(qiáng)度較高的ECC進(jìn)行加密，這樣可以充分發(fā)揮Hash、DES和ECC各自的長處，在不降低安全性的情況下，大大節(jié)省了加密的時間和加密的效率，并達(dá)到相互認(rèn)證的效果。