基于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