基于RSA的可截取簽名改進(jìn)方案

李 旭，杜小妮，王彩芬，鄭亞紅，張 記

1.西北師范大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，蘭州 730070

2.西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，蘭州 730070

基于RSA的可截取簽名改進(jìn)方案

李 旭1，杜小妮2，王彩芬1，鄭亞紅1，張 記1

1.西北師范大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，蘭州 730070

2.西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，蘭州 730070

1 準(zhǔn)備知識(shí)

可截取簽名[1]（Content Extraction Signatures，CES）允許在多方參與的環(huán)境下，給定一個(gè)已簽名的消息，使用者針對(duì)原消息的一部分，截取一個(gè)公開并可驗(yàn)證的簽名，而無(wú)需和最初的簽名者交互。簽名者對(duì)包括k個(gè)子消息的信息簽名。截取者按簽名者給定的規(guī)則截取部分信息M′，計(jì)算出截取消息M′的簽名，并把所截取消息及其簽名提供給相關(guān)的驗(yàn)證者。驗(yàn)證者驗(yàn)證M′簽名的真實(shí)性。其流程圖如圖1所示。

圖1 可截取簽名流程圖

與傳統(tǒng)的數(shù)字簽名方案[2-3]相比，可截取簽名解決了在多方參與的環(huán)境下，消息從簽名者到使用者再到驗(yàn)證者之間多次傳遞、簽名、驗(yàn)證所導(dǎo)致的安全隱患以及計(jì)算和存儲(chǔ)開銷大，不便于實(shí)際操作的問(wèn)題，在保證消息合法截取的同時(shí)，有效地實(shí)現(xiàn)了對(duì)消息的多次傳遞和驗(yàn)證[4]。鑒于這些優(yōu)點(diǎn)，可截取簽名受到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。文獻(xiàn)[5]在XML簽名規(guī)范中引入可截取簽名方法，對(duì)XML簽名[6]進(jìn)行了擴(kuò)展。文獻(xiàn)[7]在文獻(xiàn)[1]的基礎(chǔ)上，提出采用分級(jí)群組策略的可截取簽名方案，可有效地應(yīng)用于數(shù)字圖書館等環(huán)境。

批簽名[8-10]允許用戶對(duì)一批數(shù)據(jù)進(jìn)行統(tǒng)一簽名，統(tǒng)一驗(yàn)證，從而提高了簽名和驗(yàn)證效率。文獻(xiàn)[8]提出了基于二叉樹的Bi-tree批簽名方案，可以把普通的簽名算法改造成批簽名。

本文以文獻(xiàn)[1]中的可截取簽名方案為基礎(chǔ)，結(jié)合批簽名思想，提出了一種新的基于RSA的可截取簽名方案。解決了現(xiàn)有方案存在的消息截取后版式凌亂的問(wèn)題，使截取后的消息更加緊湊，符合人的正常閱讀習(xí)慣，縮短簽名和驗(yàn)證的時(shí)間消耗。

2 現(xiàn)有的可截取簽名方案

假設(shè)消息M被分成n個(gè)子消息段，即M={m1,m2,…, mn}，定義子消息編號(hào)集合Γ={1，2，…，n}。M′為用戶截取的子消息集合，共n個(gè)子消息段，其中未選的子消息段標(biāo)記為空白。截取子集CI(M′)標(biāo)記M′中選中的子消息段的編號(hào)。為了使簽名者對(duì)原消息的截取方式具有完全控制權(quán)，引入內(nèi)容截取訪問(wèn)結(jié)構(gòu)CEAS?Γ，CEAS定義為子消息編號(hào)的集合，并規(guī)定每個(gè)在CEAS中的子消息都為必選消息。例如，M={m1，m2，m3，m4}，CEAS={1}，若CI(M′)={1，3}，則 M′={m1，?，m3，?}，其中?標(biāo)記空白子消息段，則截取方式合法[1，11]，記為CEAS?CI(M′)；若CI(M′)={2，3}，M′={?，m2，m3，?}，若CEAS?CI(M′)，截取方式非法。

可截取簽名體制由以下四個(gè)步驟構(gòu)成：

（1）密鑰生成

生成RSA公、私鑰對(duì)PK=(N，e)、SK=(N，e，d)。

（2）簽名

①簽名者給出截取訪問(wèn)結(jié)構(gòu)CEAS，同時(shí)給出一個(gè)隨機(jī)產(chǎn)生的固定長(zhǎng)度的CES標(biāo)記T。

②對(duì)每個(gè)i∈CEAS，計(jì)算：

（3）簽名截取

①根據(jù)原消息M和簽名者指定的截取訪問(wèn)結(jié)構(gòu)CEAS，截取者給出截取子集CI(M′)。

②根據(jù)截取子集CI(M′)，生成截取消息M′={Mi|i∈CI(M′)}。

③對(duì)每個(gè)i∈CI(M′)計(jì)算：

δ=∏i∈CI(M′)δ[i]modN

④返回截取簽名δExt=(CEAS||T||δ||CI(M′))。

（4）簽名驗(yàn)證

①驗(yàn)證者首先驗(yàn)證CEAS?CI(M′)，如未通過(guò)，直接返回驗(yàn)證失敗。

②對(duì)每個(gè)i∈CI(M′)對(duì)應(yīng)的子消息，分別計(jì)算：

③驗(yàn)證δe=∏i∈CI(M′)h[i]modN，如未通過(guò)，返回驗(yàn)證失敗，否則返回驗(yàn)證成功。

上述方案雖然實(shí)現(xiàn)了原始消息的可截取功能，但在消息截取時(shí)，由于將不在CI(M′)中的子消息段標(biāo)記為空白，從而導(dǎo)致截取消息顯示時(shí)出現(xiàn)大面積空白，不符合一般閱讀習(xí)慣。

3 改進(jìn)的可截取簽名方案

3.1方案描述

該方案在文獻(xiàn)[1]提出的基于RSA的可截取簽名方案的基礎(chǔ)上，引入批簽名的思想，改進(jìn)了簽名和認(rèn)證部分。方案具體步驟如下：

（1）密鑰生成GK(k)

①隨機(jī)選擇兩個(gè)長(zhǎng)度為k/2的大素?cái)?shù) p和q。

②令N=p×q，Φ(N)=(p-1)×(q-1)。

③隨機(jī)選擇整數(shù)e，滿足gcd(e，Φ(N))=1，計(jì)算d≡e-1modΦ(N)。

④最后返回公鑰PK=(N，e)，私鑰SK=(N，e，d)。

（2）原消息簽名生成SIG(SK，M，CEAS)

對(duì)于長(zhǎng)度為n的原消息M，

①簽名者給出截取訪問(wèn)結(jié)構(gòu)CEAS，同時(shí)給出一個(gè)隨機(jī)產(chǎn)生的固定長(zhǎng)度的CES標(biāo)記T。

②對(duì)CEAS對(duì)應(yīng)的所有消息，構(gòu)造必選消息批簽名樹hT-batch與簽名指數(shù)dbatch，并對(duì)hT-batch進(jìn)行批簽名：

③對(duì)每個(gè)i∈ΓCEAS，計(jì)算：

（3）消息截取EXT(PK，M，CEAS，δFULL，X)

①根據(jù)原消息M和簽名者指定的截取訪問(wèn)結(jié)構(gòu)CEAS，截取者給出截取子集CI(M′)。

②根據(jù)截取子集CI(M′)，生成截取消息M′={Mi|i∈CI(M′)}。

③對(duì)每個(gè)i∈CI(M′)且i?CEAS，計(jì)算：

δ=∏i∈Xδ[i]modN

④返回截取簽名δExt=(CEAS||T||δ||δbatch||CI(M′))。

（4）驗(yàn)證VER(PK，M′，δExt)

①驗(yàn)證者首先驗(yàn)證CEAS?CI(M′)，如未通過(guò)，直接返回驗(yàn)證失敗。

②對(duì)必選消息hT-batch進(jìn)行批驗(yàn)證[6-7]，取批驗(yàn)證公鑰為ebatch：

③對(duì)每個(gè)i∈CI(M′)且i?CEAS對(duì)應(yīng)的子消息，分別計(jì)算：

h[i]=H(CEAS||T||M′[i])

④驗(yàn)證δe=∏i∈CI(M′)h[i]modN，如未通過(guò)，返回驗(yàn)證失敗，否則返回驗(yàn)證成功。

3.2 方案正確性分析

對(duì)截取文檔的簽名進(jìn)行驗(yàn)證，可得到：

3.3 方案可靠性分析

依據(jù)文獻(xiàn)[1]，本文所提出的方案在隨機(jī)預(yù)言機(jī)模型下，能夠抵抗適應(yīng)性選擇消息攻擊和身份偽造攻擊。更進(jìn)一步地，有

（1）如果RSA簽名的全域Hash函數(shù)m→H(m)d在選擇明文攻擊下具有不可偽造性，并且CES標(biāo)記T在簽名算法中不重用，則該方案具有不可偽造性。

（2）必選部分批簽名和批驗(yàn)證的可靠性由文獻(xiàn)[8]給出。

（3）在可截取簽名體制中，截取者是不可信的。截取者可能執(zhí)行以下操作：

①截取者對(duì)M按CEAS的截取規(guī)則進(jìn)行截取，得到M′，M′可通過(guò)驗(yàn)證。

②截取者將CEAS中某個(gè)（或多個(gè)）標(biāo)記為必選的部分截掉后得到M1'，則CEAS?CI(M1')，驗(yàn)證失敗。

③截取者按照CEAS截取規(guī)則進(jìn)行截取得到M2'，然后將M2'的某些消息mi篡改為mi'得到M2"，則驗(yàn)證時(shí)H(CEAS||T||mi)≠H(CEAS||T||mi')，即

驗(yàn)證失敗。

④截取者按照CEAS截取規(guī)則進(jìn)行截取得到M3'，然后在M3'后面追加k條消息mi得到M3"，則驗(yàn)證時(shí)有：

驗(yàn)證失敗。

3.4 性能分析

現(xiàn)有方案在設(shè)定CEAS和CI(M′)時(shí)，采用空白來(lái)標(biāo)記截取段落，并由此判定驗(yàn)證條件CEAS?CI(M′)是否滿足，導(dǎo)致截取后文檔出現(xiàn)大面積留白，不符合正常閱讀習(xí)慣。新方案改進(jìn)了CI(M′)的結(jié)構(gòu)，使系統(tǒng)在驗(yàn)證階段僅通過(guò)M′與CI(M′)的對(duì)應(yīng)關(guān)系就能判斷截取文檔是否滿足CEAS?CI(M′)，由此避免了文檔留白現(xiàn)象。

假設(shè)原消息 M={m1，m2，m3，m4，m5，m6，m7，m8}，截取結(jié)構(gòu)CEAS={1，3}，截取子集CI(M′)={1，3，8}，兩方案截取后的顯示效果如圖2到圖4所示。

圖2 截取前的原始文檔

3.5 復(fù)雜度分析

本節(jié)對(duì)兩種簽名方案的執(zhí)行效率進(jìn)行分析。符號(hào)說(shuō)明如表1所示。

兩種方案的效率比較見表2。

表1 符號(hào)說(shuō)明

表2 兩種方案效率比較

圖3 現(xiàn)有方案的截取效果

圖4 改進(jìn)方案的截取效果

從表2可以看出，由于采用了批簽名的思想，新方案在簽名和截取時(shí)，將現(xiàn)有方案中必選部分的mCEAS次簽名時(shí)間THA(lR)+TSRSA和驗(yàn)證時(shí)間TMRSUALL+THA(lR)+TVRSA簡(jiǎn)化為一次批簽名時(shí)間TB-S和批驗(yàn)證時(shí)間TB-V，因而提高了算法的效率。

4 結(jié)論

本文針對(duì)現(xiàn)有可截取簽名體制的普遍缺陷，結(jié)合批簽名思想，提出了一種基于RSA體制的可截取簽名改進(jìn)方案，在保證方案正確性和安全性的前提下解決了截取文檔大面積空白的缺陷，使截取后的文檔更符合人的正常閱讀習(xí)慣，而且提高了簽名效率。新方案在電子商務(wù)和電子政務(wù)系統(tǒng)中有更高的實(shí)用價(jià)值。

[1]Steinfeld R，Bull L，Zheng Y L.Content extraction signatures[C]//Information Security and Cryptology（ICISC 2001），2002.

[2]Rivest R，Shamir A，Adleman L.A method for obtaining digital signatures and public key cryptosystem[J].Communications of the ACM，1978，21（2）：120-126.

[3]Li Jin，Zhang Fangguo.Generic security-amplifying methods of ordinary digital signatures[J].Information Sciences，2012，201（15）：128-139.

[4]李新，張繼東，孫玉芳.簽名加密技術(shù)在公文系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2004，21（4）：98-99.

[5]Song F，Cui Z.Electronic voting scheme about ElGamal blind-signatures based on XML[J].Procedia Engineering，2012，29：2721-2725.

[6]謝鉉洋，謝榮傳.XML數(shù)字簽名[J].計(jì)算機(jī)應(yīng)用研究，2002（7）：92-94.

[7]Bull L，Mcg S R D，Zheng Y.A hierarchical extraction policy for content extraction signatures[J].International Journal on Digital Libraries，2004，4（3）：208-222.

[8]FIATA.Batch RSA[J].Journal of Cryptology，1997，10（2）：75-88.

[9]Hwang M S，Chang T Y，Yang W P.The batch verifying multiple digital signature scheme：a modified version of Ohta-Okamoto digital signature[C]//Computing Technology and Information Management，Gold Coast，Australia，2012：732-735.

[10]Chou Cheng-Fu，Cheng William C，Golubchik L.Performance study of online batch-based digital signature schemes[J].Journal of Network and Computer Applications，2010，33（2）：98-114.

[11]劉軍龍，王彩芬.基于身份的可截取的門限簽名方案[J].計(jì)算機(jī)應(yīng)用，2006，26（8）：1817-1820.

LI Xu1,DU Xiaoni2,WANG Caifen1,ZHENG Yahong1,ZHANG Ji1

1.College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China
2.College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,China

Content Extraction Signatures（CES）improve the efficiency of multiparty interaction and resolve the problem of multiple signature and communication.Documents’format becomes messy after messages extraction in the traditional CES scheme.To solve this problem,based on RSA,combining the batch signature idea,this paper promotes a new CES scheme and analyses the effects of the extractor’s behaviors to the verification of signature.Compared with the traditional CES,the new scheme optimizes the structure of the extracted document and improves the signature efficiency without reducing the security performance.

RSA;Content Extraction Signatures（CES）;batch signatures;context extraction access structure;chosenplaintext attack

在多方參與的簽名環(huán)境中，可截取簽名體制（CES）解決了信息的多次簽名和多次傳遞等問(wèn)題。對(duì)現(xiàn)有CES方案進(jìn)行了分析，發(fā)現(xiàn)現(xiàn)有方案截取后的文檔存在版式凌亂的缺陷。針對(duì)該缺陷，結(jié)合批簽名思想，提出了一種基于RSA的可截取簽名改進(jìn)方案，并分析了截取者的各種行為對(duì)簽名驗(yàn)證的影響 。研究表明，新方案在保持原方案安全性能不變的基礎(chǔ)上，優(yōu)化了截取文檔的結(jié)構(gòu)，提高了簽名效率。

RSA；可截取簽名；批簽名；截取訪問(wèn)結(jié)構(gòu)；選擇明文攻擊

A

TP309.7

10.3778/j.issn.1002-8331.1301-0315

LI Xu,DU Xiaoni,WANG Caifen,et al.Improved scheme of content extraction signatures based on RSA.Computer Engineering and Applications,2014,50（24）：96-99.

國(guó)家自然科學(xué)基金（No.61063041，No.61163038，No.61202395，No.61262057）；教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃（No.NCET-12-0620）；甘肅省自然科學(xué)基金（No.1208RJZA0255）。

李旭（1985—），男，碩士研究生，研究方向：信息安全與密碼學(xué)；杜小妮，通訊作者，教授，碩士生導(dǎo)師；王彩芬，教授，博士生導(dǎo)師。E-mail：ymLdxn@126.com

2013-01-28

2013-05-27

1002-8331（2014）24-0096-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-06-08，http∶//www.cnki.net/kcms/detail/11.2127.TP.20130608.0953.008.html