張雪峰,姜民富

(信陽農(nóng)林學(xué)院 信息工程學(xué)院，河南 信陽 464000)

0 引言

信息的保密和認(rèn)證是密碼學(xué)研究的兩個(gè)重要方面，數(shù)字簽名算法和公鑰加密算法是公鑰密碼學(xué)領(lǐng)域分別實(shí)現(xiàn)保密和認(rèn)證的兩類重要算法.數(shù)字簽密[1]將數(shù)字簽名和公鑰加密結(jié)合在一起，可以同時(shí)完成對(duì)消息的加密和簽名，相較于先簽名后加密，簽密算法無論在計(jì)算性能方面還是在數(shù)據(jù)傳輸量方面都有較明顯的優(yōu)勢(shì).

傳統(tǒng)的基于證書公鑰密碼體制需要解決復(fù)雜的公鑰證書的存儲(chǔ)和管理問題，而基于身份公鑰密碼體制[2]雖然不需要公鑰證書，但卻出現(xiàn)了新的安全隱患，即密鑰托管問題.無證書公鑰密碼體制[3]很好地解決了這兩個(gè)問題：由用戶自己生成公鑰，不需要公鑰證書；由用戶和私鑰生成中心(KGC)共同生成私鑰，解決了密鑰托管問題.2008年，BARBOSA等[4]提出了第一個(gè)無證書簽密方案，并定義了無證書簽密的安全模型.同年，ARANHA等[5]和WU等[6]基于雙線性對(duì)也分別提出無證書簽密方案.但SHARMILA等[7]和SELVI等[8]指出文獻(xiàn)[4,5,6]方案都不安全.文獻(xiàn)[8]還提出了一個(gè)不使用雙線性對(duì)的無證書簽密方案，由于不使用雙線性對(duì)運(yùn)算，使得方案的運(yùn)算效率有較大提高，所以備受研究者的關(guān)注.朱輝等[9]和劉文浩等[10]也分別提出了不使用雙線性對(duì)的無證書簽密方案，都聲稱方案的安全性基于離散對(duì)數(shù)難解問題.但這些方案都被證明存在安全隱患[11-14]，都不能保障不可偽造性和機(jī)密性.

最近，高鍵鑫等[15]提出一種無雙線性對(duì)的無證書簽密方案.本文對(duì)文獻(xiàn)[15]方案的安全性進(jìn)行分析，指出方案不能抵抗公鑰替換攻擊，不滿足不可偽造性.本文給出了一種改進(jìn)方案，并證明了改進(jìn)方案在隨機(jī)預(yù)言模型下對(duì)自適應(yīng)選擇消息和身份攻擊是存在性不可偽造的，其安全性依賴于群G中的DLP的難解性.

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

1.1 離散對(duì)數(shù)問題

設(shè)G是階為素?cái)?shù)q的乘法群，g是G的一個(gè)生成元.下面考慮G中的離散對(duì)數(shù)問題和假設(shè).

1)離散對(duì)數(shù)問題(DLP)：對(duì)任意的yG，計(jì)算使得y=gx.

2)DLP假設(shè)：對(duì)任意的概率多項(xiàng)式時(shí)間算法A解決DLP的優(yōu)勢(shì)：

是可以忽略的.

1.2 無證書簽密系統(tǒng)的攻擊模型

無證書密碼系統(tǒng)中，公鑰由用戶自己生成，沒有公鑰證書認(rèn)證，所以非法攻擊者可以偽造替換合法用戶的公鑰.另一方面，私鑰生成中心擁有系統(tǒng)主密鑰，可以生成所有用戶的部分私鑰.所以，在無證書密碼系統(tǒng)中，攻擊者被分成兩類：第1類攻擊者AI沒有系統(tǒng)主密鑰，但可以替換用戶的公鑰；第2類攻擊者AII知道系統(tǒng)主密鑰，但是不可以替換用戶的公鑰.

在隨機(jī)預(yù)言模型下，無證書簽密方案的安全模型(機(jī)密性和不可偽造型)可以參看文獻(xiàn)[15]，在此不作贅述.

2 對(duì)文獻(xiàn)[15]方案的攻擊

2.1 方案回顧

(4)用戶公鑰生成.用戶計(jì)算uu=gzu，生成用戶公鑰對(duì)PKu=(wu,uu).

h=H2(m,R,IDa,ua,r2),

c=E((wbubyh1)r1,(r2,m))；

將消息m的簽密文σ=(h,s,c)發(fā)送給用戶B.

(6)解密驗(yàn)證.用戶B收到簽密文σ′=(h′,s′,c′)后，計(jì)算

則通過驗(yàn)證并接受消息m′.

2.2 公鑰替換攻擊

通過分析發(fā)現(xiàn)，高鍵鑫等[15]提出的無證書簽密方案不滿足不可偽造性，第1類攻擊者AI可以施行公鑰替換攻擊具體步驟如下：

(2)偽造攻擊.對(duì)于消息m*，攻擊者進(jìn)行以下操作：

3)計(jì)算h1=H1(IDb,wb)c*=E((wbubyh1)r1,(r2,m*))，

則σ*=(h*,s*,c*)是攻擊者AI冒充用戶A偽造的發(fā)給用戶B的簽密文.

上述偽造產(chǎn)生的簽密文σ*=(h*,s*,c*)可以解密并通過驗(yàn)證證明如下：

所以

(wbubyh1)r1=(gsbgzbyxh1)r1=g(sb+xH1(IDb,wb)+zb)r1=

g(tb+zb)r1=g(tb+zb)s*(δ+h*)=

表明加密密鑰與解密密鑰相等，用戶B可以正確解密獲得消息m*.

(2)攻擊者偽造的簽密文滿足可驗(yàn)證性.由于

(gδgh*)s*=g(δ+h*)s*=gr1=R,

所以

說明由偽造簽密文σ*=(h*,s*,c*)解密獲得的消息m*可以通過驗(yàn)證.

3 對(duì)文獻(xiàn)[15]方案的改進(jìn)

3.1 改進(jìn)方案描述

改進(jìn)方案的用戶部分密鑰生成、生成用戶私鑰和生成用戶公鑰環(huán)節(jié)與原方案相同，其他環(huán)節(jié)描述如下：

(2)簽密.用戶A執(zhí)行以下操作生成發(fā)送給用戶B的消息m的簽密文.

3)計(jì)算

h=H2(m,R,IDa,ua,r2),

4)用戶A發(fā)送簽密文σ=(h,s,c)給用戶B.

(3)解密驗(yàn)證.用戶B收到簽密文σ=(h,s,c)后，進(jìn)行以下操作：

3.2 改進(jìn)方案的正確性

g(sb+xH1(IDb,wb)+h2zb)r1=g(tb+h2zb)r1=

表明加密密鑰與解密密鑰相等，用戶B可以正確解密獲得消息m.

(2)驗(yàn)證簽密文的正確性.由于

所以

說明由簽密文σ=(h,s,c)解密獲得的消息m可以通過驗(yàn)證.

4 改進(jìn)方案的安全性分析

4.1 機(jī)密性

機(jī)密性即選擇密文攻擊下的不可區(qū)分性，其嚴(yán)格證明過程與文獻(xiàn)[15]相似，在此不作詳述，僅僅分析如下：

由于第I類攻擊者AI和第II類攻擊者AII都沒有用戶A和用戶B的完全私鑰，所以無法獲得加解密密鑰，不能完成對(duì)簽密文的解密，所以所提方案對(duì)選擇密文攻擊是不可區(qū)分的，即方案滿足機(jī)密性.

4.2 不可偽造性

定理1 在隨機(jī)預(yù)言模型下，改進(jìn)方案對(duì)第I類攻擊者AI的自適應(yīng)選擇消息和身份攻擊是存在性不可偽造的，其安全性依賴于群G中的DLP的難解性.

證明假設(shè)存在攻擊者AI能夠以不可忽略的概率偽造簽密，則DLP的挑戰(zhàn)者執(zhí)行如下步驟：

(1)系統(tǒng)初始化.

挑戰(zhàn)者首先生成系統(tǒng)公開參數(shù)params=(p,q,g,y,H1,H2,H3,E,D)，并發(fā)送給攻擊者AI.其中，y=ga是系統(tǒng)公鑰，即用a模擬系統(tǒng)主密鑰，但不知道a的值，其目標(biāo)是求解出a.

(2)詢問.

AI可適應(yīng)性地向進(jìn)行多項(xiàng)式有限次的詢問，維護(hù)表L1,L2,L3,LPK,LSC記錄并響應(yīng)AI的H1詢問，H2詢問，H3詢問，公鑰詢問和簽密詢問.選擇隨機(jī)整數(shù)n，記IDn=ID*.

5)部分私鑰詢問：對(duì)AI關(guān)于用戶IDi的部分私鑰詢問，若IDi=ID*，則挑戰(zhàn)失敗，算法終止；若IDi≠ID*，則從表L1中找出項(xiàng)(IDi,si,wi,ti,qi)，將ti作為IDi的部分私鑰返回給AI.

6)秘密值詢問：AI可以向詢問用戶IDi的秘密值.查找表LPK，若不含項(xiàng)(IDi,wi,ui,zi)，說明沒有進(jìn)行過關(guān)于IDi的公鑰詢問，首先執(zhí)行公鑰詢問；將zi返回給AI作為用戶IDi的秘密值.

r1=s(gaza+ta+h),

c=E(v,(r2,m)).

如果(m,gr1,IDa,ua,r2,h)已經(jīng)含于列表L2中，則重新選擇h,r1,r2，并將(m,gr1,IDa,ua,r2,h)加到列表L2；將(h,s,c)作為身份IDa對(duì)消息m的簽密返回給AI.

(3)偽造.

如果算法沒有停止，則AI在沒有詢問過(ID*,m)的簽密和ID*的部分私鑰的前提下，偽造了用戶ID*對(duì)消息m的簽密(ID*,IDb,h,s,c).由Forking引理[16]可知，重放H2詢問，可以得到(ID*,IDb,m)的兩個(gè)有效簽密：

(ID*,IDb,h,s,c), (ID*,IDb,h′,s′,c)，

其中h≠h′，且

s(gID*zID*+tID*+h)=s′(gID*zID*+tID*+h′)，

其中tID*=sID*+a·qID*，可以解出

gID*zID*-sID*)，

即挑戰(zhàn)者獲得了DLP的解.

所以，在DLP困難的假設(shè)下，攻擊者AI不能成功偽造簽密，即所提改進(jìn)方案可以抵抗第I類攻擊者AI的自適應(yīng)選擇消息和身份下的存在性偽造攻擊.證畢.

定理1也說明了改進(jìn)方案可以抵抗第I類攻擊者的公鑰替換攻擊.

定理2 在隨機(jī)預(yù)言模型下，改進(jìn)方案對(duì)第II類攻擊者AII的自適應(yīng)選擇消息和身份攻擊是存在性不可偽造的，其安全性依賴于群G中的DLP的難解性.

證明假設(shè)存在攻擊者AII能夠以不可忽略的概率偽造簽密，則DLP的挑戰(zhàn)者執(zhí)行如下步驟：

(1)系統(tǒng)初始化.

(2)詢問.

AII可適應(yīng)性地向進(jìn)行多項(xiàng)式有限次的詢問.隨機(jī)選擇整數(shù)n，記IDn=ID*.H2詢問、H3詢問以及簽密詢問與定理1的證明相同.

3)部分私鑰詢問：AII可以向詢問用戶IDi的部分私鑰.從列表L1中找出項(xiàng)(IDi,si,wi,ti,qi)，將ti作為IDi的部分私鑰返回給AII.

4)秘密值詢問：對(duì)AII關(guān)于IDi的秘密值詢問，如果IDi=ID*，宣告失敗，算法終止；否則，即IDi≠ID*，查找表LPK，若不含項(xiàng)(IDi,wi,ui,zi)，說明沒有進(jìn)行過關(guān)于IDi的公鑰詢問，首先執(zhí)行公鑰詢問將zi返回給AII作為用戶IDi的秘密值.

(3)偽造.

如果算法沒有停止，則AII在沒有詢問過(ID*,m)的簽密和ID*的秘密值的前提下，成功偽造用戶ID*對(duì)消息m的簽密(ID*,IDb,h,s,c).由Forking引理[16]可知，重放H2詢問，可以得到(ID*,IDb,m)的兩個(gè)有效簽密

(ID*,IDb,h,s,c), (ID*,IDb,h′,s′,c)，

其中h≠h′，且

s(gID*zID*+tID*+h)=s′(gID*zID*+tID*+h′)，

可以解出

即挑戰(zhàn)者獲得了DLP的解.

所以，在DLP困難的假設(shè)下，攻擊者AII不能偽造簽密，即所提改進(jìn)方案可以抵抗第II類攻擊者AII的自適應(yīng)選擇消息和身份下的存在性偽造攻擊.證畢.

5 結(jié)語

對(duì)高鍵鑫等人[15]提出的無雙線性對(duì)的無證書簽密方案進(jìn)行了密碼攻擊，發(fā)現(xiàn)方案不能抵抗公鑰替換攻擊.為了消除這種安全缺陷，提出了一種改進(jìn)方案.安全性證明顯示改進(jìn)方案對(duì)兩類攻擊者的自適應(yīng)選擇消息和身份攻擊是存在性不可偽造的，有效地抵抗了公鑰替換攻擊.同時(shí)，改進(jìn)方案仍然沒有使用計(jì)算耗時(shí)的對(duì)運(yùn)算，具有較高的運(yùn)算效率.