高效的基于身份RSA多重?cái)?shù)字簽名

張鍵紅，肖 晗，王繼林

1(北方工業(yè)大學(xué) 電子信息工程學(xué)院，北京 100144)2(廣西師范大學(xué) 廣西多源信息挖掘與安全重點(diǎn)實(shí)驗(yàn)室，廣西 桂林541004)3(浙江財(cái)經(jīng)大學(xué) 信息管理與工程學(xué)院，杭州 310018)

1 引 言

隨著信息技術(shù)與互聯(lián)網(wǎng)的普及，電子商務(wù)迅猛發(fā)展并成為一種趨勢.人們在享受這種技術(shù)帶來的快速、高效和便捷的遠(yuǎn)距離交易同時(shí)，也面臨著諸多安全問題，如怎樣保證信息的真實(shí)性、完整以及如何現(xiàn)不可抵賴等.作為一種重要的認(rèn)證技術(shù)，數(shù)字簽名由此而產(chǎn)生，并在商業(yè)通信系統(tǒng)中廣泛使用，使得交易數(shù)據(jù)的真實(shí)性和可認(rèn)證性，以及交易雙方的身份的真實(shí)性有了安全保障，為電子商務(wù)的發(fā)展奠定了堅(jiān)實(shí)基礎(chǔ).

數(shù)字簽名 (Digital Signature) ：又稱公鑰數(shù)字簽名、電子簽章，是一種類似寫在紙上的普通的物理簽名，但是使用了公鑰加密領(lǐng)域的技術(shù)實(shí)現(xiàn)，用于鑒別數(shù)字信息的方法.簡單地說，就是只有信息的發(fā)送者才能產(chǎn)生的別人無法偽造的一段數(shù)字串、附加在數(shù)據(jù)單元上的一些數(shù)據(jù)，或?qū)卧鞯拿艽a變換. 由于與傳統(tǒng)手寫的簽名相比有著無可擬優(yōu)勢，手寫簽名正逐漸被數(shù)字所取代.出現(xiàn)了一系列數(shù)字簽名算法，如RSA、ELGAMAL、Schnorr等，然而這些算法都是一個(gè)簽名者對(duì)一個(gè)消息簽名.在現(xiàn)實(shí)生活中，有時(shí)需要多個(gè)人批閱同一份文件.例如，一個(gè)公司發(fā)布的聲明中涉及財(cái)務(wù)部、開發(fā)部、銷售部、售后服務(wù)部等部門，需要的到這些部門簽名認(rèn)可，因此，就需要這些部門對(duì)這個(gè)聲明文件進(jìn)行簽名.這就需要用到多重?cái)?shù)字簽名.

在文獻(xiàn)[1]，多重?cái)?shù)字簽名概念首次被Okamoto和Itakura等提出并給出了一種具體構(gòu)造.在1992年，Hardjono基于求解離散對(duì)數(shù)的困難性在文獻(xiàn)[2]中提出了一種新的多重?cái)?shù)字簽名.后來，Horster等人應(yīng)用該方案構(gòu)造一種多重盲簽名方案[3].這些方案存在著內(nèi)部攻擊，為了阻止內(nèi)部人員的攻擊的，Ohta等在文獻(xiàn)[4]中提出一種有效的抗內(nèi)部攻擊的多重?cái)?shù)字簽名方案.在2000年，Burmester.M 等人基于ELGamal結(jié)構(gòu)化簽名類型給出了一種多重?cái)?shù)字簽名[12]，具有較好的結(jié)構(gòu)化.在文獻(xiàn)[13]和文獻(xiàn)[14]中，Micali.S和Boldyreva.A分別基于責(zé)任子群問題和Gap Diffie-Hellman群提出了兩種不同的多重?cái)?shù)字簽名方案. 自從多重簽名提出以后，出現(xiàn)了一系列的多重?cái)?shù)字簽名[5-15].在這些方案構(gòu)造中，一些方案是基于求解離散對(duì)數(shù)困難性問題，一些方案是基于大數(shù)分解問題，再有一些是基于橢圓曲線密碼.就現(xiàn)有多重簽名的構(gòu)造過程而言，多重?cái)?shù)字簽名可分為有序多重?cái)?shù)字簽名和廣播多重?cái)?shù)字簽名兩種.

然而，現(xiàn)有的多重?cái)?shù)字簽名多數(shù)基于傳統(tǒng)的PKC公鑰框架，它使得在驗(yàn)證多重簽名前首先需要驗(yàn)證公鑰的有效性，因而，給驗(yàn)證者帶來了沉重的計(jì)算負(fù)擔(dān).同時(shí)，用戶的公鑰是一串沒有意義的字符串，對(duì)記憶而言，非常麻煩.

為了降低驗(yàn)證者的計(jì)算復(fù)雜性和便以驗(yàn)證，本文以經(jīng)典的RSA簽名方案為基礎(chǔ)，設(shè)計(jì)了一種基于身份的多重?cái)?shù)字簽名方案.通過私鑰產(chǎn)生中心為用戶分發(fā)私鑰有效的防止了證書管理問題，使得驗(yàn)證者不需要驗(yàn)證公鑰的有效性，從而降低了計(jì)算復(fù)雜性.

2 基礎(chǔ)知識(shí)

2.1 多重?cái)?shù)字簽名模型

根據(jù)多重簽名的產(chǎn)生方式不同，多重簽名方案一般可以分為按序多重?cái)?shù)字簽名和廣播多重?cái)?shù)字簽名.在按序多重?cái)?shù)字簽名中，簽名的產(chǎn)生是按照一定的順序進(jìn)行產(chǎn)生.第一位簽名者對(duì)消息產(chǎn)生部分簽名后，發(fā)送給下一個(gè)簽名者，該簽名者驗(yàn)證該簽名有效后，產(chǎn)生部分簽名并發(fā)送給下一個(gè)簽名者.直到最后一位簽名成員完成對(duì)消息的部分簽名，即完成了按序多重簽名.該形式的多重?cái)?shù)字簽名很容易通過廣播多重?cái)?shù)字簽名來實(shí)現(xiàn).因而，在本文中，我們主要研究廣播多重?cái)?shù)字簽名，在廣播多重簽名中，消息發(fā)送者將消息同時(shí)發(fā)送給每一位簽名成員，每位成員完成 自己的部分簽名后，將部分簽名發(fā)送給簽名收集者，收集者生成廣播 多重簽名后，再發(fā)送給驗(yàn)證者驗(yàn)證簽名的有效性.對(duì)于一個(gè)廣播多重?cái)?shù)字簽名而言，它的參與者主要包括消息的發(fā)送者(S)，多個(gè)簽名者Ui(i=1，2，3，…，k)，簽名的收集者(Ur)，簽名的驗(yàn)證者(Uv).所以我們可以得到多重簽名模型，如圖1所示：

圖1 廣播多重?cái)?shù)字簽名模型Fig.1 Broadcast multi-signature model

2.2 安全假設(shè)

RSA假設(shè)：讓k是一個(gè)安全的參數(shù)，N=pq是一個(gè)RSA模數(shù)，其中，p，q是兩個(gè)k-比特的大素?cái)?shù)，e 是一個(gè)隨機(jī)選擇的正整數(shù)，并且滿足e和φ(N)互素.已知(N，e)和一個(gè)隨機(jī)數(shù)y ∈Zn，對(duì)于計(jì)算一個(gè)x，使得xe≡ymodN在計(jì)算上是困難的.

2.3 RSA簽名相關(guān)理論

2.3.1 RSA簽名算法描述

RSA算法是一種非常經(jīng)典的算法，安全性極高，在工業(yè)界有很高的地位.RSA 的安全性基于大整數(shù)分解的困難性.首先選擇兩個(gè)大素?cái)?shù)p和q，計(jì)算n=p*q.每個(gè)分組的二進(jìn)制值均小于n.換句話說，分組大小必須小于等于log2(n)+1位.由于p和q是大素?cái)?shù)，根據(jù)歐拉函數(shù)故有：φ(n)=(p- 1)(q-1).然后隨機(jī)選擇e，使其滿足gcd(e，φ(n))=1且滿足1

最后，計(jì)算d，使得e·d=1 mod φ(n)，即e和d為模φ(n)乘法逆元.因此，我們就得到了公鑰PU={e，n}，私鑰PR={d，p，q}.

2.3.2 RSA簽名產(chǎn)生與驗(yàn)證

1)簽名算法：對(duì)于已知消息待簽消息M，簽名算法：對(duì)于已知消息M∈Zn，計(jì)算簽名 s=Md(modn)；

2)簽名驗(yàn)證：已知一個(gè)消息簽名(M，s)簽名驗(yàn)證：驗(yàn)證se?M(mod n)，如果成立，簽名有效否則失敗.

3 基于身份的多重?cái)?shù)字簽名方案

3.1 初始化系統(tǒng)建立

首先，假設(shè)有一個(gè)密鑰產(chǎn)生中心PKC選擇兩個(gè)大素?cái)?shù)p和q，并根據(jù)RSA密碼體制計(jì)算n、e、d，并公布 RSA 的公鑰為PU={e，n}，同時(shí)秘密保存私鑰 PR={d，p，q}.然后，選擇兩個(gè)密碼哈希函數(shù) h(·)和H(·)，用M表示待簽名的消息，用IDi(i=1，2，3，…，k)表示每個(gè)簽名者 表示每個(gè)簽名者Ui的身份并且公開.最后，密鑰中心 KC 計(jì)算：

βi=H(IDi)

并通過一個(gè)安全的秘密信道把證書 (IDi，ski)發(fā)送給每個(gè)簽名者Ui，則簽名者可以通過驗(yàn)證

來確定所得到的私鑰是否有效.

3.2 多重簽名算法的產(chǎn)生和驗(yàn)證

假設(shè)有一個(gè)簽名者發(fā)起簽名請求，多重簽名的簽名者身份的集合為ID={ID1，ID2，…，IDk-1，IDk}，則我們可以設(shè)計(jì)一種新的基于身份的RSA廣播多重?cái)?shù)字簽名方案：

步驟2. 接收者Ur計(jì)算

T=t1×t2×t3×…×tk

步驟3. 每個(gè)簽名者Ui計(jì)算

α=H(M||T)

步驟4. 簽名發(fā)起者收到(T，si)后，進(jìn)行聚合簽名，并計(jì)算：

則最后的簽名為(S，T).

步驟5. 當(dāng)驗(yàn)證簽名時(shí)，簽名的驗(yàn)證者Uv得到簽名后可計(jì)算Se，并且需要驗(yàn)證以下等式是否成立.

(1)

是否成立.若成立，則簽名(S，T)有效，否則簽名失敗.

3.3 簽名方案的正確性證明

定義1. (正確性)：在我們所建議的方案中，如果該多重?cái)?shù)字簽名是由所有簽名者誠實(shí)產(chǎn)生的，那么該簽名一定能通過驗(yàn)證.

證明：假設(shè)多重?cái)?shù)字簽名 是按3.2節(jié)中的算法計(jì)算的，則：

4 安全證明

一般來講，一個(gè)多重?cái)?shù)字簽名存在著兩種主要攻擊類型：外部攻擊和內(nèi)部攻擊.外部攻擊是可控，但是阻止內(nèi)部攻擊卻是非常困難的.所以，本文將在這兩個(gè)方面對(duì)多重簽名算法的安全性進(jìn)行分析.

4.1 外部攻擊分析

4.2 內(nèi)部攻擊分析

對(duì)于某一個(gè)簽名者，它可能是潛在的攻擊者，由于它參與整個(gè)簽名過程，因而，與外部攻擊者相比，它的攻擊性更強(qiáng).對(duì)于一個(gè)多重?cái)?shù)字簽名方案而言，如果該方案能夠抵制內(nèi)部攻擊者，則它一定能夠抵制外部攻擊.

定理1.在隨機(jī)預(yù)言模型下，假設(shè)存在一個(gè)攻擊者Adv可以 攻破本文提出的多重?cái)?shù)字簽名方案，則存在一個(gè)算法AL，它成功解決了RSA假設(shè)問題.

證明：首先，讓我們回顧一下RSA的假設(shè)問題是：已知RSA參數(shù)(N，e)，對(duì)于任意一個(gè)選擇的數(shù)y(Zn，求x滿足y≡xe(modn)是困難的.

假設(shè)存在著一個(gè)內(nèi)部攻擊者可以攻破我們所建議方案，那么，我們可以利用攻擊者和算法AL的交互，來求解RSA假設(shè)問題.在下面的交互游戲中，算法AL的目的是計(jì)算一個(gè)值x使其滿足y≡xe(modn).為此，算法AL的工作如下；

②隨機(jī)數(shù)h-Oracle提問：當(dāng)攻擊者(Mi，Ti)詢問h-Oracle時(shí)，算法Al在h-列表中查找記錄(Mi，Ti，αi)是否存在，若有則返回(αie，否則，任選αi∈{0，1}l，且滿足αie=160比特，并設(shè)置αie=H(Mi||Ti)作為函數(shù)值.最后，把αie返回給敵手，同時(shí)，在h-表中記錄(Mi，Ti，αie).注：h-表在初始時(shí)也是一個(gè)空表.

2)詢問私鑰：攻擊者詢問算法AL身份為IDi的私鑰，算法AL查找H-表，檢查記錄(IDi，ski，bi，βi).當(dāng)bi=0時(shí)，把ski當(dāng)作身份IDi的私鑰發(fā)給攻擊者.當(dāng)bi=1時(shí)，算法AL宣布失敗并退出協(xié)議.

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

故可得到以下驗(yàn)證等式成立：

(4)求解RSA假設(shè)問題：由上式可得：

由RSA假設(shè)，可以求得x，滿足y≡xe(modn).這意味著算法AL輸出x，從而，能夠成功的求解強(qiáng)RSA假設(shè)問題.由定理1知，在RSA假設(shè)和隨機(jī)預(yù)言模型下，本文在多項(xiàng)式時(shí)間內(nèi)方案是安全的.

5 性能分析

在本節(jié)，我們將對(duì)方案的效率進(jìn)行分析.在RSA密碼系統(tǒng)中，主要耗時(shí)的運(yùn)算是指數(shù)運(yùn)算、哈希運(yùn)算和乘法運(yùn)算.由于文獻(xiàn)[5，6，9]也是基于RSA密碼體制下的多重?cái)?shù)字簽名方案，因而，在下面的性能比較中，我們將通過與文獻(xiàn)[5]，文獻(xiàn)[6]和文獻(xiàn)[9]進(jìn)行比較來說明我們方案的有效性.從上面的構(gòu)造，我們知道，本文方案的多重?cái)?shù)字簽名長度是固定的，非常逼近單個(gè)簽名長度.假設(shè)有n個(gè)簽名者，本文方案的計(jì)算量與文獻(xiàn)[5，6，9]中方案的計(jì)算量比較結(jié)果見表1.

表1 本方案與文獻(xiàn)[5，6，9]中的計(jì)算量的比較Table 1 Computation comparison among our scheme and schemes[5，6，9]

從表1，我們能夠發(fā)現(xiàn)，我們的方案在計(jì)算量比方案[5，6，9]具有較大的優(yōu)勢.

6 結(jié)束語

在電子商務(wù)和無紙化自動(dòng)辦公系統(tǒng)中，多重?cái)?shù)字簽名應(yīng)用廣泛，具有很好的發(fā)展前景.本文基于身份和RSA提出了一個(gè)高效的廣播多重?cái)?shù)字簽名方案，并在隨機(jī)預(yù)言模型下給出了該方案的安全性證明，其安全性是基于強(qiáng)RSA安全假設(shè).最后，通過與現(xiàn)有的一些方案進(jìn)行比較，我們所建議的方案在計(jì)算量上具有較大的優(yōu)勢，它是一個(gè)高效的多重?cái)?shù)字簽名方案.對(duì)于在RSA體制下如何構(gòu)造標(biāo)準(zhǔn)安全模型下的多重?cái)?shù)字簽名是我們將要討論的工作.