基于RSA的可截取簽名改進方案

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

1.西北師范大學 計算機科學與工程學院，蘭州 730070

2.西北師范大學 數學與統計學院，蘭州 730070

基于RSA的可截取簽名改進方案

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

1.西北師范大學 計算機科學與工程學院，蘭州 730070

2.西北師范大學 數學與統計學院，蘭州 730070

1 準備知識

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

圖1 可截取簽名流程圖

與傳統的數字簽名方案[2-3]相比，可截取簽名解決了在多方參與的環境下，消息從簽名者到使用者再到驗證者之間多次傳遞、簽名、驗證所導致的安全隱患以及計算和存儲開銷大，不便于實際操作的問題，在保證消息合法截取的同時，有效地實現了對消息的多次傳遞和驗證[4]。鑒于這些優點，可截取簽名受到了國內外學者的廣泛關注。文獻[5]在XML簽名規范中引入可截取簽名方法，對XML簽名[6]進行了擴展。文獻[7]在文獻[1]的基礎上，提出采用分級群組策略的可截取簽名方案，可有效地應用于數字圖書館等環境。

批簽名[8-10]允許用戶對一批數據進行統一簽名，統一驗證，從而提高了簽名和驗證效率。文獻[8]提出了基于二叉樹的Bi-tree批簽名方案，可以把普通的簽名算法改造成批簽名。

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

2 現有的可截取簽名方案

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

可截取簽名體制由以下四個步驟構成：

（1）密鑰生成

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

（2）簽名

①簽名者給出截取訪問結構CEAS，同時給出一個隨機產生的固定長度的CES標記T。

②對每個i∈CEAS，計算：

（3）簽名截取

①根據原消息M和簽名者指定的截取訪問結構CEAS，截取者給出截取子集CI(M′)。

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

③對每個i∈CI(M′)計算：

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

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

（4）簽名驗證

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

②對每個i∈CI(M′)對應的子消息，分別計算：

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

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

3 改進的可截取簽名方案

3.1方案描述

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

（1）密鑰生成GK(k)

①隨機選擇兩個長度為k/2的大素數 p和q。

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

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

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

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

對于長度為n的原消息M，

①簽名者給出截取訪問結構CEAS，同時給出一個隨機產生的固定長度的CES標記T。

②對CEAS對應的所有消息，構造必選消息批簽名樹hT-batch與簽名指數dbatch，并對hT-batch進行批簽名：

③對每個i∈ΓCEAS，計算：

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

①根據原消息M和簽名者指定的截取訪問結構CEAS，截取者給出截取子集CI(M′)。

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

③對每個i∈CI(M′)且i?CEAS，計算：

δ=∏i∈Xδ[i]modN

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

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

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

②對必選消息hT-batch進行批驗證[6-7]，取批驗證公鑰為ebatch：

③對每個i∈CI(M′)且i?CEAS對應的子消息，分別計算：

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

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

3.2 方案正確性分析

對截取文檔的簽名進行驗證，可得到：

3.3 方案可靠性分析

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

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

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

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

①截取者對M按CEAS的截取規則進行截取，得到M′，M′可通過驗證。

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

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

驗證失敗。

④截取者按照CEAS截取規則進行截取得到M3'，然后在M3'后面追加k條消息mi得到M3"，則驗證時有：

驗證失敗。

3.4 性能分析

現有方案在設定CEAS和CI(M′)時，采用空白來標記截取段落，并由此判定驗證條件CEAS?CI(M′)是否滿足，導致截取后文檔出現大面積留白，不符合正常閱讀習慣。新方案改進了CI(M′)的結構，使系統在驗證階段僅通過M′與CI(M′)的對應關系就能判斷截取文檔是否滿足CEAS?CI(M′)，由此避免了文檔留白現象。

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

圖2 截取前的原始文檔

3.5 復雜度分析

本節對兩種簽名方案的執行效率進行分析。符號說明如表1所示。

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

表1 符號說明

表2 兩種方案效率比較

圖3 現有方案的截取效果

圖4 改進方案的截取效果

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

4 結論

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

[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]李新，張繼東，孫玉芳.簽名加密技術在公文系統中的應用[J].計算機應用研究，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數字簽名[J].計算機應用研究，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].計算機應用，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

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

RSA；可截取簽名；批簽名；截取訪問結構；選擇明文攻擊

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.

國家自然科學基金（No.61063041，No.61163038，No.61202395，No.61262057）；教育部新世紀優秀人才支持計劃（No.NCET-12-0620）；甘肅省自然科學基金（No.1208RJZA0255）。

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

2013-01-28

2013-05-27

1002-8331（2014）24-0096-04

CNKI網絡優先出版：2013-06-08，http∶//www.cnki.net/kcms/detail/11.2127.TP.20130608.0953.008.html