崔文軍 賈志娟 胡明生* 公 備 王利朋

1(鄭州師范學(xué)院信息科學(xué)與技術(shù)學(xué)院 河南 鄭州 450044)2(北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 北京 100124)

0 引 言

隨著計(jì)算機(jī)等網(wǎng)絡(luò)通信設(shè)施的高速發(fā)展與應(yīng)用，信息安全已然成為當(dāng)今社會(huì)重要的研究熱點(diǎn)之一，其中應(yīng)用于數(shù)據(jù)傳輸、存儲(chǔ)和身份認(rèn)證的安全加解密算法，對(duì)構(gòu)建安全平穩(wěn)的網(wǎng)絡(luò)環(huán)境有著至關(guān)重要的作用。

自公鑰密碼學(xué)出現(xiàn)以來(lái)，是否可以以安全和認(rèn)證的方式傳遞任意長(zhǎng)度的消息，且所耗代價(jià)低于傳統(tǒng)的“先簽名后加密”，這個(gè)疑問(wèn)到20世紀(jì)90年代似乎從未得到過(guò)解決。幸運(yùn)的是，Zheng[1]找到了一種名為“簽密”的新加密方案，它既能夠滿(mǎn)足數(shù)字簽名又可以公鑰加密，且成本遠(yuǎn)低于“先簽名后加密”。隨后，大量科研工作人員對(duì)各類(lèi)相關(guān)方案進(jìn)行了學(xué)習(xí)和研究。文獻(xiàn)[2]改進(jìn)了Zheng的方案，使得接受者不再需要私鑰進(jìn)行簽名驗(yàn)證，并且任何人僅僅使用發(fā)送者的公鑰便可驗(yàn)證方案，也就是說(shuō)方案具有了公開(kāi)驗(yàn)證的性質(zhì)，但其不具備前向安全性。文獻(xiàn)[3]借助離散對(duì)數(shù)問(wèn)題思考了一個(gè)具有前向安全性的簽密方案，但不具備公開(kāi)驗(yàn)證的性質(zhì)。文獻(xiàn)[4]借助雙線性對(duì)給出了一個(gè)基于身份的簽密方案，而后證明了該方案在BDH問(wèn)題難以解決的前提下是安全的。文獻(xiàn)[5]展現(xiàn)了一個(gè)既可以滿(mǎn)足前向安全性又滿(mǎn)足公開(kāi)驗(yàn)證性的簽密方案，并基于求解離散對(duì)數(shù)的困難性問(wèn)題和CDH問(wèn)題困難性證明了方案具備安全性。文獻(xiàn)[6]基于求解離散對(duì)數(shù)問(wèn)題的困難性和Hash函數(shù)的單向性提出了一個(gè)新的簽密方案，通過(guò)將參數(shù)r隱藏在指數(shù)位置(即R=gr)，使得攻擊者即便獲取了發(fā)送者的私密鑰也不可能獲得此次以及之前的秘密信息，即證明了方案具有前向安全性。當(dāng)發(fā)送方與接收方發(fā)生糾紛時(shí)，接受方便可交由第三方進(jìn)行驗(yàn)證，僅需公開(kāi)簽名和明文消息的哈希函數(shù)，這樣就保護(hù)了明文消息，達(dá)到了公開(kāi)驗(yàn)證的目的。文獻(xiàn)[7]對(duì)Zheng的方案進(jìn)行了研究和改善，改進(jìn)后的方案主要包括兩次加解密運(yùn)算和五次模指數(shù)運(yùn)算，而后給出了一個(gè)基于ECC的簽密方案。文獻(xiàn)[8]詳細(xì)分析了文獻(xiàn)[7]的方案，指出其數(shù)字簽密方案并沒(méi)有前向安全性且提出的橢圓曲線數(shù)字簽密方案復(fù)雜度過(guò)高，并針對(duì)這兩個(gè)問(wèn)題做出了改進(jìn)，使得橢圓曲線數(shù)字簽密方案摒棄模指數(shù)與模逆計(jì)算，依靠模乘運(yùn)算，計(jì)算量有了較大幅度減少?；贒L和CDH問(wèn)題的困難性，文獻(xiàn)[9]利用雙線性對(duì)設(shè)計(jì)了一個(gè)無(wú)證書(shū)的簽密方案，并進(jìn)行了有效性、不可偽造性和效率分析。由于簽密長(zhǎng)度較短，該方案能較好適應(yīng)計(jì)算能力受限的環(huán)境。在BDH和CDH問(wèn)題困難性的假設(shè)下，由于公鑰簽密不能處理任意長(zhǎng)度的消息，文獻(xiàn)[10]在隨機(jī)預(yù)言模型下，設(shè)計(jì)了一個(gè)無(wú)證書(shū)混合簽密方案，并證明了相關(guān)的安全性。文獻(xiàn)[11]對(duì)最近提出的六個(gè)簽密方案分別設(shè)計(jì)了密碼學(xué)方面的改進(jìn)，指出六個(gè)方案均不能滿(mǎn)足方案的保密性，詳細(xì)分析了文獻(xiàn)[9]方案，對(duì)其保密性和不可偽造性給出了相關(guān)方面的攻擊，并證明了改進(jìn)的措施安全性。文獻(xiàn)[12]提出了一種無(wú)雙線性映射的高效無(wú)證書(shū)簽密方案，基于CDH假設(shè)和DL困難性問(wèn)題，驗(yàn)證了該方案具有不可偽造性、機(jī)密性、不可否認(rèn)性和公開(kāi)驗(yàn)證性等優(yōu)良的安全性質(zhì)。文獻(xiàn)[13]結(jié)合了混合簽密和環(huán)簽密的優(yōu)勢(shì)，采取KEM-DEM機(jī)制生成了對(duì)稱(chēng)密鑰，并基于離散對(duì)數(shù)問(wèn)題和計(jì)算性DH問(wèn)題，證明了方案具有不可偽造性和機(jī)密性。文獻(xiàn)[14]給出了一個(gè)無(wú)Hash函數(shù)的簽密方案，并證明了該方案具有抗偽造性、前向安全性和公開(kāi)驗(yàn)證性等性質(zhì)。文獻(xiàn)[15]設(shè)計(jì)了一種基于橢圓曲線的前向安全的簽名方案，該方案不僅可以抗隨機(jī)數(shù)攻擊，而且具有前向安全性。該方案比ECDSA方案少了1次倍點(diǎn)運(yùn)算、2次模乘運(yùn)算和2次模逆運(yùn)算，運(yùn)算量較小。文獻(xiàn)[16]對(duì)一種基于橢圓曲線前向安全數(shù)字簽名方案進(jìn)行了分析，指出了其安全性漏洞并給出具體攻擊方法。

1 預(yù)備知識(shí)

1.1 有限域上的橢圓曲線[17-18]

一般來(lái)說(shuō)，稱(chēng)形如E：y2+a1xy+a3y=x3+a2x2+a4x+a6的方程為橢圓曲線的曲線方程，其中a1，a2，a3，a4，a6∈域K。其中，基于有限域Zp上的橢圓曲線方程為：

y2=x3+ax+b

(1)

基于有限域GF(2m)的橢圓曲線方程為：

y2+xy=x3+ax+b

(2)

ECC的域參數(shù)為(q,a,b,G,n,h)。其中q為素?cái)?shù)p或q=2m。常用的橢圓曲線是非奇異的，即4a3+27b2≠0。G是橢圓曲線上的基點(diǎn)，n是點(diǎn)G的大素?cái)?shù)階，即n是滿(mǎn)足nG=0的最小正整數(shù)。h是一個(gè)有橢圓曲線的階除以n產(chǎn)生的余因子，且h≤4。

1.2 橢圓曲線離散對(duì)數(shù)問(wèn)題

1.3 漢明距離[19]

用d(x,y)代表漢明距離，它表示相同長(zhǎng)度的字符串x和y對(duì)應(yīng)位置上不同字符的個(gè)數(shù)。

1.4 Hash(哈希)函數(shù)[17, 20]

Hash函數(shù)可以說(shuō)是一種壓縮映射。不論消息串的長(zhǎng)度大小，均可被映射成較短定長(zhǎng)的消息串。具體性質(zhì)如下：

(1) 正向計(jì)算簡(jiǎn)單性：對(duì)于Hash函數(shù)h和消息x，計(jì)算h(x)是極為簡(jiǎn)單的；

(2) 逆向計(jì)算困難性(也稱(chēng)單向性)：對(duì)給定的任意值y，求解h(x)=y中的x是困難的。

2 文獻(xiàn)[6]方案

2.1 初始化

2.2 簽 密

加密：

c=EK(m)r=h(h(m),yb,gkmodp)R=grmodps=k(r+xa)-1modq

A將消息m簽名為(c,R,s)，并將其發(fā)送給B。

2.3 解 密

B收到A的簽名后，進(jìn)行如下解密計(jì)算：

K=h((yaR)sxbmodp)

解密：

m=DK(c)

簽名驗(yàn)證：

R=gh(h(m),yb,(yaR)smod p)modp

若簽名驗(yàn)證通過(guò)證明簽名有效，則B接受明文消息和來(lái)自A的簽名。

2.4 方案分析

文獻(xiàn)[6]方案主要依賴(lài)于求解離散對(duì)數(shù)問(wèn)題的困難性和Hash函數(shù)的單向性。通過(guò)將參數(shù)r隱藏在指數(shù)位置(即R=gr)，使得攻擊者即便獲取了發(fā)送者的私密鑰也不可能獲得此次以及之前的秘密信息，即證明了方案具有前向安全性。當(dāng)發(fā)送者與接收者發(fā)生糾紛時(shí)，接受者便可交由第三方進(jìn)行驗(yàn)證，僅需公開(kāi)簽名和h(m)，這樣就保護(hù)了明文消息，達(dá)到了公開(kāi)驗(yàn)證的目的?；蛘咴诤灲饷艿倪^(guò)程及公開(kāi)驗(yàn)證階段，用密文c代替h(m)，避免一次哈希運(yùn)算，提高計(jì)算效率和速度。在方案設(shè)計(jì)過(guò)程中，用到了大量模指數(shù)運(yùn)算，和一次模逆運(yùn)算，導(dǎo)致運(yùn)算代價(jià)高昂，費(fèi)時(shí)費(fèi)力。如果能在摒棄模指數(shù)和模逆這樣高代價(jià)運(yùn)算的前提下實(shí)現(xiàn)方案的可公開(kāi)驗(yàn)證性和前向安全性，這樣的方案更值得推廣和應(yīng)用。

3 文獻(xiàn)[8]方案

3.1 初始化

3.2 簽 密

R=rG=(r1,r2)

KAB=ryB=(k,l)

加密：

c=Ek(m)

Hash函數(shù)值e=h(m,r1)，漢明重w=ham(e)。

(2) 隨機(jī)取整數(shù)α,β(0<α,β

u=(r-αr1-βm)modn

s=(w+αr1+xA)modn

簽密為(c,R,s,β,u)，將簽名發(fā)送給B。

3.3 解 密

收到A的簽名后，B進(jìn)行如下解密計(jì)算：

KAB=xBR=(k,l)

解密：

m=Dk(c)

Hash函數(shù)值e=h(m,r1)，漢明重w=ham(e)。

接著再計(jì)算：

γ=(s-w+βm+u)modn

驗(yàn)證等式：

γG-yA=R

若正確，則接受簽密。

3.4 方案分析

由于橢圓曲線的簽解密算法具有密鑰長(zhǎng)度和簽名長(zhǎng)度短的優(yōu)勢(shì)，使得橢圓曲線有著較廣的應(yīng)用。相較于文獻(xiàn)[6]方案，文獻(xiàn)[8]方案是基于求解橢圓曲線離散對(duì)數(shù)問(wèn)題的困難性進(jìn)行簽解密設(shè)計(jì)的。其在滿(mǎn)足公開(kāi)驗(yàn)證性和前向安全性的基礎(chǔ)上，模指數(shù)與模逆運(yùn)算0次，且主要用到了模乘運(yùn)算。方案計(jì)算速度和效率有了大范圍提高，計(jì)算量達(dá)到了較小范圍。若對(duì)該方案進(jìn)行改進(jìn)，降低模乘運(yùn)算的次數(shù)是主要的研究方向之一。

4 方案設(shè)計(jì)

文獻(xiàn)[6]方案在簽解密過(guò)程中用到了模指數(shù)和模逆運(yùn)算，導(dǎo)致運(yùn)算成本高、復(fù)雜度大、代價(jià)高昂。文獻(xiàn)[8]方案模指數(shù)與模逆運(yùn)算0次，主要用到了模乘運(yùn)算。本文在文獻(xiàn)[8]方案的基礎(chǔ)上進(jìn)行改進(jìn)，降低模乘運(yùn)算的次數(shù)是主要的研究方向。本方案借助于求解橢圓曲線離散對(duì)數(shù)問(wèn)題的困難性、Hash函數(shù)單向性和漢明距離等密碼學(xué)知識(shí)進(jìn)行簽密，待收到簽名后進(jìn)行解密，并驗(yàn)證等式βG-wA=R的成立性。整個(gè)方案保證了正確性和安全性，同時(shí)具備一些優(yōu)良性質(zhì)。簽解密過(guò)程中主要用到了模乘運(yùn)算，通過(guò)效率分析可知，本文方案在簽密過(guò)程中比文獻(xiàn)[8]方案少了一次模乘運(yùn)算，簽密長(zhǎng)度少|(zhì)n|。故本文方案在理論上達(dá)到了復(fù)雜度最小化。

4.1 初始化

4.2 簽 密

R=rG

K=rwB=(k1,k2)

加密：

c=Ek1(m)

Hash函數(shù)值e1=h(c,k2)。

此時(shí)任選與e1等長(zhǎng)的e2，計(jì)算：

d=d(e1,e2)

(2) 隨機(jī)取正整數(shù)t(t

α=r+d+xA-tcmodn

簽密為(c,R,e2,t,α)，并將其發(fā)送給B。

4.3 解 密

(1) 接受者B收到(c,R,e2,t,α)后，計(jì)算：

K=xBR=(k1,k2)

解密：

m=Dk1(c)

Hash函數(shù)值e1=h(c,k2)，漢明距離d=d(e1,e2)。

(3) 計(jì)算：

β=(α-d+tc)modn

驗(yàn)證等式：

βG-wA=R

若驗(yàn)證等式正確說(shuō)明簽名有效，則B接受明文消息和來(lái)自A的簽名。

5 方案分析

5.1 正確性證明

βG-wA=(α-d+tc)G-xAG=

(r+d+xA-tc-d+tc-xA)G=

rG=R

上述說(shuō)明此方案的驗(yàn)證過(guò)程正確。

5.2 安全性分析

5.2.1抗私密鑰攻擊

攻擊者獲取簽名(c,R,e2,t,α)后，想要恢復(fù)明文消息m首先需獲知k1(由于m=Dk1(c))。而獲取k1的途徑有兩種。第一種途徑是獲知接受者B的私密鑰xB，通過(guò)K=xBR=(k1,k2)得知。但由wB=xBG求解私密鑰xB等同于求解橢圓曲線離散對(duì)數(shù)問(wèn)題，顯然這是不現(xiàn)實(shí)的。這樣便可實(shí)現(xiàn)抗私密鑰攻擊。第二種途徑可詳看前向安全性的證明。

5.2.2不可偽造性

若對(duì)簽名進(jìn)行偽造，主要有兩類(lèi)人，一是除B之外的攻擊者，二是B本人。

(2) 由解密過(guò)程可知，接受者B偽造簽名，此時(shí)接受者B知道的信息有m、c、R、d、t、α。對(duì)于簽密方程α=r+d+xA-tc，若通過(guò)R=rG解出r等同于求解橢圓曲線離散對(duì)數(shù)問(wèn)題，顯然是不可能的。一個(gè)方程含有兩個(gè)未知量r和xA(A的私密鑰)，故無(wú)法求解簽密方程。

綜上，任何攻擊者均無(wú)法對(duì)簽名進(jìn)行偽造。

5.2.3前向安全性

若發(fā)送者A的私密鑰xA被攻擊者獲取，本方案保證了除接受者B可以得知消息明文m外，其余攻擊者均無(wú)法恢復(fù)m。這主要體現(xiàn)在獲取解密密鑰k1上(由于m=Dk1(c))。而獲取k1的途徑有兩種：

(1) 由K=rwB=(k1,k2)可知需要知道r(wB是接受者B的公開(kāi)鑰)。而R=rG，想要解出r等同于求解橢圓曲線離散對(duì)數(shù)問(wèn)題。

(2) 由K=xBR=(k1,k2)可知需要知道接受者B的私密鑰xB。

綜上，不論是獲得r還是xB，對(duì)于攻擊者來(lái)說(shuō)都是不可能的。

故本方案具有前向安全性。

5.2.4不可否認(rèn)性

即本方案滿(mǎn)足公開(kāi)驗(yàn)證性。當(dāng)矛盾出現(xiàn)時(shí)，即發(fā)送者A否認(rèn)簽密，接受者B可將簽名(c,R,e2,t,α)提供給第三方可信中心進(jìn)行解簽密證實(shí)。第三方在安全可信的基礎(chǔ)上證實(shí)A確定發(fā)送過(guò)該消息，這樣便達(dá)到了不可否認(rèn)的目的。驗(yàn)證過(guò)程中只是對(duì)密文c進(jìn)行公開(kāi)驗(yàn)證，保護(hù)了明文消息m。因此，本文方案具有一定的保密性。

5.3 效率分析

最新能夠同時(shí)保持前向安全性和可公開(kāi)驗(yàn)證性?xún)煞N性質(zhì)的簽密方案即為文獻(xiàn)[6]和文獻(xiàn)[8]方案。由表1可知，文獻(xiàn)[6]方案是基于求解Zp上離散對(duì)數(shù)問(wèn)題的困難性進(jìn)行設(shè)計(jì)的，雖保障了安全性，但在簽密的過(guò)程中主要依靠模指數(shù)和模逆運(yùn)算，導(dǎo)致方案運(yùn)算成本大，不太適用于廣泛應(yīng)用。本文方案與文獻(xiàn)[8]方案是基于求解橢圓曲線離散對(duì)數(shù)問(wèn)題的困難性進(jìn)行簽密的，主要用到了模乘運(yùn)算。但本文方案在簽密過(guò)程中比文獻(xiàn)[8]方案少了一次模乘運(yùn)算，簽密長(zhǎng)度少了|n|。因而，本文方案運(yùn)算量有了大幅度減少，加快了計(jì)算效率和速度，在理論上達(dá)到了復(fù)雜度的最小值。

表1 三種方案效率比較

6 結(jié) 語(yǔ)

本文借助于求解橢圓曲線離散對(duì)數(shù)問(wèn)題的困難性設(shè)計(jì)了一個(gè)簽密方案。已有的多數(shù)方案不能同時(shí)提供前向安全性和可公開(kāi)驗(yàn)證性?xún)煞N性質(zhì)。文獻(xiàn)[6]方案和文獻(xiàn)[8]方案具備了這兩種性質(zhì)。本文先對(duì)文獻(xiàn)[6]方案進(jìn)行分析，發(fā)現(xiàn)文獻(xiàn)[6]方案中用到了模指數(shù)和模逆運(yùn)算，這樣導(dǎo)致計(jì)算成本高、復(fù)雜度大、代價(jià)高昂，故而進(jìn)行廣泛推廣不太適用。由于橢圓曲線的簽解密算法具有密鑰長(zhǎng)度和簽名長(zhǎng)度短的優(yōu)勢(shì)，使得橢圓曲線有著廣泛應(yīng)用。文獻(xiàn)[6]方案是基于求解橢圓曲線離散對(duì)數(shù)問(wèn)題的難度而設(shè)計(jì)的。該方案運(yùn)用模乘運(yùn)算進(jìn)行方案的設(shè)計(jì)，使得方案具備了公開(kāi)驗(yàn)證性和前向安全性，且模指數(shù)與模逆運(yùn)算0次。對(duì)該方案進(jìn)行改進(jìn)，降低模乘運(yùn)算次數(shù)是主要的研究方向之一。針對(duì)此問(wèn)題，設(shè)計(jì)了本文方案。本文方案將簽密過(guò)程與求解橢圓曲線離散對(duì)數(shù)的困難性和哈希函數(shù)的單向性相結(jié)合，能夠同時(shí)滿(mǎn)足前向安全性和可公開(kāi)驗(yàn)證性，安全性高，且簽密過(guò)程中僅用到了模乘運(yùn)算，運(yùn)算速度快。正確性證明部分說(shuō)明了本方案的驗(yàn)證過(guò)程是正確的。通過(guò)驗(yàn)證等式βG-wA=R的正確性，說(shuō)明接受者收到了來(lái)自發(fā)送者的簽名。針對(duì)方案的不可偽造性，本文主要分兩部分進(jìn)行分析，一是除接受者之外的攻擊者進(jìn)行偽造簽名，二是接受者偽造簽名。通過(guò)分析得知任何攻擊者(包括B)均不能對(duì)簽密進(jìn)行偽造。對(duì)于前向安全性，本文假設(shè)了發(fā)送者的私密鑰被攻擊者獲取，但最終除接受者外其他任何人都得不到消息明文。這主要體現(xiàn)在獲取解密密鑰k1上，本文進(jìn)行了兩種情況的分析，分別是簽密和解密階段對(duì)于解密密鑰的獲取。由于方案的驗(yàn)證過(guò)程需要的是密文消息，這樣就可以保證了明文消息的機(jī)密性，進(jìn)而體現(xiàn)出方案可公開(kāi)驗(yàn)證性的性質(zhì)。最后，本文方案進(jìn)行了效率分析。分析表明，本文方案模指數(shù)與模逆運(yùn)算0次，在簽密過(guò)程中比文獻(xiàn)[8]方案少一次模乘，且簽密長(zhǎng)度少了|n|。因而，本文方案運(yùn)算量有了大幅度減少，加快了計(jì)算效率和速度，在理論上達(dá)到了復(fù)雜度的最小值，有著較廣的應(yīng)用性，為簽密技術(shù)在網(wǎng)絡(luò)通信等安全領(lǐng)域提供了一定的理論基礎(chǔ)。

同時(shí)，簽密技術(shù)在各個(gè)領(lǐng)域已經(jīng)得到了廣泛的應(yīng)用，如防火墻[21]和電子現(xiàn)金支付[22]等。安全的簽密技術(shù)可以實(shí)現(xiàn)信息的保密傳輸和生成簽名的身份認(rèn)證，保障交易過(guò)程安全進(jìn)行。在物聯(lián)網(wǎng)、云計(jì)算等相關(guān)領(lǐng)域，如在無(wú)線傳感器網(wǎng)絡(luò)中，利用簽密技術(shù)進(jìn)行密鑰分發(fā)和節(jié)點(diǎn)的可信認(rèn)證，具有廣泛的應(yīng)用前景。隨著計(jì)算機(jī)技術(shù)的發(fā)展，利用求解橢圓曲線離散對(duì)數(shù)的困難性，設(shè)計(jì)更加優(yōu)化安全的算法，減少密鑰長(zhǎng)度，仍有很多的工作要做。