基于橢圓曲線的一種盲數(shù)字簽名設(shè)計

謝 揚 ，王金鳳

（1.重慶大學 通信工程學院，重慶400044；2.重慶電子工程職業(yè)學院 軟件工程系，重慶401331）

基于橢圓曲線的一種盲數(shù)字簽名設(shè)計

謝 揚1，王金鳳2

（1.重慶大學 通信工程學院，重慶400044；2.重慶電子工程職業(yè)學院 軟件工程系，重慶401331）

隨著計算機和通信技術(shù)的迅速發(fā)展，對信息的保密性與真實性的要求越來越高。公鑰密碼體制的出現(xiàn)是為了解決對稱密鑰所不能解決的問題，而數(shù)字簽名是公鑰密碼的一個重要的應用。數(shù)字簽名在信息安全技術(shù)中的身份認證、數(shù)據(jù)完整性、不可否認性及匿名性等方面起到了重要的作用，本文基于橢圓曲線密碼體制的盲數(shù)字簽名設(shè)計，并分析了其安全性，對建立一個安全有效的電子認證系統(tǒng)有一定現(xiàn)實價值。

橢圓曲線；盲數(shù)字簽名；協(xié)議安全

1 引言

隨著計算機和通信技術(shù)的迅速發(fā)展，大量的敏感信息常常通過公共通訊設(shè)施或計算機網(wǎng)絡(luò)進行交換，越來越多的個人信息需要得到嚴格保密。公鑰密鑰密碼是現(xiàn)代密碼學中最重要的研究內(nèi)容之一，它不但能為在網(wǎng)絡(luò)中傳遞的信息提供機密性的保護，而且還能提供信息的發(fā)送人的身份認證以及信息的完整性檢驗。

公鑰密碼仍存在一些缺點：因為公鑰密碼的計算是對大數(shù)進行操作，不同于對稱密碼是對比特位進行操作，因而它的計算量較大。因此，在網(wǎng)絡(luò)上都用公鑰密碼來加密機密文件是一件花銷很大的事。我們可以利用公開密鑰的特性，只把它用于對對稱密鑰進行加密，而用對稱密鑰來加密文件，這樣的方法稱之為數(shù)字信封。這樣既解決了密鑰協(xié)商的問題，又彌補了公鑰加密速度慢的不足。

2 公鑰密碼體制的實現(xiàn)基礎(chǔ)

公鑰密碼體制的成功依賴于這樣一個問題：怎樣才能實現(xiàn)由 Ei（加密）獲得 Di（解密）,即求 Ei-1是困難的。可通過單向函數(shù)實現(xiàn)這樣的要求。嚴格單向函數(shù)：

對一個單向函數(shù)f：X→Y，如果下述條件成立：存在一個有效的方法，對所有的x∈X可計算f(x),但是不存在有效的方法由y＝f(x)計算x，對所有的y∈f[X]。則稱函數(shù)f：X→Y是嚴格單向函數(shù)。

嚴格的加密函數(shù)由于不能反向計算，所以不能用于消息的加密和解密，但是卻可以用于數(shù)字簽名和身份的認證識別。

陷門單向函數(shù)：

只允許合法的用戶通過解密訪問數(shù)據(jù)，對于單射函數(shù)f：X→Y，如果滿足對所有x∈X，存在一個有效的方法計算f(x)，而且對所有y∈f[X]，存在一個有效方法計算f-1(y)，但是對所有y∈f[X]不能從關(guān)系式y(tǒng)＝f(x)有效地導出f-1(y)：這需要額外的秘密信息，即陷門。則單射函數(shù)f：X→Y為陷門單向函數(shù)。

3 公鑰密碼體制的設(shè)計

設(shè)計公鑰密碼體制首先要尋找一個單向陷門函數(shù)，在數(shù)學中稱為NP問題或NPC問題，NP問題是指在非確定性圖靈機上可用多項式時間求解的問題，稱為非確定性多項式時間可解問題。在NP類問題中困難程度最大的一類問題稱為NP完全類，即NPC問題。

單向函數(shù)的構(gòu)造過程如下：

1.從一個困難的問題P著手，取出P中的一個子問題P1；

2.對問題P1進行偽裝，并使得其得到的問題P2看起來很像原始問題P，用P2作為加密密鑰；

3.對如何從P2恢復得到P1的有關(guān)信息保密，稱該信息為“陷門”；

4.使系統(tǒng)的合法用戶能夠通過求解容易的問題P1進行解密，而其他用戶不得不去求P2。

目前已經(jīng)出現(xiàn)的公鑰密碼體制所基于的問題有：

（1）整數(shù)分解問題；

（2）Zp上的離散對數(shù)問題；

（3）橢圓曲線上的離散對數(shù)問題；

（4）線性編碼的解碼問題；

（5）構(gòu)造非線性弱可逆有限自動機的弱逆問題。

4 公鑰密碼的加密解密和數(shù)字簽名

對公鑰密碼體制的要求：

用KPi和KCi分別表示第i個用戶的公鑰和私鑰。KPi決定了一個加密Ei，KCi決定了一個解密Di。Ei和Di都可以有效的實現(xiàn)，但{KPi}是一個公開的目錄，而KCi第i個用戶知道。對所有用戶來說，很難從KPi推導出KCi。

如果 Ei和 Di滿足：Di(Ei(x))＝x

我們稱非對稱加密方法滿足機密性要求。

如果 Ei和 Di滿足：Ei(Di(x))＝x

我們稱非對稱加密方法滿足認證要求。

非對稱加密方法：

如果A想發(fā)送消息m給B，他從目錄中選取標記為B的密鑰KPB(這決定了EB)對消息進行加密：A)c＝EB(m)

并在公開信道上將密文c發(fā)給B。

B用他的私鑰KCB(這決定了DB)來恢復消息m:B)DB(c)＝DB(EB(m))＝m

非對稱簽名方法：

如果A想發(fā)送消息m給B，為了證明這個消息是A發(fā)出的，A要用自己的私鑰KCA(這決定了DA)對消息進行簽名：

A)d＝DA(m)

并在公開信道上將經(jīng)過簽名的密文d發(fā)給B。

B從目錄中選取標記為A的公鑰KPA(這決定了EA)對d進行驗證：

B)EA(d)＝EA(DA(m))＝m

因為只有A才會用自己的私鑰對消息加密，所以B確信消息是A所發(fā)出的。

非對稱加密簽名方法：

如果A想發(fā)送一條加密消息m給B，并加上自己的簽名，他首先用自己的私鑰KCA(這決定了DA)對消息進行簽名：

A1)d＝DA(m)

并將d加到他的簽名‘A’中，接下來他從目錄中選取標記為B的密鑰KPB對(‘A’,d)加密：A2)e＝EB(‘A’,d)

并在公開信道上將e發(fā)給B。

B用自己的KCB(這決定了DB)來恢復數(shù)對：B1)DB(e)＝DB(EB(‘A’,d))＝(‘A’,d)

B從數(shù)對(‘A’,d)中得知A是發(fā)送方，然后B用A的公鑰KPA從d中恢復m：B2)EA(d)＝EA(DA(m))＝m

B獲得了消息m，而且確信消息是A所發(fā)出的，因為只有A才會用自己的私鑰對消息加密。

5 橢圓曲線在公鑰密碼系統(tǒng)中的理論基礎(chǔ)

橢圓曲線理論是代數(shù)、幾何、數(shù)論等多個數(shù)學分支的一個交叉點，它是由Weierstrass方程所確定的三次平面曲線方程，它的一般形式如下：

其中 a、b、c、d、e 是滿足一些條件的實數(shù)，滿足上述方程的數(shù)偶(x,y)我們稱為橢圓曲線上的點。點O被稱為無窮點或零點。那么橢圓曲線可以表示為E＝{(x,y)∈ K×K|y2+axy+by＝x3+cx2+dx+e}∪{O}，E 或者 E/K 就表示有限域K上的橢圓曲線。

對于橢圓曲線，可以定義這樣一種形式的加法：如果一個橢圓曲線上的三個點處于一條直線上，那么它們的和為O。從這個定義可以定義橢圓曲線的加法規(guī)則：

①O是加法的單位元。O＝－O；對于橢圓曲線上的任意一點 P 有 P＋O＝P。

②一條垂直的線和曲線相交于兩個有相同x坐標的點，即P1＝(x,y)和 P2＝(x,-y)。它也和曲線相交與無窮點。因此有 P1＋P2＋O＝O 和 P1＝－P2。 因而一個點的負值是有一個有著相同的x坐標和負的y坐標的點。(如圖1)

③要對具有不同的x坐標的兩個點Q和R進行相加，先在它們之間畫一條直線并求出第三個交點P。容易看出這種交點是唯一的 (除非這條直線在Q和R處是曲線的切線，這時取 P＝Q 或 P＝R)。那么有 Q+R+P＝O,因此有Q+R＝－P。 (如圖 1)

④要對一個點Q加倍，畫一條切線并求出另一個交點 S。 那么 Q+Q＝2Q＝－S。 (如圖 2)

這些加法規(guī)則滿足正常的加法性質(zhì)，比如交換律和結(jié)合律。一條橢圓曲線上的一個點P被另一個正整數(shù)k相乘的乘法被定義為k個P的相加，如3P＝P+P+P。

以上性質(zhì)說明：橢圓曲線上的點關(guān)于運算＋成交換群(Abel群)。橢圓曲線密碼體制的算法基礎(chǔ)正是建立在這種大數(shù)運算的操作上的。

圖1 橢圓曲線上的加法P+Q＝R

圖2 橢圓曲線上的加法P＋P＝2P＝R

6 基于橢圓曲線密碼體制的盲數(shù)字簽名設(shè)計

6.1 數(shù)字簽名與盲簽名

數(shù)字簽名是公鑰密碼的一個重要的應用，它在信息安全（包括身份認證，數(shù)據(jù)的完整性，不可否認性以及匿名性等方面）特別是在大型網(wǎng)絡(luò)安全通訊中的密鑰分配、認證及電子商務(wù)系統(tǒng)中，具有重要的作用。簡單的說，數(shù)字簽名就是一種鑒別機制，可以在一個要傳送的報文中附帶一段起到簽名作用的代碼。這個簽名保證了報文的來源和完整性。

盲簽名是需要某人對一個文件簽名，但不讓他知道文件內(nèi)容，所以先把消息盲化再讓另一個人簽名的方法稱為為盲簽名。

盲簽名過程如下圖3：

圖3 盲簽名過程框圖

一個盲簽名方案是一個包含兩個參與者的密碼協(xié)議：一個用戶U和一個簽名者S。用戶選擇一個文件，并從簽名者那里得到了簽名者對這個文件的簽名，卻沒有對簽名者泄露關(guān)于這個文件的任何信息，而且即使以后簽名者又見到了這個消息簽名時，他也無法確定是否是他簽署的。

盲數(shù)字簽名不同于一般的數(shù)字簽名，它不但具有普通數(shù)字簽名的全部作用，而且使文件簽名過程也變得更加的安全，因為簽名者無法泄露關(guān)于文件的任何信息，因此，盲數(shù)字簽名可被用來設(shè)計匿名電子現(xiàn)金系統(tǒng)。

6.2 橢圓曲線公鑰密碼的盲數(shù)字簽名設(shè)計

6．2．1 體制參數(shù)

設(shè) T＝(p，a，b，G，n，h) 為橢圓曲線的系統(tǒng)參數(shù)，na，Pa分別為簽名者A的私鑰和公鑰；nb，P b分別為用戶B的私鑰和公鑰。

6．2．2 盲簽名過程

假設(shè)，用戶B要求A對B的一個文件進行盲簽名：

1)簽名者A隨機選取一個整數(shù)k，(0

計算：Q＝kG，并將Q傳送給B；

2)用戶B接收到Q后，隨機生成一個整數(shù)r1，(0

計算：R＝r1Q＝(Rx,Ry)；

3)用戶B再隨機生成一個整數(shù)r2，(0

計算：＝(mr2)mod n 及 r＝(r2Rx)mod n。 并將(，r)傳送給A；

4) 簽名者 A 計算：＝((na＋r)/k)mod n，完成簽名，并將傳送給用戶B；

5)用戶B計算：Y＝(r1-1 r2-1)mod n，輸出簽名(R,Y)。

簽名驗證：驗證mPa＝Y(jié)R－RxG，若等式成立，則驗證通過，否則簽名不正確。

驗證公式的證明：

6．2．3 算法的安全性分析

按照盲數(shù)字簽名方案的特性，明文消息m對于簽名者A來說是盲的。所以A在對B進行認證時只能得到加密后的消息，而由得到m相當于解橢圓曲線離散對數(shù)問題，所以A不可能看到明文消息m。同樣，基于橢圓曲線離散對數(shù)問題的難解性，A也不能將盲簽名(R，Y)與盲消息對應起來。要偽造簽名是不可能的，因為在等式mPa＝Y(jié)R－RxG中如果先確定Rx，則求解Y相當于求解橢圓曲線離散對數(shù)問題，因為要求解Y，必要先求解r1，r2，那么必求解 R＝r1Q＝(Rx,Ry)和 r＝(r2Rx)mod n 這兩式，所以求解r1，r2正是求解ECDLP問題；先確定Y再求解Rx是一個指數(shù)問題，因為要確定Y，那么需求解Y＝(r1-1 r2-1)mod n，也沒有有效解法。因此，本方案滿足盲數(shù)字簽名的要求。

7 結(jié)論

盲數(shù)字簽名以橢圓曲線密碼體制的安全性為保證，橢圓曲線密碼體制的安全性是基于橢圓曲線離散對數(shù)問題的難解性之上的，目前還沒有對橢圓曲線離散對數(shù)問題的有效解法；合法用戶采用橢圓曲線盲數(shù)字簽名方法處理信息之后，非法用戶不能偽造合法用戶的簽名，因為在不知道合法用戶密鑰的情況下是不能對橢圓曲線離散對數(shù)問題求解的。同樣，基于橢圓曲線離散對數(shù)的難解性，不可能得知雙方交換信息的內(nèi)容，也無法對截獲的信息進行流量分析，重傳以及修改或偽造。以此方案，可以滿足匿名電子現(xiàn)金系統(tǒng)等方面的安全認證需要。

[1]Mohan Atreya．數(shù)字簽名[M]．北京：清華大學出版社，2003．

[2]William Stallings．Cryptography and Network Security:Principles and practice Second Edition[M]．北京：電子工業(yè)出版社，2001．

[3]DEW AGHE L．Remarks on the schoff－Elkies－Atkin algorithm[M]．Math Comp， 1998,67(223):1247～1252．

[4]MENEZES A,VANSTONE S．Elliptic Public Key Cryptosystems[M]．Bostou Ha－ rdbamd：Kiuwer Acadamic Publishers，l993．

[5]Schoof R．Elliptic curves over finite field and the computation of square roots mod p[M]．Mathematics of Computation．1985,44:483～494．

[6]Robshaw M,Yin Y．Elliptic curve cryptosystems[M]．New York：RSA Labora－ tories，1997．

[7]Menezes A,Okamoto T,Vanstone S．Reducing elliptic curve logarithms to logarithms in afinite field [M]．IEEE TIT，1993,39(5):1639～164．

TP39

A

1674－5787（2010）02－0152－03

2009-12-31

謝揚（1981—），男，重慶市人，工程師，重慶大學通信工程學院碩士研究生，研究方向：通信網(wǎng)絡(luò);王金鳳(1981—)，女，河北人，重慶電子工程學院軟件工程系，講師，研究方向：網(wǎng)絡(luò)通信。

責任編輯 王榮輝