高效的基于身份RSA多重数字签名

张键红，肖 晗，王继林

1(北方工业大学 电子信息工程学院，北京 100144)2(广西师范大学 广西多源信息挖掘与安全重点实验室，广西 桂林541004)3(浙江财经大学 信息管理与工程学院，杭州 310018)

1 引 言

随着信息技术与互联网的普及，电子商务迅猛发展并成为一种趋势.人们在享受这种技术带来的快速、高效和便捷的远距离交易同时，也面临着诸多安全问题，如怎样保证信息的真实性、完整以及如何现不可抵赖等.作为一种重要的认证技术，数字签名由此而产生，并在商业通信系统中广泛使用，使得交易数据的真实性和可认证性，以及交易双方的身份的真实性有了安全保障，为电子商务的发展奠定了坚实基础.

数字签名 (Digital Signature) ：又称公钥数字签名、电子签章，是一种类似写在纸上的普通的物理签名，但是使用了公钥加密领域的技术实现，用于鉴别数字信息的方法.简单地说，就是只有信息的发送者才能产生的别人无法伪造的一段数字串、附加在数据单元上的一些数据，或对单元所作的密码变换. 由于与传统手写的签名相比有着无可拟优势，手写签名正逐渐被数字所取代.出现了一系列数字签名算法，如RSA、ELGAMAL、Schnorr等，然而这些算法都是一个签名者对一个消息签名.在现实生活中，有时需要多个人批阅同一份文件.例如，一个公司发布的声明中涉及财务部、开发部、销售部、售后服务部等部门，需要的到这些部门签名认可，因此，就需要这些部门对这个声明文件进行签名.这就需要用到多重数字签名.

在文献[1]，多重数字签名概念首次被Okamoto和Itakura等提出并给出了一种具体构造.在1992年，Hardjono基于求解离散对数的困难性在文献[2]中提出了一种新的多重数字签名.后来，Horster等人应用该方案构造一种多重盲签名方案[3].这些方案存在着内部攻击，为了阻止内部人员的攻击的，Ohta等在文献[4]中提出一种有效的抗内部攻击的多重数字签名方案.在2000年，Burmester.M 等人基于ELGamal结构化签名类型给出了一种多重数字签名[12]，具有较好的结构化.在文献[13]和文献[14]中，Micali.S和Boldyreva.A分别基于责任子群问题和Gap Diffie-Hellman群提出了两种不同的多重数字签名方案. 自从多重签名提出以后，出现了一系列的多重数字签名[5-15].在这些方案构造中，一些方案是基于求解离散对数困难性问题，一些方案是基于大数分解问题，再有一些是基于椭圆曲线密码.就现有多重签名的构造过程而言，多重数字签名可分为有序多重数字签名和广播多重数字签名两种.

然而，现有的多重数字签名多数基于传统的PKC公钥框架，它使得在验证多重签名前首先需要验证公钥的有效性，因而，给验证者带来了沉重的计算负担.同时，用户的公钥是一串没有意义的字符串，对记忆而言，非常麻烦.

为了降低验证者的计算复杂性和便以验证，本文以经典的RSA签名方案为基础，设计了一种基于身份的多重数字签名方案.通过私钥产生中心为用户分发私钥有效的防止了证书管理问题，使得验证者不需要验证公钥的有效性，从而降低了计算复杂性.

2 基础知识

2.1 多重数字签名模型

根据多重签名的产生方式不同，多重签名方案一般可以分为按序多重数字签名和广播多重数字签名.在按序多重数字签名中，签名的产生是按照一定的顺序进行产生.第一位签名者对消息产生部分签名后，发送给下一个签名者，该签名者验证该签名有效后，产生部分签名并发送给下一个签名者.直到最后一位签名成员完成对消息的部分签名，即完成了按序多重签名.该形式的多重数字签名很容易通过广播多重数字签名来实现.因而，在本文中，我们主要研究广播多重数字签名，在广播多重签名中，消息发送者将消息同时发送给每一位签名成员，每位成员完成 自己的部分签名后，将部分签名发送给签名收集者，收集者生成广播 多重签名后，再发送给验证者验证签名的有效性.对于一个广播多重数字签名而言，它的参与者主要包括消息的发送者(S)，多个签名者Ui(i=1，2，3，…，k)，签名的收集者(Ur)，签名的验证者(Uv).所以我们可以得到多重签名模型，如图1所示：

图1 广播多重数字签名模型Fig.1 Broadcast multi-signature model

2.2 安全假设

RSA假设：让k是一个安全的参数，N=pq是一个RSA模数，其中，p，q是两个k-比特的大素数，e 是一个随机选择的正整数，并且满足e和φ(N)互素.已知(N，e)和一个随机数y ∈Zn，对于计算一个x，使得xe≡ymodN在计算上是困难的.

2.3 RSA签名相关理论

2.3.1 RSA签名算法描述

RSA算法是一种非常经典的算法，安全性极高，在工业界有很高的地位.RSA 的安全性基于大整数分解的困难性.首先选择两个大素数p和q，计算n=p*q.每个分组的二进制值均小于n.换句话说，分组大小必须小于等于log2(n)+1位.由于p和q是大素数，根据欧拉函数故有：φ(n)=(p- 1)(q-1).然后随机选择e，使其满足gcd(e，φ(n))=1且满足1

最后，计算d，使得e·d=1 mod φ(n)，即e和d为模φ(n)乘法逆元.因此，我们就得到了公钥PU={e，n}，私钥PR={d，p，q}.

2.3.2 RSA签名产生与验证

1)签名算法：对于已知消息待签消息M，签名算法：对于已知消息M∈Zn，计算签名 s=Md(modn)；

2)签名验证：已知一个消息签名(M，s)签名验证：验证se⟺M(mod n)，如果成立，签名有效否则失败.

3 基于身份的多重数字签名方案

3.1 初始化系统建立

首先，假设有一个密钥产生中心PKC选择两个大素数p和q，并根据RSA密码体制计算n、e、d，并公布 RSA 的公钥为PU={e，n}，同时秘密保存私钥 PR={d，p，q}.然后，选择两个密码哈希函数 h(·)和H(·)，用M表示待签名的消息，用IDi(i=1，2，3，…，k)表示每个签名者 表示每个签名者Ui的身份并且公开.最后，密钥中心 KC 计算：

βi=H(IDi)

并通过一个安全的秘密信道把证书 (IDi，ski)发送给每个签名者Ui，则签名者可以通过验证

来确定所得到的私钥是否有效.

3.2 多重签名算法的产生和验证

假设有一个签名者发起签名请求，多重签名的签名者身份的集合为ID={ID1，ID2，…，IDk-1，IDk}，则我们可以设计一种新的基于身份的RSA广播多重数字签名方案：

步骤2. 接收者Ur计算

T=t1×t2×t3×…×tk

步骤3. 每个签名者Ui计算

α=H(M||T)

步骤4. 签名发起者收到(T，si)后，进行聚合签名，并计算：

则最后的签名为(S，T).

步骤5. 当验证签名时，签名的验证者Uv得到签名后可计算Se，并且需要验证以下等式是否成立.

(1)

是否成立.若成立，则签名(S，T)有效，否则签名失败.

3.3 签名方案的正确性证明

定义1. (正确性)：在我们所建议的方案中，如果该多重数字签名是由所有签名者诚实产生的，那么该签名一定能通过验证.

证明：假设多重数字签名 是按3.2节中的算法计算的，则：

4 安全证明

一般来讲，一个多重数字签名存在着两种主要攻击类型：外部攻击和内部攻击.外部攻击是可控，但是阻止内部攻击却是非常困难的.所以，本文将在这两个方面对多重签名算法的安全性进行分析.

4.1 外部攻击分析

4.2 内部攻击分析

对于某一个签名者，它可能是潜在的攻击者，由于它参与整个签名过程，因而，与外部攻击者相比，它的攻击性更强.对于一个多重数字签名方案而言，如果该方案能够抵制内部攻击者，则它一定能够抵制外部攻击.

定理1.在随机预言模型下，假设存在一个攻击者Adv可以 攻破本文提出的多重数字签名方案，则存在一个算法AL，它成功解决了RSA假设问题.

证明：首先，让我们回顾一下RSA的假设问题是：已知RSA参数(N，e)，对于任意一个选择的数y(Zn，求x满足y≡xe(modn)是困难的.

假设存在着一个内部攻击者可以攻破我们所建议方案，那么，我们可以利用攻击者和算法AL的交互，来求解RSA假设问题.在下面的交互游戏中，算法AL的目的是计算一个值x使其满足y≡xe(modn).为此，算法AL的工作如下；

②随机数h-Oracle提问：当攻击者(Mi，Ti)询问h-Oracle时，算法Al在h-列表中查找记录(Mi，Ti，αi)是否存在，若有则返回(αie，否则，任选αi∈{0，1}l，且满足αie=160比特，并设置αie=H(Mi||Ti)作为函数值.最后，把αie返回给敌手，同时，在h-表中记录(Mi，Ti，αie).注：h-表在初始时也是一个空表.

2)询问私钥：攻击者询问算法AL身份为IDi的私钥，算法AL查找H-表，检查记录(IDi，ski，bi，βi).当bi=0时，把ski当作身份IDi的私钥发给攻击者.当bi=1时，算法AL宣布失败并退出协议.

(1)(S*，T*)是消息M*的有效签名.

故可得到以下验证等式成立：

(4)求解RSA假设问题：由上式可得：

由RSA假设，可以求得x，满足y≡xe(modn).这意味着算法AL输出x，从而，能够成功的求解强RSA假设问题.由定理1知，在RSA假设和随机预言模型下，本文在多项式时间内方案是安全的.

5 性能分析

在本节，我们将对方案的效率进行分析.在RSA密码系统中，主要耗时的运算是指数运算、哈希运算和乘法运算.由于文献[5，6，9]也是基于RSA密码体制下的多重数字签名方案，因而，在下面的性能比较中，我们将通过与文献[5]，文献[6]和文献[9]进行比较来说明我们方案的有效性.从上面的构造，我们知道，本文方案的多重数字签名长度是固定的，非常逼近单个签名长度.假设有n个签名者，本文方案的计算量与文献[5，6，9]中方案的计算量比较结果见表1.

表1 本方案与文献[5，6，9]中的计算量的比较Table 1 Computation comparison among our scheme and schemes[5，6，9]

从表1，我们能够发现，我们的方案在计算量比方案[5，6，9]具有较大的优势.

6 结束语

在电子商务和无纸化自动办公系统中，多重数字签名应用广泛，具有很好的发展前景.本文基于身份和RSA提出了一个高效的广播多重数字签名方案，并在随机预言模型下给出了该方案的安全性证明，其安全性是基于强RSA安全假设.最后，通过与现有的一些方案进行比较，我们所建议的方案在计算量上具有较大的优势，它是一个高效的多重数字签名方案.对于在RSA体制下如何构造标准安全模型下的多重数字签名是我们将要讨论的工作.