改進(jìn)的基于身份的簽密方案

湯鵬志，郭紅麗，張婷婷

(華東交通大學(xué) 系統(tǒng)工程與密碼學(xué)研究所，南昌 330013)

簽密能夠同時(shí)實(shí)現(xiàn)簽名和加密，大大提高了消息的安全性和計(jì)算效率。1984 年，Shamir［1］使用用戶的身份(電子郵箱或者郵政地址等)作為公鑰，提出基于身份的密碼體制。2002 年，Malone－Lee［2］提出了基于身份的簽密方案，但Libert 和Quisquater［3］指出該方案不滿足語(yǔ)義安全性。2005 年，Chen 和Malone－Lee［4］提出了效率比較高的基于身份的簽密方案，但該方案既不滿足公開(kāi)驗(yàn)證性，也不滿足數(shù)據(jù)的完備性。李發(fā)根等［5］提出了一個(gè)新的效率比較高的基于身份的簽密。近幾年，基于身份的簽密方案在理論上和應(yīng)用上都取得了很大的進(jìn)步。［6－8］可對(duì)文獻(xiàn)［9］進(jìn)行選擇性明文攻擊，由此提出一個(gè)安全高效的改進(jìn)的基于身份的簽密方案。

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

1.1 雙線性對(duì) 設(shè)G1是生成元為P 的q 階的加法循環(huán)群，G2是生成元為P 的q 階的乘法循環(huán)群，映射e:G1×G1→G2是一個(gè)雙線性對(duì)，滿足下列性質(zhì):(1)雙線性性:對(duì) U，V ∈G1，a，b ∈，有e(aU，bV)= e(U，V)ab。

(2)非退化性:-U，V ∈G1，使得e(U，V)≠1。

(3)實(shí)效性:對(duì) U，V ∈G1，e(U，V)是有效且可計(jì)算的。

1.2 (CBDHP) 已知P，aP，bP，cP ∈G1，計(jì)算e(P，P)abc∈G2。

1.3 (DBDHP) 已知P 為G1的生成元，給定a，b，c ∈，P，aP，bP，cP ∈G1，h ∈G2，判定h =e(P，P)abc是否成立。

1.4 (DLP) 對(duì) P，Q ∈G，已知P，Q，求a，使得Q = aP。

2 簽密方案的安全性定義

簽密方案的機(jī)密性和不可偽造性可定義為:

定義1 機(jī)密性。［10，11］若在適應(yīng)性選擇密文攻擊下的消息，基于身份的簽密方案具有不可區(qū)分性(IND－IBSC－CCA2)。則沒(méi)有PPT 時(shí)間內(nèi)的攻擊者，具備不可忽視的優(yōu)勢(shì)贏得以下定義的游戲的優(yōu)勢(shì)(IND－IBSC－GAME)的能力。游戲的步驟為:

(1)系統(tǒng)建立。挑戰(zhàn)者C 輸入?yún)?shù)k，執(zhí)行方案中的系統(tǒng)建立的算法。將得到的系統(tǒng)參數(shù)發(fā)送給攻擊者A。

(2)詢問(wèn)1。攻擊者A 執(zhí)行如下詢問(wèn):

1)密鑰詢問(wèn)。攻擊者A 選擇IDU發(fā)送給挑戰(zhàn)者C，C 計(jì)算SU= extract(IDU)。將計(jì)算得到的密鑰發(fā)送給攻擊者A。

2)簽密詢問(wèn)。攻擊者A 將選擇的IDA、IDB和明文消息m 發(fā)送給挑戰(zhàn)者C。挑戰(zhàn)者C 執(zhí)行簽密算法計(jì)算σ = signcrypt(m，SA，IDB)。將得到的σ 發(fā)送給攻擊者A。

3)解簽密詢問(wèn)。攻擊者A 將選擇的IDA、IDB和密文消息σ 發(fā)送給挑戰(zhàn)者C。挑戰(zhàn)者C 執(zhí)行解簽密算法計(jì)算SB= extract(IDB)和m = unsigncrypt(σ，IDA，SB)，并將得到的m 或者“⊥”發(fā)送給攻擊者A。

4)挑戰(zhàn)。攻擊者A 產(chǎn)生明文m0、m1和打算挑戰(zhàn)的IDi和IDj。IDj沒(méi)有執(zhí)行過(guò)的密鑰詢問(wèn)。C 隨機(jī)選擇u ∈{0，1}，計(jì)算σ = signcrypt(mu，Si，IDj)，并將σ 發(fā)送給攻擊者A。

5)詢問(wèn)2。攻擊者A 執(zhí)行多項(xiàng)式有界次類似于(2)的詢問(wèn)。但攻擊者A 不能對(duì)目標(biāo)用戶IDj和目標(biāo)密文σ 執(zhí)行詢問(wèn)。

6)猜測(cè)。攻擊者A 輸出u'。若u' = u，則攻擊者A 贏得此游戲。

定義2 不可偽造性。［10，11］在適應(yīng)性選擇消息和身份攻擊下，基于身份的簽密方案是存在性不可偽造的(EUF－IBSC－CMIA)。則沒(méi)有PPT 時(shí)間的攻擊者，具備不可忽視的優(yōu)勢(shì)贏得以下定義的游戲(EUF－IBSC－GAME)的能力。游戲的步驟為:

a)系統(tǒng)建立。挑戰(zhàn)者C 輸入?yún)?shù)k，執(zhí)行方案中的系統(tǒng)建立的算法，并將得到的系統(tǒng)參數(shù)發(fā)送給攻擊者A。

b)詢問(wèn)。攻擊者A 執(zhí)行類似于定義1 的詢問(wèn)。

c)偽造。最后，攻擊者A 生成新的三元組(σ'，IDA，IDB)，且(σ'，IDA，IDB)不是在尋找階段的密鑰提取預(yù)言機(jī)和簽密預(yù)言機(jī)輸出的。若unsigncrypt(σ'，SB，IDA)≠⊥，則攻擊者A 贏得以上的游戲。

3 原方案分析

原方案請(qǐng)參照文獻(xiàn)［9］，原方案不具有語(yǔ)義安全性，可以實(shí)施不可區(qū)分性明文攻擊。

假設(shè)攻擊者A 選擇明文m0，m1，C 隨機(jī)選擇mi，i ∈{0，1}。經(jīng)過(guò)簽密算法產(chǎn)生一個(gè)密文消息σ*= (C*，T*，Z*，V*)，然后A 計(jì)算h*= H3(m0|| B|| Z*|| IDr|| IDs)，最后驗(yàn)證e(V，Ppub+dIDsP)與Z*Yh*是否相等。若相等，則σ*是m0對(duì)應(yīng)的簽密密文;若不相等，則σ*是m1對(duì)應(yīng)的簽密密文。因此此方案不具有語(yǔ)義安全性。

4 原文獻(xiàn)［9］方案的改進(jìn)

為了抵抗選擇明文攻擊，本文改進(jìn)了文獻(xiàn)［10］的方案，提出改進(jìn)的基于身份的簽密方案。系統(tǒng)建立大部分參考原方案，其中修改的部分為:將原方案的系統(tǒng)主密鑰改為s，不需要哈希函數(shù)H3。下面為密鑰生成、簽密與解簽密:

(1)密鑰生成:QID= H1(ID)，公鑰為dID=sQID，私鑰為并通過(guò)秘密信道將SID傳給使用者。

(2)簽密:假設(shè)IDA為發(fā)送者，IDB為接收者，M 為所要簽密的明文，IDA執(zhí)行以下步驟:

步驟1:隨機(jī)選擇t ∈Z*q ，計(jì)算T = t(Ppub+dIDBP)，Z = Yt，C= H2(Z)⊕M。

步驟2:計(jì)算V= tSIDA，輸出密文σ= (C，V，T)。

(3)解簽密

接收者IDB收到密文σ = (C，V，T)，IDB執(zhí)行以下步驟:

步驟1:計(jì)算B = e(T，SIDB)，M = H2(B)⊕C。

步驟2:檢查e(V，Ppub+ dIDAP)= Z 是否成立，如果不成立，輸出⊥;如果成立，則接受σ 為有效密文。

算法的正確性通過(guò)以下兩個(gè)式子檢驗(yàn):

(1)驗(yàn)證簽密數(shù)據(jù)的有效性:

(2)驗(yàn)證消息的正確性

5 改進(jìn)的簽密方案的安全性分析和證明

假設(shè)哈希函數(shù)H1、H2為隨機(jī)預(yù)言機(jī)。攻擊者A在PPT 時(shí)間內(nèi)對(duì)挑戰(zhàn)者Q 執(zhí)行有限次H1詢問(wèn)、H2詢問(wèn)、公鑰詢問(wèn)、私鑰詢問(wèn)、簽密詢問(wèn)和解簽密詢問(wèn)，列表L1、L2、LPK、LSK、LS、LU，用于記錄對(duì)應(yīng)的每次詢問(wèn)的情況，q1、q2、qK、qS、qU表示對(duì)應(yīng)的詢問(wèn)次數(shù)。

5.1 機(jī)密性

在隨機(jī)預(yù)言機(jī)模型和DLP 困難問(wèn)題下，如果敵手A 能在時(shí)間t 內(nèi)以一個(gè)不可忽略的優(yōu)勢(shì)ε 贏得上述IND－IBSC 游戲，那么存在算法Q 在PPT 時(shí)間內(nèi)解決DBDHP。

證明:設(shè)算法Q 能夠解決DBDHP，即輸入(P，aP，bP，cP)和ξ，隨機(jī)選取a，b，c ∈Z*q ，判斷ξ =e(P，P)abc是否成立。

(1)系統(tǒng)參數(shù)設(shè)置:挑戰(zhàn)者Q 生成系統(tǒng)參數(shù)params = {G1，G2，e，P，Ppub，Y，H1，H2}，將系統(tǒng)參數(shù)發(fā)送給敵手A;設(shè)系統(tǒng)公鑰為Ppub= ap，a (未知)為系統(tǒng)主密鑰;目標(biāo)用戶為IDk。

(2)詢問(wèn)

1)哈希詢問(wèn)

H1詢問(wèn):挑戰(zhàn)者Q 收到攻擊者A 關(guān)于(IDi，QIDi)的H1詢問(wèn)時(shí)，當(dāng)i ≠k 時(shí)，Q 首先查詢列表L1，如果(IDi，QIDi)在列表L1中，則Q 將QIDi返回給A，否則，Q 隨機(jī)選擇QIDi∈Z*q ，計(jì)算并將其作為回答返回給A，并將(IDi，QIDi)添加列表L1;當(dāng)i = k時(shí)，設(shè)置Qk= H1(IDk)= dP。

H2詢問(wèn):當(dāng)挑戰(zhàn)者Q 收到攻擊者A 關(guān)于(ti，Zi，h2i)的H2詢問(wèn)時(shí)，Q 首先查詢列表L2，如果(ti，Zi，h2i)在列表L2中，則Q 將h2i返回給A;否則，Q隨機(jī)選擇h2i∈Z*q ，并將其作為回答返回給A，并將(ti，Zi，h2i)添加列表L1。

2)公鑰詢問(wèn)

當(dāng)挑戰(zhàn)者Q 收到攻擊者A 關(guān)于(IDi，QIDi，dIDi)的公鑰詢問(wèn)時(shí)，Q 首先查詢列表LPK，如果(IDi，QIDi，dIDi)在列表LPK中，則Q 將dIDi返回給A;否則，C 隨機(jī)選擇QIDi∈Z*q ，計(jì)算dIDi= aQIDi，并將dIDi作為回答返回給A，并將(IDi，QIDi，dIDi)添加列表LPK。

3)私鑰詢問(wèn)

當(dāng)挑戰(zhàn)者Q 收到攻擊者A 關(guān)于(IDi，SIDi)的私鑰詢問(wèn)時(shí)，Q 首先查詢列表LSK，如果(IDi，SIDi)在列表LSK中，則Q 將SIDi返回給A;否則:

(a)當(dāng)i = k 時(shí)，終止算法;

(b)當(dāng)i ≠k 時(shí)，Q 先執(zhí)行H1詢問(wèn)得到QIDi，計(jì)算將獲得的SIDi作為答復(fù)發(fā)送給A1，并將(IDi，SIDi)記錄到列表LSK中。

4)簽密詢問(wèn)

當(dāng)挑戰(zhàn)者Q 收到攻擊者A 關(guān)于(IDi，IDj)和Mi的簽密詢問(wèn)時(shí)，Q 首先檢查列表LS，如果(IDi，IDj，Zi，Mi，Ci，Vi，Ti)已經(jīng)在列表中，則將相應(yīng)的簽密數(shù)據(jù)發(fā)送給A;否則:

(a)當(dāng)i ≠k 時(shí)，Q 先執(zhí)行H1詢問(wèn)和H2詢問(wèn)，得到QIDi、h2i，再查詢列表LPK、LSK，隨機(jī)選擇t∈，計(jì)算Ti= t(Ppub+ dIDiP)，Zi= Yt，Ci=H2(Zi)⊕M，得到密文σi= (Ci，Vi，Ti)，將密文發(fā)送給攻擊者A，并將(IDi，IDj，Zi，Mi，Ci，Vi，Ti)添加到列表LS。

(b)當(dāng)i = k 時(shí)，Q 隨機(jī)選取Vk，Tk∈Z*q ，計(jì)算Zk= e(Vk，Ppub+dIDkP)，將(Vk，Tk)作為目標(biāo)用戶的簽名，計(jì)算Zk= e(Vk，Ppub+dIDkP)= e(P，P)t，通過(guò)查詢列表L2，得到h2i，計(jì)算Ck= h2i⊕Mi，將簽密數(shù)據(jù)(Ck，Vk，Tk)發(fā)送給A。

5)解簽密詢問(wèn)

當(dāng)挑戰(zhàn)者Q 收到攻擊者A 關(guān)于(IDi，IDj)的簽密數(shù)據(jù)σi= (Ci，Vi，Ti)時(shí)，查詢列表LU，如果(Ci，Vi，Ti)已經(jīng)存在于列表LU中，則返回Mi給Q，否則:

(a)當(dāng)j = k 時(shí)，算法終止，拒絕輸出消息M;

(b)當(dāng)j ≠k 時(shí)，Q 根據(jù)簽密者的身份從列表L2得到h2i，從列表LPK中查詢得到dIDi，從LS中得到Zi，計(jì)算e(Vi，Ppub+ dIDiP)= Zi是否成立，如果不成立，則拒絕接受簽密數(shù)據(jù)σi= (Ci，Vi，Ti);否則，根據(jù)從列表LS中得到Ti，計(jì)算Bj=e(Ti，SIDj)，再根據(jù)Bj查詢列表L2得到的h2j，然后計(jì)算M = h2j⊕Cj，最后將得到的明文消息M 發(fā)送給攻擊者A。

(3)挑戰(zhàn)

A 隨機(jī)選擇兩個(gè)希望挑戰(zhàn)的身份(IDi，IDj)和兩個(gè)明文M0、M1，當(dāng)j ≠k，Q 終止挑戰(zhàn);當(dāng)j = k時(shí)，Ppub= uP，Q 查詢列表L1、L2，得到(IDi，QIDi)、(ti，Zi，h2i)，計(jì)算SA= bP，隨機(jī)選擇c ∈Z*

(4)詢問(wèn)2。敵手A 繼續(xù)執(zhí)行類似于(2)的詢問(wèn)。但是不能對(duì)IDB和σ*執(zhí)行密鑰詢問(wèn)和解簽密詢問(wèn)。

(5)猜測(cè)。兩次詢問(wèn)結(jié)束后，如果敵手可以得到p' = p，則挑戰(zhàn)者Q 輸出ξ = e(Ti，SIDj)= e(a(u +ud)P，bP)= e(P，P)a(u+ud)b，即解決了DBDHP。

5.2 不可偽造性

定理2 在隨機(jī)預(yù)言機(jī)模型下，基于DLP，對(duì)于敵手A，本方案在IND－IBSC 攻擊下是存在性不可偽造的。

證明:算法B 能解決DLP 問(wèn)題，即輸入y =xP，輸出x。

系統(tǒng)設(shè)置。算法Q 生成系統(tǒng)參數(shù)params ={G1，G2，e，P，Ppub，Y，H1，H2}，其中Ppub= aP (a為系統(tǒng)主密鑰)。

詢問(wèn)。A 向Q 執(zhí)行多項(xiàng)式有界次詢問(wèn)，詢問(wèn)過(guò)程和定理1 相同。

由上述過(guò)程可知，A 通過(guò)向Q 進(jìn)行多項(xiàng)式有限次詢問(wèn)后，解決了DLP，但是這與DLP 的困難性矛盾，所以在隨機(jī)預(yù)言機(jī)模型和DLP 困難性的假設(shè)下，該方案是存在性不可偽造的。

6 總結(jié)

在基于身份的簽密中，降低計(jì)算成本，提高計(jì)算效率是人們關(guān)心的話題。本方案比原方案少了一個(gè)哈希運(yùn)算，且在隨機(jī)預(yù)言機(jī)模型下，滿足機(jī)密性和不可偽造性。

［1］ Shamir A.Identity－based cryptosystems and signature schemes［C］//Advances in Cryptology－Crypto’84，LNCS 196.Berlin:Springer－Verlag，1984:47－53.

［2］ Malone－Lee J.Identity based signcryption ［EB/OL］.Cryptology ePrint Archive，Report 2002/098，2002.http://eprint.iacr.org/2002/098.2011－6－2.

［3］ Libert B，Quisquater J.A new identity based signcryption scheme from pairings［C］.The IEEE Information Theory Workshop (ITW’2003)，Pairs，2003:155－158.

［4］ L.Chen and J.Malone－Lee.Improved identity－based signcryption.Public Key Cryptography－PKC 2005［C］，Berlin:Spring－Verlag，2005:362－379.

［5］李發(fā)根，胡予濮，李剛. 一個(gè)高效的基于身份的簽密方案［J］. 計(jì)算機(jī)學(xué)報(bào)，2006，29(9):1641－1647.

［6］張明武，楊波，周敏，等. 基于身份的公開(kāi)驗(yàn)證簽密方案［J］. 計(jì)算機(jī)應(yīng)用，2012，32(1):99－103.

［7］肖鴻飛，劉長(zhǎng)江. 一種基于身份的改進(jìn)高效簽密方案［J］. 計(jì)算機(jī)工程，2011，37(24):126－128.

［8］周才學(xué)，周頑，胡日新，等. 基于身份的簽密方案分析與改進(jìn)［J］. 計(jì)算機(jī)工程，2012，38(2):132－134.

［9］鄧倫治，王祥斌，瞿云云. 高效的基于身份的簽密方案［J］. 計(jì)算機(jī)工程與科學(xué)，2014，36(3):441－445.

［10］LIBERT B，QUISQUATER J.A new identity based signcryption schemes from pairings［C］//Proc of IEEE Information Theory Workshop，2003:155－158.

［11］何俊杰，焦淑云，祁傳達(dá). 一個(gè)基于身份的簽密方案的分析與改進(jìn)［J］. 計(jì)算機(jī)應(yīng)用研究，2013，30(3):913－920.