高效的基于身份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體制下如何構造標準安全模型下的多重數字簽名是我們將要討論的工作.